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?
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.