线性基

回想高中数学立体几何中基向量的概念，我们可以在三维欧氏空间中找到一组基向量，，，之后空间中任意一个向量都可以由这组基向量表示。换句话说，我们可以 通过有限的基向量来描述无限的三维空间，这足以体现基向量的重要性。

三维欧氏空间是特殊的线性空间，三维欧氏空间的基向量在线性空间中就被推广为了线性基。

OI 中有关线性基的应用一般只涉及两类线性空间：维实线性空间和维布尔域线性空间，我们会在应用一节中详细介绍。若您不熟悉线性代数，则推荐从应用部分开始阅读。

以下会从一般的线性空间出发来介绍线性基，并给出线性基的常见性质。

前置知识：线性空间。

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

定义

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

规定线性空间的基为空集。

可以证明任意线性空间均存在线性基¹，我们定义线性空间的维数为线性基的元素个数（或势），记作。

性质

对于有限维线性空间 , 设其维数为 , 则：
1. 中的任意个向量线性相关。
2. 中的任意个线性无关的向量均为的基。
3. 若中的任意向量均可被向量组线性表出，则其是的一个基。
  
  证明
  
  任取中的一组基 , 由已知条件，向量组可被线性表出，故
  
  因此
4. 中任意线性无关向量组均可通过插入一些向量使得其变为的一个基。
（子空间维数公式）令是关于的有限维线性空间，且和也是有限维的，则

证明

设 ,,.

取的一组基 , 将其分别扩充为和中的基：和 .

接下来只需证明向量组线性无关即可。

设 .

则 .

注意到上式左边在中，右边在中，故两边均在中，因此

故 , 进而
令是关于的有限维线性空间，且和也是有限维的，则下列诸款等价：
1. .
2. .
3. 若是的一组基，是的一组基，则是的一组基。
Note

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

例子

考虑的基。

如图

是一组基。
如图

是一组基。
如图

不是一组基，因为 .
如图

不是一组基，因为 .

正交基与单位正交基

若线性空间的一组基满足（即两两正交），则称这组基是 正交基。

若线性空间的一组正交基还满足，则称这组基是 单位正交基。

任意有限维线性空间的基都可以通过 Schmidt 正交化变换为正交基。

应用

根据前文内容，我们可以利用线性基实现：

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

在 OI 中，我们一般将维实线性空间下的线性基称为 实数线性基，维布尔域线性空间下的线性基称为 异或线性基。

Tip

中的加法为异或，乘法为与，可以证明是域。

可以证明代数系统是线性空间，其中：

即加法是异或，数乘是与。

以异或线性基为例，我们可以根据给定的一组布尔序列构造出一组异或线性基，这组基有如下性质：

中任意非空子集的异或和不为；
对中的任意元素，都可在中取出若干元素使其异或和为；
对任意满足上两条的集合，其元素个数不会小于的元素个数。

我们可以利用异或线性基实现：

判断一个数能否表示成某数集子集的异或和；
求一个数表示成某数集子集异或和的方案数；
求某数集子集的最大/最小/第大/第小异或和；
求一个数在某数集子集异或和中的排名。

构造方法

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

贪心法

对原集合的每个数转为二进制，从高位向低位扫，对于第位是的，如果不存在，那么令并结束扫描，如果存在，令。

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

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

查询原集合内任意几个元素的最小值，就是线性基集合所有元素中最小的那个。

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

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

#include <algorithm>
#include <iostream>
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];
  }
}

using std::cin;
using std::cout;

int main() {
  int n;
  cin >> n;
  ull a;
  for (int i = 1; i <= n; ++i) {
    cin >> a;
    insert(a);
  }
  ull ans = 0;
  for (int i = 63; ~i; --i) {
    ans = std::max(ans, ans ^ p[i]);
  }
  cout << ans << '\n';
  return 0;
}

高斯消元法

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

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

#include <iostream>
using ull = unsigned long long;
constexpr int MAXN = 1e5 + 5;

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

ull a[MAXN];
using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> 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];
  }
  cout << ans << '\n';
  return 0;
}

性质

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

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

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

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

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

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

提供一组样例：

5
633 211 169 841 1008

二进制表示：

贪心法生成的线性基：

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

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

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

时间复杂度

设向量长度为 , 总数为 , 则时间复杂度为 . 其中高斯消元法的常数略大。

若是实数线性基，则时间复杂度为 .

练习题

参考资料与注释

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

Proof that every vector space has a basis ↩

最后更新: 2024年4月21日
创建日期: 2018年7月11日