线性基

前置知识：线性空间的定义以及相关概念中的线性相关、线性无关、极大线性无关组、子空间等。

线性基是线性空间的一组基，是研究线性空间的重要工具。

由于 OI 中只涉及有限维线性空间，故本处仅介绍有限维线性空间的情况。

定义¶

称线性空间 \(V\) 的一个极大线性无关组为 \(V\) 的一组 Hamel 基 或 线性基，简称基。

规定线性空间 \(\{\theta\}\) 的基为空集。

另外，将 \(V\) 的维数记作 \(\dim V\), 定义为基的元素个数。

性质¶

对于有限维线性空间 \(V\), 设其维数为 \(n\), 则：
1. \(V\) 中的任意 \(n+1\) 个向量线性相关。
2. \(V\) 中的任意 \(n\) 个线性无关的向量均为 \(V\) 的基。
3. 若 \(V\) 中的任意向量均可被向量组 \(a_1,a_2,\dots,a_n\) 线性表出，则其是 \(V\) 的一个基。
  
  证明
  
  任取 \(V\) 中的一组基 \(b_1,b_2,\dots,b_n\), 由已知条件，向量组 \(b_1,b_2,\dots,b_n\) 可被 \(a_1,a_2,\dots,a_n\) 线性表出，故
  
  \[ n=\operatorname{rank}\{b_1,b_2,\dots,b_n\}\leq\operatorname{rank}\{a_1,a_2,\dots,a_n\}\leq n \]
  
  因此 \(\operatorname{rank}\{a_1,a_2,\dots,a_n\}=n\)
4. \(V\) 中任意线性无关向量组 \(a_1,a_2,\dots,a_m\) 均可通过插入一些向量使得其变为 \(V\) 的一个基。
（子空间维数公式）令 \(V_1,V_2\) 是关于 \(\Bbb{P}\) 的有限维线性空间，且 \(V_1+V_2\) 和 \(V_1\cap V_2\) 也是有限维的，则 \(\dim V_1+\dim V_2=\dim(V_1+V_2)+\dim(V_1\cap V_2)\)

证明

设 \(\dim V_1=n_1\),\(\dim V_2=n_2\),\(\dim(V_1\cap V_2)=m\).

取 \(V_1\cap V_2\) 的一组基 \(a_1,a_2,\dots,a_m\), 将其分别扩充为 \(V_1\) 和 \(V_2\) 中的基：\(a_1,a_2,\dots,a_m,b_1,b_2,\dots,b_{n_1-m}\) 和 \(a_1,a_2,\dots,a_m,c_1,c_2,\dots,c_{n_2-m}\).

接下来只需证明向量组 \(a_1,a_2,\dots,a_m,b_1,b_2,\dots,b_{n_1-m},c_1,c_2,\dots,c_{n_2-m}\) 线性无关即可。

设 \(\sum_{i=1}^m r_ia_i+\sum_{i=1}^{n_1-m} s_ib_i+\sum_{i=1}^{n_2-m} t_ic_i=\theta\).

则 \(\sum_{i=1}^{n_2-m} t_ic_i=-\sum_{i=1}^m r_ia_i-\sum_{i=1}^{n_1-m} s_ib_i\).

注意到上式左边在 \(V_2\) 中，右边在 \(V_1\) 中，故两边均在 \(V_1\cap V_2\) 中，因此 \(\sum_{i=1}^{n_2-m} t_ic_i=\sum_{i=1}^m k_ia_i\)

故 \(t_1=t_2=\dots=t_{n_2-m}=k_1=k_2=\dots=k_m=0\), 进而 \(r_1=r_2=\dots=r_m=s_1=s_2=\dots=s_{n_1-m}=t_1=t_2=\dots=t_{n_2-m}=0\)
令 \(V_1,V_2\) 是关于 \(\Bbb{P}\) 的有限维线性空间，且 \(V_1+V_2\) 和 \(V_1\cap V_2\) 也是有限维的，则下列诸款等价：
1. \(V_1+V_2=V_1\oplus V_2\).
2. \(\dim V_1+\dim V_2=\dim(V_1+V_2)\).
3. 若 \(a_1,a_2,\dots,a_n\) 是 \(V_1\) 的一组基，\(b_1,b_2,\dots,b_m\) 是 \(V_2\) 的一组基，则 \(a_1,a_2,\dots,a_n,b_1,b_2,\dots,b_m\) 是 \(V_1+V_2\) 的一组基。
Note

1,3 两条可推广到无限维线性空间中

例子¶

考虑 \(\Bbb{R}^2\) 的基。

如图

\(u,v\) 是一组基。
如图

\(u,v\) 是一组基。
如图

\(u,v\) 不是一组基，因为 \(u=-v\).
如图

\(u,v,w\) 不是一组基，因为 \(u+4v+6w=\theta\).

应用¶

线性基在 OI 中的应用一般包含以下方面：

对给定的向量组，找到一组极大线性无关组（或其张成的线性空间的一组基）。
向给定的向量组插入某些向量，在插入操作后的向量组中找到一组极大线性无关组（或其张成的线性空间的一组基）。
对找到的一组极大线性无关组（或基），判断某向量能否被其线性表出
求极大线性无关组（或基）的秩。
对找到的一组极大线性无关组（或基），求其张成的线性空间中的最大元/最小元。

特别地：

若限定向量均在 \(\Bbb{Z}_2^n\) 下，则称找到的基为 异或线性基。
若限定向量均在 \(\Bbb{R}^n\) 下，则称找到的基为 实数线性基。

构造方法¶

因为异或线性基与实数线性基没有本质差别，所以接下来以异或线性基为例，实数线性基版本的代码只需做一点简单修改即可。

贪心法¶

对原集合的每个数 \(p\) 转为二进制，从高位向低位扫，对于第 \(x\) 位是 \(1\) 的，如果 \(a_x\) 不存在，那么令 \(a_x \leftarrow p\) 并结束扫描，如果存在，令 \(p\leftarrow p~\text{xor}~a_x\)。

查询原集合内任意几个元素 \(\text{xor}\) 的最大值，只需将线性基从高位向低位扫，若 \(\text{xor}\) 上当前扫到的 \(a_x\) 答案变大，就把答案异或上 \(a_x\)。

为什么能行呢？因为从高往低位扫，若当前扫到第 \(i\) 位，意味着可以保证答案的第 \(i\) 位为 \(1\)，且后面没有机会改变第 \(i\) 位。

查询原集合内任意几个元素 \(\text{xor}\) 的最小值，就是线性基集合所有元素中最小的那个。

查询某个数是否能被异或出来，类似于插入，如果最后插入的数 \(p\) 被异或成了 \(0\)，则能被异或出来。

代码（洛谷 P3812 【模板】线性基）

#include <bits/stdc++.h>
using ull = unsigned long long;

ull p[64];

void insert(ull x) {
  for (int i = 63; ~i; --i) {
    if (!(x >> i))  // x 的第 i 位是 0
      continue;
    if (!p[i]) {
      p[i] = x;
      break;
    }
    x ^= p[i];
  }
}

int main() {
  int n;
  scanf("%d", &n);
  ull a;
  for (int i = 1; i <= n; ++i) {
    scanf("%llu", &a);
    insert(a);
  }
  ull ans = 0;
  for (int i = 63; ~i; --i) {
    ans = std::max(ans, ans ^ p[i]);
  }
  printf("%llu\n", ans);
  return 0;
}

高斯消元法¶

高斯消元法相当于从线性方程组的角度去构造线性基，正确性显然。

代码（洛谷 P3812 【模板】线性基）

#include <bits/stdc++.h>
using ull = unsigned long long;
const int MAXN = 1e5 + 5;

ull deg(ull num, int deg) { return num & (1ull << deg); }

ull a[MAXN];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%llu", &a[i]);
  int row = 1;
  for (int col = 63; ~col && row <= n; --col) {
    for (int i = row; i <= n; ++i) {
      if (deg(a[i], col)) {
        std::swap(a[row], a[i]);
        break;
      }
    }
    if (!deg(a[row], col)) continue;
    for (int i = 1; i <= n; ++i) {
      if (i == row) continue;
      if (deg(a[i], col)) {
        a[i] ^= a[row];
      }
    }
    ++row;
  }
  ull ans = 0;
  for (int i = 1; i < row; ++i) {
    ans ^= a[i];
  }
  printf("%llu\n", ans);
  return 0;
}

性质¶

贪心法构造的线性基具有如下性质：

线性基没有异或和为 \(0\) 的子集。
线性基中各数二进制最高位不同。

高斯消元法构造出的线性基满足如下性质：

高斯消元后的矩阵是一个行简化阶梯形矩阵。

该性质包含了贪心法构造的线性基满足的两条性质

如果不理解这条性质的正确性，可以跳转高斯消元。

提供一组样例：

5
633 211 169 841 1008

二进制表示：

贪心法生成的线性基：

高斯消元法生成的线性基：

这是一条非常好的性质，能帮我们更方便的解决很多问题。比如：给定一些数，选其中一些异或起来，求异或最大值，如果用贪心法构造线性基，需要再做一遍贪心，如果 ans 的当前位是 0，那么异或一定会更优，否则当前位如果为 1，则一定不会更优；而使用高斯消元法构造线性基后直接将线性基中所有元素都异或起来输出即可。

对于其他比较经典的问题（查询一个数能否被异或得到，查询能被异或得到的第 \(k\) 大数等），高斯消元法得到的线性基也能更加方便地解决。

时间复杂度¶

设向量长度为 \(n\), 总数为 \(m\), 则时间复杂度为 \(O(nm)\). 其中高斯消元法的常数略大。

若是实数线性基，则时间复杂度为 \(O(n^2m)\).

练习题¶

参考资料与注释¶

丘维声，高等代数（下）。清华大学出版社。
Basis (linear algebra) - Wikipedia
Vector Basis -- from Wolfram MathWorld