「线性基」线性基入门笔记

线性基入门

下面数学内容大概是氵长度,可以暂且跳过直接看线性基

前备知识

本文的前备知识:

  • 什么是向量,懂得常用表示方法
  • 了解什么是方程组
  • 善用搜索引擎搜索自己需要的内容 搜索亦是一门艺术

任何向量可由它所处的空间中的 基向量 线性组合表示,向量就是将基向量缩放并相加得到的。所以有了缩放和相加,就可以在基向量确定的空间构造任意向量。

比如二维空间的基向量通常被叫做 \hat i \hat j ,那么对于向量 \left[ \begin{array} { c } { - 2 } \\ { 3 } \end{array} \right] 就可以表示为 -2\times \hat i +3\times \hat j

采用数值描述一个向量时严格依赖于当前使用的基,对于向量 \left[ \begin{array} { c } { x } \\ { y } \end{array} \right] 在不同基的情况下是不同的

线性组合

两个数乘向量的和,就可以被称作 线性组合

比如对于 a \vec { v } + b \vec { w } 就是 \vec { v } \vec { w } 的线性组合

下面来看一下为什么叫做 线性 组合

对于 \vec { v } \vec { w } 的线性组合,我们现在固定 b 的值,那么最后其线性组合所成向量的终点会在一条直线上(可以感性理解

向量的线性组合所成向量集合也叫做向量所 张成 的空间

对于两个向量 \vec { v } \vec { w } 张成的空间

  • \vec { v } \vec { w } 都为零向量时,其张成的空间为原点

  • \vec { v } \vec { w } 共线,其张成的空间为 \vec { v } \vec { w } 所在直线

  • \vec { v } \vec { w } 不共线,其张成的空间为 \vec { v } \vec { w } 所在平面

线性相关与线性无关

几何地来说,就是对于一组向量 \{\overrightarrow { a _ { 1 } } , \overrightarrow { a _ { 2 } } , \cdots , \overrightarrow { a _ { n } }\} 所张成的空间,若移除一个向量 \vec {a_i} 其剩下的向量所张成的空间不变,那么这个向量对所张成的空间没有贡献(如两个共线的向量),就可以称这组向量是 线性相关 的,同时这个向量一定可以被表示为其他向量的线性组合

否则就称作这组向量 线性无关,也就是说其中任何向量 \vec {a_i} 都不能被其他向量表示出来

硬核地来说,就是对于向量组 \{\overrightarrow { a _ { 1 } } , \overrightarrow { a _ { 2 } } , \cdots , \overrightarrow { a _ { n } }\} 与标量 \{\lambda_1,\lambda_2,\cdots,\lambda_n\} 组成的式子 \sum _ { i = 1 } ^ { n } \lambda _ { i } \vec { a } _ { i } ,当且仅当 \lambda_1=\lambda_2=\cdots=\lambda_n=0 时,其值为 0 ,那么就可以说向量组 \{\overrightarrow { a _ { 1 } } , \overrightarrow { a _ { 2 } } , \cdots , \overrightarrow { a _ { n } }\} 线性无关,否则就说明其线性相关

证明:若存在 \lambda _i\neq0 式子 \sum _ { i = 1 } ^ { n } \lambda _ { i } \vec { a } _ { i }=0 成立,那么一定可以表示为 \vec {a_k} = -{\sum _ { i = 1 ,i\neq k} ^ { n } \lambda _ { i }\vec { a } _ { i }\over \lambda_k} ,也就是 \vec{a_k} 被我们表示成了其他向量,说明这组向量线性相关 这证明貌似啥都没说

线性基

我们将一个数 x 表示为二进制 \overline {a_1a_2\cdots a_n}_{(2)} 我们分离各个位使它变为一个向量 \vec v

对于许多二进制数的集合 \{b_1,b_2,\cdots,b_n\} 我们将其所有子集异或的结果也用上面方法分离为向量,其张成的向量空间叫做 \text{V} ,那么 \text{V} 就是一个域为 \{0,1\} ,基本运算是 异或 的向量空间 (下文中的异或用 \oplus 表示,前面定义的向量 的异或代表其对应二进制异或),而在信息学竞赛中讨论的线性基通常又被叫做 极大线性无关向量组

显然地 \text{V} 作为向量空间是由基向量组成的,我们求出这些基,就能表示出 \text{V} 的所有向量

现在考虑如何求出这些向量,这里给出一个较为简单的做法,首先考虑一个性质:

对于基中的两个向量 \vec a \vec b ,令 \vec c = \overrightarrow a \oplus \overrightarrow b , 则将 \vec b 替换为 \vec c ,其张成的空间不变

证明:证明很简单,当将 \overrightarrow a_p 替换为 \overrightarrow a_q' = \overrightarrow a_q \oplus \overrightarrow a_p,(p\neq q) 时,原来的 \overrightarrow a_q = \overrightarrow a_q' \oplus \overrightarrow a_q ,于是前后的基是不变的

所以对于基里面的向量如何上述操作其所张成的空间总是不变的

现在构造一个线性基使其满足下面的性质

  1. 向量对应的二进制 递增(即满足线性基中向量对应二进制的最高位递增)
  2. 向量对应的二进制最高位 两两不同(若相同,则通过对两个向量进行 \oplus 来消去)

上述限定也就是让得到的线性基唯一,根据这个,就自然得到了一个插入一个向量(二进制数)的算法:

从高到低枚举当前数的二进制的非零位 i ,若线性基中不存在第 i 位为有值的,则插入到线性基中;若线性基中已经存在,则通过异或消去第 i

这样,就得到了一个 \text O(\log n) 的做法,下面给出 C++ 的代码实现

1
2
3
4
5
6
7
8
9
10
void insert (unsigned long long x) {
for (int i = 62; i >= 0; i--)
if (x & (1ll << i)) {
if (base[i]) x ^= base[i];
else {
base[i] = x;
break;
}
}
}

因为这个基的一些性质,OI 中提到的线性基一般都是通过这个方法得到的


对于两个向量空间,当然可以通过合并其基底来进行向量空间的合并。注意到由于向量空间是基向量的线性组合,故其向量空间的合并并非是两个空间的并,而是基向量的并的线性组合

由于笔者只会暴力合并,并不会更高级的合并方法,也并未在搜索引擎中有所收获,于是这里只给出暴力合并的方法

也就是对于两个线性基 A = \{\overrightarrow { a _ { 1 } } , \overrightarrow { a _ { 2 } } , \cdots , \overrightarrow { a _ { n } }\} B = \{\overrightarrow { b _ { 1 } } , \overrightarrow { b _ { 2 } } , \cdots , \overrightarrow { b _ { n } }\} 每次取出 B 中的每个向量 \vec b_i 暴力插入 A 中即可

1
2
3
4
5
void merge (unsigned long long *a, unsigned long long *b) {
for (int i = 62; i >= 0; i--) {
if (b[i]) insert(a, b[i]);
}
}

求解最大异或和亦是线性基的一个应用,也就是对于一个集合 T ,选出 T 中的一个子集 S ,满足 \bigoplus _ {x\in S} x 最大,求出这个最大值 「这不是sb题吗」

对于这个问题,直接贪心选取线性基中的元素即可

例题

给定一个边有边权的无向连通图,求出一条从 1 号节点到 N 号节点的路径,使得路径上经过的边的权值的 XOR 和最大(「WC2011」最大XOR和路径)

做法就是把所有环的长度插入线性基,然后随便找个链,在线性基中查询最大异或就好了

代码:

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#define ul unsigned long long
#define int long long

const int N = 200000 + 10;
const int M = 400000 + 10;

ul base[N];
std::vector <std::pair <int, int> > e[N];

inline void add (int u, int v, int w) { e[u].pb(mp(v, w)); e[v].pb(mp(u, w)); }

void insert (ul x) {
down (i, 60, 0)
if (x & (1ll << i)) {
if (base[i]) x ^= base[i];
else {
base[i] = x;
break;
}
}
}

ul query (ul x) {
down (i, 60, 0)
if (x < (x ^ base[i])) x ^= base[i];
return x;
}

int vis[N];
ul d[N];

void dfs (int u) {
if (vis[u]) return;
vis[u] = 1;
for (auto i : e[u]) {
if (vis[i.x]) insert(d[u] ^ d[i.x] ^ i.y);
else d[i.x] = d[u] ^ i.y;
dfs(i.x);
}
}

signed main () {
int n, m;
n = read(); m = read();
int u, v, w;
up (i, 1, m) {
u = read(); v = read(); w = read();
add (u, v, w);
}

dfs(1);

print(query(d[n]));
return 0;
}
坚持原创技术分享,您的支持将鼓励我继续创作!