线性基总结

Believe_in_dreams · 2025-11-30 22:32:15 · 算法·理论

线性基总结

未完工。。。

概念

线性基通常指 异或空间线性基 。

指能通过子集异或运算 构成 ”集合 A 的异或空间“ 的集合 。

例如 A=\{1,2,3\} ，则 A 的线性空间为 \{1,2,3\} 。

一个该线性空间的线性基为 \{1,2\} 。

因为 1=1,2=2,3=1\oplus 2 。

注意:

• 我们只关心非 0 异或和。

• 一个线性空间可能有多组线性基。

性质

::::info[性质证明的前置知识]

异或运算！

• 交换律 a\oplus b=b\oplus a

• 抵消性质 a\oplus a=0

::::

• 对于数集 A 若有 a,b\in A

  则用 a\oplus b 替换 a,b 不会影响异或线性空间的组成。

  ::::info[证明]

  如果把 a 换成了 a\oplus b ，则可以把 b\oplus (a\oplus b) 当作 a 使用。

  换 b 同理，即得证。

  ::::

• 对于数集 A 若有 a,b\in A,~a\oplus b=0 ，

  则任意删去 a,b 中的一个不会影响异或线性空间的组成。

  ::::info[证明]

  显然此时 a=b ，易证。

  ::::

  ::::info[扩展]

  进一步地，对于数集 A 。

  若有数集 B\subset A ，且有 \oplus x\in B=0 ，

  则任意删去 B 其中的一个元素不影响 A 的异或线性空间组成。

  :::info[证明]

  显然删去的这个元素可以有 B 集中其他元素异或得到，

  故是否存在不影响异或空间，得证。

  :::

  ::::