The characteristic and minimal polynomial of a companion matrix The companion matrix of a monic polynomial $f \in \mathbb F\left[x\right]$ in $1$ variable $x$ over a field $\mathbb F$ plays an important role in understanding the structure of finite dimensional $\mathbb F[x]$-modules.
It is an important fact that the characteristic polynomial and the minimal polynomial of $C(f)$ are both equal to $f$. This can be seen quite easily by induction on the degree of $f$.
Does anyone know a different proof of this fact? I would love to see a graph theoretic proof or a non inductive algebraic proof, but I would be happy with anything that makes it seem like more than a coincidence!

This is essentially Yuval's answer expressed in a slightly different way.
Let your companion matrix be
$$C=\pmatrix{0&1&0&\cdots&0\\\\
0&0&1&\cdots&0\\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\\
0&0&0&\cdots&1\\\\
-a_0&-a_1&-a_2&\cdots&-a_{n-1}}.$$
Then for the vector $v=(1\,\,0\,\,0\cdots 0)$,
$$v\sum_{j=0}^{n-1} b_j C^j=
\pmatrix{b_0&b_1&b_2&\cdots&b_{n-1}}$$
so that $g(C)\ne0$ for all nonzero polynomials $g$ of degree less than $n$.
So the minimal polynomial has degree $n$, and equals the
characteristic polynomial (via Cayley-Hamilton).
But $vC^n=(-a_0\,\, {-a_1}\,\, {-a_2}\cdots{-a_{n-1}})$
and for $v(C^n+\sum_{j=0}^{n-1}b_j C^j)=0$ we need $a_j=b_j$. So the minimal
and characteristic polynomials both equal $f$.
