In linear algebra, when studying a particular matrix, one is often interested in polynomial relations satisfied by this matrix. For example, the matrix satisfies , where denotes the -by- identity matrix: Knowing such relations can be useful in matrix computations (e.g. computing powers of matrices), as well as in investigating the eigenvalues and eigenvectors of a matrix.
The Cayley-Hamilton theorem produces an explicit polynomial relation satisfied by a given matrix. In particular, if is a matrix and is its characteristic polynomial, the Cayley-Hamilton theorem states that .
Consider the matrix given in the introduction above. Suppose one wishes to compute its fourth power . This can be done by using the polynomial relation as a way to reduce exponents in the expression: More generally, one can use the recurrence to write any power of as an integer linear combination of and .
At least for the sake of doing computations like this, one is interested in finding polynomials satisfied by a given matrix. In symbols, for a matrix , one seeks polynomials such that . Note that here, is itself a matrix, not a number; the in this expression denotes the matrix whose entries are all zero.
One way to find a polynomial satisfied by an -by- matrix is to exploit the vector space structure on the set of all -by- matrices. Let denote the vector space of -by- matrices with entries in a field (for instance, could be the real numbers or the complex numbers ). Since an -by- matrix has entries, the space has dimension . This implies that the matrices are linearly dependent over (since there are matrices in this collection). Thus, there are , such that The polynomial is therefore satisfied by .
However, this method is lacking in that it is nonconstructive; the coefficients are shown to exist but are not produced/computed. On the other hand, the Cayley-Hamilton theorem is constructive; is shown to satisfy an explicit and easily computed polynomial, namely the characteristic polynomial of . This polynomial is and the Cayley-Hamilton theorem states that . Proving this is not as simple as making the substitution , since the variable in the definition of characteristic polynomial represents a number, not a matrix.
Suppose is an -by- matrix. When has entries in , one can prove the Cayley-Hamilton theorem as follows:
A matrix is called diagonalizable if there exists invertible such that is diagonal. Recall that a diagonal matrix is a matrix for which all entries off the main diagonal (the diagonal from top left to bottom right) are zero. Diagonal matrices have a very simple multiplicative structure; when one multiplies two diagonal matrices, the entries in both main diagonals multiply termwise. In particular, one can see why a diagonal matrix should satisfy its own characteristic polynomial: each entry on the main diagonal is an eigenvalue of the matrix. Consequently, it follows any diagonalizable matrix also satisfies its own characteristic polynomial, since The proof of Cayley-Hamilton therefore proceeds by approximating arbitrary matrices with diagonalizable matrices (this will be possible to do when entries of the matrix are complex, exploiting the fundamental theorem of algebra). To do this, first one needs a criterion for diagonalizability of a matrix:
Lemma: If has distinct eigenvalues, then is diagonalizable.
Suppose the roots of the characteristic polynomial are all distinct, i.e. the eigenvalues with have for . Let denote the eigenvector associated with .
Assume that there are coefficients with Applying to this equation gives the relation Choose a polynomial such that and for (using, for instance, Lagrange interpolation). The above equations imply . Thus, the eigenvectors are linearly independent.
Since there are eigenvectors, the collection must form a basis for the vector space . In this basis, the matrix for the linear transformation corresponding to is diagonal. Let denote the change of basis matrix sending to the standard basis vector i.e. where is in the slot Then is diagonal, as desired.
Corollary: If , for any there is a diagonalizable matrix such that entries in are within of corresponding entries in .
The roots of are continuous functions of the entries in . Thus, arbitrarily small perturbations of these entries will suffice to make all these roots distinct. This reasoning is only valid because of the fundamental theorem of algebra, which ensures all roots of are in .
To complete the proof, let be a sequence of diagonalizable matrices converging to (where convergence is matrix-entry-wise). Since for all and is continuous as a function of the matrix entries, taking implies , which is the result of the Cayley-Hamilton theorem.
Prove that the inverse of a -by- matrix is given by the formula below:
Let denote the given matrix; its characteristic polynomial is By the Cayley-Hamilton theorem, it follows that where is the -by- identity matrix. Thus,
Let be an -by- matrix. is called nilpotent if there exists some integer such that . Prove that if is nilpotent, then .
Suppose is a nonzero eigenvector of , with eigenvalue . Then Since all roots of the (degree ) characteristic polynomial are eigenvalues, it follows . By the Cayley-Hamilton theorem, we may now conclude .
Consider the set of -by- matrices whose entries are integers modulo , for some prime . The matrices in this set with nonzero determinant are invertible, and thus form a group under matrix multiplication; this group is given the name , where the "GL" stands for "general linear."
Given a matrix , its order is defined to be the smallest integer such that , where denotes the identity matrix. In this problem, you will compute the maximum possible order of a matrix in . That is, you will answer the question "What is the largest integer such that is the order of a matrix in "
Hint & Proof Sketch:
Let be a matrix in . Consider the vector space generated by the powers of , with coefficients in the field of elements. That is, is the vector space (under addition) of linear combinations where the coefficients are integers modulo . The Cayley-Hamilton theorem implies is finite dimensional; what is the largest possible value of its dimension as ranges over the group
Suppose . What does this imply about the order of in To answer this question, note that any power of must be in , since the exponents in powers of can be reduced using the polynomial relation produced by Cayley-Hamilton.
Let denote the largest possible value of when ranges over . Can you find a matrix whose order is at least What does this imply in light of the previous two steps?
As your answer to this problem, submit the maximum possible order of a matrix in , i.e.