Briliant.orgConsider the set of $n$-by-$n$ matrices whose entries are integers modulo $p$, for some prime $p$. The matrices in this set with nonzero determinant are invertible, and thus form a group under matrix multiplication; this group is given the name $\text{GL}(n,p)$, where the "GL" stands for "general linear."
Given a matrix $M \in \text{GL}(n,p)$, its order is defined to be the smallest integer $k$ such that $M^k = I$, where $I \in \text{GL}(n,p)$ denotes the identity matrix. In this problem, you will compute the maximum possible order of a matrix in $\text{GL}(n,p)$. That is, you will answer the question "What is the largest integer $m \in \mathbb{N}$ such that $m$ is the order of a matrix in $\text{GL}(n,p)?$"
Hint & Proof Sketch:
Let $A$ be a matrix in $\text{GL}(n,p)$. Consider the vector space $V(A,p)$ generated by the powers of $A$, with coefficients in the field of $p$ elements. That is, $V(A,p)$ is the vector space (under addition) of linear combinations $$a_0 + a_1 A + a_2 A^2 + a_3 A^3 + \cdots,$$ where the coefficients $a_i$ are integers modulo $p$. The Cayley-Hamilton theorem implies $V(A,p)$ is finite dimensional; what is the largest possible value of its dimension $\big($as $A$ ranges over the group $\text{GL}(n,p)\big)?$ Suppose $\dim\big(V(A,p)\big) = k$. What does this imply about the order of $A$ in $\text{GL}(n,p)?$ To answer this question, note that any power of $A$ must be in $V(A,p)$, since the exponents in powers of $A$ can be reduced using the polynomial relation produced by Cayley-Hamilton. Let $K$ denote the largest possible value of $\dim\big(V(A,p)\big)$ when $A$ ranges over $\text{GL}(n,p)$. Can you find a matrix $B \in \text{GL}(n,p)$ whose order is at least $K?$ What does this imply in light of the previous two steps?
As your answer to this problem, submit the maximum possible order of a matrix in $\text{GL}(4,5)$, i.e. $$\max_{A \in \text{GL}(4,5)} \text{Order}(A).$$
Solution.
We will work over the field $𝔽_p$ with $p$ elements throughout.
Since $V(A,p)$ is spanned by $I_n,A,..,A^{n-1}$, by Cayley-Hamilton, we know that $\dim_{𝔽_p}(V(A,p))\leq n$. Thus $V(A,p)$ contains at most $p^n-1$ non-zero matrices.
There must exist two integers $1\leq a<b\leq p^n$ such that $A^a=A^b$, or $A^{b-a}=I_n$: The order of $A$ is at most $p^n-1$.
Consider a multiplicative generator $a$ of the field with $p^n$ elements, and let $f(x)$ be the minimal polynomial of $a$ over $𝔽_p$, a polynomial of degree $n$. Let $A$ be an $n\times n$ matrix whose characteristic polynomial is $f(x)$. Since $a$ is an eigenvalue of $A$, the order of $A$ will be at least $p^n-1$.
It follows that the maximum possible order of $A$ is exactly $p^n-1$, which is $5^4-1=\boxed{624}$ in our case.
| 
