Existence of Singer Cycle in GL(n,q)

[the_fox]

Assume GL(n,q) is the general linear group of nxn matrices with entries in the finite field with q elements. Define a Singer Cycle to be an element of GL(n,q) of order (q^n)-1. How can we show that such an element always exists? That is, for all n and q.

Thanx in advance.

 

[morphism]

Hint 1: The multiplicative group of a finite field is cyclic.

Hint 2: GF(q^n)* can be embedded into GL(n,q).

 

[the_fox]

I am aware of the first hint. For the second, by an embedding you mean an injective homomorphism? I would think that if someone could find such a map, say f, then f(a) would be the element we are looking for, where a is a generator of GF(q^n)*. Of course it should be established that f is order preserving. Am I correct?

 

[morphism]

Yup.

 

[the_fox]

Take T:GF(q^n)-->GF(q^n), with T=ax, GF(q^n)*=<a>. Then there exists a basis {e_1,...,e_n} of GF(q^n) over GF(q) such that Te_j=Σa_ije_i and T corresponds isomorphically to a matrix A=[a_ij] in GL(n,q) which must necessarily have order q^n-1. Does that sound correct?

 

[morphism]

Yes -- good work! (Just make sure you notice that T is invertible.)

 

[the_fox]

Allright, I'd like to take it a step further:how about a singer cycle's minimal polynomial? It seems that its degree is always n, but I can't prove it. Any hints? Thank you for your help morphism.

 

[morphism]

Do you have any reason to believe that is always the case? I don't immediately see how this can be proved. I actually think it may be false. If you can find a natural number n and a prime p such that the following inequality holds

$$\sum_{d | n} \mu(d) p^{n/d} < \varphi(p^n - 1),$$

where $\mu$ is the Mobius function and $\varphi$ is the Euler totient function, then I can explain how this can be used to produce a counterexample. I haven't given this much thought, so it's very probable that this inequality may never hold.

I'll try to think about this problem some more later.

 

[morphism]

Ignore my previous post -- the term minimal polynomial slightly threw me off.

What you want to do is show that every Single cycle A arises as above, i.e. as a generator of GF(q^n)*. Then, if m(t) is the minimal polynomial of A, we can see that GF(q)[t]/<m(t)> is GF(q^n). Hence deg(m(t)) = [GF(q^n) : GF(q)] = n.

[Incidentally I think this will prove that $\varphi(p^n - 1) \leq \sum_{d | n} \mu(d) p^{n/d}$ for all n and p.]

 

[morphism]

Some googling brought up http://www.hull.ac.uk/php/masrs/2003/clgln2e2.pdf. You might find it useful.

 

[the_fox]

Yeah you are right! At some point I thought of that, but for some reason I rejected it.. I'll look more into this. Btw taking the rational canonical form, you get that every singer cycle is similar to a unique companion matrix, which implies that there are as many singer cycles as irreducible polynomials of degree n over GF(q). Right? Thanx for the paper.

 

[the_fox]

That's not quite right.. Any ideas about how many singer cycles there are?

 

[the_fox]

Ignore my previous post -- the term minimal polynomial slightly threw me off.

What you want to do is show that every Single cycle A arises as above, i.e. as a generator of GF(q^n)*. Then, if m(t) is the minimal polynomial of A, we can see that GF(q)[t]/<m(t)> is GF(q^n). Hence deg(m(t)) = [GF(q^n) : GF(q)] = n.

[Incidentally I think this will prove that $\varphi(p^n - 1) \leq \sum_{d | n} \mu(d) p^{n/d}$ for all n and p.]

But, how do we know that every singer cycle in GL(n,q) corresponds to a linear transformation T=ax, where a is a primitive element?

 

[morphism]

Just look at how GL(n,q) acts on GF(q^n)*.