Cayley–Hamilton theorem

Every square matrix over a commutative ring satisfies its own characteristic equation

In linear algebra, the Cayley–Hamilton theorem (named after the mathematicians Arthur Cayley and William Rowan Hamilton) states that every square matrix over a commutative ring (such as the real or complex field) satisfies its own characteristic equation.

For a 1×1 matrix A = (a1,1), the characteristic polynomial is given by p(λ) = λ − a, and so p(A) = (a) − a1,1 = 0 is trivial.

the characteristic polynomial is given by p(λ) = λ2 − (a + d)λ + (ad − bc), so the Cayley–Hamilton theorem states that

which is indeed always the case, evident by working out the entries of A2.

For a general n×n invertible matrix A, i.e., one with nonzero determinant, A−1 can thus be written as an (n − 1)-th order polynomial expression in A: As indicated, the Cayley–Hamilton theorem amounts to the identity

The coefficients ci are given by the elementary symmetric polynomials of the eigenvalues of A. Using Newton identities, the elementary symmetric polynomials can in turn be expressed in terms of power sum symmetric polynomials of the eigenvalues:

where tr (Ak) is the trace of the matrix Ak. Thus, we can express ci in terms of the trace of powers of A.

In general, the formula for the coefficients ci is given in terms of complete exponential Bell polynomials as [nb 2]

In particular, the determinant of A equals (-1)nc0. Thus, the determinant can be written as the trace identity:

and, by multiplying both sides by A−1 (note −(−1)n = (−1)n−1), one is led to an expression for the inverse of A as a trace identity,

Another method for obtaining these coefficients ck for a general n×n matrix, provided no root be zero, relies on the following alternative expression for the determinant,

where the exponential only needs be expanded to order λn, since p(λ) is of order n, the net negative powers of λ automatically vanishing by the C–H theorem. (Again, this requires a ring containing the rational numbers.) Differentiation of this expression with respect to λ allows one to express the coefficients of the characteristic polynomial for general n as determinants of m×m matrices,[nb 3]

For instance, the first few Bell polynomials are B0 = 1, B1(x1) = x1, B2(x1, x2) = x2
1
+ x2
, and B3(x1, x2, x3) = x3
1
+ 3 x1x2 + x3
.

Using these to specify the coefficients ci of the characteristic polynomial of a 2×2 matrix yields

The coefficient c0 gives the determinant of the 2×2 matrix, c1 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 cn−1 of λn−1 and cn−2 of λn−2 in the characteristic polynomial of any n×n matrix, respectively. So, for a 3×3 matrix A, the statement of the Cayley–Hamilton theorem can also be written as

where the right-hand side designates a 3×3 matrix with all entries reduced to zero. Likewise, this determinant in the n = 3 case, is now

This expression gives the negative of coefficient cn−3 of λn−3 in the general case, as seen below.

and so on for larger matrices. The increasingly complex expressions for the coefficients ck is deducible from Newton's identities or the Faddeev–LeVerrier algorithm.

The Cayley–Hamilton theorem always provides a relationship between the powers of A (though not always the simplest one), which allows one to simplify expressions involving such powers, and evaluate them without having to compute the power An or any higher powers of A.

Notice that we have been able to write the matrix power as the sum of two terms. In fact, matrix power of any order k can be written as a matrix polynomial of degree at most n - 1, where n 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.

and the characteristic polynomial p(x) of degree n of an n × n matrix A, the function can be expressed using long division as

where q(x) is some quotient polynomial and r(x) is a remainder polynomial such that 0 ≤ deg r(x) < n.

By the Cayley–Hamilton theorem, replacing x by the matrix A gives p(A) = 0, so one has

Thus, the analytic function of the matrix A can be expressed as a matrix polynomial of degree less than n.

Since p(λ) = 0, evaluating the function f(x) at the n eigenvalues of A, yields

This amounts to a system of n linear equations, which can be solved to determine the coefficients ci. Thus, one has

When the eigenvalues are repeated, that is λi = λj for some i ≠ j, two or more equations are identical; and hence the linear equations cannot be solved uniquely. For such cases, for an eigenvalue λ with multiplicity m, the first m – 1 derivatives of p(x) vanish at the eigenvalue. This leads to the extra m – 1 linearly independent solutions

which, combined with others, yield the required n equations to solve for ci.

Finding a polynomial that passes through the points (λi, f (λi)) 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 p(x) = (x − 1)(x − 3) = x2 − 4x + 3, and the eigenvalues are λ = 1, 3. Let r(x) = c0 + c1x. Evaluating f(λ) = r(λ) at the eigenvalues, one obtains two linear equations, et = c0 + c1 and e3t = c0 + 3c1.

Solving the equations yields c0 = (3ete3t)/2 and c1 = (e3tet)/2. Thus, it follows that

If, instead, the function were f(A) = sin At, then the coefficients would have been c0 = (3 sin t − sin 3t)/2 and c1 = (sin 3t - sin t)/2; hence

then the characteristic polynomial is p(x) = x2 + 1, and the eigenvalues are λ = ±i.

As before, evaluating the function at the eigenvalues gives us the linear equations eit = c0 + i c1 and eit = c0ic1; the solution of which gives, c0 = (eit + eit)/2 = cos t and c1 = (eiteit)/2i = sin t. Thus, for this case,

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,

which is Rodrigues' rotation formula. For the notation, see rotation group SO(3)#A note on Lie algebra.

More recently, expressions have appeared for other groups, like the Lorentz group SO(3, 1),[11] O(4, 2)[12] and SU(2, 2),[13] as well as GL(n, R).[14] The group O(4, 2) is the conformal group of spacetime, SU(2, 2) its simply connected cover (to be precise, the simply connected cover of the connected component SO+(4, 2) of O(4, 2)). The expressions obtained apply to the standard representation of these groups. They require knowledge of (some of) the eigenvalues of the matrix to exponentiate. For SU(2) (and hence for SO(3)), closed expressions have been obtained for all irreducible representations, i.e. of any spin.[15]

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 n×n matrix

requires two steps: first the coefficients ci of the characteristic polynomial are determined by development as a polynomial in t of the determinant

and then these coefficients are used in a linear combination of powers of A that is equated to the n×n null matrix:

The left-hand side can be worked out to an n×n matrix whose entries are (enormous) polynomial expressions in the set of entries ai,j of A, so the Cayley–Hamilton theorem states that each of these n2 expressions equals 0. For any fixed value of n, 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 n, so a uniform proof for all n is needed.

If a vector v of size n is an eigenvector of A with eigenvalue λ, in other words if Av = λv, then

which is the null vector since p(λ) = 0 (the eigenvalues of A are precisely the roots of p(t)). This holds for all possible eigenvalues λ, so the two matrices equated by the theorem certainly give the same (null) result when applied to any eigenvector. Now if A admits a basis of eigenvectors, in other words if A is diagonalizable, then the Cayley–Hamilton theorem must hold for A, since two matrices that give the same values when applied to each element of a basis must be equal.

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 (diagonalizable or not), nor on the kind of entries allowed (for matrices with real entries the diagonalizable ones do not form a dense set, and it seems strange one would have to consider complex matrices to see that the Cayley–Hamilton theorem holds for them). 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 (matrices, polynomials with numeric entries, determinants), 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.

All proofs below use the notion of the adjugate matrix adj(M) of an n×n matrix M, the transpose of its cofactor matrix.

This is a matrix whose coefficients are given by polynomial expressions in the coefficients of M (in fact, by certain (n − 1)×(n − 1) determinants), 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 (i,j) entry of the matrix product on the left gives the expansion by column j of the determinant of the matrix obtained from M by replacing column i by a copy of column j, which is det(M) if i = j 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 (commutativity must be assumed for determinants to be defined in the first place). This is important to note here, because these relations will be applied below for matrices with non-numeric entries such as polynomials.

This proof uses just the kind of objects needed to formulate the Cayley–Hamilton theorem: matrices with polynomials as entries. The matrix t InA whose determinant is the characteristic polynomial of A 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 B is also a matrix with polynomials in t as entries, one can, for each i , collect the coefficients of ti in each entry to form a matrix B i of numbers, such that one has

(The way the entries of B are defined makes clear that no powers higher than tn−1 occur). 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 n constant matrices, and the coefficient t i has been written to the left of the matrix to stress this point of view.

one obtains an equality of two matrices with polynomial entries, written as linear combinations of constant matrices with powers of t as coefficients.

Such an equality can hold only if in any matrix position the entry that is multiplied by a given power ti is the same on both sides; it follows that the constant matrices with coefficient ti in both expressions must be equal. Writing these equations then for i from n down to 0, one finds

Finally, multiply the equation of the coefficients of ti from the left by Ai, and sum up:

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 (in fact there is no obvious notion of polynomial function in this case that is closed under multiplication). So when considering polynomials in t with matrix coefficients, the variable t 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 t to a specific value.

respecting the order of the coefficient matrices from the two operands; obviously this gives a non-commutative multiplication.

At this point, it is tempting to simply set t equal to the matrix A , which makes the first factor on the left equal to the null matrix, and the right hand side equal to p(A); however, this is not an allowed operation when coefficients do not commute. It is possible to define a "right-evaluation map" evA : M[t] → M, which replaces each ti by the matrix power Ai of A , where one stipulates that the power is always to be multiplied on the right to the corresponding coefficient.

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 A is in the center of the ring of coefficients, so that it commutes with all the coefficients of the polynomials (the argument proving this is straightforward, exactly because commuting t with coefficients is now justified after evaluation).

Equating the coefficients shows that for each i, we have A Bi = Bi A as desired. Having found the proper setting in which evA is indeed a homomorphism of rings, one can complete the proof as suggested above:

In the first proof, one was able to determine the coefficients Bi of B based on the right-hand fundamental relation for the adjugate only. In fact the first n equations derived can be interpreted as determining the quotient B of the Euclidean division of the polynomial p(t)In on the left by the monic polynomial IntA, 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 P 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 P to be a factor (here that is to the left).

But the dividend p(t)In and divisor IntA used here both lie in the subring (R[A])[t], where R[A] is the subring of the matrix ring M(n, R) generated by A: the R-linear span of all powers of A. Therefore, the Euclidean division can in fact be performed within that commutative polynomial ring, and of course it then gives the same quotient B and remainder 0 as in the larger ring; in particular this shows that B in fact lies in (R[A])[t].

But, in this commutative setting, it is valid to set t to A in the equation

In addition to proving the theorem, the above argument tells us that the coefficients Bi of B are polynomials in A, while from the second proof we only knew that they lie in the centralizer Z of A; in general Z is a larger subring than R[A], and not necessarily commutative. In particular the constant term B0= adj(−A) lies in R[A]. Since A is an arbitrary square matrix, this proves that adj(A) can always be expressed as a polynomial in A (with coefficients that depend on A).

Note that this identity also implies the statement of the Cayley–Hamilton theorem: one may move adj(−A) to the right hand side, multiply the resulting equation (on the left or on the right) by A, and use the fact that

In this form, the following proof can be obtained from that of (Atiyah & MacDonald 1969, Prop. 2.4) (which in fact is the more general statement related to the Nakayama lemma; one takes for the ideal in that proposition the whole ring R). The fact that A is the matrix of φ in the basis e1, ..., en means that

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(φ)(ei) = 0 ∈ V; thus p(φ) vanishes on all ei, and since these elements generate V it follows that p(φ) = 0 ∈ End(V), 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 (which space might have smaller dimension than n, or in case the ring R is not a field it might not be a free module at all).

One persistent elementary but incorrect argument[18] for the theorem is to "simply" take the definition

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

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.