2
$\begingroup$

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.

$\endgroup$
14
  • $\begingroup$ 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$. $\endgroup$ Feb 9 at 15:38
  • $\begingroup$ 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. $\endgroup$
    – Randall
    Feb 9 at 15:41
  • $\begingroup$ 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. $\endgroup$ Feb 9 at 15:41
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 9 at 15:57
  • 1
    $\begingroup$ (cont'd) That follows for example from Skolem-Noether even though it is likely overkill for such a purpose :-) $\endgroup$ Feb 9 at 15:58

2 Answers 2

3
$\begingroup$

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)}. $$

$\endgroup$
10
  • $\begingroup$ 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? $\endgroup$
    – Randall
    Feb 9 at 16:46
  • $\begingroup$ @Randall Yes! Typo from my first attempt $\endgroup$ Feb 9 at 16:55
  • $\begingroup$ @Randall And yes, the Singer cycles will necessarily be an undercount, as you say $\endgroup$ Feb 9 at 17:26
  • $\begingroup$ @Randall You might find my latest edit to be helpful. $\endgroup$ Feb 9 at 18:23
  • 1
    $\begingroup$ @JyrkiLahtonen Well we're talking about the matrix of a Siger cycle, and the matrix of a linear transformation requires a basis $\endgroup$ Feb 9 at 23:18
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .