Feit–Fine 公式: 可交换矩阵的对数-526互联

固定有限域 $\mathbb F_q$, 记 $a_n$ 为 $AB=BA$ 在 $M_{n\times n}(\mathbb F_q)$ 中解的数量, 有:

定理 (W. Feit, N. J. Fine, 1958)

\[1+\sum_{n\geq 1} \frac{a_n}{|\mathrm{GL}_n(\mathbb F_q)|} z^n = \prod_{i=1}^\infty \prod_{j=0}^\infty \frac 1{(1-q^{1-j}z^i)}. \]
注意 $|\mathrm{GL}_n(\mathbb F_q)| = (q^n-1)(q^n-q)\cdots(q^n-q^{n-1})$.

(没错, 这个 Feit 就是 Feit–Thompson 定理的那个 Feit.)

一些引理

为了证明这个公式, 首先我们需要找一个线性映射的观察角度.

引理 1. 对于任意 $A\in M_{n\times n}(F)$, 给出 $F^n$ 的一个直和分解 $F^n = \ker(A^n) \oplus \operatorname{im}(A^n)$

证明: 线性代数习题难度, 略. $\square$

我们记 $K_A = \ker(A^n), I_A = \operatorname{im}(A^n)$.

引理 2. $AB=BA$ 当且仅当下述两条性质皆成立:

$K_A, I_A$ 是 $B$-不变子空间.

$A|_{K_A}$ 和 $B|_{K_A}$ 交换, $A|_{I_A}$ 和 $B|_{I_A}$ 交换.

证明: 注意到 $K_A,I_A$ 总是 $A$-不变子空间, $\impliedby$: 显然. $\implies$: 容易分别对两个子空间验证是 $B$-不变的, 然后第二条性质显然. $\square$

结构分析

接下来就是计数的策略了: 首先枚举一个直和分解 $\mathbb F_q^n = K \oplus I$, 然后枚举 $A|_K, A|_I, B|_K, B|_I$. 我们的要求有:

$A|_K$ 是幂零的.
$A|_I$ 是可逆的.
$B|_K$ 和 $A|_K$ 交换.
$B|_I$ 和 $A|_I$ 交换.

那么我们先看看如果 $\dim K = k, \dim I = n-k$ 之后数数会发生什么.

$I$ 侧

先看 $I$ 这部分, 这部分 $A$ 是可逆的, 记 $X = \operatorname{End}(I,I), G = \mathrm{GL}(I)$, $G$ 共轭作用在 $X$ 上, Burnside 引理告诉我们

\[|X/G| = \frac 1{|G|} \sum_g |X^g|, \]

注意 $|X^g|$ 就给出了和 $A$ 交换的矩阵的数量, 所以

\[\#\{AB=BA \mid \det A\neq 0\} = |G| \cdot |X/G|, \]

这里 $|G| = |\mathrm{GL}(I)|$, 很好数, $|X/G|$ 是本质不同的线性变换的数量, 根据有理标准型 / Frobenius 标准型 / PID 上有限生成模结构定理, 我们知道 $|X/G|$ 就是如下多项式序列 $\{f_i\}$ 的数列:

$f_1 \mid f_2 \mid \cdots \mid f_k$, 且 $\sum \deg f_i = \dim I$.

那么这个怎么数呢? 我们待会再说, 我们再转过来看看 $K$ 这部分.

$K$ 侧

因为要求 $AB=BA$, 对于每个 $i$, $\ker(A^i)$ 都应当是 $B$-不变的. 我们先考虑一个固定的 $A$, 我们知道 $B$ 的结构本质上只取决于 $(\dim \ker A, \dim \ker A^2, \dots,)$ 这个序列.

我们知道, 这给出一个整数拆分 $\lambda \vdash \dim K$, 其中 $\lambda_i = \dim \ker(A^i) - \dim \ker(A^{i-1})$. 有一组基 $v_{ij} : j\leq \lambda_i$ 满足 $i\leq \ell$ 的部分构成 $\ker A^\ell$ 的基, 并且 $A v_{ij} = v_{(i-1)j}$.

注意合法的 $B$ 构成一个线性空间. 现在我们考虑 $B$ 的自由度. $ABv_{ij} = BAv_{ij} = Bv_{i(j-1)}$, 这实际上就告诉我们, 某些 "极大" 的 $v_{ij}$ 决定了 $B$, 我们稍后会看到, $B$ 的自由度具体如何计算.

计算!

首先我们解决一个基本问题: 我们枚举了直和 $K\oplus I$, 这种直和分解的方案数

\[\#\{ \mathbb F_q^n = K\oplus I : \dim K = k \} \]

是多少呢?

这个问题的答案其实不是很复杂, 做法就是数两遍: $n$ 个线性无关的向量 $v_1,\dots,v_n$, 这个序列的方案数是

\[|\mathrm{GL}_n(\mathbb F_q)| = (q^n-1)(q^n-q)\cdots(q^n-q^{n-1}), \]

我们令 $K$ 为 $v_1,\dots,v_k$ 张成的空间, $I$ 为剩下的向量张成的空间. 这样一来每个 $(K, I)$ 对被数了多少次呢? 就是 $|\mathrm{GL}_k(\mathbb F_q)| \cdot |\mathrm{GL}_{n-k}(\mathbb F_q)|$ 次, 接下来我们简记作 $G_n=|\mathrm{GL}_n(\mathbb F_q)|$,

我们就有

\[\frac{\#(A,B)}{G_n} = \sum_{k=0}^n \frac{\#(A_K,B_K)_k}{G_k} \frac{\#(A_I,B_I)_{n-k}}{G_{n-k}}, \]

我们只需要分别求解如下问题:

$\#(A_K,B_K)_n$: $A,B$ 是 $n$ 阶矩阵, $AB=BA$, 其中 $A$ 幂零的解.
$\#(A_I,B_I)_n$: $A,B$ 是 $n$ 阶矩阵, $AB=BA$, 其中 $A$ 可逆的解.

$K$ 侧

根据前面的分析, 我们先固定整数拆分 $\lambda (\lambda_1\geq \lambda_2\geq \cdots \geq \lambda_r)$, 然后 $\dim(\ker A^i)-\dim(\ker A^{i-1}) = \lambda_i$ 的矩阵 $A$ 就好了. 在杨表里, 这个杨表上的一个格子就代表一个向量, 我们还是有 $G_n$ 种选取向量的方式. 那么问题来了, 这种情况下一个 $A$ 被数了几遍呢?

注意到 $Av_{ij} = v_{(i-1)j}$, 这意味着只有表面的一层格子是有自由度的, 下面的格子都被这个关系确定了. 举个例子, 看下面这个杨表

...
.

表示 $\dim \ker A = 3$, $\dim \ker A^2 = 4$, 对应着 $\lambda = (3, 1)$.

我们选取满足要求的基的方式有多少种呢? 首先让我们来选

$..
*

这个 * 代表的向量, 一旦它被我们选择了, $ 也随之被确定了, 不需要我们再选. * 的选法是从 $\ker(A^2) \smallsetminus \ker(A)$ 里选一个, 有 $q^4-q^3$ 种选择.

接下来我们考虑剩下的两个向量: 1 和 2.

$12
*

1 能如何选择呢? 注意到 $ 已经占了一维了, 所以 1 只有 $q^3-q$ 种选项, 进一步, 2 只有 $q^3-q^2$ 种选项.

我们知道选取向量的方法把 $q$ 都提取出来之后应该形如
$q^? \prod(1-q^{-?})$ 的形式, 我们先确定后面 $1-q^{-?}$ 都长啥样.

容易看出, 我们应该考虑的是 $\lambda$ 的转置得到的整数拆分 $\mu$, 现在 $d$ 刚好就是 $\ker A$.

我们记 $\mu = 1^{x_1}2^{x_2}\cdots n^{x_n}$, 其中 $x_i$ 表示 $i$ 在 $\mu$ 这个整数拆分里出现的次数 (所以 $\sum x_i = d$). 那么对于 $i$ 来说, 它能选择的余维数就是它右手边格子的数量, 也就是说这 $x_i$ 个 $i$ 对应的是 $x_i, x_i-1,\dots,1$, 我们得到这部分是

\[\prod_{i=1}^n (1-q^{-1})(1-q^{-2})\cdots (1-q^{-x_i}). \]

而 $q^?$ 的部分应该是 $? = \sum_i x_i \cdot \dim(\ker A^i)$, 进而有

\[\begin{align*} \sum_i x_i \cdot \dim(\ker A^i) &= \sum_i x_i \cdot \sum_j x_j \min(j, i)\\ &= \sum_i x_i \cdot \sum_j x_j \sum_{k\geq 1} [k\leq i] [k\leq j]\\ &= \sum_{k\geq 1} \left(\sum_{i\geq k} x_i\right)^2\\ &= \sum_{k\geq 1}\lambda_k^2. \end{align*} \]

我们经过变换, 又回到了 $\lambda$. 总而言之, $\lambda$ 对应的幂零矩阵 $A$ 的数量就是

\[G_n \cdot \frac{q^{-\sum_i \lambda_i^2}}{\prod_i(1-q^{-1})\cdots(1-q^{-x_i})}. \]

别忘了, 我们还希望确定 $B$ 的自由度, 我们发现能选的 $Bv_{ij}$ 实际上和我们之前在杨表上选的位置是一样的, 我们任意地对固定 $j$ 的极大的 $i$, 选取 $Bv_{ij}\in \ker(A^i)$, 然后用 $Bv_{(i-1)j} = ABv_{ij}$ 自上而下定义出整个 $B$. 这样的 $B$ 对每个 $v_{ij}$ 都满足 $ABv_{ij}=BAv_{ij}$, 自然就满足 $AB=BA$. 这里对 $B$ 的限制体现在 $i=1$ 的时候满足 $ABv_{1j}=0$, 说明 $Bv_{1j} \in \ker (A)$, 进而 $Bv_{ij} \in \ker(A^i)$. 因此, $B$ 总共的自由度和前面的推导类似, 也是 $\sum \lambda_i^2$.

这样一来, 对于给定的 $\lambda$,

\[\#(A_K,B_K)_{\lambda} = G_n \cdot \frac{1}{\prod_i(1-q^{-1})\cdots(1-q^{-x_i})}, \]

我们就有

\[\frac{\#(A_K,B_K)_n}{G_n} = \sum_{\lambda\vdash n}\frac{1}{\prod_i(1-q^{-1})\cdots(1-q^{-x_i})}, \]

丢进生成函数里, 就有

\[\begin{align*} \sum_n \frac{\#(A_K,B_K)_n}{G_n} z^n &= \prod_{i\geq 1} \left( \sum_{x\geq 0} \frac{z^{xi}}{(1-q^{-1})\cdots (1-q^{-x})} \right) \\ &= \prod_{i\geq 1} \prod_{j\geq 0} \frac 1{1-q^{-j} z^i}. \end{align*} \]

$I$ 侧

前面我们已经推导得到, 我们的目标是数 $f_1 \mid f_2 \mid \cdots \mid f_k$ 这种塔的数量, 做一下商, 就得到 $g_1, g_2, \dots, g_k$, 满足 $g_i = f_i / f_{i-1}$, 我们要求 $\sum (k-i+1)\deg g_i = n$, 翻转一下, 就是

\[\frac{\#(A_I,B_I)_n}{G_n} = \#\left\{ g_1,\dots,g_k : \sum i\deg g_i = n \right\}, \]

显然次数为 $i$ 的多项式有 $q^i$ 个, 所以

\[\begin{align*} \frac{\#(A_I,B_I)_n}{G_n} &= \prod_{i\geq 1} (1 + qz^i + q^2 z^{2i} + \cdots)\\ &= \prod_{i\geq 1} \frac 1{1-qz^i}. \end{align*} \]

结论

最后, 我们就得到了

\[\begin{align*} \sum_n \frac{\#(A,B)}{G_n} z^n &= \left(\sum_n \frac{\#(A_K,B_K)}{G_n} z^n\right)\left(\sum_n \frac{\#(A_I,B_I)}{G_n} z^n\right)\\ &= \left(\prod_{i\geq 1} \prod_{j\geq 0} \frac 1{1-q^{-j} z^i}\right)\left(\prod_{i\geq 1} \frac 1{1-qz^i}\right)\\ &= \prod_{i=1}^\infty \prod_{j=0}^\infty \frac 1{(1-q^{1-j}z^i)}. \square \end{align*} \]

参考文献

W. Feit and N. J. Fine, Pairs over commuting matrices over a finite field, Duke Math. J., 27 (1960) 91-94.

后记

这个结果还挺漂亮的, 通过对线性映射的一些基本的分析, 再加上对于 $q$-阶乘相关的一些熟练的推导就能得到, 而且...

这个问题还有扩展:

定理 (Huang, 2021) 对于 $m$ 次本原单位根 $\zeta$, 记 $AB=\zeta BA$ 的解数为 $K_{\zeta, n}$, 有

\[\sum_n \frac{K_{\zeta,n}}{G_n} z^n = \prod_{i\geq 1} \left(\frac{1-z^{mi}}{(1-z^i)(1-qz^{mi})} \prod_{j\geq 0} \frac 1{(1-q^{-j}z^{i})} \right). \]

以及... 这是啥?

这又是啥?:

定理 (Huang, One, Saad, 2023) 对于特征大于 $2$ 的 $\mathbb F_q$ 上的 $n\times n$ 矩阵, 满足 $A,B$ 交换, 且满足 "椭圆曲线" 方程

\[B^2=A(A-I)(A-aI), \quad (a\neq 0,1) \]
的这样的 $A, B$, 设解数为 $N_2(a;q)$, 我们有

\[N_2(a;q) = P(n,0)_q - \sum_{k=1}^n \phi_{q^k}(-1)\cdot P(n,k)_q\cdot {_2F_1^{\mathrm{ff}}}(a)_{q^k}, \]
其中

\[P(n,k)_q := (-1)^k q^{n(n-k)+k(k+1)/2} \sum_{s=0}^{\lfloor(n-k)/2\rfloor} q^{2s(s-n+k)} \binom{n}{s,n-k-2s,k+s}_q. \]