Minimal polynomial of matrix Find the minimal polynomial of the matrix M:
\begin{pmatrix}
0 & 0 & 0 & \dots & 0 & a_{1}\\
1 & 0 & 0 & \dots & 0 & a_{2}\\
0 & 1 & 0 & \dots & 0 & a_{3} \\
\dots & \dots \\
0 & 0 & 0 & \dots & 1 & a_{n}
\end{pmatrix}
Let's take vector $e_{1}$:
\begin{pmatrix}
1 \\
0 \\
\vdots\\
0
\end{pmatrix}
$M e_{1} = e_{2}$, $M e_{2} = e_{3}$, $M e_{3}= e_{4}\dots$.
$M^{n} e_{1}=(a_{1}\dots a_{n})$. 
Why does $x^{n}-(a_{1}+a_{2}x+\dots+a_{n}x^{n-1})=0$  be the minimal polynomial of this matrix? How does it connect with the dimension of image?  
 A: Your computation shows that $M^n(e_1)-a_nM^{n-1}(e_1)-\cdots-a_2M(e_1)-a_{1}e_1=0$, and since $e_1,M(e_1),\ldots,M^{n-1}(e_1)$ are linearly independent, no nonzero polynomial of lower degree than$~n$ has this property of the polynomial $P=x^n-a_nx^{n-1}-\cdots-a_2x-a_1$. Then the minimal polynomial $\mu$ of$~M$, which has $\mu[M](v)=0$ for every $v$, must be a polynomial multiple of$~P$.
By definition $\mu$ has leading coefficient$~1$, and you may know that $\deg\mu\leq n$ always holds (for instance from the Cayley-Hamilton theorem), and this implies that $\mu=P$ is the only possibility. One does not need to reason like that though, as one can directly show $P[M](v)=0$ to hold for every$~v$, by showing it for $v=M^k(e_1)$ with $0\leq k<n$, which for a basis of the vector space: $P[M](M^k(v))=M^k(P[M](v))=M^k(0)=0$ since $P[M]$ and $M^k$ commute.
A: Consider a monic polynomial $q(x) = b_nx^n + b_{n-1}x^{n-1} + b_{n-2}x^{n-2} + ... + b_1x + b_0$ of $M$ of degree $m\le n$ (if $m<n$, we have $b_m=1$ and $b_{m+1}=b_{m+2}=\cdots=b_n=0$) and let $\{e_1,e_2,\ldots,e_n\}$ be the standard basis of $\mathbb{R}^n$. If $q(M)=0$, we have, in particular,
$$q(M)e_1=b_n\sum_{i=1}^na_ie_i + b_{n-1}e_n + b_{n-2}e_{n-1} + ... + b_1e_2 + b_0e_1 = 0.\tag{1}$$
Note that $b_n\neq0$, or else $(1)$ would imply that all $b_i$s are zero, which is impossible. Therefore $b_n=1$ ($q$ is monic by definition). By comparing coefficients on both sides of $(1)$, we see that $q$ must be in the form of
$$q(x)=x^n-(a_{1}+a_{2}x+\dots+a_{n}x^{n-1}).\tag{2}$$
Now it is easy to verify that $q(M)e_i=0$ for all $i$. Hence the minimal polynomial of $M$ is given by $(2)$.
