I am trying to find a general step-by-step "easy" / "intuitive" solution to finding Jordan basis and Jordan matrix (based on the basis) for a nilpotent matrix.
If you can add an intuition for the steps and an example, it will be great! I will appreciate your help!
As I understand, we don't have to calculate the vectors we are adding while finding the basis: like $Av$ or $A^2v$ and we can see it on the $A$ or $A^2$ matrix as well — how? same on finding the joradn matrix based on the appropriate Jordan basis (without calculating $P^{-1}AP$) — how?
Not sure about easy or intuitional, but this one works for sure. As the matrix is nilpotent, all of its eigenvalues are $0$. So the only question is the size of Jordan blocks.
The number of Jordan blocks is the corank of $A$, which you can easily compute using Gaussian elimination. More generally, the number of at least $k\times k$ Jordan blocks for $k\geq 1$ is the rank of $A^{k-1}$ minus the rank of $A^{k}$, which, again you can easily compute using Gaussian elimination.
So you just need the rank of $A^k$ for $1\leq k \leq n$ at worst.
This requires at most $n$ Gaussian elimination processes, and the computation of the first (at most) $n$ powers of the matrix. So altogether, the runtime is $O(n^4)$. It is convenient that you calculate $A^n$: that way you can make sure that the matrix is indeed nilpotent. (An $n\times n$ matrix $A$ is nilpotent iff $A^n=0$.)
There are much smarter and quicker ways, but this is easy to understand.