# Do Singer cycles create all matrices of maximal order in $\operatorname{GL}_n(\mathbb{F}_q)$?

I am interested in elements of $$\operatorname{GL}_n(\mathbb{F}_q)$$ of maximal order. It is known that the maximum possible order of such an element is $$q^n-1$$ and that this bound is achievable via Singer cycles. These are built in the following simple way. Regard $$V=\mathbb{F}_{q^n}$$ as a vector space over $$\mathbb{F}_q$$ and take a primitive element $$\alpha$$ of $$\mathbb{F}_{q^n}$$. Define the linear transformation $$T_\alpha: V \to V$$ by $$T_\alpha(x)=\alpha x$$. It is then a simple matter to check that $$T_\alpha$$ represents an element of $$\operatorname{GL}_n(\mathbb{F}_q)$$ of order $$q^n-1$$.

My question is: do the Singer cycles create all the elements of $$\operatorname{GL}_n(\mathbb{F}_q)$$ of order $$q^n-1$$. That is, given such a matrix $$A$$, is there a way to find a primitive element $$\alpha$$ so that $$A$$ represents $$T_\alpha$$? I have tried making use of the information gathered from the minimal polynomial of such a matrix $$A$$ (as it must divide $$x^{q^n-1}-1$$), but I do not see how to connect this to a suitable primitive in $$\mathbb{F}_{q^n}$$. This made me think that maybe it's just not true. Any guidance and/or references are appreciated.

Added for context: I am attempting to count the number of matrices $$A \in \operatorname{GL}_n(\mathbb{F}_q)$$ of maximal order $$q^n-1$$. If these matrices are in one-to-one correspondence with the Singer cycles [who in turn correspond to primitives] then I am done. In order to establish such a correspondence, I need the answer to this question to be in the affirmative when one basis is fixed for $$V$$ over $$\mathbb{F}_q$$ for the whole of the argument.

• This is a good question. I haven't thought it through, but I think this is true. After all, a linear transformation from $GL_n$ is a zero of it s characteristic polynomial by Cayley-Hamilton. My first attack on proving this would be to try and show that the characteristic polynomial (obvious of the correct degree $n$) should be irreducible, when the order of the matrix is $q^n-1$. Feb 9 at 15:38
• Part of the issue, to confess, is my rustiness on the results on decompositions of an endomorphism and all the informative polynomial/canonical form business. Feb 9 at 15:41
• Actually, your question is likely to be a duplicate of this one. My vote to close it as such would be immediately binding, so I will wait for a little while so that interested parties can have their say. Feb 9 at 15:41
• Randall, I think the third bullet point is simply about not all matrices of order $q^n-1$ being conjugate. After all, the conjugate matrices share the same minimal polynomial over $\Bbb{F}_q$, but within a single copy of $\Bbb{F}_{q^n}$, only $n$ of the primitive elements (out of $\phi(q^n-1)$) share the same minimal polynomial. On the other hand, if $K_1$ and $K_2$ are any two copies of $\Bbb{F}_{q^n}$ within $M_{n\times n}(\Bbb{F}_q)$, then they are conjugate in the sense that we can find a matrix $A$ such that $AK_1A^{-1}=K_2$ as sets. Feb 9 at 15:57
• (cont'd) That follows for example from Skolem-Noether even though it is likely overkill for such a purpose :-) Feb 9 at 15:58

The answer is "no" if you mean that these matrices correspond to a fixed choice of basis.

I will build a counterexample for the case of $$q = 2, n = 3$$. Note that all maps of the form $$T_\alpha$$ for $$\alpha \in \Bbb F_{2^3}$$ commute. Thus, if we find an $$\alpha \in \Bbb F_{2^3}$$ and a matrix $$M \in \Bbb F_2^{3 \times 3}$$ such that $$M^7 = I$$ (since $$q^n - 1 = 7$$) but $$MT_{\alpha} \neq T_\alpha M$$, then we have found an $$M$$ that cannot be realized as a Singer cycle.

Present $$\Bbb F_8$$ as $$\Bbb F_2[x]/\langle x^3+x+1 \rangle$$. Then relative to the basis $$\mathcal B = \{1,x,x^2\}$$ of $$\Bbb F$$, the matrix of $$T_{x}$$ is given by $$[T_x]_{\mathcal B} = \pmatrix{0&0&1\\ 1&0&1\\ 0&1&0}.$$ Because $$x$$ is a primitive element, $$T_x$$ has order $$7$$. This matrix fails to commute with its transpose, $$M = ([T_x]_{\mathcal B})^\top$$. However, $$M$$ must have the same order as $$T_x$$. Thus, $$M$$ is a matrix of order $$q^n - 1$$ that does not correspond to a singer cycle (relative to this basis $$\mathcal B$$).

For posterity: we find that $$[T_x]_{\mathcal B}([T_x]_{\mathcal B})^\top = \pmatrix{1&1&0\\1&0&0\\ 0&0&1},\\ ([T_x]_{\mathcal B})^\top[T_x]_{\mathcal B} = \pmatrix{1&0&1\\0&1&0\\ 1&0&0}.$$

It is notable that two matrices of maximal order need not even be conjugate to each other. As counterexample to this, consider $$[T_x]_{\mathcal B}$$ as above and the matrix $$M = \pmatrix{0&0&1\\1&0&0\\0&1&1},$$ which also has order $$7$$. We can see that these matrices are not conjugate since they have characteristic polynomials $$x^3 + x + 1$$ and $$x^3 + x^2 + 1$$ respectively.

Regarding the project of counting elements of $$GL_n(\Bbb F_q)$$ of maximal order, I would note the following for the case that $$q$$ is prime.

It is known that the cyclotomic polynomial $$\Phi_{q^n - 1}(x)$$ factors into a product of irreducible polynomials of the same degree, which (given the existence of primitive elements) must be of degree $$n$$. Each of the $$\varphi(q^n - 1)/n$$ factors (that I believe are distinct) are a possible candidate for the characteristic (and minimal) polynomial of a matrix in $$GL_n(\Bbb F_q)$$. In other words matrix with maximal order must be conjugate to the companion matrix associated with one of these polynomials.

With that, the process of selecting a matrix of maximal order can be broken down to selecting a factor of $$\Phi_n$$, then selecting a matrix that is conjugate to the associated companion matrix.

As for counting the elements conjugate to a given companion matrix $$C$$, the following argument works.

Consider the action of $$GL_n(\Bbb F_q)$$ on itself given by conjugation, i.e. the action $$A \cdot X = AXA^{-1}$$.

• The matrix $$C$$ is non-derogatory, which means that $$A$$ is in the stabilizer of $$C$$ if and only if $$A = f(C)$$ for some polynomial $$f$$.
• The non-zero matrices of the form $$f(C)$$ for such a polynomial form a subgroup of $$GL_n(\Bbb F_q)$$ that is isomorphic to the multiplicative group of $$\Bbb F_{q^n}$$. Thus, $$GL_n(\Bbb F_q)_C$$, the stabilizer subgroup of $$C$$ has order $$q^n - 1$$.
• By the orbit stabilizer theorem, the number of distinct elements conjugate to $$C$$ is given by $$\frac{|GL_n(\Bbb F_q)|}{|GL_n(\Bbb F_q)_C|} = \frac{(q^n - 1)(q^n - q)\cdots (q^n - q^{n-1})}{q^n - 1} = (q^n - q)\cdots (q^n - q^{n-1}).$$

Putting the previous two sections together, we have a potential answer for prime values of $$q$$. If we accept the hypothesis that $$\Phi_{q^n - 1}$$ has no repeating factors, then the total number of distinct matrices in $$GL_n(\Bbb F_q)$$ with order $$q^n - 1$$ is given by $$\frac{\varphi(q^n - 1)}{n} \cdot (q^n - q)\cdots (q^n - q^{n-1}).$$ Equivalently, the fraction of elements of $$GL_n(\Bbb F_q)$$ that have maximal order is $$\frac{\varphi(q^n - 1)}{n\cdot (q^n - 1)}.$$

• This seems helpful. I think you are right in your first sentence: I think I do mean that I am fixing a single basis once and for all. For clarity, I am trying to count the number of matrices of order $q^n-1$, so having a one-to-one correspondence with Singer cycles would be great. However, your (fantastic) example is showing that counting the Singer cycles will be an undercount, right? Feb 9 at 16:46
• @Randall Yes! Typo from my first attempt Feb 9 at 16:55
• @Randall And yes, the Singer cycles will necessarily be an undercount, as you say Feb 9 at 17:26
• @Randall You might find my latest edit to be helpful. Feb 9 at 18:23
• @JyrkiLahtonen Well we're talking about the matrix of a Siger cycle, and the matrix of a linear transformation requires a basis Feb 9 at 23:18

Let $$f$$ be any irreducible $$\Bbb F_q$$-polynomial of degree $$n$$ and $$A$$ its Frobenius companion matrix. (Apparently) $$A$$ generates a Singer cycle. Its centralizer in $$M_n(\Bbb F_q)$$ is an $$n$$-dimensional subalgebra (that is $$\cong \Bbb F_{q^n}$$), so its orbit in $$GL_n$$ wrt conjugation is of order $$(q^n-q)(q^n-q^2)\cdots(q^n-q^{n-1}) \approx q^{n^2-n}$$, much more than the amount of primitive elements $$\varphi(q^n - 1) < q^n$$.

On the other hand, if the only thing fixed is the characteristic polynomial, and we can freely choose the basis, then a similarity to the Frobenius form would give a power basis of the field.