# Order of matrix and monic irreducible polynomial over finite field

I want to verify (and prove - in case it is true) the following proposition.

Suppose $\mathbb{F}_p$ is a finite field and $m(x)$ is a monic irreducible polynomial over $\mathbb{F}_p$ with $\mathrm{deg}(m(x))=n$.

If $\mathbf{A}$ is an $n \times n$ matrix over $\mathbb{F}_p$ whose characteristic polynomial is $m(x)$, then $\mathrm{ord}(\mathbf{A})=p^n-1$, where $\mathrm{ord}(\mathbf{A})$ denotes the least positive integer $k$ such that $\mathbf{A}^k = \mathbf{I}$, where $\mathbf{I}$ is the identity matrix.

For example, in $\mathbb{F}_2$, $m(x)=x^3+x^2+1$ is a monic irreducible polynomial. The characteristic polynomial of matrix $\mathbf{A}=$

\begin{bmatrix}0&0&1\\1&0&0\\0&1&1\end{bmatrix}

is equal to $m(x)$ and $\mathbf{A}$ satisfies $\mathrm{ord}(\mathbf{A})=7$. Note that $2^3-1=7$.

I have already checked using SAGE mathematical software that the companion matrices of a monic irreducible polynomial have order $q^n-1$ for $q=2$ and $2\leq n \leq 21$.

My question is, is the above proposition true in general?

My attempt to prove the theorem is by using group isomorphism between $\mathbb{F}^{*}_p = (\mathbb{F}_p[x]/m(x))^{*}$, i.e. the non zero elements of the finite field, and the matrix group $S = \{\mathbf{A}^k | k \in \mathbb{Z}\}$. But a problem occurs, how to construct an isomorphism from $\mathbb{F}^{*}_p$ to $S$ ? I have tried the function $\theta: \alpha \mapsto \mathbf{A}$ where $\alpha$ is the primitive element in $\mathbb{F}^{*}_p$, but I can not complete the detail.

I have read several references, this book, p. 65 by R. Ridl and H. Niedereitter and this article by W. P. Wardlaw. The proposition seems true, but I have not found any formal proof about it.

ADDENDUM: Apparently, the proposition is not true in general. There is a counterexample in W. P. Wardlaw article for $m(x)=x^2+1$ in $\mathbb{F}_3$. (Credit to WimC). However the condition is true for $m(x)=x^2+x+2$.

So what is there any additional requirement for $m(x)$ in order to make the proposition true?

• This does not hold over $\Bbb{F}_2$ either. The polynomial $p(x)=x^4+x^3+x^2+x+1$ is irreducible, but because $p(x)(x-1)=x^5-1$ its zeros (and the companion matrix) are of order five. Small finite fields (extensions of $\Bbb{F}_2$ in particular) are often defined using a so called primitive polynomial. A zero of a primitive polynomial is, by definition of primitive, of maximal order $2^n-1$. In other words, your sample of irreducible polynomials may have been biased for this reason. – Jyrki Lahtonen Jan 1 '16 at 8:47
• I am sorry Jyrki, but I think you did not read the addendum and WimC answer to my question. Not all companion matrices of irreducible polynomial satisfy the condition, but some companion matrix does satisfy the condition. If we choose $p(x)=x^4+x+1$, the matrix $\mathbf{A}$ whose characteristic polynomial is $p(x)$ satisfies the condition. – Iqazra Jan 1 '16 at 9:40
• I did read it. I was mostly looking for an explanation as to why your sampling might have initially lead you to think that the order is $p^n-1$ more often than it actually is. Sorry about not making that clear. A curious fact is that if $2^p-1$ is a prime (i.e. Mersenne prime), then all irreducibles over $\Bbb{F}_2$ of degree $p$ are primitive. This happens for irreducibles of degree $3,5,7$ which is another reason for sample bias. +1 to you both was there. – Jyrki Lahtonen Jan 1 '16 at 9:55
• Okay then, I posted a clearer problem in this one. The references say that the isomorphism is indeed exist, but I still struggling with the formal proof. I should have replace the minimal polynomial with primitive polynomial. – Iqazra Jan 1 '16 at 10:20

No this is not true in general. The polynomial $m(X)=X^2+1$ is irreducible over $\mathbb{F}_3$ but the order of $X$ in $(\mathbb{F}_3[X]/m(X))^{\ast}$ is $4$. In other words, not all non-zero elements in the multiplicative group of a finite field with $p^n$ elements need to have the maximal order $p^n-1$.
• Thank you, but for the polynomial $m(x)=x^2+x+2$, any $3 \times 3$ matrix over $\mathbb{F}_3$ whose characteristic polynomial is $m(x)$ does satisfies the condition. I added an addendum in my question. Now, what are the additional requirement for $m(x)$? – Iqazra Jan 1 '16 at 8:09
• $m$ must divide $x^4+1$ in $\mathbb{F}_3[x]$. In general $m$ must divide the cyclotomic polynomial $\Phi_{q-1}$. For example $\Phi_8=x^4+1=(x^2+x+2)(x^2+2x+2)$ over $\mathbb{F}_3$. – WimC Jan 1 '16 at 8:29