$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}})$ 不是循环群）。

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