Welcome to our community

Be a part of something great, join today!

Minimal Polynomial Finding Algorithm

Sudharaka

Well-known member
MHB Math Helper
Feb 5, 2012
1,621
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?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
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...
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
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

Well-known member
MHB Math Helper
Feb 5, 2012
1,621
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? :)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
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

Well-known member
MHB Math Scholar
Feb 15, 2012
1,967
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.