# 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" –  Guess who it is. 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 $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$.

-

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

-

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.

-
The "only if" part is the statement that if $p_M=c_M$ then $M$ is similar to a companion matrix (namely if $x$ is a vector whose existence the "only if" part asserts, then the matrix of $A$ on the basis of $A^i(x)$ for $i=0,\ldots,n-1$ is a companion matrix). So if you just assume that fact, then I don't see what this answer really explains about the "only if" part. –  Marc van Leeuwen Apr 7 '14 at 13:08
@MarcvanLeeuwen No, I'm not assuming the existence of the vector $x$ in question. I'm proving it. Maybe your approach to establishing rational canonical forms depends on the conclusion of this post? But the approach I've learned doesn't (instead, it uses polynomial matrices, and passes from Smith form to rational form). Maybe it's not a satisfatory approach (too indirect), but at least it validates my argument - it's not a circular one. –  AaronS Apr 7 '14 at 13:54
Then I think I don't understand what you wrote. Where in your proof do you show that the basis $\beta$ (from which $x$ is taken) exists? You just say it exists because $M$ is similar to a companion matrix, but that is just saying there exists a basis on which $M$ is given by a companion matrix, so I just don't see where you are showing this. I know this can be deduced from the unique existence of a RCF, as I added to my answer, but in your answer this seems to be used without being said, before your actual argument even starts. –  Marc van Leeuwen Apr 7 '14 at 16:43