nXn Matrices over GF(q) with a given characteristic polynomial.

[Edwin Clark]

On Fri, 21 Nov 2003, Yuval Dekel wrote:

> 
> Let a(n)  = number of nXn matrices over GF(q) having characteristic 
> polynomial x^n   = 0 and

 Note that matrix A has char poly x^n = 0 if and only if A is nilpotent.
So a(n) is not new.


>      b(n)  = number of nXn matrices over GF(q) having characteristic 
> polynomial x^n-1 = 0 .
> 
You can get the formula from the abstract in MathSciNet. Here's the
abstract:

Reiner, Irving 
On the number of matrices with given characteristic polynomial. 
Illinois J. Math. 5 1961 324--329.

--------------------------------------------------------------------------------
Let $K$ be a finite field with $q$ elements, let $K_n$ be the ring of all
$n$-by-$n$ matrices with elements in $K$, and define
$F(u,r)=(1-u^{-1})(1-u^{-2})\cdots(1-u^{-r})$. (1) If $f(x)$ is
irreducible in $K[x]$ and has degree $d\geq 1$, then the number of
elements $X$ of $K_{dn}$ for which $f(X)$ is nilpotent is
$q^sF(q,dn)/F(q^d,n)$ with $s=dn(dn-1)$. (2) Let $g(x)$ in $K[x]$ be of
degree $n$ and let $g(x)$ be the product of factors
$f_i{}^{n_i}(x) (i=1,\cdots,k)$ with $f_i(x)$ distinct irreducibles of
$K[x]$ of degree $d_i (i=1,\cdots,k)$. Then the number of elements in
$K_n$ which have $g(x)$ as characteristic polynomial is $q^tF(q,n)/D$ with
$t=n^2-n$ and $D=\prod_{i=1}^kF(q^{d_i},n_i)$. Fine and Herstein [same
J. 2 (1958), 499--504; MR 20 #3160] proved (1) for $f(x)=x$. The author
bases his proofs of (1) and (2) on a combinatorial lemma of Fine and
Herstein and a study of the automorphisms of modules over certain
commutative local rings [see also Gerstenhaber, ibid. 5 (1961), 330--333
--------------------------------------------------------------------------

With not too much effort using the above I can compute b(n) = number of
nxn matrices over GF(q) with charpoly x^n - 1 when q is prime (or for any
other polynomial for that matter--but I agree that x^n - 1 is particularly
nice). 


Here's b(n) for n >=1: 

for q=2:

1, 4, 56, 4096, 666624, 1194590208, 3343877406720, 72057594037927936,
3701652434038082764800, 1021880992906173430024372224

for q=3:

1, 12, 729, 758160, 2972290464, 354396766517640, 92079975413927255040,
939180873931369976460153600

for q = 5:

1, 30, 15500, 453375000, 95367431640625, 1200572419921875000000,
216114100769531250000000000000


Yuval, would you like to submit these since you thought of the idea.

Here's a maple procedure a(n,q) to generate b(n) as defined above for
prime q. (It would be more difficult for non-prime prime powers!)
The main difficulty is factoring x^n - 1 mod q and finding the degrees and
multiplicities of the irreducible factors:

> F:=(u,r)->product(1-u^(-i),i=1..r):
> a:=proc(n,q)
> local f,i,g,d,r,N;
> if n=1 then return 1; end if;
> f:=Factor(x^n-1) mod q;
> if type(f,`^`)=true then 
>    N:=1; 
>    d[1]:=degree(op(1,f)); 
>    r[1]:=op(2,f); 
> else
>   N:=nops(f);
>   for i from 1 to N do
>     g:=op(i,f);
>     op(1,g),op(2,g);
>     if type(g,`^`) then 
>        d[i]:=degree(op(1,g)); 
>        r[i]:=op(2,g);
>     else
>        d[i]:=degree(g);
>        r[i]:=1;
>     end if;
>   end do;
> end if;
> q^(n^2-n)*F(q,n)/mul(F(q^d[i],r[i]),i=1..N);
> end proc:
> 

--Edwin