跳转至

線性基

前置知識：線性空間 的定義以及相關概念中的線性相關、線性無關、極大線性無關組、子空間等。

線性基是線性空間的一組基，是研究線性空間的重要工具。

由於 OI 中只涉及有限維線性空間，故本處僅介紹有限維線性空間的情況。

定義

稱線性空間 \(V\) 的一個極大線性無關組為 \(V\) 的一組 Hamel 基 或 線性基，簡稱 基。

規定線性空間 \(\{\theta\}\) 的基為空集。

另外，將 \(V\) 的 維數 記作 \(\dim V\), 定義為基的元素個數。

性質

  1. 對於有限維線性空間 \(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\) 的一個基。

  2. （子空間維數公式）令 \(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\)

  3. 令 \(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\) 的基。

  1. 如圖

    \(u,v\) 是一組基。

  2. 如圖

    \(u,v\) 是一組基。

  3. 如圖

    \(u,v\) 不是一組基，因為 \(u=-v\).

  4. 如圖

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

應用

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

  1. 對給定的向量組，找到一組極大線性無關組（或其張成的線性空間的一組基）。
  2. 向給定的向量組插入某些向量，在插入操作後的向量組中找到一組極大線性無關組（或其張成的線性空間的一組基）。
  3. 對找到的一組極大線性無關組（或基），判斷某向量能否被其線性表出
  4. 求極大線性無關組（或基）的秩。
  5. 對找到的一組極大線性無關組（或基），求其張成的線性空間中的最大元/最小元。

特別地：

  • 若限定向量均在 \(\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 【模板】線性基） 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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 【模板】線性基） 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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\) 的子集。
  • 線性基中各數二進制最高位不同。

高斯消元法構造出的線性基滿足如下性質：

  • 高斯消元后的矩陣是一個行簡化階梯形矩陣。

    該性質包含了貪心法構造的線性基滿足的兩條性質

    如果不理解這條性質的正確性，可以跳轉 高斯消元。

提供一組樣例：

1
2
5
633 211 169 841 1008

二進制表示：

1
2
3
4
5
1001111001
0011010011
0010101001
1101001001
1111110000

貪心法生成的線性基：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
1001111001
0100110000
0011010011
0001111010
0000000000
0000010000
0000000000
0000000000
0000000000
0000000000

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
1000000011
0100100000
0010101001
0001101010
0000010000
0000000000
0000000000
0000000000
0000000000
0000000000

這是一條非常好的性質，能幫我們更方便的解決很多問題。比如：給定一些數，選其中一些異或起來，求異或最大值，如果用貪心法構造線性基，需要再做一遍貪心，如果 ans 的當前位是 0，那麼異或一定會更優，否則當前位如果為 1，則一定不會更優；而使用高斯消元法構造線性基後直接將線性基中所有元素都異或起來輸出即可。

對於其他比較經典的問題（查詢一個數能否被異或得到，查詢能被異或得到的第 \(k\) 大數等），高斯消元法得到的線性基也能更加方便地解決。

時間複雜度

設向量長度為 \(n\), 總數為 \(m\), 則時間複雜度為 \(O(nm)\). 其中高斯消元法的常數略大。

若是實數線性基，則時間複雜度為 \(O(n^2m)\).

練習題

參考資料與註釋

  1. 丘維聲，高等代數（下）。清華大學出版社。
  2. Basis (linear algebra) - Wikipedia
  3. Vector Basis -- from Wolfram MathWorld
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：cesonic, Enter-tainer, Great-designer, Ir1d, ksyx, lychees, MegaOwIer, RUIN-RISE, wjy-yy, rsdbkhusky, ouuan, Menci, Tiphereth-A
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用