Finding the order of an element in $GL(2,\mathbb F_p)$.

Question

Let $\mathbb F_p=\mathbb{Z}/p\mathbb{Z}$. I am looking for a general method of finding the order of an element in $GL(2,\mathbb F_p)$. Suppose $p=7$ and I am given the element $\begin{pmatrix} 5 &1 \\ 1& 1\\\end{pmatrix}$, and I am asked to find the order, then how should I proceed. One way to proceed is to calculate $A^k$ for each $k$ and see when it takes the value $I_2$ for the first time. But this becomes a tedious task when the order is large. I think there is some other way to figure out the order by some group representation technique, but I do not know that topic very well. Can someone help me?

Answer 1

In general, this is a difficult problem, as even finding the order or an element in $\mathbb F_p$ is a nontrivial problem. That said, there are a few observations that one can make.

First, the size of $GL(2,\mathbb F_p)$ is $(p^2-1)(p^2-p)=p(p-1)^{2}(p+1)$, and by Lagrange's theorem, the order of any element must divide the size of the group. However, we can do better. Proceeding as Jyrki does, we can look at the characteristic polynomial and eigenvalues. The characteritic polynomial will be $t^2-t \operatorname{tr}(A)+\det(A)$, and the discriminant of this polynomial is $\operatorname{tr}(A)^2-4\det(A)$.

If the discriminant is a quadratic residue, which can be determined easily by using quadratic reciprocity and Legendre symbols/Jacobi symbols, then both the eigenvalues are elements of $\mathbb F_p$, and so the order divides $p-1$ (again, by Lagrange's theorem, or by Euler's theorem or Fermat's little theorem). If we compute those eigenvalues and compute their orders in $\mathbb F_p^{\times}$, then the order of $A$ will be the least common multiple of the orders.

If the discriminant is not a quadratic residue, then the eigenvalues are conjugate elements of $\mathbb F_{p^2}$ which are NOT elements of $\mathbb F_p$. Therefore, their orders (which are the same) will divide $p^2-1$ (the size of $\mathbb F_{p^2}^{\times}$), but will NOT divide $p-1$.

Additionally, since $\det(A^n)=\det(A)^n$, we must have that $\operatorname{ord}_{\mathbb F_p^{\times}}(\det(A))$ will divide the order of $A$.

Unfortunately, even with all this information, the problem of determining the order of an element of $\mathbb F_p$ or $\mathbb F_{p^2}$ is in general a hard problem. For small values of $p$, it isn't too terrible, but unfortunately, even having a list of the possible orders can be insufficient if $p-1$ or $p^2-1$ have a lot of distinct prime factors.

For example, with with your particular example, we know that the order has to divide $48$, but not divide $6$, and it has to be a multiple of $\operatorname{ord}_{\mathbb F_7}(4)=3$. This is fortunate, as $48=2^{4}\cdot 3$, and so the order is either 3, 6, 12, 24, or 48, and after an initial cubing, we can test the other powers with only repeated squaring. We will rarely be this fortunate.