Linear Algebra/Polynomials of Maps and Matrices

Linear Algebra Polynomials of Maps and Matrices Jordan Form 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.2ex:PolySendRotMatToZ 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.5minimal poly 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.6ex:MinPolyForRotMat 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.7le:PolyMapsFactor 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)th:CayHam 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.9le:MatSatItsCharPoly 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.12ex:MinPolyUsingCH 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 . Exercises Problem 1 What are the possible minimal polynomials if a matrix has the given characteristic polynomial? <li> <li> <li> <li> What is the degree of each possibility? Problem 2 Find the minimal polynomial of each matrix. <li> <li> <li> <li> <li> <li> Problem 3 Find the minimal polynomial of this matrix. Problem 4 What is the minimal polynomial of the differentiation operator on ? 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. 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. 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? Problem 14 Interpret the minimal polynomial of Example 1.2 geometrically. Problem 15 What is the minimal polynomial of a diagonal matrix? Problem 16projection 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 17exer:SomeRootsMinPolyAreEigs The first two items of this question are review. <li> Prove that the composition of one-to-one maps is one-to-one. <li> 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. <li> 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 . <li> Now show that similar matrices have the same characteristic polynomial. <li> Show that similar matrices have the same minimal polynomial. <li> Decide if these are similar. Problem 20 <li> Show that a matrix is invertible if and only if the constant term in its minimal polynomial is not . <li> Show that if a square matrix is not invertible then there is a nonzero matrix such that and both equal the zero matrix. Problem 21exer:PolyMapsFactor <li> Finish the proof of Lemma 1.7. <li> 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/ References Charles G. Cullen Matrices and Linear Transformations Second Dover 1990. Linear Algebra Polynomials of Maps and Matrices Jordan Form Jordan Canonical Form