线性基杂谈

线性基与空间向量

向量 (vector)

向量是有方向的量。

在低维空间中 (指 3 维及以下)，我们可以很方便的想象一个从原点出发的向量。比如向量 (3,4,5) 在空间直角坐标系中就是一个在 x,y,z 轴上投影为 3,4,5 的箭头。但是当空间维度更高时，我们就不能方便地想象向量了。因此对高维向量的分析也将困难许多。所以，本文旨在从低维空间地思想出发，得出处理多维空间中向量线性基 (linear basis) 的普遍方法。

线性无关 (linearly independent)

简单的说，对于向量空间中的 n 个向量 $V_1,V_2,V_3.\cdots V_n$，若方程 $a_1V_1+a_2V_2+\cdots +a_nV_n=0$只有一个解 ${a_1,a_2\cdots a_n=0}$，那么这几个向量就是线性无关的。反之他们线性相关。

为什么要这么定义呢？我们可以从两个方面去理解。

$a_1V_1+a_2V_2+\cdots +a_nV_n=0$通过移项可得：$a_1V_1=-(a_2V_2+a_3V_3+\cdots +a_nV_n)$也就是说，其中任意一个向量都可以用剩下的向量表示出来。那么，这几个向量中至少有一个是多余的。去掉其中的一个，这些向量依旧依旧可以表示出去掉的那一个。但是至于究竟我们可以去掉那些向量，使得剩下的向量最少，但是依旧可以表示出原来的所有向量呢？我们还需要更直观的手段。

向量张成的空间 (vector space)

由一个向量组 $(V1,V2\cdots Vn)$张成的空间可以简单地描述为由向量 $V(V=a_1V1+a_2V_2+\cdots+a_nV_n)$ 构成的集合。比如平面向量 (1,0),(0,1) 可以张成整个二维平面，当然 (3,6),(6,3) 也可以。但是向量 (3,5),(6,10) 就只能张成直线 $y=\frac{5}{3}x$，因为这两个向量是共线的。而准确描述几个 n 维向量能否张满 n 维空间的方法就是行列式。

基 (basis)

一组可以张成 n 维空间 V 的向量组 $(V_1,V_2\cdots Vn)$如果是线性无关的 (而且必定是的), 这个向量组就是这个空间的一个基。

行列式 (determinant)

determinant 一词意为 “决定因素”，因为在数学中，行列式的值直接体现了一组向量能否张满空间。一组向量组成的行列式的值就是这些向量组成的平行多维体的带符号多维体积。比如 2 阶行列式代表以这两个向量为边的平行四边行的面积，3 阶代表一个平行六面体的体积。

所以，如果 3 个向量中有一个是多余的，这个平行六面体就被压扁了，成为一个平面。同理，n 个向量中若有一个多余，这个多维体就会被压瘪到 n-1 维，因此体积就为 0 了。这样，我们就建立了行列式和向量空间中直观的联系。

行列式是你将 n 个 n 维向量排成一个方阵后，通过一系列运算得到的一个值。所以可以理解为：行列式是对一个向量方阵的一次运算。比如：向量 (1,2,3),(4,5,6),(7,8,9) 组成的行列式就是：
$$
\begin{vmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{vmatrix}OR\begin{vmatrix}
1 & 4 & 7 \\
2 & 5 & 8 \\
3 & 6 & 9
\end{vmatrix}
$$

而其最基本的计算方法是选出不同行不同列的 n 个元素 (显然有 n! 种选法)，将他们乘起来，带上与选法有关的正负号，再相加。这样计算的复杂度为 O(n!)

行列式有以下几个性质 (当然还有更多)，有兴趣可以参考《工程数学线性代数》

行列式绕 “东南-西北” 对角线 (主对角线) 反转后值不变(也就是说行列式转置后值不变)
行列式如果主对角线下方全部为 0，那么行列式的值就是主对角线上数的积
行列式的某一行加上令一行的 k 倍后行列式值不变: 这是个非常重要的性质，这说明行列式是支持高斯消元的。

高斯消元求线性基

我们明确这样一个结论：一个矩阵通过高斯消元后得到一个上三角矩阵，这个矩阵中的各个向量肯定是线性无关的。

因此，如果我们可以利用高斯消元求出一个矩阵对应的上三角矩阵，就等于求出了这个矩阵对应向量的线性基。这个肯定是谁都会的。哪怕这个上三角矩阵中有几行全是 0，这也只是说明原来的向量张成的空间不是 n 维的。剩下的非 0 行就是原来向量可以张成的空间的一个线性基。

OI 中的线性基

异或运算下的基

既然我们已经知道了线性基是可以用高斯消元维护的，异或方程也是支持高斯消元的，那么我们可以大胆地猜想，一些 01 向量的基也可以由高斯求出。这实际上是正确的。

这样，我们就可以 $O(n^3)$求出一些 01 向量的基，通过压位优化，可以达到 $O(\frac{n^3}{64})$的复杂度。

但是基于异或的很多奇特性质，以及向量的维数一般不超过 64 维，我们可以做到 $O(64n)$求出一些 01 向量的基。具体的做法无异于高斯消元，这里直接放上代码。(代码摘自这篇博客)

/*O(64n)*/
void cal() {
    for (int i = 0; i < n; ++i)
        for (int j = MAX_BASE; j >= 0; --j)
            if (a[i] >> j & 1) {
                if (b[j]) a[i] ^= b[j];
                else {
                    b[j] = a[i];
                    for (int k = j - 1; k >= 0; --k) if (b[k] && (b[j] >> k & 1)) b[j] ^= b[k];
                    for (int k = j + 1; k <= MAX_BASE; ++k) if (b[k] >> j & 1) b[k] ^= b[j];
                    break;
                }
}

以上代码的原型就是普通的高斯消元，但与高斯消元不同的是，它并不是对矩阵进行行操作，而是向矩阵内添加行向量。代码中间的两个很讨厌的循环维护了线性基的两个很有用的性质：

此线性基主对角线上为 1 的位上方全是 0
此线性基主对角线上为 0 的位上方 1 的个数不确定

根据这两个性质我们就可以将这个从线性代数演变而来的算法应用于很多问题之中。

线性基运用

最大异或值

给定 $n(1≤n≤10^5)$ 个数 $a_1, a_2, \cdots, a_n$，请问这些数能够组成的最大异或和是什么？

我们知道，这些数可以异或出的数一定都可以用这些数的线性基异或出，它们不能异或出的数也不能用线性基异或出，因此我们求这些数的线性基。根据线性基的性质 1,2，我们可以从大到小依次尝试将线性基中的数异或起来，如果可以使答案更大则选择这个数，不能则不选。这样最终的答案也是原来的数可以异或出的最大数。

k 大异或值

给定 $n(1\le n\le 10^4)$个数，求这 n 个数能异或出的第 k 大数是什么？(有 $10^4$次询问)

同样，我们根据线性基的性质 1,2：若 k 的二进制表示为 $(b _ t,b _ {t-1},\cdots ,b_1,b_0) _ {(2)}$，线性基中的非 0 数从大到小依次为 $(a _ s,a _ {s-1},\cdots ,a _ 2,a _ 1)$，那么答案就是 $b _ ta _ t\oplus b _ {t-1}a _ {t-1}\oplus\cdots\oplus b _ 2a _ 2\oplus b _ 1a _ 1(t<=s)$，这个结论根据线性基的性质 1 也是非常显然的。

最大异或值路径

给定一个 $n(n<=5*10^4)$个节点 $m(m<=10^5)$条边的无向图，求 1 到 n 经过边边权异或值最大的路径的异或值

引理 1：任意一条 1 到 n 的路径都可以通过任意一条 1 到 n 的路基异或上一些环组成。同时，任意的路径和任意的几个环异或都是一条路径的异或值。

证明 1：这两条路径彼此异或后的结果一定是若干个环。因为他们有相同的起点和终点。这样，这些环和其中一条路径异或得到另一条路径。同时，一个孤立的环可以看成是走到环绕一圈再原路返回的路径异或值，非孤立环与原有路径有公共点，所以只需要在路径上顺便拜访即可。这样，环和任意路径的异或值与任意路径的异或值是一一对应的。

引理 2：任意一个环可以通过 dfs 树上的返祖边所在的简单环异或得到。

证明 2：相邻两个环异或得到一个大环。大环继续和简单环异或并重复这个过程就可以得到所有环。

因此，我们只需要找出所有 dfs 树上返祖边所在的简单环，以及任意一条 1 到 n 的路径。将环的异或值求线性基，再询问路径异或值与线性基的最大异或值。求法与例题 1 类似。

动态线性基

给定一个 01 向量集合，要求可以动态地支持向这个集合加入一个新的向量，或删除一个原有的向量。

我们令 $S$为原有向量集合，$B$为线性基中的向量。$B$中任何一个元素都是由 $S$中的若干元素异或得到的。因而我们可以维护一张表 $T$，表的内容为 $B$中的每个元素由 $S$中那些元素异或得到。

如果新增一个向量 $v$，按原始线性基的做法插入这个向量，并更新表 $T$。

如果删除一个向量 $v$，我们通过 $T$找到 $v$参与构成了 $B$中的哪些向量。我们需要将 $B$中这些向量中 $v$的影响消除。具体做法是：找到 $B$中包含 $v$的最小的一个向量 (最高位最低)，用这个向量异或其它包含了 $v$的向量。这样做的好处是，其它包含了 $v$的向量的最高位不会发生改变，故线性基的结构没有发生变化。现在我们只需要将最小的这个向量异或上 $v$，得到一个新的不含 $v$的向量，但是这个向量最高位发生了变化，因此我们需要再将这个向量重新插入线性基。

无论是线性基 $B$还是表 $T$，我们都可以用 bitset 压缩以降低复杂度。

因此，这样动态维护的复杂度是：插入和删除均是 $O(\frac{|v|(|v|+|S|)}{\omega})$，即这是一个平方级别的复杂度。

在实现上有些许技巧，比如可以再建立一个索引 $bpos[i]$表示线性基中最高位为 $i$的那一项在第几行。这样，线性基中元素就不一定要升序排列了。下面代码只有一个 modify(p,x)函数，意为将原集合 $S$内的第 $p$个元素异或上 $x$，这样就可以同时支持删除和加入两个操作。


typedef bitset<MX> bset;
bset base[MX], from[MX];
int bpos[MX];
int n, m;   //n = |S|, m = |v|

void modify(int p, bset x)
{
    int q = 0;
    for(int i=1; i<=n; i++)
        if(from[i][p] && base[i].none())
        {
            q = i;
            break;
        }
    if(!q)
        for(int i=0; i<m; i++)
            if(from[bpos[i]][p])
            {
                q = bpos[i];
                bpos[i] = 0;
                break;
            }
    for(int i=1; i<=n; i++)
        if(from[i][p] && i!=q)
        {
            from[i] ^= from[q];
            base[i] ^= base[q];
        }
    base[q] ^= x;
    for(int i=m-1; i>=0; i--)
        if(base[q][i])
        {
            if(bpos[i] == 0)
            {
                bpos[i] = q;
                break;
            }
            else
            {
                from[q] ^= from[bpos[i]];
                base[q] ^= base[bpos[i]];
            }
        }
}

用该算法可以通过 $UOJ91$。

【算法】线性基杂谈

于2017年12月30日2017年12月30日由boshi发布