GL(n,Fp)群阶的研究

前言·

上次在 模n的Fibonacci的快速计算 里算出了二维的Fibonacci矩阵除了$p=5$的情况，阶是$p^2-1$；三维的"3-Fibonacci"矩阵在$p=e$（这是题目给的参数，不是自然常数）下的阶是$e^2-1$，但$p$是其他值是不一定是$p^2-1$。

赛后尝试了一下，用随机矩阵统计了一下，发现了一个神奇的规律：

n	阶（自乘多少次变$I$）
2	$p(p-1)(p+1)$
3	$p(p-1)(p+1)(p^2+p+1)$
4	$p(p-1)(p+1)(p^2+p+1)(p^2+1)$
5	$p(p-1)(p+1)(p^2+p+1)(p^2+1)(p^4+p^3+p^2+p+1)$
6	$p(p-1)(p+1)(p^2+p+1)(p^2+1)(p^4+p^3+p^2+p+1)(p^2-p+1)$
…	$...\ ...$

可以看出$n_{i+1}$项其实就是在$n_i$项上乘上一个多项式，这些多项式可以组成一个数列，如果把这个数列记为$P$的话，就是：

$P_i$	值
$P_0$	$p$ ??
$P_1$	$(p-1)$
$P_2$	$(p+1)$
$P_3$	$(p^2+p+1)$
$P_4$	$(p^2+1)$
$P_5$	$(p^4+p^3+p^2+p+1)$
$P_6$	$(p^2-p+1)$
…	$...\ ...$

总结一下性质，以及这个数列是怎么生成的：

• $P_0=p$ 且 $P_1=p-1$ ;
• 如果$q$是素数的话，有$P_q=\sum_{i=0}^{q-1}p^i$ ;
• $P_{a^2}=\frac{p^{a*b}-1}{P_1*P_a}$ ;
• $P_{a*b}=\frac{p^{a*b}-1}{P_1*P_a*P_b}$ , $a \ne b$

所以如果$M$是一个$n*n$的非奇异矩阵（即行列式不为0）、$p$是奇素数的话，就（可能）会有：

$$M_{n*n}^{\prod_{i=0}^{n}P_i} = I_{n*n} \ (mod\ p)$$

这个是当时的猜想1，附上一段验证的代码（其实猜的大部分是对的，但还是有些代码里没考虑到的小细节错了）：

# Sage
var('x')
def getOrderX(n):
  P = [x, x-1]
  for i in range(2, n+1):
    if is_prime(i):
      P.append(sum([x^j for j in range(i)]))
    else:
      for j in range(2, i):  # brute
        if i%j==0:
          if j^2==i:
            P.append((x^i-1)/(P[1]*P[j]))
          else:
            P.append((x^i-1)/(P[1]*P[j]*P[i//j]))
          break
  return P

def getOrder(p, n):
  return int(product(getOrderX(n)).expand()(x=p))

def randMp(p, n):
  while True:
    mt = matrix(IntegerModRing(p), [[randrange(p) for _ in range(n)] for _ in range(n)])
    if mt.det()!=0:
      return mt

if __name__ == '__main__':
  fail = 0
  for i in range(10):
    n = randint(2, 100)
    while True:
      p = random_prime(100000)
      if p > 1: break
    I = identity_matrix(IntegerModRing(p), n)
    order = getOrder(p, n)
    yes = True
    for _ in range(10):
      m = randMp(p, n)
      if pow(m, order)==I:
        continue
      else:
        print('%s\t%s\tfail' % (p, n))
        print(pow(m, order))
        fail += 1
        yes = False
        break
    if yes:
      print('%s\t%s\tyes' % (p, n))
  print('------')
  print('done!')
  print('fail: %s' % fail)  # 0

捣鼓一下，其实还有另一个猜想：当时统计了一下，发现其实$\prod_{i=0}^{n}P_i$是一个很松的界，实际测试（枚举小$n$和小$p$下的全部非奇异矩阵）的话是没有试过能到达这个阶的，而实际能达到的最大阶是：

$$\prod_{d|n}\phi_d(p) = p^n-1$$

记这个作猜想2吧（名字好像不重要：）

正文·

上面说的其实是一个星期前的内容了，根据这几天搜集到的资料，发现其实有更多可以完善的地方，比如：

1. 上面说的“模p非奇异矩阵的群”其实就是在$\mathbb{F}_p$上的一般线性群（general linear group over $\mathbb{F}_p$），通常记作$GL(n, \mathbb{F}_p)$，其中$n$是方阵的维度，$\mathbb{F}_p$是指矩阵元素在域$\mathbb{F}_p$上（当然也可以在其他域上，不过就是另外的内容了）；
2. 上面说的数列$P$除了第0项其实是叫分圆多项式（cyclotomic polynomial），通常把它的第$i$项写作$\phi_i(p)$，但那四点性质还是适用的；

网上拿“GL(n,p)”作关键字搜了一堆后，最终在这里找到“简单”的证明，还有一篇论文[1]，然后有以下结论：

1. 猜想2是对的，而且论坛的回复里一句话就证了：

   

   大概意思是，计算$A$的特征值时，$|A-\lambda I|$计算出来的多项式最多有$n$项，除去全零项的话即最多$p^n-1$种（然后后面怎么扯上$GL(n, \mathbb{F}_p)$的还没搞懂，）

2. 根据[1]的Theorem1，

   

   在$\mathbb{F}_p$上，其实就是$m=1$，即有：

   $$q_n=LCM(p-1, p^2-1, ..., p^n-1)$$

   实际上可以把分圆多项式代进去化简，即：

   $$q_n = LCM(\prod_{d|1}\phi_d(p), \prod_{d|2}\phi_d(p), ...,\prod_{d|n}\phi_d(p) ) = \prod_{i=1}^{n}\phi_i(p)$$

   在猜想1中，这一半是没问题的，有一个小细节问题是$p^r$，论文的要求是$p^r \ge n > p^{r-1}$，而我的$n$是在randint(2, 100)中选的，$p$是在random_prime(100000)中选的，即大概率是$p^1 \ge n > p^0$，也即$r$大概率会是$1$

   另外扩展一下，符合$GL(n, \mathbb{F}_p)$的元素个数，即元素在$\mathbb{F}_p$上的$n$维非奇异矩阵的个数是：

   $$\prod_{i=0}^{n-1}(p^n-p^i) = \prod_{i=0}^{n-1}p^i(p^{n-i}-1)$$

   即其实上面的$p^rq_n$包含了这个式子的所有因子

总结以上，最后的结论是：

设 $\phi_i$ 为分圆多项式的第$i$项、$GL(n, \mathbb{F}_p)$是域 $\mathbb{F}_p$上的一般线性群、$A \in GL_n(\mathbb{F}_p)$、$I$是$GL(n, \mathbb{F}_p)$单位元，则有:

$$A^{p^r\prod_{i=1}^{n}\phi_i(p)} \equiv I \ \ (in\ GL_n(\mathbb{Z}_p))$$

其中$p^r \ge n > p^{r-1}$；实际上，$GL(n, \mathbb{F}_p)$中元素的最大阶只能到：

$$\prod_{d|n}\phi_d(p) = p^n-1$$

总结·

在翻资料的时候“好像”瞄到了有求$GL(n, \mathbb{F}_p)$特征值然后分解的，看看能不能再水一篇（逃

当初线性代数没学好啊… …

当初抽象代数也没学好啊… …

参考·

[1] Ivan Niven, Fermat theorem for matrices, Duke Math. J. 15 (1948), 823-826