一个关于异或线性基的有趣结论

作者并不是很懂线性代数相关的一些术语，所以可能本文很多东西说法并不是很标准，不过从逻辑上应该是足够严谨的。

符号约定：

• 本文线性基均指 异或线性基。
• 本文向量均指 01 向量。
• 一个大小为 n 线性基为 n 个大小为 n 的向量构成。
  • 一个向量 p_i=(p_{i,1},p_{i,2},\cdots,p_{i,n})，p_{i,j}\in\{0,1\}。
  • 一个线性基 P=(p_1,p_2,\cdots p_n)。特别的，我们认为：
  • 若 p_{i,i}=0，则 \forall j\in[1,n] 有 p_{i,j}=0。
  • 若 p_{i,i}=1，则 \forall j\in[1,i) 有 p_{i,j}=0。
• 记 S_B 表示线性基 B 张成的线性空间中所有元素的集合。
• 对于向量 a,b，我们称 a<b 当且仅当：
  • 存在 k\in[1,n] 使得 a_k<b_k 且 \forall i\in[1,k) 有 a_i=b_i。
• 定义向量异或运算 \oplus 为：
• 记 F_{\max,B}(x) 表示 \max\limits_{y\in S_B}{x\oplus y}。
• 记 F_{\min,B}(x) 表示 \min\limits_{y\in S_B}{x\oplus y}。

结论：

证明：

考虑一个我们求 F_{\max,B}(x) 的过程：

1. 令 i\gets 1。
2. 若 x_i=0，则令 x\gets x\oplus B_i。

这里有一个非常棘手的操作是：我们进行第二步操作后，x 后面的值会发生变化！也就是存在某个 j 最初 x_j=1，后来变成了 x_j=0，也就是我们没法在最开始就确定每个位置是否会进行操作！

但是我们断言：必然存在一个线性基 B' 满足：

• 对于任意 1\le i<j\le n 且 B'_{i,j}=1 满足 B'_{j,j}=0。

也就是我们对于线性基 B' 可以在最初确定哪些位置需要进行操作（所有 x_i=0 的位置）。

尝试给出构造性证明，考虑归纳：

1. 对于 i=n 显然满足条件。
2. 当前对于 i=k+1\sim n 满足条件，考虑取出所有 B'_{i,j}=1 的位置 j，令 B'_i\gets B'_i\oplus B'_j 即可。

最终得到的 B' 显然满足条件。

且 F_{\max,B}(x)=F_{\max,B'}(x)=x\oplus(\overset{n}{\underset{1\le i\le n,x_i=0}{\oplus}} B'_{i})。

我们记 G_{\max,B}(x)=\overset{n}{\underset{1\le i\le n,x_i=0}{\oplus}} B_{i}，同理有 G_{\min,B}(x)=\overset{n}{\underset{1\le i\le n,x_i=1}{\oplus}} B_{i}。

即得 F_{\max,B'}(x)=x\oplus G_{\max,B'}(x) 和 F_{\min,B'}(x)=x\oplus G_{\min,B'}(x)。

考虑刻画 F_{\max,B}(x\oplus y)：

故证毕！

注意其中标红的部分，手玩一下真值表可以说明，而 G_{\max,B} 就没有这样好的性质，这也就是我们强行扯出了 \min 的意义。