线性基求交:设 \(A,B\) 为两个线性基,\(V_A,V_B\) 分别为其生成空间,则 \(V_C=V_A\cap V_B\) 是一个线性空间,称 \(A\) 与 \(B\) 两个线性基的交为 \(C\)。
首先证明 \(V_C\) 是一个线性空间。其实很显然,对于任意 \(x,y\in V_C=V_A\cap V_B\),\(x,y\in V_A\implies x\oplus y\in V_A\),同理 \(x\oplus y\in V_B\),从而 \(x\oplus y\in V_A\cap V_B=V_C\)。
以下是求线性基的交 \(C\) 的算法:
首先对线性基 \(B\) 进行一些调整(后面会讲),保持其生成空间 \(V_B\) 不变。
设存在一个线性基 \(W\),满足以下三条性质:
说成人话,就是 \(W\) 是线性基 \(B\) 中与 \(V_A\) 有交的那部分,\(B\) 中其余部分与 \(A\) 线性无关。
那么可以证明,\(W\) 即为所求的线性基的交 \(C\)。
分两步证明 \(V_W=V_A+V_B\):
- 假设存在 \(u\notin V_W\) 且 \(u\in V_A\cap V_B\)。
由于 \(u\in V_B\),故此时存在一些 \(\{b_i\}\) 满足 \(b_i\in B,\ \bigoplus b_i=u\)。将这些 \(b_i\) 分成两部分,前者 \(\in W\),后者 \(\in B-W\),令前者的异或和为 \(s\),后者为 \(t\),则 \(s\in V_W,t\in V_{B-W}\)。
而 \(u\in V_A,s\in V_W\subseteq V_A\),故 \(t=u\oplus s\in V_A\)。又 \(t\in V_{B-W}\),由性质 3 得 \(t=0\),从而 \(u=s\in V_W\),矛盾。 - 假设存在 \(u\in V_W\) 且 \(u\notin V_A\cap V_B\)。
组成 \(u\) 的基底既在 \(B\) 中也在 \(V_A\) 中,显然矛盾。
现在我们剩下的问题就剩下求出 \(W\) 了。
对每个 \(b_i\) 依次执行以下操作:
- 若 \(b_i\in \mathrm{span}(\{a_1,a_2,\dots,a_n,b_1,b_2,\dots,b_{i-1}\})\),设其表示为 \(b_i=\alpha \oplus \beta\),其中 \(\alpha \in V_A,\beta \in \mathrm{span}\{b_1,\dots,b_{i-1}\}\),令 \(b_i\leftarrow b_i\oplus \beta\),并标记其为 \(1\) 类;
否则,不做任何操作,标记其为 \(2\) 类。
最终得到的 \(\{b_i\}\) 与 \(V_A\) 的交即为满足条件的 \(W\)。以下证明其满足 \(V_{B-W}\cap V_A=\{0\}\):
发现经过前面的操作,所有 \(1\) 类的 \(b_i\) 都 \(\in V_A\),所有 \(2\) 类的 \(b_i\) 都 \(\notin V_A\)。于是 \(1\) 类 \(b_i\) 所组成的集合即为 \(W\),\(2\) 类即为 \(B-W\)。
若存在 \(u\neq 0\) 满足 \(u\in V_{B-W}\) 且 \(u\in V_A\),则存在若干个 \(2\) 类 \(b_i\) 以及若干个 \(a_i\) 使得 \(\bigoplus b_i=u=\bigoplus a_i\),取出这些 \(b_i\) 中下标最大的那个 \(b_k\),则 \(b_k=b_1\oplus b_2\oplus \dots \oplus b_{k-1} \oplus \bigoplus a_i\),与在位置 \(k\) 时 \(b_k\) 没有标记为 \(1\) 类矛盾!
证毕。
标签:dots,notin,cap,基求,算法,bigoplus,线性,oplus From: https://www.cnblogs.com/Charlie-Vinnie/p/17084753.html