线性基

转自线性基学习笔记

概述

基(basis) 是线性代数中的一个概念,它是描述、刻画向量空间的基本工具。而在现行的 OI 题目中,通常在利用基在异或空间中的一些特殊性质来解决题目,而这一类题目所涉及的知识点被称作「线性基」。

先说明一点,$a_i$,表示一个标量,而加粗的 $\mathbf{a}_i$,表示一个向量,以便于区分。

预备知识

向量空间(vector space)

向量空间 - 维基百科

定义 ($F, V, +, \cdot$) 为向量空间(vector space),其中 $F$ 为域,$V$ 为集合,$V$ 中元素称为向量,$+$ 为向量加法,$\cdot$ 为标量乘法,且运算满足 8 条公理(见维基百科)。

线性无关(linearly independent)

线性无关 - 维基百科

对于向量空间中 $V$ 上 $n$ 个元素的向量组 ($\mathbf{v}_1, \ldots, \mathbf{v}_n$),若存在不全为 $0$ 的数 $a_i \in F$,满足
$$
a_{1}\mathbf {v} {1}+a{2}\mathbf {v} {2}+\ldots +a{n}\mathbf {v} _{n} = 0
$$
则称这 $n$ 个向量线性相关(linearly dependent),否则称为线性无关(linearly independent)

张成(span)

对于向量空间中 $V$ 上 $n$ 个元素的向量组 ($\mathbf{v}_1, \ldots, \mathbf{v}_n$),其所有线性组合所构成的集合称为 ($\mathbf{v}_1, \ldots, \mathbf{v}_n$) 的张成(span),记为 $\mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}_n$)。

基(basis)

若向量空间 $V$ 中向量组 $\mathfrak{B}$ 既是线性无关的又可以张成 $V$,则称其为 $V$ 的基(basis)

$\mathfrak {B}$ 中的元素称为基向量。如果基中元素个数有限,就称向量空间为有限维向量空间,将元素的个数称作向量空间的维数。

性质

设 $\mathfrak {B}$ 是向量空间 $V$ 的基。则 $\mathfrak {B}$ 具有以下性质:

  • $V$ 是 $\mathfrak {B}$ 的极小生成集,就是说只有 $\mathfrak {B}$ 能张成 $V$,而它的任何真子集都不张成全部的向量空间。
  • $\mathfrak {B}$ 是 $V$ 中线性无关向量的极大集合,就是说 $\mathfrak {B}$ 在 $V$ 中是线性无关集合,而且 $V$ 中没有其他线性无关集合包含它作为真子集。
  • $V$ 中所有的向量都可以按唯一的方式表达为 $\mathfrak {B}$ 中向量的线性组合。

第三点尤其重要,感性的理解,基就是向量空间中的一个子集,它可以通过唯一的线性组合,来张成向量空间中所有的向量,这样就可以大大的缩小我们向量空间的大小。

线性基

对于数 $a_0, a_1, \ldots, a_n$,将 $a_i$ 的二进制表示 $a_i = (b_{m}\ldots b_0)_2$ 看作一个向量 $\mathbf{a}_i = (b_m, \ldots, b_0)$,为了叙述上的方便,下文称向量 $\mathbf{a}_i$ 的第 $j$ 位为 $b_j$。

向量组 $\mathbf{a}_1, \ldots, \mathbf{a}_n$ 可以张成一个向量集合 $\mathrm{span}(\mathbf{a}_1, \ldots, \mathbf{a}_n)$,加上我们的异或运算和乘法运算(显然满足 8 条公理),即可形成一个向量空间 $V = ({0, 1}, \mathrm{span}(\mathbf{a}_1, \ldots, \mathbf{a}_n), \oplus, \cdot)$。

我们考虑求出向量空间 $V$ 的一个基 $\mathfrak{B}$,从 $\mathfrak{B} = (\mathbf{a}_1, \ldots, \mathbf{a}_n)$ 开始。

第 1 步:如果 $\mathbf{a}_1 = \mathbf{0}$ ,则从 $\mathfrak{B}$ 中去掉 $\mathbf{a_1}$​ ,否则保持 $\mathfrak{B}$ 不变。

第 j 步:若 $\mathbf{a}_j \in \mathrm{span}(\mathbf{a}1, \ldots, \mathbf{a}{j - 1})$,则从 $\mathfrak{B}$ 中去掉 $\mathbf{a}_j$​​ ,否则保持 $\mathfrak{B}$ 不变。

经过 $n$ 步后终止程序,得到一个向量组 $\mathfrak{B}$。由于每一次去掉的向包含于前面诸向量的张成,到最后这个组 $\mathfrak{B}$ 仍然可以张成 $V$。而且这一程序确保了 $\mathfrak{B}$ 中的任何向量都不包含与它前面诸向量的张成,根据线性相关性引理可知 $\mathfrak{B}$ 是线性无关的。于是 $\mathfrak{B}$ 是 $V$ 的一个基。

利用高斯消元来判断向量能否被前面的向量张成,就可以写出下面的程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct LB {
int basis[MAX_BASE + 1];
LB() { memset(basis, 0, sizeof(basis)); }
int query() {
int ret = 0;
for (int i = MAX_BASE; i >= 0; i--) {
ret = max(ret, ret ^ basis[i]);
}
return ret;
}
bool insert(int x) {
for (int i = MAX_BASE; i >= 0 && x; --i)
if (x >> i & 1) {
if (basis[i])
x ^= basis[i];
else {
basis[i] = x;
return true;
}
}
return false;
}
void clear() { memset(basis, 0, sizeof(basis)); }
};

线性基求交集

严格的说法是两个线性空间求交集。

两个线性空间的交集仍然是线性空间,那么必然可以用一组线性基来描述。

假设 $V_1$ 和 $V_2$ 是两个线性空间,他们的基分别是 $B_1$ 和 $B_2$。

令 $W = B_2 \cap V_1$,若 $B_1 \cup (B_2 - W)$ 线性无关,则 $W$ 是 $V_1 \cap V_2$的一组基。

我们可以枚举 $B_2$ 中的元素,若和 $B_1$ 线性无关,则插入到 $B_1$ 中。 否则把 $V_1$ 对该元素的贡献加到答案中。

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
37
38
39
40
LB Intersect(LB A, LB B) {
LB All, C, D;
All.clear();
C.clear();
D.clear();
for (int i = MAX_BASE; i >= 0; i--) {
All.basis[i] = A.basis[i];
D.basis[i] = 1ll << i;
}
for (int i = MAX_BASE; i >= 0; i--) {
if (B.basis[i]) {
int v = B.basis[i], k = 0;
bool can = true;
for (int j = MAX_BASE; j >= 0; j--) {
if (v & (1ll << j)) {
if (All.basis[j]) {
v ^= All.basis[j];
k ^= D.basis[j];
} else {
can = false;
All.basis[j] = v;
D.basis[j] = k;
break;
}
}
}

if (can) {
int v = 0;
for (int j = MAX_BASE; j >= 0; j--) {
if (k & (1ll << j)) {
v ^= A.basis[j];
}
}
C.insert(v);
}
}
}
return C;
}