How can one show that a matrix is nilpotent or not?

Question

Context: In linear algebra, a nilpotent matrix is a square matrix $N$ such that $$ N^{k}=0\, $$ for some positive integer $k$. (The smallest such $k$ is sometimes called the index of $N$.)

Question: How can one show that a matrix is nilpotent or not? Direct matrix multiplication for checking the definition is an obvious choice but seems not efficient. Is there any other method to do it?

Answer 1

A matrix is nilpotent iff its only eigen value (in the algebraic closure of the base field) is $0$. This follows easily from Caley - Hamilton Theorem. See https://en.wikipedia.org/wiki/Cayley%E2%80%93Hamilton_theorem

Thanks to Kezer for pointing out the taking the algebraic closure is needed.

Answer 2

It is useless considering the algebraic closure of the base field $K$. Indeed, to calculate the $A$'s eigenvalues, ​​using standard numeric methods, is a bad idea because (in general) we only get approximations of them.

Assume, for example, that $A\in M_n(\mathbb{Z})$ ($\mathbb{Z}$ is not even a field). We are led to show that

i) or $\det(xI-A)=x^n$. The calculation can be done (using an elaborate software) in $O(n^3)$ operations. Yet, when $n$ is large, the coefficients may be very large; in binary operations, the complexity can be reduced (via a complicated software) to $(n^{3.2}\log(max(|a_{i,j}|)))^{1+o(1)}$, cf.

https://perso.ens-lyon.fr/gilles.villard/BIBLIOGRAPHIE/PDF/KaVi04.pdf

ii) Either $A^k=0$ where $k\geq n$; we calculate $A^n$ with the binary method $A^2,A^4,\cdots$. We calculate $O(\log n)$ products, that is, using $O(n^3\log n)$ operations. As in i), the entries may be very large; then, in elemetary operations, the complexity is at least in $O(n^4\log n)$.