线性基与线性代数

对于二进制来说，我们的数域是 $F=\{0,1\}$，$a\circ_+b=(a+b)\%2,a\circ_{-}b=(a-b+2)\%2,a\circ_{\times}b=a \& b$。可以发现其对四则运算封闭。

对于一个二进制数，我们可以把它看做一个向量，每一维分别是这一位上二进制的值，如 $5=(101)_2=(1,0,1)$。我们称这样的向量为二进制向量。

问这样的向量是否组成一个线性空间？

1. 交换律，显然满足
2. 结合律，显然满足
3. 零元存在，每维全部为 0。
4. 负元存在，即 $\alpha$ 本身。
5. 数乘，$1\alpha=\alpha$。
6. $k(l\alpha)=l(k\alpha)=(kl)\alpha$。
7. $(k+l)\alpha=k\alpha+l\alpha$，可以分别讨论 $k=l=0;k=1,l=0;k=1,l=1$ 的情况，都是符合的。
8. $k(\alpha+\beta)=k\alpha+k\beta$。

那么，二进制向量组成一个线性空间。

线性基要我们解决的问题就是，给出 $n$ 个二进制向量，要你找出一个二进制向量是其线性组合，满足其十进制表示最大。

一组向量与其极大线性无关组等价，而我们现在可以用高斯消元法求出其极大线性无关组。