# Some iterate of a linear operator over $\mathbf F_q$ is a projection

If $T$ is an endomorphism of a finite-dimensional vector space $V$ over a finite field, then how can I show that there exists a positive integer $r$ such that $T^r$ is a projection operator?

-
Please do not ask questions in the imperative, you make it sound like a homework question. And if it is indeed a homework question, please first read our FAQ on that: meta.math.stackexchange.com/q/1803/1543 – Willie Wong Aug 13 '11 at 16:57
Do you know what is a Jordan normal form? – Prometheus Aug 13 '11 at 17:18
@Prometheus, if I remember correctly, you can't use the Jordan normal form for matrices over finite fields. – Calle Aug 13 '11 at 17:48
@Sarah: what have you tried so far? What tools did you consider? – Olivier Bégassat Aug 13 '11 at 17:57
@Calle Are you certain? The proofs I've seen of the JNF only rely on the structure theorem for modules over a PID, and $k[x]$ is a PID for any field $k$. You need the characteristic polynomial to split, but this only requires moving up to a larger finite field. – Aaron Aug 13 '11 at 18:06

You can do this very much in the spirit of Aaron's first hint (but I work with the finite ring of endomorphisms as opposed to the field itself):

1) The ring of endomorphisms of $V$ is finite.

2) Therefore there are repetitions among the powers $T^r$, $r$ a positive integer.

3) Therefore the sequence $(T^i)_{i\in\mathbf{N}}$ is eventually periodic with a period $\ell$.

4) If $\ell$ is a period, then so are $2\ell,3\ell,\ldots$.

5) $r=k\ell$ works for a large enough value of $k$ such that $T^r$ is in the periodic part of the above sequence of operators.

-
That's very nice! You lose the explicit construction of $r$, but you require less, and the ideas here are reusable. – Aaron Aug 13 '11 at 18:21

Here is an outline and some hints:

1. Show that over the finite field $\mathbb F_q$, there exists a number $r(q)$ such that every element of $\mathbb F_q$ is a solution to $x^{2r(q)}=x^{r(q)}$ (hint: what is the order of $\mathbb F^*_q$)?
2. If $A$ is a matrix of a finite field, some power of a $A$ is diagonalizable (hint: it suffices to consider Jordan blocks and use the formula $(a+b)^p=a^p+b^p$ where $p$ is the characteristic).

Note that for step 2, we require the existence of Jordan normal form. Unfortunately, if the eigenvalues of $T$ don't lie in $\mathbb F_q$, we will have to pass to a larger field which does contain them. The simplest way is just to adjoin all the eigenvalues to $\mathbb F_q$, which yields a larger finite field. In particular, this implies that for part 1, we have to replace $q$ with $q^n$ (where $n$ depends on the eigenvalues of $T$).

-
Not every matrix over $\mathbb{F}_q$ has a Jordan form over $\mathbb{F}_q$: you need the characteristic polynomial to split. Of course, you can go to an extension of $\mathbb{F}_q$ and do the Jordan form there. – Arturo Magidin Aug 13 '11 at 18:18
Undoubtedly you know this, but just to make sure: The eigenvalues of $A$ (and hence also the Jordan blocks) may need elements of a finite extension field of $F_q$. But we can replace $F_q$ with the field $F_{q^m}$ generated by all those eigenvalues, and work with that instead. – Jyrki Lahtonen Aug 13 '11 at 18:21
@Arturo, Jyrki Yes, I am aware. See my comment under the main question. Editing my answer to make this more noticeable. – Aaron Aug 13 '11 at 18:33
@Aaron: Yup. +1 was already there. As you said in your comment to my answer: a method for getting (something like) an explicit value for $r$. – Jyrki Lahtonen Aug 13 '11 at 18:51

Lemma. Every polynomial $a(t) \in \mathbb{F}_q [t]$ divides $t^{rs} - t^r$, for some $r,s \geq 2$.

Proof. Pick $n$ such that $\mathbb{F}_{q^n}$ contains every root of $a(t)$ in a fixed algebraic closure $\overline{\mathbb{F}_q}$ of $\mathbb{F}_q$. So $t^{q^n} - t$ contains every prime factor of $a$. Therefore, if $q^m$ is greater than all multiplicities of the roots of $a$, $a \vert (t^{q^n} - t)^{q^m} = t^{q^{n+m}} - t^{q^m}$. Pick $r = q^m$ and $s = q^n$. $\square$

Now, let $f$ an endomorphism of a finite vector space $V$ over $\mathbb{F}_q$. Consider the minimal polynomial $m_f(t)$ of $f$. For the observation, there exist $r, s \geq 2$ such that $m_f(t) \vert t^{rs}- t^r$, therefore $f^{rs} = f^r$. Finally $P = f^{r(s-1)}$ is a projection because $P^2 = f^{rs} f^{r(s-2)} = f^r f^{r(s-2)} = f^{r(s-1)} = P$.

-
Nice. +1 for that Lemma alone. It shows up every now and then at surprising places. – Jyrki Lahtonen Aug 13 '11 at 18:55