Counting matrices over finite fields of a given order

Question

How can I count/enumerate matrices in ${\rm GL}(2,{\rm GF}(2^5))$ of order $3$? In general, how can I obtain the number of matrices in ${\rm GL}(2,{\rm GF}(q))$, where $q$ is a power of a prime, of order, say, $t$?

Answer 1

Well, if $X^3=1$, then $(X-1)(X^2+X+1)=0$. At first, assume that 1 is eigenvalue of $X$, then the second eigenvalue $v$ belongs to the field $GF(32)$, so $v^3=v^{31}=1$, $v=1$. That is, $X=Id+Y$ for nilpotent $Y$, $X^3=Id+3Y=Id+Y$, $Y=0$, order of $X$ equals 1, not 3. So $X^2+X+1=0$, and this is both minimal and characteristic polynomial of $X$. So, we count number of quadruples $(a,b,c,d)$ for which $a+d=1,ad-bc=1$. Fix arbitrary $d$ and arbitrary $c\ne 0$, then $a$ and $b$ are defined uniquely. Thus the answer is $32\cdot 31$.

In general case do the same steps, you have to know how many linear and quadratic factors does polynomial $X^t-1$ have in your field, this is standard (number of linear factors is $gcd(t,q-1)$, total degree of linear and quadratic factors is $gcd(t,q^2-1)$.)

Well, let me be more precise in this case. We count number $f(t)$ of solutions of equation $X^t=1$, then use Moebius inversion formula for count number of matrices of order $t$: it equals $\sum_{n|t} f(n)\mu(t/n)$.

We denote $m_1$ the number of linear factor of $X^t-1$, it equals $gcd(t,q-1)$, and $m_2$ the number of quadratic irreducible factors of $X^t-1$, we have $m_1+2m_2=gcd(t,q^2-1)$. There are $m_1$ scalar matrices $X$ and $(q+1)qm_1(m_1-1)/2$ diagonalizable but not scalar matrices ($q+1$ possible directions of first eigenvector, $m_1$ possible eigenvalues, then $q$ possible directions of second eigenvector and $m_1-1$ possible eigenvalues, each matrix is counted twice.) Now we count number of $X$ such that $X=c\cdot Id+Y$ with nilpotent $Y$ and some number $c$ such that $c^t=1$. We have $X^t=Id+tc^{t-1}Y$, thus we get $Y=0$ if $gcd(t,q)=1$ and any $Y$ is ok if $gcd(t,q)>1$. Nilpotent non-zero matrix is something like $\pmatrix{a&b\cr a^2/b&a}$, $b\ne 0$, or $\pmatrix{0&0\cr c&0},c\ne 0$. Totally, there are $q(q-1)+(q-1)=q^2-1$ nilpotent non-zero matrices, and $m_1(q^2-1)$ matrices $X=c\cdot Id+$(nilpotent), this is when $gcd(q,t)>1$.

Finally, we count matrices $X$ with irreducible characteristic polynomial $X^2+pX+q$ of degree 2, this polynomial is chosen between $m_2$ quadratic factors of $X^t-1$. It reduces to system of equations $a+d=p,ad-bc=q$. Fix arbitrary $d$ and arbitrary $c\ne 0$, then $a$ and $b$ are defined uniquely. Thus the answer is $q(q-1)$ matrices for each fixed polynomial, totally $m_2q(q-1)$ matrices.

Answer 2

In GAP, you can find the number of elements of order $t$ in ${\rm GL}(2,q)$ by the following function:

NumberOfElementsOfGivenOrderInGL2q := function ( q, t )
  return Sum(List(Filtered(ConjugacyClasses(GL(2,q)),
                           cl->Order(Representative(cl))=t),Size));
end;

For example in your case, i.e., $q = 2^5$ and $t = 3$, you obtain

gap> NumberOfElementsOfGivenOrderInGL2q(32,3);
992