第 52 章 有限域上的线性代数¶
前置：向量空间 (Ch04) · 多项式代数 (Ch00) · 抽象代数基础
本章脉络：从连续域到离散域 \(\to\) 有限域 \(GF(q)\) 的定义与构造 \(\to\) 域的特征 (Characteristic) \(\to\) 有限域上的向量空间 \(\to\) 维数与基向量的计数原理 \(\to\) 矩阵的秩与 RREF \(\to\) 典型群 \(GL(n, q)\) 的阶数 \(\to\) 应用：纠错码（线性码、Hamming 码）、密码学（AES 算法中的域运算）、设计理论
延伸：有限域上的线性代数是现代数字通信的支柱；它证明了线性空间的概念并不依赖于数值的大小，只依赖于代数结构的完备性，是处理二进制、十六进制数据的终极数学语言
在前面的章节中，我们通常假设标量来自于实数域 \(\mathbb{R}\) 或复数域 \(\mathbb{C}\)。然而，在计算机科学和通信工程中，标量通常取自有限的集合。有限域（Finite Fields，或称 Galois 域）上的线性代数，处理的是“离散”的线性空间。尽管直观上有所不同（如 \(1+1=0\)），但向量空间、基、秩和特征值等核心概念在有限域上依然完美成立。本章将介绍这一作为纠错码与密码学底层逻辑的代数体系。
52.1 有限域 \(GF(q)\) 的性质¶
定义 52.1 (有限域)
包含有限个元素的域称为有限域。其阶数 \(q\) 必须是素数 \(p\) 的幂，记作 \(GF(p^k)\)。 - \(GF(p)\)：即模 \(p\) 同余类环 \(\mathbb{Z}/p\mathbb{Z}\)。 - 特征：域内满足 \(p \cdot 1 = 0\) 的最小正整数 \(p\)。
52.2 维数与计数原理¶
定理 52.1 (向量空间的大小)
设 \(V\) 是 \(GF(q)\) 上的 \(n\) 维向量空间。则 \(V\) 中总共包含 \(q^n\) 个不同的向量。
计数：\(GL(n, q)\) 的阶
\(GF(q)\) 上所有 \(n\) 阶可逆矩阵构成的群的阶数为： $\(|GL(n, q)| = (q^n - 1)(q^n - q)(q^n - q^2) \cdots (q^n - q^{n-1})\)$ 这来源于构造线性无关列向量的选择方法。
52.3 线性码应用¶
应用：纠错码
一个 \((n, k)\) 线性码 是 \(GF(q)^n\) 的一个 \(k\) 维子空间。 - 生成矩阵 \(G\)：子空间的基构成的矩阵。 - 校验矩阵 \(H\)：子空间的正交补（零空间）的基构成的矩阵。 - 纠错原理：利用线性空间的稀疏性，通过矩阵乘法 \(H\mathbf{r}^T\) 判定并定位传输中的错误。
练习题¶
1. [基础] 在 \(GF(2)\) 中，计算 \((1, 0, 1) + (1, 1, 0)\)。
参考答案
计算步骤： 1. \(GF(2)\) 中的加法对应于异或 (XOR) 运算：\(1+1=0, 1+0=1, 0+0=0\)。 2. 第一分量：\(1+1 = 0\)。 3. 第二分量：\(0+1 = 1\)。 4. 第三分量：\(1+0 = 1\)。 结论：结果为 \((0, 1, 1)\)。
2. [基计数] 在 \(GF(3)\) 上的 2 维空间中，有多少个非零向量？共有多少组基？
参考答案
计算： 1. 总向量数：\(3^2 = 9\)。 2. 非零向量数：\(9 - 1 = 8\)。 3. 基的计数： - 第一个向量选择：8 种（任意非零向量）。 - 第二个向量选择：不能是第一个向量的倍数。倍数有 \(\{0, v, 2v\}\) 共 3 个。故有 \(9 - 3 = 6\) 种。 - 总排列基数：\(8 \times 6 = 48\)。 - 无序基数：\(48 / 2! = 24\)。
3. [矩阵秩] 判定 \(GF(2)\) 上的矩阵 \(\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}\) 的秩。
参考答案
消元步骤： 1. \(R_2 - R_1 \to R_2\)。 2. 计算：\(1-1=0, 1-1=0\)（注意在 \(GF(2)\) 中 \(1-1=1+1=0\)）。 3. 结果矩阵为 \(\begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix}\)。 结论：秩为 1。这与实数域结果一致。
4. [特征值] 求 \(GF(2)\) 上矩阵 \(\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\) 的特征值。
参考答案
解特征方程： 1. \(p(\lambda) = \det(\lambda I - A) = \det \begin{pmatrix} \lambda & 1 \\ 1 & \lambda \end{pmatrix} = \lambda^2 - 1\)。 2. 在 \(GF(2)\) 中，\(-1 = 1\)，故方程为 \(\lambda^2 + 1 = 0\)。 3. 由于 \((\lambda+1)^2 = \lambda^2 + 2\lambda + 1 = \lambda^2 + 1\)。 结论：特征值为 \(\lambda = 1\)，重数为 2。
5. [线性码] 已知生成矩阵 \(G = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix}\) 在 \(GF(2)\) 上。该码包含哪些码字？
参考答案
枚举线性组合： 1. \(0 \cdot G_1 + 0 \cdot G_2 = (0, 0, 0)\) 2. \(1 \cdot G_1 + 0 \cdot G_2 = (1, 0, 1)\) 3. \(0 \cdot G_1 + 1 \cdot G_2 = (0, 1, 1)\) 4. \(1 \cdot G_1 + 1 \cdot G_2 = (1, 1, 0)\) 结论：码集为 \(\{(0,0,0), (1,0,1), (0,1,1), (1,1,0)\}\)。
6. [校验阵] 为上题中的线性码求校验矩阵 \(H\)。
参考答案
寻找零空间： 1. 码字 \((x_1, x_2, x_3)\) 需满足 \(x_1+x_3=0\) 且 \(x_2+x_3=0\)。 2. 故 \(x_1=x_3, x_2=x_3\)。 3. 取 \(x_3=1\)，得基础解系 \((1, 1, 1)\)。 结论：\(H = \begin{pmatrix} 1 & 1 & 1 \end{pmatrix}\)。
7. [逆矩阵] 在 \(GF(5)\) 中计算 2 的逆元。
参考答案
解方程 \(2x \equiv 1 \pmod 5\)： 1. \(2 \times 3 = 6 \equiv 1 \pmod 5\)。 结论：\(2^{-1} = 3\)。这在有限域矩阵求逆中频繁使用。
8. [性质] 在 \(GF(p)\) 上的向量空间中，是否存在“长度”概念？
参考答案
辨析： 传统的欧几里得长度（实数平方根）在有限域上没有定义。虽然可以定义二次型 \(x^T x\)，但它不满足正定性（如 \(GF(2)\) 中 \((1,1)\) 的“长度平方”为 \(1+1=0\)）。因此，有限域上的几何通常被称为伪欧几里得几何，主要关注正交性而非大小。
9. [典型群] 计算 \(GL(2, 2)\) 的阶。
参考答案
套用公式： \(|GL(2, 2)| = (2^2-1)(2^2-2) = (3)(2) = 6\)。 补充：这 6 个矩阵分别是 3 个置换矩阵及其线性组合。
10. [应用] 简述线性代数在 AES 加密算法中的应用。
参考答案
AES 的核心步骤 MixColumns 是一个在 \(GF(2^8)\) 上的固定线性变换。它通过将状态矩阵的每一列乘以一个最大距离可分 (MDS) 矩阵，实现了信息的快速扩散（Diffusion），确保了微小的明文变化会导致密文剧烈波动。
本章小结¶
有限域上的线性代数是数字世界的代数灵魂：
- 公理的一致性：它证明了线性空间的所有运算逻辑在舍弃了连续性与大小直观后依然严丝合缝，展现了数学真理的纯粹性。
- 计数的威力：有限性使得我们能精确量化空间的大小与群的阶数，为信息论中的搜索空间估计和安全强度评估提供了基准。
- 纠错的基石：通过将通信序列建模为有限域上的子空间，线性代数不仅实现了信息的传递，更赋予了数据自我修复的能力，支撑了整个现代互联网的物理层。