Equality of minimal and characteristic polynomial I'm trying to prove that for a companion matrix $C$ of a monic polynomial $f$, the minimal and the characteristic polynomial is the same. I am attempting a proof by Induction on the degree of $f$ but I'm not sure how to proceed:
$$ \deg(f)=2 \rightarrow f(x)=c_0+c_1x+x^2 \rightarrow C=\begin{bmatrix} 0&-c_0 \\ 1 & -c_1
\end {bmatrix}, \det(xI_n-C)=c_0+c_1x+x^2.\ f\text{ is minimal.}$$
$$ \deg(f)=n \rightarrow f(x)=c_0+c_1x+...+c_{n-1}x^{n-1}+x^n \rightarrow C= \begin{bmatrix} 0&0&0 &...&-c_0 \\ 1 & 0&0&...&-c_1 \\0 & 1 & 0&...&-c_2\\\vdots & \vdots & \vdots &\dots & \vdots \\ 0&0&0 &\dots 1&-c_{n-1}
\end {bmatrix}$$
$$\deg(f)=n+1 \rightarrow f(x)=c_0+c_1x+...+c_nx^n +x^{n+1}\rightarrow C=\begin{bmatrix} 0&0&0 &...&-c_0 \\ 1 & 0&0&...&-c_1 \\0 & 1 & 0&...&-c_2\\\vdots & \vdots & \vdots &\dots & \vdots \\ 0&0&0 &\dots 1&-c_{n}
\end {bmatrix}$$ Then I use the laplace expansion for determinants: $$\det(C)=\sum_{j=1}^{n+1}(-1)^{i+j} C_{i,j} M_{i,j}=\sum_{j=1}^{n+1}(-1)^{i+j} C_{i,j} |C_n|=$$
Here is where I'm stuck I don't know how to expand the sum to show that what I get is the  characteristic polynomial of $f$ with higher degree and I don't know how I can show that it has the smallest degree while satisfying $f(C)=0$.
 A: You can show that $\ f(x)\ $ is the characteristic polynomial of its companion matrix by induction.  You've already shown it for $\ \deg f(x)=2\ $ (and it's also true for $\ \deg f(x)=1\ $), so now suppose it's true for all polynomials of degree $\ n\ $, and let $\ f(x)=x^{n+1}+\sum_\limits{i=0}^nc_ix^i\ $ be an arbitrary monic polynomial of degree $\ n+1\ $.  The characteristic polynomial of the companion matrix of $\ f(x)\ $ is
$$
g(x)=\det\pmatrix{x&0&0&\dots&c_0\\
-1&x&0&\dots&c_1\\
0&-1&x&\dots&c_2\\
\vdots&&\ddots&\ddots&\vdots\\
0&0&0&\dots&x+c_n}\ .
$$
Expanding out this determinant by its first row gives
\begin{align}
&g(x)=\\
&x\det\pmatrix{x&0&0&\dots&c_1\\
-1&x&0&\dots&c_2\\
0&-1&x&\dots&c_3\\
\vdots&&\ddots&\ddots&\vdots\\
0&0&0&\dots&x+c_n}+(-1)^nc_0\det\big(-I_{n\times n}\big)\ .
\end{align}
Now the first determinant in the above expression is the characteristic polynomial of the companion matrix of the monic polynomial $\ x^n+\sum_\limits{i=0}^{n-1}c_{i+1}x^i\ $ of degree $\ n\ $, which is therefore also its characteristic polynomial by our induction hypothesis. Therefore
\begin{align}
g(x)&=x\left(x^n+\sum_{i=0}^{n-1}c_{i+1}x^i\right)+c_0\\
&=f(x)\ ,
\end{align}
which completes the proof by induction.
To show that $\ f(x)\ $ is also the minimal polynomial of its companion matrix, $\ C\ $, say, first note that
\begin{align}
e_1C&=c_0e_n\ ,\ \text{ and}\\
e_iC&=e_{i-1}+c_{i-1}e_n
\end{align}
for $\ i=2,\dots,n\ $, where $\ f(x)= x^n+\sum_\limits{i=0}^{n-1}c_ix^i\ $, and $\ e_i\ $ is the $\ i^{\,\text{th}}\ $ row of the $\ n\times n\ $ identity matrix. It follows from this that $\ e_nC^j=$$\,e_{n-j}+\sum_\limits{i=n-j+1}^na_{ji}e_i$ for $\ j\le n-1\ $ and some scalars $\ a_{ji}\ $.  In light of the Cayley-Hamilton theorem, the characteristic polynomial of $\ C\ $ will be its minimal polynomial if it doesn't satisfy any non-zero polynomial equation of degree less than $\ n\ $.  Suppose, therefore, that
$$
\sum_{k=0}^{n-1}d_kC^k=0\ .
$$
Multiplying this equation on the left by $\ e_n\ $ gives
\begin{align}
0&=\sum_{k=0}^{n-1}d_ke_nC^k\\
&=\sum_{k=0}^{n-1}d_k\left( e_{n-k}+\sum_{i=n-k+1}^na_{ki}e_i\right)\\
&=d_{n-1}e_1+ \sum_{k=0}^{n-2}d_k\left( e_{n-k}+\sum_{i=n-k+1}^na_{ki}e_i\right)\ .
\end{align}
The first entry in the row vector on the left of this last equation is $\ d_{n-1}\ $ which must therefore be zero. Therefore, we now have
\begin{align}
0&=\sum_{k=0}^{n-2}d_k\left( e_{n-k}+\sum_{i=n-k+1}^na_{ki}e_i\right)\\
&=d_{n-2}e_2+ \sum_{k=0}^{n-3}d_k\left( e_{n-k}+\sum_{i=n-k+1}^na_{ki}e_i\right)\ .
\end{align}
Now the second entry in the row vector on the left of this equation is $\ d_{n-2}\ $, which must also be zero.  Continuing in this way, we get $\ d_{n-1}=$$\,d_{n-2}=$$\,\dots=$$\,d_2=0\ $, and we're left with
\begin{align}
0&=d_1e_nC^1+d_0e_nC^0\\
&=d_1e_{n-1}+\big(d_0+d_1c_0\big)e_n\ ,
\end{align}
from which it follows that $\ d_0=d_1=0\ $. Thus, the only polynomial equation of degree less than $\ n\ $ that $\ C\ $ satisfies is the trivial one in which the polynomial is zero.  Therefore, its minimal polynomial is $\ f(x)\ $.
A: A much shorter proof.
Clearly, we have that the minimal polynomial satisfies $p(C)=0$, and that this must imply that $p(C)e_1=0$. Note also that we have that $Ce_i=e_{i+1}$ for $i=1,\ldots,n-1$.
Now, assume that the minimal polynomial is of degree $k<n$ and takes the form
$$p(s)=s^k+p_{k-1}s^{k-1}+\dots+p_0.$$
So, we have that $p(C)=0$, which must also imply that
$$p(C)e_1=e_{k+1}+p_{k-1}e_k+\ldots+p_0e_1=0.$$
But this yields a contradiction since the vectors $\{e_{k+1},e_k,\ldots,e_1\}$ are independent.
Therefore, we must have that $k\ge n$, which proves that the degree of the characteristic polynomial and that of the minimal polynomial must be the same.
