Cayley–Hamilton theorem

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 numbers or the integers) satisfies its own characteristic equation.

The characteristic polynomial of an matrix is defined as $p_A(\lambda)=\det(\lambda I_n-A)$, where is the determinant operation, is a variable scalar element of the base ring, and is the identity matrix. Since each entry of the matrix $(\lambda I_n-A)$ is either constant or linear in , the determinant of $(\lambda I_n-A)$ is a degree- monic polynomial in , so it can be written as
$p_A(\lambda) = \lambda^n + c_\lambda^ + \cdots + c_1\lambda + c_0.$ By replacing the scalar variable with the matrix , one can define an analogous matrix polynomial expression, $p_A(A) = A^n + c_A^ + \cdots + c_1A + c_0I_n.$
(Here, $A$ is the given matrix—not a variable, unlike $\lambda$—so $p_A(A)$ is a constant rather than a function.)
The Cayley–Hamilton theorem states that this polynomial expression is equal to the zero matrix, which is to say that $p_A(A) = \mathbf 0;$ that is, the characteristic polynomial $p_A$ is an annihilating polynomial for $A.$

One use for the Cayley–Hamilton theorem is that it allows to be expressed as a linear combination of the lower matrix powers of :
$A^n = -c_A^ - \cdots - c_1A - c_0I_n.$
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.

A special case of the theorem was first proved by Hamilton in 1853 in terms of inverses of linear functions of quaternions. This corresponds to the special case of certain real or complex matrices. Cayley in 1858 stated the result for and smaller matrices, but only published a proof for the case. As for matrices, Cayley stated “..., I have not thought it necessary to undertake the labor of a formal proof of the theorem in the general case of a matrix of any degree”. The general case was first proved by Ferdinand Frobenius in 1878.

Examples

matrices

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

matrices

As a concrete example, let
$A = \begin1&2\\3&4\end.$
Its characteristic polynomial is given by
$\begin p(\lambda) &= \det(\lambda I_2-A) = \det\!\begin\lambda-1&-2\\-3&\lambda-4\end \\ &=(\lambda-1)(\lambda-4)-(-2)(-3)=\lambda^2-5\lambda-2. \end$

The Cayley–Hamilton theorem claims that, if we ''define''
$p(X) = X^2 - 5X - 2I_2,$
then
$p(A) = A^2-5A-2I_2 = \begin0&0\\0&0\\\end.$
We can verify by computation that indeed,
$A^2-5A-2I_2 = \begin7&10\\15&22\\\end - \begin5&10\\15&20\\\end - \begin2&0\\0&2\\\end = \begin0&0\\0&0\\\end.$

For a generic matrix,
$A=\begina&b\\c&d\\\end ,$

the characteristic polynomial is given by , so the Cayley–Hamilton theorem states that
$p(A) = A^2-(a+d)A+(ad-bc)I_2 = \begin0&0\\0&0\end;$
which is indeed always the case, evident by working out the entries of .

Applications

Determinant and inverse matrix

For a general invertible matrix , i.e., one with nonzero determinant, ⁻¹ 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:
$s_k = \sum_^n \lambda_i^k = \operatorname(A^k),$
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 asSee Sect. 2 of . An explicit expression for the coefficients
is provided by :
$c_i = \sum_\prod_^ \frac\operatorname(A^l)^,$
where the sum is taken over the sets of all integer partitions satisfying the equation
$\sum_^lk_ = n-i.$
$c_ = \frac B_k(s_1, -1! s_2, 2! s_3, \ldots, (-1)^(k-1)! s_k).$

In particular, the determinant of equals . Thus, the determinant can be written as the trace identity:
$\det(A) = \frac B_n(s_1, -1! s_2, 2! s_3, \ldots, (-1)^(n-1)! s_n).$

Likewise, the characteristic polynomial can be written as
$-(-1)^n\det(A)I_n = A(A^+c_A^+\cdots+c_I_n),$
and, by multiplying both sides by (note ), one is led to an expression for the inverse of as a trace identity,

\begin
A^ & = \frac(A^+c_A^+\cdots+c_I_n), \\ pt & = \frac\sum_^ (-1)^\frac B_k(s_1, -1! s_2, 2! s_3, \ldots, (-1)^(k-1)! s_k).
\end

Another method for obtaining these coefficients for a general matrix, provided no root be zero, relies on the following alternative expression for the determinant,
$p(\lambda)= \det (\lambda I_n -A) = \lambda^n \exp (\operatorname (\log (I_n - A/\lambda))).$
Hence, by virtue of the Mercator series,
$p(\lambda)= \lambda^n \exp \left( -\operatorname \sum_^\infty \right),$
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. (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 as determinants of matrices,See, e.g., p. 54 of , which solves Jacobi's formula,
$\frac = p(\lambda) \sum^\infty _\lambda ^ \operatornameA^m = p(\lambda) ~ \operatorname \frac\equiv\operatorname B~,$
where is the adjugate matrix of the next section.

There also exists an equivalent, related recursive algorithm introduced by Urbain Le Verrier and Dmitry Konstantinovich Faddeev—the Faddeev–LeVerrier algorithm, which reads

\begin
M_0 &\equiv O & c_n &= 1 \qquad &(k=0) \\ ptM_k &\equiv AM_ -\frac(\operatorname(AM_)) I \qquad \qquad & c_ &= -\frac 1 k \operatorname(AM_k) \qquad &k=1,\ldots ,n ~.
\end

(see, e.g., .) Observe as the recursion terminates.
See the algebraic proof in the following section, which relies on the modes of the adjugate, .
Specifically, $(\lambda I-A) B = I p(\lambda)$ and the above derivative of when one traces it yields

$\lambda p' -n p =\operatorname (AB)~,$ (), and the above recursions, in turn.
$c_ = \frac \begin \operatornameA & m-1 & 0 & \cdots \\ \operatornameA^2 &\operatornameA & m-2 &\cdots \\ \vdots & \vdots & & & \vdots \\ \operatornameA^ &\operatornameA^& \cdots & \cdots & 1 \\ \operatornameA^m &\operatornameA^& \cdots & \cdots & \operatornameA \end ~.$

; 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

\begin
c_2 = B_0 = 1, \\ ptc_1 = \frac B_1(s_1) = - s_1 = - \operatorname(A), \\ ptc_0 = \frac B_2(s_1, -1! s_2) = \frac(s_1^2 - s_2) = \frac((\operatorname(A))^2 - \operatorname(A^2)).
\end

The coefficient gives the determinant of the matrix, minus its trace, while its inverse is given by
$A^ = \frac(A + c_1 I_2) = \frac.$

It is apparent from the general formula for ''c''_{''n''−''k''}, expressed in terms of Bell polynomials, that the expressions
$-\operatorname(A)\quad \text \quad \tfrac 1 2 (\operatorname(A)^2 - \operatorname(A^2))$

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
$A^3- (\operatornameA)A^2+\frac\left((\operatornameA)^2-\operatorname(A^2)\right)A-\det(A)I_3=O,$
where the right-hand side designates a matrix with all entries reduced to zero. Likewise, this determinant in the case, is now
\begin
\det(A) &= \frac B_3(s_1, -1! s_2, 2! s_3) = \frac(s_1^3 + 3 s_1 (-s_2) + 2 s_3) \\ pt &= \frac \left (\operatornameA)^3-3\operatorname(A^2)(\operatornameA)+2\operatorname(A^3) \right
\end
This expression gives the negative of coefficient of in the general case, as seen below.

Similarly, one can write for a matrix ,
A^4-(\operatornameA)A^3 + \tfrac\left \operatornameA)^2-\operatorname(A^2)\right^2 - \tfrac\left (\operatornameA)^3-3\operatorname(A^2)(\operatornameA)+2\operatorname(A^3)\rightA + \det(A)I_4 = O,

where, now, the determinant is ,

\tfrac\! \left (\operatornameA)^4-6 \operatorname(A^2)(\operatornameA)^2 + 3\left(\operatorname(A^2)\right)^2 + 8\operatorname(A^3)\operatorname(A) -6\operatorname(A^4) \right

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 (though not always the simplest one), which allows one to simplify expressions involving such powers, and evaluate them without having to compute the power ^''n'' or any higher powers of .

As an example, for $A = \begin1&2\\3&4\end$ the theorem gives
$A^2=5A+2I_2\, .$

Then, to calculate , observe
\begin
A^3&=(5A+2I_2)A=5A^2+2A=5(5A+2I_2)+2A=27A+10I_2, \\ exA^4&=A^3A=(27A+10I_2)A=27A^2+10A=27(5A+2I_2)+10A=145A+54I_2\, .
\end
Likewise,
\begin
A^ &= \frac\left(A-5I_2\right)~. \\ exA^ &= A^ A^ = \frac \left(A^2-10A+25I_2\right) = \frac \left((5A+2I_2)-10A+25I_2\right) = \frac \left(-5A+27I_2\right)~.
\end

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
$f(x) = \sum_^\infty a_k x^k$
and the characteristic polynomial of degree of an matrix , the function can be expressed using long division as
$f(x) = q(x) p(x) + r(x),$
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
$f(A) = r(A).$

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

Let the remainder polynomial be
$r(x) = c_0 + c_1 x + \cdots + c_ x^.$
Since , evaluating the function at the eigenvalues of yields
$f(\lambda_i) = r(\lambda_i) = c_0 + c_1 \lambda_i + \cdots + c_ \lambda_i^, \qquad \text i=1,2,...,n.$
This amounts to a system of linear equations, which can be solved to determine the coefficients . Thus, one has
$f(A) = \sum_^ c_k A^k.$

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
$\left.\frac\_ = \left.\frac\_\qquad \text k = 1, 2, \ldots, m-1,$
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

HOME


Content is Copyleft
Website design, code, and AI is Copyrighted (c) 2014-2017 by Stephen Payne


Consider donating to Wikimedia



As an Amazon Associate I earn from qualifying purchases