Linear Algebra/Polynomials of Maps and Matrices

< Linear Algebra
Linear Algebra
 ← Jordan Form Polynomials of Maps and Matrices Jordan Canonical Form → 

Recall that the set of square matrices is a vector space under entry-by-entry addition and scalar multiplication and that this space has dimension . Thus, for any matrix the -member set is linearly dependent and so there are scalars such that is the zero matrix.

Remark 1.1

This observation is small but important. It says that every transformation exhibits a generalized nilpotency: the powers of a square matrix cannot climb forever without a "repeat".

Example 1.2

Rotation of plane vectors radians counterclockwise is represented with respect to the standard basis by

and verifying that equals the zero matrix is easy.

Definition 1.3

For any polynomial , where is a linear transformation then is the transformation on the same space and where is a square matrix then is the matrix .

Remark 1.4

If, for instance, , then most authors write in the identity matrix: . But most authors don't write in the identity map: . In this book we shall also observe this convention.

Of course, if then , which follows from the relationships , and , and .

As Example 1.2 shows, there may be polynomials of degree smaller than that zero the map or matrix.

Definition 1.5

The minimal polynomial of a transformation or a square matrix is the polynomial of least degree and with leading coefficient such that is the zero map or is the zero matrix.

A minimal polynomial always exists by the observation opening this subsection. A minimal polynomial is unique by the "with leading coefficient " clause. This is because if there are two polynomials and that are both of the minimal degree to make the map or matrix zero (and thus are of equal degree), and both have leading 's, then their difference has a smaller degree than either and still sends the map or matrix to zero. Thus is the zero polynomial and the two are equal. (The leading coefficient requirement also prevents a minimal polynomial from being the zero polynomial.)

Example 1.6

We can see that is minimal for the matrix of Example 1.2 by computing the powers of up to the power .

Next, put equal to the zero matrix

and use Gauss' method.

Setting , , and to zero forces and to also come out as zero. To get a leading one, the most we can do is to set and to zero. Thus the minimal polynomial is quadratic.

Using the method of that example to find the minimal polynomial of a matrix would mean doing Gaussian reduction on a system with nine equations in ten unknowns. We shall develop an alternative. To begin, note that we can break a polynomial of a map or a matrix into its components.

Lemma 1.7

Suppose that the polynomial factors as . If is a linear transformation then these two are equal maps.

Consequently, if is a square matrix then and are equal matrices.

Proof

This argument is by induction on the degree of the polynomial. The cases where the polynomial is of degree and are clear. The full induction argument is Problem 21 but the degree two case gives its sense.

A quadratic polynomial factors into two linear terms (the roots and might be equal). We can check that substituting for in the factored and unfactored versions gives the same map.

The third equality holds because the scalar comes out of the second term, as is linear.

In particular, if a minimial polynomial for a transformation factors as then is the zero map. Since sends every vector to zero, at least one of the maps sends some nonzero vectors to zero. So, too, in the matrix case— if is minimal for then is the zero matrix and at least one of the matrices sends some nonzero vectors to zero. Rewording both cases: at least some of the are eigenvalues. (See Problem 17.)

Recall how we have earlier found eigenvalues. We have looked for such that by considering the equation and computing the determinant of the matrix . That determinant is a polynomial in , the characteristic polynomial, whose roots are the eigenvalues. The major result of this subsection, the next result, is that there is a connection between this characteristic polynomial and the minimal polynomial. This results expands on the prior paragraph's insight that some roots of the minimal polynomial are eigenvalues by asserting that every root of the minimal polynomial is an eigenvalue and further that every eigenvalue is a root of the minimal polynomial (this is because it says "" and not just "").

Theorem 1.8 (Cayley-Hamilton)

If the characteristic polynomial of a transformation or square matrix factors into

then its minimal polynomial factors into

where for each between and .

The proof takes up the next three lemmas. Although they are stated only in matrix terms, they apply equally well to maps. We give the matrix version only because it is convenient for the first proof.

The first result is the key— some authors call it the Cayley-Hamilton Theorem and call Theorem 1.8 above a corollary. For the proof, observe that a matrix of polynomials can be thought of as a polynomial with matrix coefficients.

Lemma 1.9

If is a square matrix with characteristic polynomial then is the zero matrix.

Proof

Let be , the matrix whose determinant is the characteristic polynomial .

Recall that the product of the adjoint of a matrix with the matrix itself is the determinant of that matrix times the identity.

The entries of are polynomials, each of degree at most since the minors of a matrix drop a row and column. Rewrite it, as suggested above, as where each is a matrix of scalars. The left and right ends of equation () above give this.

Equate the coefficients of , the coefficients of , etc.

Multiply (from the right) both sides of the first equation by , both sides of the second equation by , etc. Add. The result on the left is , and the result on the right is the zero matrix.

We sometimes refer to that lemma by saying that a matrix or map satisfies its characteristic polynomial.

Lemma 1.10

Where is a polynomial, if is the zero matrix then is divisible by the minimal polynomial of . That is, any polynomial satisfied by is divisable by 's minimal polynomial.

Proof

Let be minimal for . The Division Theorem for Polynomials gives where the degree of is strictly less than the degree of . Plugging in shows that is the zero matrix, because satisfies both and . That contradicts the minimality of unless is the zero polynomial.

Combining the prior two lemmas gives that the minimal polynomial divides the characteristic polynomial. Thus, any root of the minimal polynomial is also a root of the characteristic polynomial. That is, so far we have that if then must has the form where each is less than or equal to . The proof of the Cayley-Hamilton Theorem is finished by showing that in fact the characteristic polynomial has no extra roots , etc.

Lemma 1.11

Each linear factor of the characteristic polynomial of a square matrix is also a linear factor of the minimal polynomial.

Proof

Let be a square matrix with minimal polynomial and assume that is a factor of the characteristic polynomial of , that is, assume that is an eigenvalue of . We must show that is a factor of , that is, that .

In general, where is associated with the eigenvector , for any polynomial function , application of the matrix to equals the result of multiplying by the scalar . (For instance, if has eigenvalue associated with the eigenvector and then .) Now, as is the zero matrix, and therefore .

Example 1.12

We can use the Cayley-Hamilton Theorem to help find the minimal polynomial of this matrix.

First, its characteristic polynomial can be found with the usual determinant. Now, the Cayley-Hamilton Theorem says that 's minimal polynomial is either or or . We can decide among the choices just by computing:

and

and so .

ExercisesEdit

This exercise is recommended for all readers.
Problem 1

What are the possible minimal polynomials if a matrix has the given characteristic polynomial?

  1.  
  2.  
  3.  
  4.  

What is the degree of each possibility?

This exercise is recommended for all readers.
Problem 2

Find the minimal polynomial of each matrix.

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
Problem 3

Find the minimal polynomial of this matrix.

 
This exercise is recommended for all readers.
Problem 4

What is the minimal polynomial of the differentiation operator   on  ?

This exercise is recommended for all readers.
Problem 5

Find the minimal polynomial of matrices of this form

 

where the scalar   is fixed (i.e., is not a variable).

Problem 6

What is the minimal polynomial of the transformation of   that sends   to  ?

Problem 7

What is the minimal polynomial of the map   projecting onto the first two coordinates?

Problem 8

Find a   matrix whose minimal polynomial is  .

Problem 9

What is wrong with this claimed proof of Lemma 1.9: "if   then  "? (Cullen 1990)

Problem 10

Verify Lemma 1.9 for   matrices by direct calculation.

This exercise is recommended for all readers.
Problem 11

Prove that the minimal polynomial of an   matrix has degree at most   (not   as might be guessed from this subsection's opening). Verify that this maximum,  , can happen.

This exercise is recommended for all readers.
Problem 12

The only eigenvalue of a nilpotent map is zero. Show that the converse statement holds.

Problem 13

What is the minimal polynomial of a zero map or matrix? Of an identity map or matrix?

This exercise is recommended for all readers.
Problem 14

Interpret the minimal polynomial of Example 1.2 geometrically.

Problem 15

What is the minimal polynomial of a diagonal matrix?

This exercise is recommended for all readers.
Problem 16

A projection is any transformation   such that  . (For instance, the transformation of the plane   projecting each vector onto its first coordinate will, if done twice, result in the same value as if it is done just once.) What is the minimal polynomial of a projection?

Problem 17

The first two items of this question are review.

  1. Prove that the composition of one-to-one maps is one-to-one.
  2. Prove that if a linear map is not one-to-one then at least one nonzero vector from the domain is sent to the zero vector in the codomain.
  3. Verify the statement, excerpted here, that preceeds Theorem 1.8.

    ... if a minimial polynomial   for a transformation   factors as   then   is the zero map. Since   sends every vector to zero, at least one of the maps   sends some nonzero vectors to zero. ... Rewording ...: at least some of the   are eigenvalues.

Problem 18

True or false: for a transformation on an   dimensional space, if the minimal polynomial has degree   then the map is diagonalizable.

Problem 19

Let   be a polynomial. Prove that if   and   are similar matrices then   is similar to  .

  1. Now show that similar matrices have the same characteristic polynomial.
  2. Show that similar matrices have the same minimal polynomial.
  3. Decide if these are similar.
     
Problem 20
  1. Show that a matrix is invertible if and only if the constant term in its minimal polynomial is not  .
  2. Show that if a square matrix   is not invertible then there is a nonzero matrix   such that   and   both equal the zero matrix.
This exercise is recommended for all readers.
Problem 21
  1. Finish the proof of Lemma 1.7.
  2. Give an example to show that the result does not hold if   is not linear.
Problem 22

Any transformation or square matrix has a minimal polynomial. Does the converse hold?

Solutions

ReferencesEdit

  • Cullen, Charles G. (1990), Matrices and Linear Transformations (Second ed.), Dover .
Linear Algebra
 ← Jordan Form Polynomials of Maps and Matrices Jordan Canonical Form →