# 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$ be a matrix in $n\times n$ matrix in a field 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 ?

-
Another way of saying the purported theorem: "the characteristic polynomial and the minimal polynomial are identical if and only if there exists a corresponding nonsingular Krylov matrix" –  Ｊ. Ｍ. Nov 19 '11 at 0:58
See also this question. –  Marc van Leeuwen Nov 19 '11 at 11:24

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 0) 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 necessary for $x$ to exist; the "if" part of your claim is therefore clear.

The "only if" part will follow from 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 is the somewhat more complicated part, that 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$, for otherwise multiplication by the other powers of irreducibles would give a polynomial of degree less than that of $p_M$ that would kill all $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 different irreducible polynomials, so it is 1 and $v=\vec0$. 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, so $x$ is a vector only annihilated by $p_M$ (and its multiples) whose existence 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 (whose name in English I unfortunately do not know) 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$.

-

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$.

-
I didn't get the hint. I do understand Marc van Leeuwen answer but I will love to have another argument. And it seems you have a different solution. Can you please elaborate? –  Lior B-S Nov 27 '12 at 19:31
If there exists an $x$ such that $x, Mx, \ldots, M^{n-1}x$ are linearly independent, then for every polynomial $f$ of degree less than $n$, we have $f(M)x \ne 0$, and hence $f(M) \ne 0$. That's probably what I was thinking when I wrote that a year ago. The converse is not as simple and I don't have an argument for it. –  Ted Nov 28 '12 at 4:43
Thanks! I have the feeling that one must follow some type of argument as in Leeuwen, because, even in the special case where the field is algebraically closed and $c_M=p_m=x^n$ I couldn't find a simpler argument... –  Lior B-S Nov 28 '12 at 6:56
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