由线性无关性,我们不难知道 $|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$ 同构于一些

的乘积。其中$p$ 是素数($p$ 一般默认为素数),$1 \leq e_1 \leq \cdots \leq e_n$ 是正整数。

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

乘积的自同构

若$H$ 和 $K$ 是有限群,且它们的阶数互素。那么我们就有同构:

Proof :我们构造很自然的映射:

容易验证 $\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$的自同态:

由于$\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}$

我们定义(精华所在)

注意到 $\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$ 为:

我们不难验证 $\psi: R_p \to E_p$

是环满同态(需要验证映射合理性,环同态,满射)且 $\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)$ 形如:

注意到 $\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$的数量是

将$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}$ 种

从而

$|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$

$\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}$可以表示成:

可以通过矩阵幂在 $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)$ ,则

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

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