What is an algorithm to compute the minimal polynomial?

For characteristic polynomial, there is a very straight forward algorithm.

Compute $\det(\lambda I - A) = 0$

Now I have looked for the method for calculating minimal polynomial everywhere but could not find an algorithm even for a 2x2 case.

Give a simple matrix, say

$A = \begin{bmatrix}a&b\\c&d\end{bmatrix}$

How can we calculate its minimal polynomial?

• you can try to solve linear equations, check whether or not \begin{align*} A&\in kI\\ A^2&\in kA+kI\\ A^3&\in kA^2+kA+kI\\ &\text{etc.} \end{align*} – yoyo Mar 6 '15 at 1:42
• yoyo how does this help I am desperate – Carlos - the Mongoose - Danger Mar 6 '15 at 1:43

For the 2 x 2 case, here's an algorithm: Compute the characteristic polynomial. If it's not a perfect square, then it actually IS the minimal polynomial. If it IS a perfect square, say $(x - a)^2$, then your matrix is either $aI$, in which case the minimal polynomial is $(x-a)$, or it's not, in which case the minimal polynomial is $(x-a)^2$.

Why does this work? 1. The minimal polynomial always divides the characteristic polynomial.

1. The minimal polynomial of the Jordan form is the same as the minimal polynommial of $M$. If $M$ has two distinct eigenvalues, then its jordan form is $$\begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix}$$ and it's evident that the minimal polynomial of this is $(x - \lambda_1)(x - \lambda_2)$.

If it has duplicate eigenvalues, then the Jordan form looks like either $$\begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_1 \end{bmatrix}$$ or $$\begin{bmatrix} \lambda_1 & 1 \\ 0 & \lambda_1 \end{bmatrix}$$ In the first case, your matrix is conjugate to $\lambda_1 I$, hence must equal $\lambda_1 I$, whose minimal polynomial is $(x - \lambda_1)$.

In the second case, the matrix doesn't satisfy that polynomial, so the min poly must have two $(x - \lambda_1)$ factors, hence must be $(x - \lambda_1)^2$.

• Can you illustrate with an example for my pea brain for the second case? – Carlos - the Mongoose - Danger Mar 6 '15 at 1:48
• Any reference helps – Carlos - the Mongoose - Danger Mar 6 '15 at 1:48
• I hope my additional comments clarify things. – John Hughes Mar 6 '15 at 1:52