First, let’s assume $f$ has a cyclic vector $v$. Then $B=\{v,f(v),...,f^{{n-1}}(v)\}$ is a basis for $V$. Suppose $g$ is a linear transformation which commutes with $f$. Consider the coordinates $(\alpha_{{0}},...,\alpha_{{n-1}})$ of $g(v)$ in B, that is

Let

We show that $g=P(f)$. For $w\in V$, write

then

Now, to finish the proof, suppose $f$ doesn’t have a cyclic vector (we want to see that there is a linear transformation $g$ which commutes with $f$ but is not a polynomial evaluated in $f$). As $f$ doesn’t have a cyclic vector, then due to the cyclic decomposition theorem $V$ has a basis of the form

Let $g$ be the linear transformation defined in $B$ as follows:

The fact that $f$ and $g$ commute is a consequence of $g$ being defined as zero on one $f$-invariant subspace and as the identity on its complementary $f$-invariant subspace. Observe that it’s enough to see that $g$ and $f$ commute in the basis $B$ (this fact is trivial). We see that, if $k=0,...,j_{{1}}-1$, then

If $k=j_{{1}}$, we know there are $\lambda_{{0}},...,\lambda_{{j_{{1}}}}$ such that

so

Now, let $i=2,...,r$ and $k_{{i}}=0,...,j_{{i}}-1$, then

In the case $k_{{i}}=j_{{i}}$, we know there are $\lambda_{{0,i}},...,\lambda_{{j_{{i}},i}}$ such that

then

and

This proves that $g$ and $f$ commute in $B$. Suppose now that $g$ is a polynomial evaluated in $f$. So there is a

such that $g=P(f)$. Then, $0=g(v_{{1}})=P(f)(v_{{1}})$, and so the annihilator polynomial $m_{{v_{{1}}}}$ of $v_{{1}}$ divides $P$. But then, as the annihilator $m_{{v_{{2}}}}$ of $v_{{2}}$ divides $m_{{v_{{1}}}}$ (see the cyclic decomposition theorem), we have that $m_{{v_{{2}}}}$ divides $P$, and then $0=P(f)(v_{{2}})=g(v_{{2}})=v_{{2}}$ which is absurd because $v_{{2}}$ is a vector of the basis $B$. This finishes the proof.