Characteristic polynomial equals minimal polynomial iff $x, Mx, \ldots, M^{n-1} x$ are linearly independent I have been trying to compile conditions for when characteristic polynomials equal minimal polynomials and I have found a result that I think is fairly standard but I have not been able to come up with a proof for.  Any references to a proof would be greatly appreciated.
Let $M\in M_n(\Bbb F)$ and let $c_M$ be the characteristic polynomial of $M$ and $p_M$ be the minimal polynomial of $M$.

How do we show that $p_M = c_M$ if and only if there exists a column vector $x$ such that $x, Mx, \ldots M^{n-1} x$ are linearly independent ?

 A: Hint: Since $c_M$ has degree $n$, we have $p_M = c_M$ iff $f(M) \ne 0$ for all polynomials $f$ of degree less than  $n$.  
A: The statement you give is true, but it has simple and somewhat more complicated aspects. One has $p_M=c_M$ if and only if $\deg(p_M)=n$ (provided one defines $c_M$ so that it is always unitary), due to the Cayley-Hamilton theorem, which also ensures that $\deg(p_M)\leq n$ always. So your claim is that $\deg(p_M)\geq n$ if and only if for some $x$ the first $n$ iterated images by $M$ (starting from $M^0(x)=x$) are linearly independent. But the degree statement says that the first $n$ powers of $M$ are linearly independent in the vector space of matrices, which is certainly a necessary condition for $x$ to exist; therefore the "if" part of your claim is clear.
The "only if" part is a corollary to the existence of the Rational Canonical Form of a matrix, which is a block diagonal matrix similar to the original matrix, and whose blocks are companion matrices for a sequence of nonconstant monic polynomials, each one of which divides the next polynomial (if there is one). The minimal and characteristic polynomials of the RCF of$~M$, which are the same as those of$~M$ itself, are the last (least common multiple) respectively the product of the polynomials, and they are equal only if there is just one polynomial in the list. In that case $M$ is similar to a (single) companion matrix, and the first vector of the basis on which this form is obtained is$~x$ of the question (the other vectors are the images $M^i(x)$ for $i=1,\ldots,n-1$).
To show the second part without using the theory of rational canonical forms, one can prove a more general fact: for all $M$ there is a vector $x$ so that a polynomial in $M$ annihilates $x$ only of it annihilates the whole space. This  requires a bit of polynomial arithmetic. The only way I know to prove that involves decomposing $p_M$ into powers of irreducible polynomials, and the space into a direct sum of subspaces $V_i$ that are annihilated by those powers of irreducibles, evaluated in $M$. Assume for now that this is indeed a direct sum decomposition of the whole space. All $V_i$ are stable under $M$, and therefore under polynomials in $M$. If $p_i$ is the irreducible factor for $V_i$, and $m_i$ its multiplicity in $p_M$, then $p_i^{m_i-1}[M]$ will not annihilate all of $V_i$: otherwise multiplying $p_i^{m_i-1}$ by the other powers of irreducibles would give a polynomial of degree less than that of $p_M$ that would kill all the factors $V_i$, and therefore the whole space. So $V_i$ contains vectors $v_i$ not in $\ker(p_i^{m_i-1}[M])$.
The irreducible factor $p_i$ acts in an invertible way on any other $V_j$: if $p_i(M)$ kills some vector $v\in V_j$, the minimal polynomial killing $v$ divides two relatively prime polynomials $p_i$ and $p_j^{m_j}$, so it is $1$, which means that $v=0$. Therefore taking the sum $x$ of the vectors $v_i$ as indicated above, no proper divisor of $p_M$ evaluated in $M$ and applied to $x$ will annihilate all components in the direct sum decomposition. Then $x$ is a vector that is only annihilated by $p_M$ (and its multiples); it is the existence of such a vector that we wanted to show.
It remains to show that the sum of the spaces $V_i$ is direct and fill the whole space. This follows from a well known general result (sometimes referred to as Chinese remainder theorem) that for mutually coprime polynomials, the subspace $W$ annihilated by their product (evaluated in $M$) is the direct sum of those annihilated by the individual polynomials. For completeness here's a proof (you may have seen different ones). The general case follows by induction from the two-factor case. If $P,Q$ are coprime then the kernels $\ker_P,\ker_Q$ of $P[M]$ and $Q[M]$ are certainly contained in $W=\ker((PQ)[M])$, and we have seen that their intersection is the null subspace. Also $P[M](W)\subseteq\ker_Q$, which by the rank-nullity theorem means that $\dim(W)\leq\dim(\ker_P)+\dim(\ker_Q)$, and so necessarily $W=\ker_P\oplus\ker_Q$.
A: Let $M$ be an $n$ by $n$ matrix with coefficient in a field $K$; view $K^n$ as a $K[X]$-module, where the indeterminate $X$ acts as $M$; and let $\chi,\mu\in K[X]$ be the characteristic and minimal polynomials of $M$. 
Claim: $\chi=\mu$ if and only if $K^n\simeq K[X]/(f)$ for some $f$ in $K[X]$ (in which case we have $f=\chi=\mu$).
Proof: We can assume $\mu=g^m$ and $\chi=g^c$ for some irreducible polynomial $g$ in $K[X]$ and some positive integers $m\le c$. 
Then there is a unique non-decreasing tuple $(n_1,\dots,n_k)$ of positive integers such that 
$$
K^n\simeq\frac{K[X]}{(g^{n_1})}\oplus\cdots\oplus\frac{K[X]}{(g^{n_k})}\quad, 
$$ 
and we have $m=n_k$, $c=\sum n_i$. QED
A: Here is a simple proof for the "only if" part, using rational canonical form.
For clarity's sake, I'll assume that $M$ is a linear map.
If $M$ is such that $p_M=c_M$, then it is similar to $F$, the companion matrix of $p_M$.i.e. There is a basis $\beta = (v_1, \dots ,v_n)$ for $V$ under which the matrix of $M$ is $F$. Let $e_i (i \in \{1,\dots,n\})$ be the vector with $1$ as its $i$-th component and $0$ anywhere else, then $F^{i} e_{1} = e_{i+1}$ for $i \in \{1, \dots , n-1\}$. But $e_1, \dots , e_n$ are just the coordinates of the vectors $v_1, \dots , v_n$ under the basis $\beta$ itself. So this means that $M^i v_1 = v_{i+1}$ for $i \in \{1, \dots , n-1\}$. In other words, $(v_1, M v_1, \dots , M^{n-1} v_1) = (v_1, v_2, \dots , v_n)$ is a basis for $V$, which is of course linearly independent.
