线性基杂谈

线性基与空间向量

向量(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类似。

分类: 文章

1 条评论

konnyakuxzy · 2017年12月30日 10:43 下午

Orz
这行压得

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *