一、域上线性空间回顾与极大无关组
1.1 上节课回顾
线性代数中，只要不涉及实数/复数的比较大小和取模长，几乎所有概念和结论都可以照搬到一般域上。线性代数课本里的许多证明虽然是对实数或复数写的，但把域替换成任何一个域，证明直接就能通过。
以下讨论均限于有限维情形。
1.2 极大无关组的定义
设 $V$ 是域 $\mathbb{F}$ 上的线性空间，$S = \{x_1, x_2, \ldots, x_n\} \subseteq V$ 是有限子集。取子集 $A = \{v_1, v_2, \ldots, v_m\} \subseteq S$（两两不同），称 $A$ 为 $S$ 的极大线性无关组（Maximal Linearly Independent Subset），如果满足：
- $A$ 在 $\mathbb{F}$ 上线性无关
- $S$ 中任意向量都可由 $A$ 中向量线性表出
即对任意 $w \in S$，存在系数 $a_1, \ldots, a_m \in \mathbb{F}$ 使得：
\[w = a_1 v_1 + a_2 v_2 + \cdots + a_m v_m\]1.3 例：$\mathbb{R}^2$ 中的三个向量
考虑 $S = \left\{ \begin{bmatrix}1\\0\end{bmatrix}, \begin{bmatrix}0\\1\end{bmatrix}, \begin{bmatrix}1\\1\end{bmatrix} \right\}$
- 前两个向量线性无关
- 第三个向量 = 第一个 + 第二个
- 因此取 $A = \left\{ \begin{bmatrix}1\\0\end{bmatrix}, \begin{bmatrix}0\\1\end{bmatrix} \right\}$ 就是极大无关组
极大无关组不唯一。也可以取 $A = \left\{ \begin{bmatrix}1\\0\end{bmatrix}, \begin{bmatrix}1\\1\end{bmatrix} \right\}$ 或 $A = \left\{ \begin{bmatrix}0\\1\end{bmatrix}, \begin{bmatrix}1\\1\end{bmatrix} \right\}$，都满足条件。但元素个数始终为 2。
1.4 极大无关组的基本性质
性质 1（存在性）：极大无关组一定存在。
具体找法（贪心算法）：逐个检查每个向量
- 先把 $x_1$ 放入（若 $x_1 \neq 0$）
- 若 $x_2$ 与已选向量线性无关则放入，否则跳过
- 依此类推，有限步完成
存在性的另一种证明（极大元方法）：
- 考虑集合 $T = \{\text{所有 } S \text{ 中在 } \mathbb{F} \text{ 上线性无关的子集}\}$（规定空集线性无关）
- $T$ 非空，且 $S$ 有限，故 $T$ 中元素个数有上界
- 取 $T$ 中元素个数最大的 $B$
- 断言 $B$ 就是极大无关组
- 条件 1（线性无关）：由 $T$ 的定义自动满足
- 条件 2（线性表出）：若 $w \notin B$，则 $B \cup \{w\}$ 不在 $T$ 中（否则与 $B$ 的最大性矛盾），故线性相关，可推出 $w$ 可由 $B$ 线性表出
这种”取元素个数最大的子集”的方法是离散数学中非常常见的技巧。图论中证明生成树的存在性也是类似思路——取边数最大的无圈子图就是生成树。
性质 2（元素个数唯一性）：极大无关组的元素个数是唯一确定的。
证明思路：取两个极大无关组 $A$ 和 $B$，它们各自线性无关且可互相线性表出。若 $|B| > |A|$，由线性代数基本引理可推出 $B$ 线性相关，矛盾。对称可得 $|A| \ngtr |B|$，故 $|A| = |B|$。
这个结论保证了”维数”这个定义是合理的——把维数定义为线性空间中最大线性无关组的元素个数，这个个数是确定的。
二、域上的矩阵
2.1 基本定义
域 $\mathbb{F}$ 上的 $m \times n$ 矩阵：记作 $\mathbb{F}^{m \times n}$ 或 $M_{m \times n}(\mathbb{F})$。
常见的记号还有 $M_{m,n}(\mathbb{F})$，看作从指标集 $\{1,\ldots,m\} \times \{1,\ldots,n\}$ 到 $\mathbb{F}$ 的映射。
2.2 矩阵运算
- 加法：对应位置分量相加（和实数域完全一样）
- 数乘：每个位置乘上固定元素
- 矩阵乘法：当第一个矩阵的列数等于第二个矩阵的行数时可定义。若 $A \in \mathbb{F}^{m \times n}, B \in \mathbb{F}^{n \times p}$，则 $C = AB \in \mathbb{F}^{m \times p}$，其中：
运算律（与实数情形一致）：加法结合律/交换律、乘法结合律、乘法对加法的分配律。
2.3 单位矩阵与可逆矩阵
$n$ 阶单位矩阵 $I_n$：对角线上为域中乘法幺元 $1$，其余位置为 $0$。满足对任意 $A \in \mathbb{F}^{m \times n}$：$I_m A = A I_n = A$。
可逆矩阵：方阵 $A \in \mathbb{F}^{n \times n}$ 称为可逆的，若存在 $B$ 使得：
\[AB = BA = I_n\]从抽象代数的角度看，可逆矩阵就是矩阵乘法半群中的可逆元。所有 $n$ 阶方阵在加法和乘法下构成一个环，可逆矩阵在乘法下构成一个群。
可逆的等价条件（与实数域一样）：
- 行列式不为零（$\det A \neq 0$）
- 矩阵是满秩的（秩 $= n$）
三、矩阵的秩
3.1 定义
设 $A \in \mathbb{F}^{m \times n}$，将 $A$ 的 $m$ 行取出来，视为 $\mathbb{F}^n$ 中的 $m$ 个 $n$ 元行向量。这 $m$ 个行向量作为一个子集，其极大无关组的元素个数就定义为矩阵 $A$ 的秩（Rank）。
同理，取列向量的极大无关组元素个数，结果是一样的——这是域上矩阵的重要性质：行秩 = 列秩。
3.2 秩的计算
与线性代数中完全相同：通过初等行变换（一行乘上域中元素加到另一行、交换两行），可将矩阵化为标准形：
\[PAQ = \begin{bmatrix} I_r & 0 \\ 0 & 0 \end{bmatrix}\]其中 $r$ 就是矩阵的秩，等于对角线上 $1$ 的个数。这里 $1$ 是域 $\mathbb{F}$ 中的乘法幺元。
四、行列式
4.1 域上行列式的定义
域 $\mathbb{F}$ 上的行列式定义与实数域一致，但前提是乘法可交换（域满足此条件）。
递归定义（余子式展开法）：
- 一阶：$\det[a] = a$
- 二阶：$\det\begin{bmatrix} a & b \\ c & d \end{bmatrix} = ad - bc$
- $n$ 阶：按某一列（如第一列）展开， \(\det A = \sum_{i=1}^{n} (-1)^{i+1} a_{i1} \det(M_{i1})\) 其中 $M_{i1}$ 是划去第 $i$ 行和第 $1$ 列后的 $(n-1)$ 阶子式。
无论按哪一行/哪一列展开，结果都是相同的（这需要严格证明）。
4.2 置换定义（组合定义）
另一种更统一的定义方式——利用对称群和逆序数：
\[\det A = \sum_{\sigma \in S_n} (-1)^{\text{inv}(\sigma)} \prod_{i=1}^{n} a_{i, \sigma(i)}\]其中 $S_n$ 是 $n$ 阶对称群，$\text{inv}(\sigma)$ 是置换 $\sigma$ 的逆序数。
这个定义的好处是规避了”为什么按不同行/列展开结果相同”的问题。但实际计算时仍用递归法——置换定义的求和有 $n!$ 项，计算量太大，仅利于理论分析。
4.3 有限域上计算行列式的注意事项
在有限域上计算行列式时，必须明确是在哪个域上计算。
例：考虑矩阵 $\begin{bmatrix} 1 & 2 \\ 2 & 1 \end{bmatrix}$
- 在 $\mathbb{R}$ 上：$\det = 1 \cdot 1 - 2 \cdot 2 = -3 \neq 0$，可逆
- 在 $\mathbb{F}_3$（模 3 的有限域）上：$1 \cdot 1 - 2 \cdot 2 = 1 - 4 \equiv 1 - 1 = 0$，不可逆
原因是在 $\mathbb{F}_3$ 中，第一行 $[1, 2]$ 乘以 $2$（模 3）得到 $[2, 4] \equiv [2, 1]$，两行线性相关。
同一个矩阵，在不同域上可逆性可能完全不同。在 $\mathbb{F}_3$ 上计算行列式，结果应在 $\{0, 1, 2\}$ 中。
五、有限域上的线性代数
5.1 有限域简介
有限域（Finite Field）：元素个数有限的域。元素个数 $q$ 必为素数的幂次 $q = p^k$。最常见的例子：
- $\mathbb{F}_p = \{0, 1, 2, \ldots, p-1\}$（模素数 $p$ 的剩余类域）
- 如 $\mathbb{F}_2 = \{0, 1\}$，$\mathbb{F}_3 = \{0, 1, 2\}$
有限域的一个独特优势是：在实数/复数上无法讨论的计数问题，在有限域上变得可以讨论——因为元素个数有限。
5.2 $\mathbb{F}_2$ 上二阶可逆矩阵
问题：$\mathbb{F}_2$ 上的 $2 \times 2$ 可逆矩阵有多少个？全部写出来。
分析：方阵可逆 $\iff$ 两行线性无关。
解法：
- 第一行：不能取零向量 $[0, 0]$，有 $2^2 - 1 = 3$ 种选择（$[1,0], [0,1], [1,1]$）
- 设第一行取 $[1, 0]$，第二行：不能是零向量，也不能是第一行的线性组合
- 在 $\mathbb{F}_2$ 上，第一行的线性组合只有 $0 \cdot [1,0] = [0,0]$ 和 $1 \cdot [1,0] = [1,0]$
- 排除后剩下：$[0,1]$ 和 $[1,1]$
- 同理分析其他第一行取值
答案：共 6 个可逆矩阵：
\[\begin{bmatrix}1&0\\0&1\end{bmatrix}, \begin{bmatrix}1&0\\1&1\end{bmatrix}, \begin{bmatrix}0&1\\1&0\end{bmatrix}, \begin{bmatrix}0&1\\1&1\end{bmatrix}, \begin{bmatrix}1&1\\0&1\end{bmatrix}, \begin{bmatrix}1&1\\1&0\end{bmatrix}\]在 $\mathbb{F}_2$ 中这 6 个矩阵的行列式都等于 $1$（因为 $\mathbb{F}_2$ 中 $-1 = 1$）。这 6 个矩阵在乘法下构成一个群，且该群同构于三阶对称群 $S_3$。
5.3 $\mathbb{F}_2$ 上三阶可逆矩阵的个数
逐行确定法：
- 第一行：$2^3 - 1 = 7$ 种（非零三元向量）
- 第二行：不能是第一行的线性组合 → 排除 $2$ 种，剩余 $2^3 - 2 = 6$ 种
- 第三行：不能是前两行的线性组合 → 前两行线性无关，其线性组合有 $2^2 = 4$ 种，排除后剩余 $2^3 - 4 = 4$ 种
总数 = $7 \times 6 \times 4 = 168$
5.4 一般公式：$q$ 元有限域上 $m \times n$ 满秩矩阵的个数
设 $\mathbb{F}$ 是元素个数为 $q$ 的有限域，考虑 $m \times n$ 矩阵（$1 \leq m \leq n$），要求秩 $= m$（满行秩）。
逐行确定法推广：
- 第 1 行：$q^n - 1$ 种（非零）
- 第 2 行：排除第一行的线性组合（$q$ 种） → $q^n - q$
- 第 3 行：排除前两行的线性组合（$q^2$ 种） → $q^n - q^2$
- …
- 第 $k$ 行：排除前 $k-1$ 行的线性组合（前 $k-1$ 行线性无关，线性组合共 $q^{k-1}$ 种） → $q^n - q^{k-1}$
总数：
\[\prod_{k=1}^{m} (q^n - q^{k-1}) = \prod_{k=0}^{m-1} (q^n - q^k)\]5.5 $n$ 阶可逆矩阵（$\text{GL}_n(\mathbb{F}_q)$）的个数
当 $m = n$ 时（方阵可逆），个数为：
\[|\text{GL}_n(\mathbb{F}_q)| = \prod_{k=0}^{n-1} (q^n - q^k)\]六、子空间计数与高斯二项式系数
6.1 问题的提出
在 $\mathbb{F}_q$ 上的 $n$ 维向量空间中，有多少个 $m$ 维子空间？（$0 \leq m \leq n$）
这个问题类似于：$n$ 元集合有多少个 $m$ 元子集？答案是组合数 $\binom{n}{m}$。
6.2 高斯二项式系数
记号为 $\binom{n}{m}_q$（或称为 Q-二项式系数 / Gaussian Binomial Coefficient），其公式为：
\[\binom{n}{m}_q = \frac{(q^n - 1)(q^n - q) \cdots (q^n - q^{m-1})}{(q^m - 1)(q^m - q) \cdots (q^m - q^{m-1})}\]推导思想：
- 每个 $m$ 维子空间对应一个 $m \times n$ 满秩矩阵（以子空间的一组基为行）
- 但不同矩阵可能生成同一个子空间（相差一个 $m$ 阶可逆矩阵的乘法）
- 分母正是 $\text{GL}_m(\mathbb{F}_q)$ 的阶，用于消去重复计数
6.3 与组合数的类比
对照组合数 $\binom{n}{m} = \frac{n!}{m!(n-m)!} = \frac{n(n-1)\cdots(n-m+1)}{m(m-1)\cdots 1}$：
把 $q^k - 1$ 对应成 $k$，形式上完全一致。
一个更深刻的关系是——当 $q \to 1^+$ 时，$\binom{n}{m}_q$ 的极限恰好是普通的组合数 $\binom{n}{m}$。这说明有限域上的组合问题与有限集合上的组合问题有内在联系。
七、补充说明
本节课前半部分（极大无关组、域上矩阵、秩、行列式）是线性代数知识在一般域上的自然推广，需要重点关注有限域上计算的不同之处。后半部分（有限域上矩阵/子空间计数）是代数与组合的结合点，需要掌握计数公式的推导思路。