Nilpotent matrices over finite fields

What sort of criterion is there for determining whether a matrix is nilpotent?

Specifically, I'm interested in the nilpotent matrices over finite fields. I realize that any such matrix will have to be singular, but if one repeatedly exponentiates a singular matrix over a finite field it will either return to its original value (without turning into the identity first) or turn into the zero matrix. So how can one know how the matrix is going to behave?

-
By definition, after many times of exponentiation (specifically man times $\leq$ the dimension of your matrix), it becomes 0. – Soarer Oct 5 '11 at 3:40
Well, not necessarily. Considering the singular matrix $$A=\left( \begin{array}{cc} 1 & 1 \\ 1 & 1 \\ \end{array} \right)$$ over, say, $\mathbb{F}_3$, multiplying A by any other 2x2 matrix doubles all of its entries. Doing this repeatedly in $\mathbb{F}_3$ will never reduce to the zero matrix. – Will Dana Oct 5 '11 at 3:58
but how is this matrix nilpotent? It has an eigenvalue 2. What is your definition of nilpotence? – Soarer Oct 5 '11 at 3:59
@Soarer gives probably the fastest way of settling this question. An answer?? Alternatively you could compute the characteristic polynomial (has to be $T^n$). Sometimes nilpotency is easier to decide on the side of the linear mappings. – Jyrki Lahtonen Oct 5 '11 at 4:00
Compute the characteristic polynomial. If it is $x^n$, then the matrix is nilpotent. If not, then the matrix is not nilpotent. – Matt E Oct 5 '11 at 4:02

If $A$ is $n\times n$ and nilpotent, then its characteristic polynomial will be $t^n$ (or $(-1)^nt^n$, depending on how exactly you define the characteristic polynomial).
By the Cayley-Hamilton Theorem, evaluating the polynomial at $A$ will be zero; thus, if $A$ is nilpotent, then necessarily $A^n = 0$. Conversely, if $A^n=0$, then $A$ is nilpotent.
Thus, it suffices to check if $A^n=0$. You can do this in $\lceil\log_2(n)\rceil$ steps by repeated squaring.