Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Another exponent problem. $GL(n,q)$ is the group of invertible $n\times n$ matrices over the finite field $GF(q)$, where $q$ is a prime power. I am trying to figure out the exponent of this group.

Ideas:

We'd be doin real good if we could find the set of element orders $\{o(A):A\in GL(n,q)\}$, so I am looking for things to help me figure this out.

  1. The order of $GL(n,q)$ is $$|GL(n,q)|=\prod_{k=0}^{n-1}\left(q^n-q^k\right)$$ The set of prime factors of this number is a little unpredictable so I'm not sure whether I can use this.

  2. If $q$ is prime, the maximum order of an element in $GL(n,q)$ is at most $p^n-1$ (and this bound is strict I think). Also I guess the maximal power of $p$ that occurs as an order of this group is $p^{\lceil \log_pn\rceil}$. (source)

  3. I am aware of this, which I believe implies that $\text{Exp}(GL(2,p^n))=\text{lcm}\{p(p^{2n}-1),p-1\}$. I am trying to think of how to extend it to the general case but I'm not sure.

And I'm stuck; can't think of anything else that might help.

share|improve this question
    
Your formula for the exponent of $GL(2,p^n)$ does not work; check it on $GL(2,3)$. Computing with GAP suggests that the correct one is $LCM(p(p^{2n}-1),p-1)$. –  Mariano Suárez-Alvarez Feb 2 '13 at 7:41
    
I don't see why in the question, and the comment by @MarianoSuárez-Alvarez, one takes for $GL(2,p^n)$ an LCM with $p-1$, since this factor divides $p^{2n}-1$. See also my answer. –  Marc van Leeuwen Feb 4 '13 at 14:54
add comment

2 Answers

up vote 7 down vote accepted

Let us write $G=GL(n,q)$ for your group.

By the theorem that states that the so called Block Jordan Canonical Form of matrices over finite fields exist, we know that every matrix in $G$ is conjugate to one which is a block matrix with blocks of the form $$\begin{pmatrix}C_f\\I&C_f\\&I&C_f\\&&\ddots&\ddots\end{pmatrix} \tag{$\star$}$$ with $f$ an irreducible polynomial over the field $\mathbb F_q$ of some degree $d$, $C_d$ its companion matrix and $I$ the identity matrix of size $d$; see, for example, this notes.

It follows that the exponent of $G$ is the LCM of the orders of all matrices of this form with total size at most $n$.

So let $A$ be a matrix of the form $(\star)$, with $r\times r$ blocks, $f\in\mathbb F_q[X]$ an irreducible polynomial of degree $d$, $C_f$ its companion matrix and $I=I_d$ the $d\times d$ identity matrix. If we let $D$ be the «diagonal part» and $N$ be the «lower triangular part» (so that $D$ is a block diagonal matrix with $r$ blocks equal to $C_f$ along the diagonal and $N$ is a block matrix with non-zero blocks equal to $I_d$ exactly where these appear in $A$), we have $A=D+N$, $DN=DN$ and $N^r=0$. It follows immediately from this and the binomial formula that $$A^s=D^s+\binom{s}{1}D^{s-1}N+\binom{s}{2}D^{s-2}N^2+\cdots+\binom{s}{r-1}D^{s-r+1}N^{r-1}$$ for all $s\geq0$. It is easy to see what each term in this sum looks like, and using that we can see that $A^s=I_{dr}$ if and only if $D^s=I_{dr}$ and $\binom{s}{i}D^{s-i}=0$ for all $i\in\{1,\dots,r-1\}$. This happens iff $$\text{$C^s=I_d$ and $\binom{s}{i}=0$ for all $i\in\{1,\dots,r-1\}$.}$$ Of course, the order of $A$ is the least positive number $s$ which satisfies this condition. Plainly, it depends only on $f$ and on $r$, so we can call it $o(f,r)$. Moreover, it is clear that $o(f,r)\mid o(f,r+1)$, so the exponent of $G$ is $$LCM\{o(f,\lfloor n/\deg(f)\rfloor:f\in\mathbb F_q[X],\text{$f$ irreducible}, \deg(f)\leq n\}$$

If $n=2$, it is not very difficult to compute this: I get $LCM(p(p^{2n}-1),p(p^n-1))$, which happily equals with the formula I gave in a comment to the question.

share|improve this answer
    
Isn't $LCM(p(p^{2n}-1),p(p^n-1))=p(p^{2n}-1)$ ? –  tj_ Feb 2 '13 at 8:32
    
+1, nice answer. Just one remark: $N$ has nilpotency degree $r$, so that $N^r=0$, and $\binom si\equiv 0\pmod p$ needs to hold only for $0<i<r$, where $p$ is the characteristic (and I think this means that $s$ is divisible by the smallest power $p^i\geq r$). –  Marc van Leeuwen Feb 2 '13 at 8:42
    
Right! I hopefully fixed it now. –  Mariano Suárez-Alvarez Feb 2 '13 at 19:03
add comment

One can in fact give a quite explicit formula for the exponent of $GL(n,\Bbb F_q)$, and a fairly explicit description of the set of orders of elements that can occur.

First, the order of $A\in GL(n,\Bbb F_q)$ only depends on the minimal polynomial $f$ of $A$, and is equal to the minimal exponent $e>0$ such that $X^e-1$ is divisible by $f$. Since $A$ is invertible the constant term of $f$ is nonzero, but otherwise $f$ can be essentially made to be any polynomial of degree at most $n$ in $\Bbb F_q[X]$ using companion matrices ("essentially" because extending a matrix with an identity matrix block may change its minimal polynomial: it becomes the $\def\lcm{\operatorname{lcm}}\lcm$ of $X-1$ and the old minimal polynomial; this does not however affect the associated value $e$). So we get that the set of orders of elements $A$ is equal to the set of expoenents $e$ associated to polynomials of degree at most $n$ in $\Bbb F_q[X]$, and the exponent of $GL(n,\Bbb F_q)$ is the least $e>0$ for which $X^e-1$ is divisible by all such polynomials.

However not all such polynomials need to be considered. If we decompose a polynomial into pairwise relatively prime factors, then the associated $e$ will be the least common multiple of those numbers for the factors, by the Chinese remainder theorem for $K[X]$. Also if $f$ is irreducible of degree $d$ then the associated exponent $e_f$ will be a divisor of $q^d-1$ (because $\Bbb F_q[X]/(f)$ is a finite field of order $q^d$), and $e_f=q^d-1$ will occur for certain such polynomials, called primitive polynomials (because the multiplicative group of that finite field is cyclic). We must also consider the exponents associated to powers $f^i$ of irreducible polynomials (as long as their degree is at most $n$); here too the interesting case will be when $f$ is a primitive polynomial. Since $X^{q^d-1}-1$ is the product of all monic irreducible polynomials with degree dividing $d$, except $X$, it is divisible by $f$ but not by $f^2$, it follows that $q^{e_f}-1$, which is divisible by $f$ by assumption, is not divisible by $f^2$ either. Say $X^{e_f}=1+af$ with $a$ not divisible by $f$. Then by the binomial formula $X^{e_fk}\not\equiv 1\pmod{f^2}$ for $0<k<p$, where $p$ is the characteristic of $\Bbb F_q$, but on the other hand $X^{e_fp}=1+a^pf^p$ by the Frobenius endomorphism of $\Bbb F_q[X]$. Similarly $X^{e_fpk}\not\equiv 1\pmod{f^{p+1}}$ for $0<k<p$, but $X^{e_fp^2}=1+a^{p^2}f^{p^2}$. Continuing like this, it follows that the smallest exponent $e>0$ with $X^e\equiv 1\pmod{f^i}$ is given by $$ e=e_fp^{\lceil\log_p i\rceil} $$ which is maximal (in the multiplicative sense) among irreducible polynomials of degree $d$ when $f$ is primitive, and then gives $$ e=(q^d-1)p^{\lceil\log_p i\rceil} $$

The problem of finding all orders of elements of $GL(n,\Bbb F_q)$ becomes that of finding the numbers expressible as the least common multiple of a collection of such numbers $e$, each for some $(d,i)$, under the constraint that the sum of the values $di=\deg(f^i)$ be at most $n$ (of course all divisors of such numbers also occur as order of an elements of $GL(n,\Bbb F_q)$). I don't know of any really transparent way of describing this set of orders. In any case, as the link in the question indicates, the fact that $\Bbb F_q[A]$ has only $q^d-1$ nonzero elements where $d$ is the degree of the minimal polynomial of $A$ shows that the maximum (in the additive sense) possible order $q^n-1$ is attained for a single pair $(d,i)=(n,1)$.

However the exponent of $GL(n,\Bbb F_q)$ can be explicitly given. The multiplicity of $p$ in it is $\lceil\log_p n\rceil$, obtained for $(d,i)=(1,n)$. The factor relatively prime to $p$ is $\lcm(q-1,q^2-1,\ldots,q^n-1)$. It is known (see for instance this question) that $\gcd(q^k-1,q^l-1)=q^{\gcd(k,l)}-1$, so the only common factors to consider here are the ones that occur in the list themselves, and indeed given the preceding numbers, the number $q^k-1$ contibutes as fresh factor the value $\Phi_k(q)$, where $\Phi_k$ is the $k$-th cyclotomic polynomial. Thus finally, the exponent of $GL(n,\Bbb F_q)$ is equal to $$ p^{\lceil\log_p n\rceil} \prod_{k=1}^n\Phi_k(q) \qquad\text{where }p\text{ is the characteristic of }\Bbb F_q. $$

As a sanity check, I'll plug in $n=2$ to give the exponent $p(q-1)(q+1)=p(q^2-1)$. For $n=3$ one gets exponent $2^2(q^2-1)(q^2+q+1)$ in characteristic $2$ (indeed the exponent of $GL(3,\Bbb F_2)$, which has order $168$, is $4\times3\times7=84$) and $p(q^2-1)(q^2+q+1)$ in any other characteristic $p$.

share|improve this answer
    
I left the LCM unevaluated simply out of lazyness, really :-) I wrote it that way (with the two arguments) because that's the way I found it, grouping all the $o(f,r)$ according to the $r$ (which is either $1$ or $2$). And, surely, what you explained is exactly what I did to compute this: the key observations are, precisely, that there exist primitive polynomials, that the vanishing of the binomial numbers is equivalent to what you observed in your comment to my answer, and that the two parts of the condition I found are «coprime». –  Mariano Suárez-Alvarez Feb 4 '13 at 18:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.