Cayley–Hamilton theorem


In linear algebra, the Cayley–Hamilton theorem states that every square matrix over a commutative ring satisfies its own characteristic equation.
If is a given matrix and is the identity matrix, then the characteristic polynomial of is defined as
where is the determinant operation and is a variable for a scalar element of the base ring. Since the entries of the matrix are polynomials in, the determinant is also an -th order monic polynomial in. The Cayley–Hamilton theorem states that if one defines an analogous matrix equation,, consisting of the replacement of the scalar variable with the matrix, then this polynomial in the matrix results in the zero matrix,
The powers of, obtained by substitution from powers of, are defined by repeated matrix multiplication; the constant term of gives a multiple of the power 0, which is defined as the identity matrix.
The theorem allows to be expressed as a linear combination of the lower matrix powers of. When the ring is a field, the Cayley–Hamilton theorem is equivalent to the statement that the minimal polynomial of a square matrix divides its characteristic polynomial.
The theorem was first proved in 1853 in terms of inverses of linear functions of quaternions, a non-commutative ring, by Hamilton. This corresponds to the special case of certain real or complex matrices. The theorem holds for general quaternionic matrices. Cayley in 1858 stated it for and smaller matrices, but only published a proof for the case. The general case was first proved by Frobenius in 1878.

Examples

matrices

For a matrix, the characteristic polynomial is given by, and so is trivial.

matrices

As a concrete example, let
Its characteristic polynomial is given by
The Cayley–Hamilton theorem claims that, if we define
then
We can verify by computation that indeed,
For a generic matrix,
the characteristic polynomial is given by, so the Cayley–Hamilton theorem states that
which is indeed always the case, evident by working out the entries of 2.

Applications

Determinant and inverse matrix

For a general invertible matrix, i.e., one with nonzero determinant, −1 can thus be written as an order polynomial expression in : As indicated, the Cayley–Hamilton theorem amounts to the identity
The coefficients are given by the elementary symmetric polynomials of the eigenvalues of. Using Newton identities, the elementary symmetric polynomials can in turn be expressed in terms of power sum symmetric polynomials of the eigenvalues:
where is the trace of the matrix. Thus, we can express in terms of the trace of powers of.
In general, the formula for the coefficients is given in terms of complete exponential Bell polynomials as
In particular, the determinant of equals. Thus, the determinant can be written as the trace identity:
Likewise, the characteristic polynomial can be written as
and, by multiplying both sides by , one is led to an expression for the inverse of as a trace identity,
Another method for obtaining these coefficients for a general matrix, provided no root be zero, relies on the following alternative expression for the determinant,
Hence, by virtue of the Mercator series,
where the exponential only needs be expanded to order , since is of order, the net negative powers of automatically vanishing by the C–H theorem. Differentiation of this expression with respect to allows one to express the coefficients of the characteristic polynomial for general as determinants of matrices,
; Examples
For instance, the first few Bell polynomials are = 1,,, and.
Using these to specify the coefficients of the characteristic polynomial of a matrix yields
The coefficient gives the determinant of the matrix, minus its trace, while its inverse is given by
It is apparent from the general formula for cn-k, expressed in terms of Bell polynomials, that the expressions
always give the coefficients of and of in the characteristic polynomial of any matrix, respectively. So, for a matrix, the statement of the Cayley–Hamilton theorem can also be written as
where the right-hand side designates a matrix with all entries reduced to zero. Likewise, this determinant in the case, is now
This expression gives the negative of coefficient of in the general case, as seen below.
Similarly, one can write for a matrix,
where, now, the determinant is ,
and so on for larger matrices. The increasingly complex expressions for the coefficients is deducible from Newton's identities or the Faddeev–LeVerrier algorithm.

''n''-th Power of matrix

The Cayley–Hamilton theorem always provides a relationship between the powers of , which allows one to simplify expressions involving such powers, and evaluate them without having to compute the power or any higher powers of.
As an example, for the theorem gives
Then, to calculate, observe
Likewise,
Notice that we have been able to write the matrix power as the sum of two terms. In fact, matrix power of any order can be written as a matrix polynomial of degree at most, where is the size of a square matrix. This is an instance where Cayley–Hamilton theorem can be used to express a matrix function, which we will discuss below systematically.

Matrix functions

Given an analytic function
and the characteristic polynomial of degree of an matrix, the function can be expressed using long division as
where is some quotient polynomial and is a remainder polynomial such that.
By the Cayley–Hamilton theorem, replacing by the matrix gives, so one has
Thus, the analytic function of the matrix can be expressed as a matrix polynomial of degree less than.
Let the remainder polynomial be
Since, evaluating the function at the eigenvalues of, yields
This amounts to a system of linear equations, which can be solved to determine the coefficients. Thus, one has
When the eigenvalues are repeated, that is for some, two or more equations are identical; and hence the linear equations cannot be solved uniquely. For such cases, for an eigenvalue with multiplicity, the first derivatives of vanish at the eigenvalue. This
leads to the extra linearly independent solutions
which, combined with others, yield the required equations to solve for.
Finding a polynomial that passes through the points is essentially an interpolation problem, and can be solved using Lagrange or Newton interpolation techniques, leading to Sylvester's formula.
For example, suppose the task is to find the polynomial representation of
The characteristic polynomial is, and the eigenvalues are. Let. Evaluating at the eigenvalues, one obtains two linear equations, and.
Solving the equations yields and. Thus, it follows that
If, instead, the function were, then the coefficients would have been and ; hence
As a further example, when considering
then the characteristic polynomial is, and the eigenvalues are.
As before, evaluating the function at the eigenvalues gives us the linear equations and ; the solution of which gives, and. Thus, for this case,
which is a rotation matrix.
Standard examples of such usage is the exponential map from the Lie algebra of a matrix Lie group into the group. It is given by a matrix exponential,
Such expressions have long been known for,
where the are the Pauli matrices and for,
which is Rodrigues' rotation formula. For the notation, see rotation group SO#A note on Lie algebra.
More recently, expressions have appeared for other groups, like the Lorentz group, and, as well as. The group is the conformal group of spacetime, its simply connected cover. The expressions obtained apply to the standard representation of these groups. They require knowledge of the eigenvalues of the matrix to exponentiate. For , closed expressions have been obtained for all irreducible representations, i.e. of any spin.
, German mathematician. His main interests were elliptic functions, differential equations, and later group theory.
In 1878 he gave the first full proof of the Cayley-Hamilton theorem.

Algebraic number theory

The Cayley–Hamilton theorem is an effective tool for computing the minimal polynomial of algebraic integers. For example, given a finite extension of and an algebraic integer which is a non-zero linear combination of the we can compute the minimal polynomial of by finding a matrix representing the -linear transformation
If we call this transformation matrix, then we can find the minimal polynomial by applying the Cayley–Hamilton theorem to.

Proofs

The Cayley–Hamilton theorem is an immediate consequence of the existence of the Jordan normal form for matrices over algebraically closed fields. In this section, direct proofs are presented.
As the examples above show, obtaining the statement of the Cayley–Hamilton theorem for an matrix
requires two steps: first the coefficients of the characteristic polynomial are determined by development as a polynomial in of the determinant
and then these coefficients are used in a linear combination of powers of that is equated to the null matrix:
The left-hand side can be worked out to an matrix whose entries are polynomial expressions in the set of entries of, so the Cayley–Hamilton theorem states that each of these expressions equals. For any fixed value of, these identities can be obtained by tedious but straightforward algebraic manipulations. None of these computations, however, can show why the Cayley–Hamilton theorem should be valid for matrices of all possible sizes, so a uniform proof for all is needed.

Preliminaries

If a vector of size is an eigenvector of with eigenvalue, in other words if, then
which is the null vector since . This holds for all possible eigenvalues, so the two matrices equated by the theorem certainly give the same result when applied to any eigenvector. Now if admits a basis of eigenvectors, in other words if is diagonalizable, then the Cayley–Hamilton theorem must hold for, since two matrices that give the same values when applied to each element of a basis must be equal.
Consider now the function which maps matrices to matrices given by the formula, i.e. which takes a matrix and plugs it into its own characteristic polynomial. Not all matrices are diagonalizable, but for matrices with complex coefficients many of them are: the set of diagonalizable complex square matrices of a given size is dense in the set of all such square matrices. Now viewed as a function we see that this function is continuous. This is true because the entries of the image of a matrix are given by polynomials in the entries of the matrix. Since
and since the set is dense, by continuity this function must map the entire set of matrices to the zero matrix. Therefore, the Cayley–Hamilton theorem is true for complex numbers, and must therefore also hold for - or -valued matrices.
While this provides a valid proof, the argument is not very satisfactory, since the identities represented by the theorem do not in any way depend on the nature of the matrix, nor on the kind of entries allowed. We shall therefore now consider only arguments that prove the theorem directly for any matrix using algebraic manipulations only; these also have the benefit of working for matrices with entries in any commutative ring.
There is a great variety of such proofs of the Cayley–Hamilton theorem, of which several will be given here. They vary in the amount of abstract algebraic notions required to understand the proof. The simplest proofs use just those notions needed to formulate the theorem, but involve technical computations that render somewhat mysterious the fact that they lead precisely to the correct conclusion. It is possible to avoid such details, but at the price of involving more subtle algebraic notions: polynomials with coefficients in a non-commutative ring, or matrices with unusual kinds of entries.

Adjugate matrices

All proofs below use the notion of the adjugate matrix of an matrix, the transpose of its cofactor matrix.
This is a matrix whose coefficients are given by polynomial expressions in the coefficients of , in such a way that
the following fundamental relations hold,
These relations are a direct consequence of the basic properties of determinants: evaluation of the entry of the matrix product on the left gives the expansion by column of the determinant of the matrix obtained from by replacing column by a copy of column, which is if and zero otherwise; the matrix product on the right is similar, but for expansions by rows.
Being a consequence of just algebraic expression manipulation, these relations are valid for matrices with entries in any commutative ring. This is important to note here, because these relations will be applied below for matrices with non-numeric entries such as polynomials.

A direct algebraic proof

This proof uses just the kind of objects needed to formulate the Cayley–Hamilton theorem: matrices with polynomials as entries. The matrix whose determinant is the characteristic polynomial of is such a matrix, and since polynomials form a commutative ring, it has an adjugate
Then, according to the right-hand fundamental relation of the adjugate, one has
Since is also a matrix with polynomials in as entries, one can, for each , collect the coefficients of in each entry to form a matrix of numbers, such that one has
. While this looks like a polynomial with matrices as coefficients, we shall not consider such a notion; it is just a way to write a matrix with polynomial entries as a linear combination of constant matrices, and the coefficient has been written to the left of the matrix to stress this point of view.
Now, one can expand the matrix product in our equation by bilinearity
Writing
one obtains an equality of two matrices with polynomial entries, written as linear combinations of constant matrices with powers of as coefficients.
Such an equality can hold only if in any matrix position the entry that is multiplied by a given power is the same on both sides; it follows that the constant matrices with coefficient in both expressions must be equal. Writing these equations then for from down to 0, one finds
Finally, multiply the equation of the coefficients of from the left by , and sum up:
The left-hand sides form a telescoping sum and cancel completely; the right-hand sides add up to :
This completes the proof.

A proof using polynomials with matrix coefficients

This proof is similar to the first one, but tries to give meaning to the notion of polynomial with matrix coefficients that was suggested by the expressions occurring in that proof. This requires considerable care, since it is somewhat unusual to consider polynomials with coefficients in a non-commutative ring, and not all reasoning that is valid for commutative polynomials can be applied in this setting.
Notably, while arithmetic of polynomials over a commutative ring models the arithmetic of polynomial functions, this is not the case over a non-commutative ring. So when considering polynomials in with matrix coefficients, the variable must not be thought of as an "unknown", but as a formal symbol that is to be manipulated according to given rules; in particular one cannot just set to a specific value.
Let be the ring of matrices with entries in some ring R that has as an element. Matrices with as coefficients polynomials in, such as or its adjugate B in the first proof, are elements of.
By collecting like powers of, such matrices can be written as "polynomials" in with constant matrices as coefficients; write for the set of such polynomials. Since this set is in bijection with, one defines arithmetic operations on it correspondingly, in particular multiplication is given by
respecting the order of the coefficient matrices from the two operands; obviously this gives a non-commutative multiplication.
Thus, the identity
from the first proof can be viewed as one involving a multiplication of elements in .
At this point, it is tempting to simply set equal to the matrix , which makes the first factor on the left equal to the null matrix, and the right hand side equal to ; however, this is not an allowed operation when coefficients do not commute. It is possible to define a "right-evaluation map" ev : M → M, which replaces each ti by the matrix power i of , where one stipulates that the power is always to be multiplied on the right to the corresponding coefficient.
But this map is not a ring homomorphism: the right-evaluation of a product differs in general from the product of the right-evaluations. This is so because multiplication of polynomials with matrix coefficients does not model multiplication of expressions containing unknowns: a product is defined assuming that commutes with , but this may fail if is replaced by the matrix .
One can work around this difficulty in the particular situation at hand, since the above right-evaluation map does become a ring homomorphism if the matrix is in the center of the ring of coefficients, so that it commutes with all the coefficients of the polynomials.
Now, is not always in the center of M, but we may replace M with a smaller ring provided it contains all the coefficients of the polynomials in question:, , and the coefficients of the polynomial B. The obvious choice for such a subring is the centralizer Z of , the subring of all matrices that commute with ; by definition is in the center of Z.
This centralizer obviously contains, and, but one has to show that it contains the matrices. To do this, one combines the two fundamental relations for adjugates, writing out the adjugate B as a polynomial:
Equating the coefficients shows that for each i, we have Bi = Bi as desired. Having found the proper setting in which ev is indeed a homomorphism of rings, one can complete the proof as suggested above:
This completes the proof.

A synthesis of the first two proofs

In the first proof, one was able to determine the coefficients of based on the right-hand fundamental relation for the adjugate only. In fact the first equations derived can be interpreted as determining the quotient of the Euclidean division of the polynomial on the left by the monic polynomial, while the final equation expresses the fact that the remainder is zero. This division is performed in the ring of polynomials with matrix coefficients. Indeed, even over a non-commutative ring, Euclidean division by a monic polynomial is defined, and always produces a unique quotient and remainder with the same degree condition as in the commutative case, provided it is specified at which side one wishes to be a factor.
To see that quotient and remainder are unique, it suffices to write as and observe that since is monic, cannot have a degree less than that of , unless.
But the dividend and divisor used here both lie in the subring , where is the subring of the matrix ring generated by : the -linear span of all powers of . Therefore, the Euclidean division can in fact be performed within that commutative polynomial ring, and of course it then gives the same quotient and remainder 0 as in the larger ring; in particular this shows that in fact lies in .
But, in this commutative setting, it is valid to set to in the equation
in other words, to apply the evaluation map
which is a ring homomorphism, giving
just like in the second proof, as desired.
In addition to proving the theorem, the above argument tells us that the coefficients of are polynomials in , while from the second proof we only knew that they lie in the centralizer of ; in general is a larger subring than , and not necessarily commutative. In particular the constant term lies in . Since is an arbitrary square matrix, this proves that can always be expressed as a polynomial in by , and use the fact that

A proof using matrices of endomorphisms

As was mentioned above, the matrix p in statement of the theorem is obtained by first evaluating the determinant and then substituting the matrix A for t; doing that substitution into the matrix before evaluating the determinant is not meaningful. Nevertheless, it is possible to give an interpretation where p is obtained directly as the value of a certain determinant, but this requires a more complicated setting, one of matrices over a ring in which one can interpret both the entries of A, and all of A itself. One could take for this the ring M of n×n matrices over R, where the entry is realised as, and A as itself. But considering matrices with matrices as entries might cause confusion with block matrices, which is not intended, as that gives the wrong notion of determinant. It is clearer to distinguish A from the endomorphism φ of an n-dimensional vector space V defined by it in a basis, and to take matrices over the ring End of all such endomorphisms. Then φ ∈ End is a possible matrix entry, while A designates the element of M whose i,j entry is endomorphism of scalar multiplication by ; similarly will be interpreted as element of M. However, since End is not a commutative ring, no determinant is defined on M; this can only be done for matrices over a commutative subring of End. Now the entries of the matrix all lie in the subring R generated by the identity and φ, which is commutative. Then a determinant map M → R is defined, and evaluates to the value p of the characteristic polynomial of A at φ ; the Cayley–Hamilton theorem states that p is the null endomorphism.
In this form, the following proof can be obtained from that of . The fact that A is the matrix of φ in the basis e1,..., en means that
One can interpret these as n components of one equation in Vn, whose members can be written using the matrix-vector product M × Vn → Vn that is defined as usual, but with individual entries ψ ∈ End and v in V being "multiplied" by forming ; this gives:
where is the element whose component i is ei. Writing this equation as
one recognizes the transpose of the matrix considered above, and its determinant is also p. To derive from this equation that p = 0 ∈ End, one left-multiplies by the adjugate matrix of, which is defined in the matrix ring M, giving
the associativity of matrix-matrix and matrix-vector multiplication used in the first step is a purely formal property of those operations, independent of the nature of the entries. Now component i of this equation says that p = 0 ∈ V; thus p vanishes on all ei, and since these elements generate V it follows that p = 0 ∈ End, completing the proof.
One additional fact that follows from this proof is that the matrix A whose characteristic polynomial is taken need not be identical to the value φ substituted into that polynomial; it suffices that φ be an endomorphism of V satisfying the initial equations
for some sequence of elements e1,...,en that generate V.

A bogus "proof": ''p''(''A'') = det(''AI''''n'' − ''A'') = det(''A'' − ''A'') = 0

One persistent elementary but incorrect argument for the theorem is to "simply" take the definition
and substitute for, obtaining
There are many ways to see why this argument is wrong. First, in Cayley–Hamilton theorem, p is an n×n matrix. However, the right hand side of the above equation is the value of a determinant, which is a scalar. So they cannot be equated unless n = 1. Second, in the expression, the variable λ actually occurs at the diagonal entries of the matrix. To illustrate, consider the characteristic polynomial in the previous example again:
If one substitutes the entire matrix A for λ in those positions, one obtains
in which the "matrix" expression is simply not a valid one. Note, however, that if scalar multiples of identity matrices
instead of scalars are subtracted in the above, i.e. if the substitution is performed as
then the determinant is indeed zero, but the expanded matrix in question does not evaluate to ; nor can its determinant be compared to p. So the argument that still does not apply.
Actually, if such an argument holds, it should also hold when other multilinear forms instead of determinant is used. For instance, if we consider the permanent function and define, then by the same argument, we should be able to "prove" that q = 0. But this statement is demonstrably wrong. In the 2-dimensional case, for instance, the permanent of a matrix is given by
So, for the matrix A in the previous example,
Yet one can verify that
One of the proofs for Cayley–Hamilton theorem above bears some similarity to the argument that. By introducing a matrix with non-numeric coefficients, one can actually let A live inside a matrix entry, but then is not equal to A, and the conclusion is reached differently.

Proofs using methods of abstract algebra

Basic properties of Hasse–Schmidt derivations on the exterior algebra of some B-module M have been used by to prove the Cayley–Hamilton theorem. See also.

Abstraction and generalizations

The above proofs show that the Cayley–Hamilton theorem holds for matrices with entries in any commutative ring R, and that p = 0 will hold whenever φ is an endomorphism of an R module generated by elements e1,...,en that satisfies
This more general version of the theorem is the source of the celebrated Nakayama lemma in commutative algebra and algebraic geometry.

Remarks