$GL_n(\mathbb{Z}_m)$ 的阶数

由线性无关性，我们不难知道 \(|GL_n(\mathbb{Z}_p)| = \prod_{i=0} ^{n-1} (p^n-p^i)\)，但是 \(|GL_n(\mathbb{Z}_m)|\) 却是一个相对复杂的问题，它本质上是在考虑有限 Abel 群的自同构群的阶数问题。它又跟递推数列模 \(m\) 的周期密切相关。

2007 年 CHRISTOPHER J. HILLAR AND DARREN L. RHEA 发表一篇论文《AUTOMORPHISMS OF FINITE Abelian GROUPS》 完美的解决了这个问题。

有限生成 Abel 群结构定理

设 \(G\) 是一个有限 Abel 群，那么 \(G\) 同构于一些 \[ H_p = \mathbb{Z}_{p^{e_1}} \times \cdots \mathbb{Z}_{p^{e_n}} \] 的乘积。其中 \(p\) 是素数（\(p\) 一般默认为素数），\(1 \leq e_1 \leq \cdots \leq e_n\) 是正整数。

证明可见任意一般抽象代数（或近世代数）书。

乘积的自同构

若 \(H\) 和 \(K\) 是有限群，且它们的阶数互素。那么我们就有同构： \[ Aut(H) \times Aut(K) \simeq Aut(H \times K) \] Proof ：我们构造很自然的映射： \[ \begin{aligned} \phi: Aut(H) \times Aut(K) \to Aut(H \times K) \\ \phi(\alpha,\beta)(h,k) = (\alpha(h),\beta(k)) \end{aligned} \] 容易验证 \(\phi\) 是合理的映射，并且是单射，然后我们同构构造它的逆映射来说明它是满射。

我们记 \(n = |H|,m = |K|\)，\(\pi_H,\pi_K\) 是标准投影映射： \(\pi_H: H \times K \to H\)，\(\pi_K: H \times K \to K\) 。对于给定的 \(\omega \in Aut(H \times K)\)，我们定义同态 \(\gamma: K \to H\)， \(\gamma(k) = \pi_H(\omega(1_H,k))\)，注意到 \(\lbrace k^n: k \in K \rbrace \subseteq \ker \gamma\)。又 \(m,n\)是互素的，所以 \(\gamma\) 是平凡的映射。同理，我们定义 \(\delta: H \to K\)，\(\delta(h) = \pi_K(\omega(h,1_K))\) 也是平凡映射。最后我们定义\(H\)和\(K\)的自同态： \[ \begin{aligned} \omega_H(h) = \pi_H(w(h,1_K)) ,\quad \omega(k) = \pi_K(w(1_H,k)) \\ \omega(h,k) = \omega(h,1_K) \omega(1_H,k) = (\omega_H(h), \omega_K(k)) = \phi(w_H,w_k)(h,k) \end{aligned} \] 由于 \(\omega_H,\omega_K\) 都是单射，并且 \(H,K\) 是有限群，所以它们是自同构，证毕。

所以我们考虑 \(Aut(G)\)，只需考虑 \(Aut(H_p)\) 即可

\(H_p\) 的自同态

我们定义，环 \(E_p = End(H_p)\)（加法就是映射的加法，乘法就是映射的复合）

由于循环群 \(C_{p^{e_i}}\) 对应的是 模 \(p^{e_i}\) 的加法群。所以 \(H_p\) 中的元素可以表示成列向量 \((\overline{h_1},\cdots \overline{h_n})^T\)，其中 \(\overline{h_i} \in \mathbb{Z}_{p^{e_i}}, \; h_i \in \mathbb{Z}\)

我们定义（精华所在) \[ R_p \doteq \lbrace (a_{ij} \in \mathbb{Z}^{n \times n}: p^{e_i - e_j}|a_{ij} \quad \forall 1 \leq j < i \leq n) \]

注意到 \(\forall A \in R_p\)，\(A = P A' P^{-1}\)，其中 \(P = diag(p^{e_1},\cdots,p^{e_n}), A' \in \mathbb{Z}^{n \times n}\)。从而 \(R_p\) 根据加法和矩阵乘法，构成了一个环。

我们定义 \(\pi_i: \mathbb{Z} \to \mathbb{Z}_{p^{e_i}}\) 为标准商映射。\(\pi: \mathbb{Z}^n \to H_p\) 为： \[ \pi(h_1,\cdots h_n)^T = (\pi_1(h_1),\cdots,\pi_n(h_n))^T = (\overline{h_1},\cdots \overline{h_n})^T \] 我们不难验证 \(\psi: R_p \to E_p\) \[ \psi(A)(\overline{h_1},\cdots \overline{h_n})^T = \pi(A(h_1,\cdots,h_n)^T) \] 是环满同态（需要验证映射合理性，环同态，满射）且 \(\ker \psi = \lbrace A = (a_{ij}) \in R_p: p^{e_i} | a_{ij}\)

\(H_p\) 的自同构 \(Aut(H_p)\)

\(M = \psi(A) \in Aut(H_p)\) 当且仅当 \(A \mod p \in GL_n(\mathbb{F}_p)\)，即 \(\det(A) \in U(H_p)\) 是 \(H_p\) 中可逆元。

Proof：利用 \(A\) 的逆矩阵推出 \(M\) 是自同构，利用 \(M\) 的逆映射给出 \(A\) 的逆矩阵。

\(| Aut(H_p)|\)

定义：\(d_k = \max \lbrace l: e_l = e_k \rbrace, c_k = \min \lbrace l: e_l = e_k \rbrace\)，显然 \(c_k \leq k \leq d_k\)。我们需要计算

• 所有 \(GL_n(\mathbb{F}_p)\) 中可以拓展成 \(A \in R_p\) 的元素
• 每个元素拓展方式

我们找到所有 \(M \in GL_n(\mathbb{F}_p)\) 形如： \[ M = \begin{pmatrix} m_{11} & & & \star \\ \vdots \\ m_{d_1 1} \\ & m_{d_2 2} \\ & & \ddots \\ 0 & & & m_{d_n n} \end{pmatrix} \] > 注意到 \(\sum_{j=1} ^n \sum_{i=1} ^{d_j} m_{ij} = \sum_{e_i \leq e_j} m_{ij} = \sum_{i=1} ^n \sum_{j = c_i}^n m_{ij}\)

因为我们只考虑线性无关的，所以这种 \(M\) 的数量是 \[ \prod_{k=1} ^n (p^{d_k} - p^{k-1}) \] 将 \(m_{ij}\) 从 \(\overline{m_{ij}} \in \mathbb{Z}_p\) 到 \(\overline{a_{ij}} \in p^{e_i-e_j} \mathbb{Z}/p^{e_i} \mathbb{Z}\) 使得 \(a_{ij} \equiv m_{ij} \mod p\) 的方案数分两种情况

• \(e_i > e_j\) 时， \(p^{e_j}\) 种
• \(e_i \leq e_j\) 时， \(p^{e_i-1}\) 种

从而 \[ |Aut(H_p)| = \prod_{k=1} ^n (p^{d_k} - p^{k-1}) \prod_{j=1} ^n (p^{e_j})^{n-d_j} \prod_{i=1} ^n (p^{e_i -1})^{n-c_i+1} \]

\(|GL_n(\mathbb{Z}_m)|\)

由 \(|Aut(H_p)|\) 的公式的特殊形式，我们知道 \(|GL_n(Z_{p^s})| = p^{n^2 (s-1)} \prod_{k=1} ^n (p^n - p^{k-1})\)。

将 \(m\) 质因数分解 \(m = p_1^{s_1} \cdots p_r ^{s_r}, \quad p_1 < \cdots < p_r\) \[ |GL_n(\mathbb{Z}_m)| = \prod_{i=1} ^r |GL_n(Z_{p_i^{s_i}})| \]

\(\mathbb{Z}_m\) 上\(n\) 阶给定可逆矩阵 \(A\) 的周期

设 \(f(\lambda) = | \lambda I -A|\)，\(A\) 可逆等价于 \(\gcd(f(\lambda),\lambda) = 1\)，由于 \(A^k\) 都可以由 \(I,A,\cdots A^{n-1}\)，线性表出，但是由于是在 \(\mod m\) 的意义下，所以根据容斥原理，对任意 \(k \geq m^n\) 时，必然存在 \(l < k\)，使得 \(A^k = A^l\)。即 \(A\) 的周期上限是 \(m^n\)，并且周期是 \(|GL_n(\mathbb{Z}_m)|\) 的一个真因子（\(n>1\)）。

显然若 \(A\) 可对角化，那么 \(A\) 的周期必然是 \(\phi(m)\) 的一个因子！但是注意这里 \(A\) 对称并不能推出 \(A\) 可对角化。

常系数递推数列模意义下的周期

给定初值，\(x_1,\cdots x_s\), 和递推关系：\(x_{n+s} = a_1 x_{n+s-1} + \cdots + a_s x_n, a_s \neq 0\) 的数列 \({x_n}\)可以表示成： $$ \[\begin{pmatrix} x_n \\ x_{n-1} \\ \vdots \\ x_{n-s+1} \end{pmatrix}\] = \[\begin{pmatrix} a_1 & a_2 &\cdots & a_s \\ 1 & 0 \\ \vdots & & & 0\\ 0 &\cdots & 1& 0 \end{pmatrix}\] \[\begin{pmatrix} x_{n-1} \\ x_{n-2} \\ \vdots \\ x_{n-s} \end{pmatrix}\]

$$

可以通过矩阵幂在 \(O(s^3 \log n)\) 复杂度求出。

当 \(s\) 相对较大时，根据特征多项式将系数矩阵 \(A^n\) 写成 \(I,A,\cdots A^{s-1}\) 的线性组合，然后只考虑仅乘以第一行，就可以在 \(O(s^2\log n)\) 复杂度求出

我们考虑 数列 \(\lbrace x_n \mod m \rbrace\) ，由容斥原理知，数列 \(\lbrace x_n \mod m \rbrace\) 是周期数列，记它的最小正周期为 \(f(m)\) ，则 \[ f(m) = lcm(f(p_1^{s_1}),\cdots f(p_r^{s_r})) \] 只要 \(p_i \not| \; a_s\)，则 \(f(p_i ^{s_i})\) 是 \(|GL_n(\mathbb{Z}_{p_i^{s_i}})|\) 的一个真因子（当 \(n>1\) 时，\(GL_n(\mathbb{Z}_{p_i^{s_i}})\) 不是循环群）。

精确的周期要具体问题具体分析。