Let $f:V\to V$ be a linear map, $\dim V =n$. A basis $( v_1, \ldots, v_n)$ of $V$ such that for all $j=1, \ldots,n$ the space $\text{span}(v_1,\ldots,v_j)$ is $f$-invariant is called a fan basis of $V$ w.r.t. $f$. Clearly, a basis is a fan basis iff the transformation matrix of $f$ w.r.t. to it is upper-triangular.
One can show that $V$ has a fan basis w.r.t. $f$ iff the characteristic polynomial of $f$ can be completely factored into linear factors over $\mathbb K$. All the proofs seem to show it via induction which doesn't demonstrate what's going on. The worked out examples of triangulating a matrix aren't quite illuminating either since one jumps to the change of basis matrices and crops the transformation matrices in such a way that I can't see how can one put it in terms of the original map $f$.
Say, our $f$ has $k$ pairwise distinct eigenvalues $\lambda_1, \ldots, \lambda_k$ and the characteristic polynomial of $f$ can be completely factored into linear factors. How do we find the fan basis $( v_1, \ldots, v_n)$ of $V$ w.r.t. $f$? (I am looking for a matrix-free explanation.)
I can start: take $v_1$ to be an eigenvector of $\lambda_1$.
Edit: I understand the Jordan normal form but finding the fan basis should be much easier, so I don't understand which parts of the Jordan procedure can be left out.
You won't get around finding generalised Eigenvectors of $f$, but for the first $v_1, \ldots, v_k$ you can chose the (usual) eigenvectors of $f$, since every eigenspace of $f$ is $f$-invariant. Now the next $f$-invariant spaces are precisely the generalised eigenspaces or direct sums thereof wich means you'll need to find $n-k$ generalised eigenvectors to get valid $v_i$ unless $f$ is diagonalisable (i.e. $k=n$).
Since the vectors in $\{v_i\}$ must always be generalised Eigenvectors, we can use a known fan basis to get the JNF of $f$ directly from it. This shows that finding a fan basis is equally difficult as finding the JNF. Note that to make this argument rigorous you need to see that the only $f$-invariant subspaces of $V$ are the direct sums of (generalised) Eigenspaces of arbitrary order.