Minimalpolynomial of a Matrix without calculating the characterstic polynomial

Is there a way calculating the minimal polynomial of a matrix without using the characteristic polynomial?

For example following matrix $$M = \left( \begin{array}{cccc} 1 & 0 & -2 & 0 \\ -2 & -1 & 4 & 2 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 2 & 1 \\ \end{array} \right).$$

Calculating the characteristic polynomial I get $\chi_M = (x-1)^2(x+1)^2$ with eigenvalues $-1$ and $1$ with algebraic multiplicity 2. Using the characteristic polynomial I have to check all possibilities for the minimal polynomial $\mu_M$ which are $$(x-1), (x-1)^2, (x+1), (x+1)^2, (x-1)(x+1), (x-1)^2(x+1), (x-1)(x+1)^2, (x-1)^2(x+1)^2.$$

Is there a way to see from the form of the matrix, what the minimal polynomial could be? Since $M$ could be partitioned as follows:

$$M = \left( \begin{array}{cccc} 1 & 0 & -2 & 0 \\ -2 & -1 & 4 & 2 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 2 & 1 \\ \end{array} \right)= \left( \begin{array}{cc} A & B \\ 0 & C \\ \end{array} \right),$$ with $A =\left( \begin{array}{cc} 1 & 0 \\ -2 & -1 \\ \end{array} \right), B = \left( \begin{array}{cc} -2 & 0 \\ 4 & 2 \\ \end{array} \right)$ and $C = \left( \begin{array}{cc} -1 & 0 \\ 2 & 1 \\ \end{array} \right)$.

• the minimal polynomial can be "see" from the Jordan canonical form of your matrix: glimpse wolframalpha.com/input/…, so the answer is $\mu_M(x)=(x+1)(x-1)$ – janmarqz Sep 19 '15 at 16:59
• @janmarqz: Using the Jordan canonical form to compute a minimal polynomial is putting the cart before the horse. Can you compute the JCF without calculating (and factoring!) the characteristic polynomial? – Marc van Leeuwen Oct 4 '15 at 5:16
• hey @MarcvanLeeuwen, in a formal scene you are right but in an informal setting anyone should use robots (like wolframalpha) to see what is happening – janmarqz Oct 4 '15 at 13:46

I'll answer the general question of how to compute a minimal polynomial$~\mu$ of $M$ without using the characteristic polynomial, and only then apply it specifically for this matrix, which has very special features that facilitate computing the minimal polynomial.

The easy to state (but not so easy to perform) method for finding$~\mu$ is to compute successive powers of your matrix $M^0=I,M,M^2,\ldots$, and check each time whether it is a linear combination of previous powers. This is bound to happen at or before the power $M^n$, where $n$ is the matrix size; if the first relation found is $M^d=c_0I+c_1M+\cdots+c_{d-1}M^{d-1}$, then $\mu=X^d-c_{d-1}X^{d-1}-\cdots-c_1C-c_0$.

Easier in practice is to pick some nonzero vector $v$ (some standard basis vector will do fine) and similarly compute a sequence of vectors $v,Mv,M^2v,\ldots$, and again find the first linear dependence, leading similarly to the minimal degree monic polynomial $P\in K[X]$ such that $P[M]v=0$. This polynomial may not yet be $~\mu$ but is guaranteed to divide $\mu$. However in the (likely) case that $d=\deg P$ equals $n$, this divisibility implies $\mu=P$, and you can stop here. Assuming this did not happen (so $d<n$), it remains to find the quotient$~Q=\mu/P$, which is the minimal degree monic polynomial such that $Q[M]P[M]=0$, in other words such that $Q[M]$ vanishes in the image subspace $P[M](K^n)$; one can compute that subspace, and if it is nonzero continue recursively to compute $Q$ using a nonzero vector of $P[M](K^n)$. Since $P[M]$ is known to kill each of the independent vectors $v,Mv,M^2v,\ldots M^{d-1}v$, one can complete that to a basis of $K^n$ and compute $P[M](K^n)$ using just the added vectors.

So here is how it works for your matrix $M$. With $v=e_1$, the vectors $v$ and $Mv=(1,-2,0,0)$ are linearly independent, but $M^2(v)=(1,0,0,0)$ is dependent on them, in fact $M^2v=v$ so we get $P=X^2-1$ and $d=2$. Since $d<n$ we must continue, so complete $v,Mv$ to a basis of $K^4$, for which $e_3,e_4$ will do fine. On has $P[M](e_3)=M^2e_3-e_3=e_3-e_3=0$ (amazing coincidence) and $P[M](e_4)=M^2e_4-e_4=e_4-e_4=0$ (another amazing coincidence), so one has $P[M](K^4)=0$, which is "annihilated" by $Q=1$, so $\mu=QP=P=X^2-1$ after all. It would have been more fun, and more instructive, if the last two columns had not been so very special.

• One can also compute the minimal polynomial for each element in a basis and then compute the lcm of all of them. – Mariano Suárez-Álvarez Oct 4 '15 at 5:25

In fact, if we take $$A = \pmatrix{1&-2\\0&-1}, \quad B = \pmatrix{1&0\\-2&-1}$$ Then we have $$M = \pmatrix{a_{11}B & a_{12}B\\a_{21}B & a_{22}B} = A \otimes B$$ Where $\otimes$ denotes the Kronecker product. Since both $A$ and $B$ have eigenvalues $\{-1,1\}$, $A \otimes B$ will have the spectrum $\{-1,-1,1,1\}$.

Note also that the Kronecker product of diagonalizable matrices is diagonalizable, so $M$ must have the minimal polynomial $q_M(x) = (x-1)(x+1)$.

In general, the exponent of a linear term in the minimal polynomial of $A \otimes B$ cannot exceed any of the exponents in the minimal polynomials of $A$ or $B$.

In fact, given the Jordan forms of $A$ and $B$, we can deduce the Jordan form of $A \otimes B$.

Another approach: the characteristic polynomial of a matrix of the form $$M = \pmatrix{A&B\\0&C}$$ with $A,C$ square will be $\chi_M(x) = \chi_A(x)\chi_C(x)$.

• Yes, because it's a block matrix. But I don't know, if it's possible to calculate the minimal polynomial without the characteristic polynomial. – monoid Sep 19 '15 at 18:57
• Oh, I missed that bit. You can infer the minimal polynomial (and Jordan form) using the kronecker product, but not generally using the upper-triangular bit. I'll clarify that when I have the chance. – Omnomnomnom Sep 19 '15 at 22:05