Search for probability and statistics terms on Statlect
StatLect
Index > Matrix algebra

Minimal polynomial

by , PhD

The minimal polynomial is the annihilating polynomial having the lowest possible degree.

Table of Contents

Definition

In the next definition and in the remainder of this lecture, matrices, variables and coefficients of polynomials are assumed to be complex.

Definition Let A be a $K	imes K$ matrix. An annihilating polynomial p (i.e., such that [eq1]) is called a minimal polynomial of A if and only if it is monic and no other monic annihilating polynomial of A has lower degree than p.

Here is a very simple example.

Example Consider the $K	imes K$ identity matrix I. Then, the polynomial [eq2]is monic (its leading coefficient is equal to 1) and it is annihilating for I because[eq3]The polynomial p has degree 1. There are no other monic annihilating polynomials of lower degree because the only monic polynomial of degree lower than 1 is[eq4]which is not annihilating. Therefore, p is the minimal polynomial of A.

Existence and uniqueness

A minimal polynomial always exists and it is unique.

Proposition The minimal polynomial of a matrix A exists.

Proof

The set of annihilating polynomials has at least a monic member because the characteristic polynomial of A is a monic annihilating polynomial by the Cayley-Hamilton theorem. Moreover, there is a lower bound to the degree of monic annihilating polynomials ([eq5]).

Proposition The minimal polynomial of a matrix A is unique.

Proof

The proof is by contradiction. Assume that $p_{1}$ and $p_{2}$ are two distinct minimal polynomials. It must be that [eq6] (otherwise one of the two is not minimal). Now consider the annihilating polynomial[eq7]Since $p_{1}$ and $p_{2}$ are monic and have the same degree, their difference has at least one degree less than they have. We can divide p by its leading coefficient (which is different from zero because $p_{1}$ and $p_{2}$ are distinct) and obtain a monic annihilating polynomial that has a lower degree than $p_{1}$ and $p_{2}$. Hence, $p_{1}$ and $p_{2}$ are not minimal polynomials, a contradiction.

How to derive the minimal polynomial

In this section we present an algorithm for finding the minimal polynomial of a $K	imes K$ matrix A.

We start by asking whether there is an annihilating polynomial among the monic polynomials of degree 1, that is, those taking the form[eq8] If there is one, then it can be found by searching for the coefficient $a_{0} $ that solves the equation[eq9]

If the equation has a solution, then we have found the minimal polynomial. Otherwise, we search for a monic annihilating polynomial of degree $2$, whose coefficients must solve the equation[eq10]

If there is a solution, then we have found the minimal polynomial. If not, we increase the degree of the polynomial and we keep increasing it until we find the minimal polynomial. We are guaranteed to find it in the first K steps because the Cayley-Hamilton theorem guarantees that $A^{K}$ can be written as a linear combination of lower powers of A.

Example Let us search for the minimal polynomial of the matrix [eq11]There is no coefficient $a_{0}$ solving[eq12]The square of A is[eq13]and the equation[eq14]is solved by $a_{1}=-5$ and $a_{0}=6$. Thus, the minimal polynomial of A is[eq15]

Divisor of other polynomials

Every annihilating polynomial is a multiple of the minimal polynomial.

Proposition The minimal polynomial of A divides every annihilating polynomial of A.

Proof

Denote the minimal polynomial by p. Let $p_{1}$ be any other annihilating polynomial. It must be that [eq16] (otherwise p is not minimal). By the Division Algorithm, we have[eq17]where [eq18] (the case $q=0$ and $r=p_{1}$ is excluded by the fact that [eq19]). Moreover,[eq20]Thus, the remainder $r$ is an annihilating polynomial. If $r$ is not identically equal to zero, it can be divided by its leading coefficient and it becomes a monic annihilating polynomial whose degree is less than that of p, which contradicts the hypothesis that p is a minimal polynomial. Therefore, $r$ must be identically equal to zero and[eq21]In other words, p divides every other annihilating polynomial.

Similarities with the characteristic polynomial

Remember that the characteristic polynomial of a matrix A is [eq22]where I is the identity matrix.

Also remember that, by the fundamental theorem of algebra, any polynomial p of degree $mgeq 1$ can be factorized as[eq23]where [eq24] are roots of p and k is a constant. The factorization is unique up to a permutation of the factors.

The linear factors $z-lambda _{j}$ are not necessarily distinct, that is, two or more linear factors can be equal to each other. If the same linear factor appears mu times in the factorization, then we say that is has multiplicity mu.

In the case of the characteristic polynomial $cleft( z
ight) $, $k=1$ and the roots are the eigenvalues of A. If the same eigenvalue shows up in more than one linear factor, then we say that the eigenvalue is repeated.

Proposition Let A be a matrix with characteristic polynomial [eq25]where [eq24] are the distinct eigenvalues of A and [eq27] are their respective algebraic multiplicities. Then, the minimal polynomial of A is[eq28]where [eq29] for $j=1,ldots ,m$.

Proof

The minimal polynomial p divides every annihilating polynomial, including the characteristic polynomial $c$, which is annihilating by the Cayley-Hamilton theorem. Therefore, the minimal polynomial p must have the form[eq30]where [eq31] for $j=1,ldots ,m$. We are going to prove by contradiction that $
u _{j}>0$. Suppose that $
u _{j}=0$ for some $j$. Then $lambda _{j}$ is not a root of $pleft( z
ight) $, that is,[eq32]But [eq33] is an eigenvalue of $pleft( A
ight) $ (see eigenvalues of a matrix polynomial), which implies that [eq34]because the zero matrix has only zero eigenvalues. This is impossible because p is an annihilating polynomial. Thus, we have arrived at a contradiction and it must be that $
u _{j}>0$ for every $j$.

Proposition If a matrix has no repeated eigenvalues, then its characteristic and minimal polynomial coincide.

Proof

If there are no repeated eigenvalues, then we have [eq35] in the previous proof, which implies[eq36]because $
u _{j}>0$ for $j=1,ldots ,m$.

Similar matrices have the same minimal polynomial

Remember that two matrices A and $B$ are similar if and only if there exists an invertible matrix $P$ such that[eq37]

It turns out that similar matrices have the same minimal polynomial.

Proposition Let A and $B$ be two similar $K	imes K$ matrices. Then, the minimal polynomials of A and $B$ coincide.

Proof

Let p be a polynomial[eq38]Then,[eq39]or[eq40]If p is an annihilating polynomial of A, then [eq41] and[eq42]which implies that [eq43] because $P$ is invertible (hence the only way to get zero vectors by combining its columns is to set all the coefficients equal to zero). Similarly, [eq43] implies [eq45]. Hence, p is an annihilating polynomial of A if and only if it is an annihilating polynomial of $B$. In other words, the sets of annihilating polynomials of the two matrices coincide. As a consequence, also their respective minimal polynomials need to coincide (because they are the lowest-degree monic polynomials in the respective sets of annihilating polynomials).

A key take-away from the proof of the proposition is that not only two similar matrices have the same minimal polynomial, but they have the same set of annihilating polynomials.

Understanding and interpreting the minimal polynomial

In order to fully understand the minimal polynomial, we need to study the Primary Decomposition Theorem, which provides the key to interpreting the exponents [eq46] of the linear factors of the minimal polynomial.

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

Let A be a $3	imes 3$ matrix with eigenvalues $lambda _{1}=2$, $lambda _{2}=1$, $lambda _{3}=-1$. Derive the minimal polynomial of A.

Solution

Since A has no repeated eigenvalues, then its characteristic and minimal polynomial coincide. Therefore, the minimal polynomial of A is[eq47]

Exercise 2

Find the minimal polynomial of the matrix[eq48]

Solution

The equation [eq49]has clearly no solution. The square of A is[eq50]The equation[eq51]is written explicitly as[eq52]It has no solution because the $left( 2,3
ight) $-th entry of $A^{2}$ is equal to $-1$ and it cannot be replicated by taking a linear combination of two zero entries (the $left( 2,3
ight) $-th entries of I and A). The third power of A is[eq53]The Cayley-Hamilton theorem guarantees that we can find a solution of[eq54]or[eq55]The solution is $a_{0}=1$ (found by solving for the $left( 3,3
ight) $-th entry of $A^{3}$), $a_{2}=-3$ (found by solving for the $left( 2,3
ight) $-th entry of $A^{3}$), $a_{1}=2$ (found by solving for any other entry of $A^{3}$). Thus, the minimal polynomial of A is[eq56]

How to cite

Please cite as:

Taboga, Marco (2017). "Minimal polynomial", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/minimal-polynomial.

The book

Most of the learning materials found on this website are now available in a traditional textbook format.