Minimal Polynomial Finding Algorithm

[Sudharaka]

Hi everyone, :)

This is one of the thoughts that I got after thinking about finding the minimal polynomial of a matrix. I know that the minimal polynomial is easy to find when a matrix is diagonalizable. Then the minimal polynomial only consist all the distinct linear factors of the characteristic polynomial.

But the problem is how do we find the minimal polynomial of a matrix in the general case? Is there a specific method to do so?

 

[I like Serena]

Hi everyone, :)

This is one of the thoughts that I got after thinking about finding the minimal polynomial of a matrix. I know that the minimal polynomial is easy to find when a matrix is diagonalizable. Then the minimal polynomial only consist all the distinct linear factors of the characteristic polynomial.

But the problem is how do we find the minimal polynomial of a matrix in the general case? Is there a specific method to do so?

To find the minimal polynomial you basically need the same information as you need for the Jordan normal form...

 

[I like Serena]

For the record, the wiki article gives an alternative way to find the minimal polynomial.
Note that this also gives you the information you need to construct the Jordan normal form.

 

[Sudharaka]

For the record, the wiki article gives an alternative way to find the minimal polynomial.
Note that this also gives you the information you need to construct the Jordan normal form.

Great. Thanks for the information. But I didn't quite understand the method that the wiki article speaks about. Let us take the matrix,

\[T=\begin{pmatrix}-1&-5&0\\0&1&1\\0&0&1\end{pmatrix}\]

The eigenvalues are \(1,\,1\mbox{ and }-1\). Now the characteristic polynomial is, \((x+1)(x-1)^2\). So if we follow the procedure of the wiki article we have,

\[e_1=\begin{pmatrix}1\\0\\0\end{pmatrix}\]

\[T.e_1=\begin{pmatrix}-1\\0\\0\end{pmatrix}\]

I feel that I am doing something wrong here, 'cause then I would get the minimal polynomial as, \(x+1\) which is obviously not the case. Can you tell me what I am doing wrong.

To find the minimal polynomial you basically need the same information as you need for the Jordan normal form...

Okay, so in the case of the Jordan normal form we have to find the dimension of the kernel for each eigenvalue so that we can get the number of Jordan blocks. Can you please elaborate a little bit about how this is the same in the case of finding the minimal polynomial? :)

 

[I like Serena]

Great. Thanks for the information. But I didn't quite understand the method that the wiki article speaks about. Let us take the matrix,

\[T=\begin{pmatrix}-1&-5&0\\0&1&1\\0&0&1\end{pmatrix}\]

The eigenvalues are \(1,\,1\mbox{ and }-1\). Now the characteristic polynomial is, \((x+1)(x-1)^2\). So if we follow the procedure of the wiki article we have,

\[e_1=\begin{pmatrix}1\\0\\0\end{pmatrix}\]

\[T.e_1=\begin{pmatrix}-1\\0\\0\end{pmatrix}\]

I feel that I am doing something wrong here, 'cause then I would get the minimal polynomial as, \(x+1\) which is obviously not the case. Can you tell me what I am doing wrong.

Checking each of the unit vectors we find the minimal relations:

\begin{array}{lclclcl}
Te_1 &=& -e_1 &\Rightarrow &(T+I)e_1 &=& 0 \\
T^2e_2 &=& e_2 &\Rightarrow &(T-I)^2e_1 &=& 0 \\
T^3e_1 &=& T^2e_3 + Te_3 - e_3 &\Rightarrow &(T^3-T^2-T+I)e_3 &=& 0
\end{array}

Each of those polynomials are minimal for their respective vectors.
Therefore each of them must divide the minimal polynomial.
Their least common multiple is the minimal polynomial.

It becomes a bit easier since for $e_3$ we find a 3rd order polynomial which therefore has to be the minimal polynomial.

Okay, so in the case of the Jordan normal form we have to find the dimension of the kernel for each eigenvalue so that we can get the number of Jordan blocks. Can you please elaborate a little bit about how this is the same in the case of finding the minimal polynomial?

We are looking for powers of $(T-\lambda I)$ such that it just annihilates and becomes the null matrix.
Suppose you have a 3x3 (sub) matrix in the form of a Jordan block. Which power do you need before it becomes the null matrix?
Generally, the size of the largest Jordan block for an eigenvalue is the power you need for that eigenvalue.

 

[Deveno]

If the size (the "n" of an nxn matrix) is small enough, the minimal polynomial can be found by trial-and-error.

If the eigenvalues of $T$ are $\lambda_1,\dots,\lambda_r$, then:

$\mu_T(x) = (x - \lambda_1)^{k_1}\dots(x - \lambda_r)^{k_r}$

so one just has to determine the integers $k_j$.

For example, if n = 4, we have the following possibilities:

1) 4 eigenvalues
2) 3 eigenvalues
3) 2 eigenvalues
4) 1 eigenvalue

Case (1) is easy, and case (4) isn't much harder (only four 4 powers of a linear factor to try).

Case (2) also isn't that bad, either the minimal polynomial is:

$(x - a)^2(x - b)(x - c)$

or

$(x - a)(x - b)(x - c)$

So if the latter polynomial doesn't annihilate $T$ there are just 3 other candidates to try. If the field $F$ that $T$ has entries in isn't algebraically closed, sometimes the field that the eigenvalues lie in can give us some clues: for example, suppose we have a 4x4 rational matrix with 2 complex eigenvalues. Either the minimal polynomial has degree 4 (and is the characteristic polynomial), or it is a real quadratic.

Another example:

Suppose you have a 4x4 matrix $T$ with characteristic polynomial $x^4 - 1$, and 2 eigenvalues 1,-1. The only possible minimal polynomials are:

$x^2 - 1$
$x^4 - 1$

because the cubics:

$(x^2 - 1)(x + 1)$
$(x^2 - 1)(x - 1)$

do not divide the characteristic polynomial.