有关有限域上向量空间的组合计数

参考文献：Combinatorics of Vector Spaces over Finite Fields

\(\mathbb F_q\) 上的 \(n\) 维向量空间含有的向量计数

在这里讲一些线性代数的预备知识与符号定义

由 \(m \times n\) 个数排成的 \(m\) 行 \(n\) 列的数表称为 \(m\) 行 \(n\) 列的矩阵，简称 \(m \times n\) 矩阵

对于一个集合，在其上定义两种运算，若其满足一些公理，则称其是一个域，若一个域的元素个数有限，则称其为有限域

一个包含 \(q\) 个元素的有限域存在当且仅当 \(q\) 是某个素数的幂，并且此时在同构意义下恰好仅有一个大小为 \(q\) 的域，这个域用 \(\mathbb F_q\) 表示

一个向量空间由满足一些公理的一个阿贝尔群和一个域构成，有限域上的有限维向量空间包含有限个向量，接下来的计数围绕其展开

由于 \(\mathbb F_q\) 上的每个 \(n\) 维向量空间都彼此同构，因此不失一般性的，我们统计坐标空间 \(\mathbb F_q ^ n = \{(a_1, a_2, \cdots, a_n | a_i \in \mathbb F_q)\}\)

\(\mathbf{Theorem\ 1}\)：\(\mathbb F_q ^ n\) 中 \(n\) 维向量的数量显然是 \(q ^ n\) 啦 (>v<)

\(\mathbb F_q ^ n\) 上的向量组成的线性无关有序列表计数

呐，这也挺 easy 的嘛！依次决定每一个向量，第 \(i\) 个向量不能落在前 \(i - 1\) 个向量张成的空间中，乘法原理 DA☆ZE~

由定理 \(1\)，前 \(i - 1\) 个向量线性无关，故张成一个 \(i - 1\) 维的向量空间，大小为 \(q ^ {i - 1}\)，可选的向量数即为 \(q ^ n - q ^ {i - 1}\)

\(\mathbf{Definition\ 2.1}\)：记 \(((n)_k)_q\) 为 \(\mathbb F_q ^ n\) 上的向量组成线性无关的长为 \(k\) 的有序列表的方案数

\(\mathbf{Theorem\ 2.2}\)：\(\displaystyle ((n)_k)_q = \prod_{i = 0} ^ {k - 1} (q ^ n - q ^ i)\)

由此，我们引出一些 q-analog 的概念

\(\mathbf{Definition\ 2.3}\)：\([n]_q := 1 + q + \cdots + q ^ {n - 1}, [n]_q! := [n]_q[n - 1]q \cdots [1]_q\)，其中 \([0]_q! := 1\)，前者称为 q-整数，后者称为 q-阶乘

这些概念可能很突兀，但是马上它就会发挥很大的威力，顺带，易知有 \(\displaystyle [n]_q = \frac{1 - q ^ n}{1 - q}, [n]_q! = \frac{1}{(1 - q) ^ n}\prod_{i = 1} ^ n (1 - q ^ i)\)

现在我们可以重写 \(\displaystyle ((n)_k)_q = \prod_{i = 0} ^ {k - 1} (q ^ n - q ^ i) = \frac{(q - 1) ^ k q ^ {\tbinom{k}{2}}[n]_q!}{[n - k]_q!}\)，可以发现其形式类似下降幂

给定维数的 \(\mathbb F_q ^ n\) 子空间计数

考虑对 \(\mathbb F_q ^ n\) 中维数为 \(k\) 的子空间计数

先从 \(\mathbb F_q ^ n\) 中钦定一组基，其方案数为 \(((n)_k)_q\)，然后一个维数为 \(k\) 的子空间可以钦定出 \(((k)_k)_q\) 种不同的基

\(\mathbf{Definition\ 3.1}\)：\(\displaystyle \dbinom{n}{k}_q := \frac{((n)_k)_q}{((k)_k)_q} = \frac{[n]_q!}{[k]_q![n - k]_q!}\)，称为 q-组合数

\(\mathbf{Theorem\ 3.2}\): \(\mathbb F_q ^ n\) 中维数为 \(k\) 的子空间数量为 \(\displaystyle \dbinom{n}{k}_q\)

\(\mathbb F_q\) 上的元素构成的给定秩的 \(m \times n\) 矩阵计数

先抛出结论：\(m \times n\) 的矩阵秩为 \(k\) 的方案数为 \(\displaystyle \frac{((m)_k)_q((n)_k)_q}{((k)_k)_q}\)

我们先给出如下结论：\(\mathbb F_q ^ n\) 到 \(\mathbb F_q ^ m\) 的线性满射通过对偶映射一一对应到 \(\mathbb F_q ^ m\) 到 \(\mathbb F_q ^ n\) 的线性单射

由此，在每一行填入一个 \(\mathbb F_q ^ k\) 的元素，且整个矩阵秩为 \(k\) 的方案数等价于 \(\mathbb F_q ^ m\) 到 \(\mathbb F_q ^ k\) 的线性满射的数量，也即 \(\mathbb F_q ^ k\) 到 \(\mathbb F_q ^ m\) 的线性单射的数量

通过观察 \(\mathbb F_q ^ k\) 的一组基可以得知，\(\mathbb F_q ^ k\) 到 \(\mathbb F_q ^ m\) 的线性单射的数量为 \(((m)_k)_q\)，再乘上 \(\mathbb F_q ^ n\) 中 \(\mathbb F_q ^ k\) 的子空间个数，即可得数量为 \(\displaystyle ((m)_k)_q\dbinom{n}{k}_q = \frac{((m)_k)_q((n)_k)_q}{((k)_k)_q}\)

以下我们对其进行详细说明：

\(\mathbf{Lemma}\ 4.1\)：设 \(U, V\) 为域 \(\mathbb F\) 上的有限维向量空间，\(u_{1 \sim n}\) 是 \(U\) 的一个基，\(v_{1 \sim n}\) 为 \(V\) 中的任意向量，那么线性映射 \(T\) 使得 \(Tu_i = v_i\) 被唯一确定

\(\mathbf{Lemma}\ 4.2\)：设 \(U, V\) 为域 \(\mathbb F\) 上的有限维向量空间，\(u_{1 \sim n}\) 是 \(U\) 的一个基，\(T\) 是 \(U\) 到 \(V\) 的一个线性映射，那么 \(T\) 是一个单射当且仅当 \(Tu_i\) 线性无关

\(\mathbf{Lemma}\ 4.3\)：设 \(U, V\) 为域 \(\mathbb F\) 上的有限维向量空间，\(u_{1 \sim n}\) 是 \(U\) 的一个基，\(T\) 是 \(U\) 到 \(V\) 的一个线性映射，那么 \(T\) 是一个满射当且仅当 \(\operatorname{span}(Tu_i) = W\)

\(\mathbf{Lemma}\ 4.4\)：两个域 \(\mathbb F\) 上的有限维向量空间彼此同构当且仅当它们维数相同

\(\mathbf{Definition}\ 4.5\)：域 \(\mathbb F\) 上有限维向量空间 \(V\) 的对偶空间是由 \(V\) 到 \(\mathbb F\) 的线性函数构成的空间，记 \(V^* = \mathcal L(V, F)\)

顺带的，设域 \(\mathbb F\) 上有限维向量空间 \(V\) 的一组基 \(v_{1 \sim n}\)，则 \(\varphi_i(v_j) = [i = j]\) 是 \(V^*\) 的一组基，故 \(\operatorname{dim} V = \operatorname{dim} V^*\)，彼此同构

\(\mathbf{Definition}\ 4.6\)：设 \(T\) 是 \(U\) 到 \(V\) 的一个线性映射，则其的对偶映射为 \(T^* : V^* \to U^*; \varphi \mapsto \varphi \circ T\)

\(\mathbf{Definition}\ 4.7\)：设 \(U\) 是 \(V\) 的一个子空间，\(U\) 的零化子为 \(V^*\) 的一个子空间 \(U^\circ := \{\varphi | \forall u : \varphi(u) = 0\}\)

\(\mathbf{Lemma}\ 4.8\)：设 \(U\) 是 \(V\) 的一个子空间，\(\operatorname{dim} U + \operatorname{dim} U^\circ = \operatorname{dim} V\)

证明：令 \(u_{1 \sim m}\) 为 \(U\) 的一组基，将其拓展到 \(V\) 的一组基 \(u_{1 \sim n}\)，令其对应 \(V^*\) 的一组基 \(\varphi_{1 \sim n}\)，容易证明 \(\operatorname{span}(\varphi_{m + 1 \sim n}) = U^\circ\)

由此，我们还能得知 \(V^* = U^\circ\) 当且仅当 \(U = \{0\}\)，\(U^\circ = \{0\}\) 当且仅当 \(U = V\)

\(\mathbf{Lemma}\ 4.9\)：两个 \(U\) 到 \(V\) 的一个线性映射相等当且仅当它们的对偶映射相等

\(\mathbf{Lemma}\ 4.10\)：设 \(T\) 是 \(U\) 到 \(V\) 的一个线性映射，则 \(\operatorname{null} T^* = (\operatorname{range} T)^\circ\)

证明：\(\varphi \in \operatorname{null} T^* \iff T^*(\varphi) = 0 \iff \forall v \in V : \varphi(Tv) = 0 \iff \varphi \in (\operatorname{range} T)^\circ\)

\(\mathbf{Lemma}\ 4.11\)：设 \(T\) 是 \(U\) 到 \(V\) 的一个线性映射，则 \(T\) 是满射当且仅当 \(T^*\) 是单射

证明：\(\operatorname{range} T = W \iff (\operatorname{range} T)^\circ = \{0\} \iff \operatorname{null} T^* = \{0\}\)

\(\mathbf{Lemma}\ 4.12\)：\(\Phi : \mathcal L(V, W) \to \mathcal L(V^*, W^*) ; T \mapsto T^*\) 是一个一一映射

证明：由 \(\operatorname{dim}\mathcal L(V, W) = \operatorname{dim}\mathcal L(V^*, W^*)\)，只需证 \(\operatorname{null} \Phi = \{0\}\)

有 \(T \in \operatorname{null} \Phi \iff \Phi(T) = 0 \iff T^* = 0 \iff (\operatorname{span}(T))^\circ = W^* \iff \operatorname{span}(T) = \{0\} \iff T = 0\)

\(\mathbf{Theorem}\ 4.13\)：设 \(U, V\) 为域 \(\mathbb F\) 上的有限维向量空间，\(\operatorname{dim} U = n, \operatorname{dim} V = m\)，则 \(U\) 到 \(V\) 的线性单射个数为 \(((m)_n)_q\)，\(U\) 到 \(V\) 的线性满射个数为 \(((n)_m)_q\)

证明：设 \(U\) 的一组基 \(u_{1 \sim n}\)，设 \(T\) 是 \(U\) 到 \(V\) 的一个线性映射，则由引理 \(4.1, 4.2\)，统计 \(V\) 上线性无关 \(n\) 元组的个数作为 \(Tu_i\) 即可不重不漏，其数量为 \(((m)_n)_q\)

由引理 \(4.11\)，\(T\) 是满射当且仅当 \(T^*\) 是单射，数量即 \(V^*\) 到 \(U^*\) 的单射数量，由上可知 \(((n)_m)_q\)

\(\mathbf{Theorem}\ 4.13\)：秩为 \(k\) 的 \(m \times n\) 矩阵数量等于 \(\displaystyle \frac{((m)_k)_q((n)_k)_q}{((k)_k)_q} \qquad Q.E.D\)