Applications of the Cayley-Hamilton theorem

Question

The Cayley-Hamilton theorem is usually presented in standard undergraduate courses in linear algebra as an important result. Recall that it says that any square matrix is a "root" of its own characteristic polynomial.

Question. Does this theorem have important applications?

Being not an algebraist, I am aware of only one application of this result which I would call important; it is very basic for commutative algebra, algebraic geometry, and number theory. It is as follows. Let a commutative unital ring $A$ be imbedded into a field $K$. Consider the set of elements of $K$ which are integral over $A$, i.e. are roots of a polynomial with coefficients in $A$ with the leading coefficient equal to 1. Then this set is a subring of $K$.

Answer 1

Cayley-Hamilton theorem can be used to prove Gelfand's formula (whose usual proofs rely either on complex analysis or normal forms of matrices).

Let $A$ be a $d\times d$ complex matrix, let $\rho(A)$ denote spectral radius of $A$ (i.e., the maximum of the absolute values of its eigenvalues), and let $\|A\|$ denote the norm of $A$. (Fix your favorite matrix norm.)

Gelfand's formula: $\rho(A) = \lim_{n \to \infty} \|A^n\|^{1/n}$.

Proof: The choice of the norm does not affect the validity of the result, so choose an operator norm. The existence of the limit $r:=\lim_{n \to \infty} \|A^n\|^{1/n}$ is a simple consequence of submultiplicativity of the norms (by Fekete Lemma). Existence of (complex) eigenvectors implies $r \ge \rho(A)$, so the nontrivial part is to show that $r \le \rho(A)$.

It follows from Cayley-Hamilton theorem that $$\|A^d\|\le C \rho(A) \|A\|^{d-1},$$ where $C>0$ is a constant that depends only on $d$; this is a straightforward exercise -- or see this post by Ian Morris for the details.

Applying this inequality to $A^n$ and taking the $n$-th root we obtain: $$\|A^{dn}\|^{1/n}\le C^{1/n} \rho(A) \|A^n\|^{(d-1)/n}.$$ Making $n \to \infty$ we get $r^d \le \rho(A) r^{d-1}$, thus concluding the proof of Gelfand's formula.

Reference:

Jairo Bochi, Inequalities for numerical invariants of sets of matrices, Linear Algebra Appl. 368 (2003), 71--81.

Answer 2

Cayley-Hamilton can be useful in commutative algebra. Related to its close connection with Nakayama's lemma as mentioned in a comment by Qiaochu (see also Wikipedia), see for example the development given in the Stacks Project here. Among the consequences that I find sort of cool and maybe even a little surprising at first glance, we have

• Let $M$ be a finitely generated module over a commutative ring. Then any surjective module map $M \to M$ is an isomorphism.

Answer 3

In control theory, it is used to define very important concepts of observability and controllability of linear systems.

http://www.ece.rutgers.edu/~gajic/psfiles/chap5traCO.pdf

Answer 4

This may be too trivial for what you have in mind, but I've always found Cayley-Hamilton useful to calculate eigenvectors of a square matrix given the eigenvalues, without having to solve any additional equations.

Suppose that you have a square matrix $A$ over $\mathbb{C}$, say, and that you have determined its characteristic polynomial $$ \chi_A(z) = (z-\lambda_1)(z-\lambda_2) \cdots (z-\lambda_N) $$ where the eigenvalues $\{\lambda_i\}$ may be repeated. Then if you pick any vector $v$, Cayley-Hamilton tells you that $$ (A-\lambda_1)\cdots (A-\lambda_{i-1})(A-\lambda_{i+1})\cdots (A-\lambda_N) v $$ lies in the kernel of $(A-\lambda_i)$ for all $i$. (It could be zero, of course, so one has to play a little sometimes.)

Answer 5

A nice application is Ilya Bogdanov's mathoverflow answer which proves in less than $3$ lines that the elements of $\text{GL}(n,\mathbb F_q)$ have order at most $q^n-1$.

Answer 6

This might be somewhat vague, but the Cayley-Hamilton theorem is important in Galois theory. Specifically, if $L/K$ is a finite extension of fields, then an element $a \in L$ has both a minimal polynomial and a characteristic polynomial over $K$. The Cayley-Hamilton theorem yields that the former divides the latter. The two polynomials have their different advantages -- e.g., the minimal polynomial is irreducible and thus can be used to study intermediate fields, whereas the characteristic polynomial depends polynomially on $a$, always has degree $\left[L:K\right]$, and has various other nice functoriality-type properties. The divisibility relation between them makes it possible for one of them to help out the other when necessary.

Concrete example (Proposition 8.6 in Patrick Morandi, Field and Galois theory, Springer 1996, quoted with edits):

Let $K / F$ be a field extension, and let $n = \left[K : F\right] < \infty$. Let $a \in K$, and let $p\left(x\right) = x^m + a_{m-1} x^{m-1} + \cdots + a_1 x^1 + a_0 x^0$ be the monic minimal polynomial of $x$ over $F$. Then, $\operatorname{Norm}_{K/F}\left(a\right) = \left(-1\right)^n a_0^{n/m}$ and $\operatorname{Tr}_{K/F}\left(a\right) = -\dfrac{n}{m} a_{m-1}$.

Answer 7

Cayley-Hamilton is part of what makes the Wiedemann algorithm for efficient sparse linear algebra work so well

Answer 8

The Cayley-Hamilton theorem is used in the proof of a Theorem of Jacobson:

Let $k$ be a field of characteristic $0$. Let $A,B\in{\bf M}_n(k)$ be such that $[[A,B],A]=0_n$. Then $[A,B]$ is nilpotent.

A consequence is that if $A\in{\bf M}_n({\mathbb C})$ satisfies $[[A,A^*],A]=0_n$, then $A$ is normal.

Answer 9

I hope that readers will forgive my answering a slightly different question by describing what I perceive to be the value of the Cayley-Hamilton Theorem in general: it captures in an essential way the fact that $A$ is specifically a $d$-dimensional matrix. I have a couple of rules of thumb in linear algebra, and one is that if I am using the $d$-dimensionality of a matrix in some specific way then surely the Cayley-Hamilton Theorem lies just around the corner. Let me list some examples:

1) Noam Elkies provided an excellent answer to a different question which bears repetition here. The question is, why is it obvious that $$\left(\begin{array}{cc}a&b\\c&d\end{array}\right)^{-1}=\frac{1}{ad-bc}\left(\begin{array}{cc}d&-b\\-c&a\end{array}\right)?$$ Let us denote the matrix in question by $A$; then as Noam points out, $$A^2-(\mathrm{tr} A)A+(\det A)I=0$$ and so multiplying by $(\det A)A^{-1}$ yields $$A^{-1}=\frac{1}{\det A}\left((\mathrm{tr A})I-A)\right)$$ which is clearly the formula given above. This is inherently a statement specific to two-dimensional matrices, so it is natural that we use the Cayley-Hamilton Theorem in order to capture the specific fact that the dimension is $2$.

2) If $A^n=0$ for some integer $n>0$ then necessarily $A^d=0$. Indeed, if $A^n=0$ then no nonzero eigenvalues exist and the characteristic polynomial is $x^d$, so by Cayley-Hamilton $A^d=0$.

3a) $\min\{\mathrm{rank }\,A^n\colon n \geq 0\}=\mathrm{rank}\,A^d$. Equivalently, $\max\{\mathrm{dim}\,\mathrm{ker}\,A^n\colon n \geq 0\}=\mathrm{dim}\,\mathrm{ker}\,A^d$. Equivalently:

3b) If $A^nv=0$ for some $n>0$ then necessarily $A^dv=0$. Proof: consider the vector space $V$ generated by the vectors $A^iv$ for $i \geq 0$. We have $AV\subseteq V$ and $A^nV=\{0\}$. Let $d'=\dim V \leq d$ and let $B:=A|_V$, then $B^n=0$, hence $B^{d'}=0$ using 2 above, hence $B^d=0$, hence $A^dv=0$, QED.

4) would have been Jairo's answer if he hadn't posted it already =o)

Answer 10

For recent examples of perhaps surprising applications in quite advanced research topics, one can note the following:

• A graphical proof of the Cayley-Hamilton Theorem inspired Prop 7.1 in this work of V. Lafforgue.
• The Cayley-Hamilton Theorem is also a key element in the proof of a new case of Zamolodchikov periodicity by Pylyavskyy, see Section 3.3 of this article.

Answer 11

Here is a beautiful result from numerical analysis. Given any nonsingular $n\times n$ system of linear equations $Ax=b$, an optimal Krylov subspace method like GMRES must necessarily terminate with the exact solution $x=A^{-1}b$ in no more than $n$ iterations (assuming exact arithmetic).

The Cayley-Hamilton theorem provides a simple, elegant proof of this statement. To begin, recall that at the $k$-th iteration, minimum residual methods like GMRES solve the least-squares problem $$\underset{x_k\in\mathbb{R}^n}{\text{minimize }} \|Ax_k-b\|$$ by picking a solution from the $k$-th Krylov subspace $$\text{subject to } x_k \in \mathrm{span}\{b,Ab,A^2b,\ldots,A^{k-1}b\}.$$ If the objective $ \|Ax_k-b\|$ goes to zero, then we have found the exact solution at the $k$-th iteration (we have assumed that $A$ is full-rank).

Next, observe that $x_k=(c_0 + c_1 A + \cdots + c_{k-1}A^{k-1})b=p(A)b$, where $p(\cdot)$ is a polynomial of order $k-1$. Similarly, $\|Ax_k-b\|=\|q(A)b\|$, where $q(\cdot)$ is a polynomial of order $k$ satisfying $q(0)=-1$. So the least-squares problem from above for each fixed $k$ can be equivalently posed as a polynomial optimization problem with the same optimal objective

$$\text{minimize } \|q_k(A)b\| \text{ subject to } q_k(0)=-1,\; q_k(\cdot) \text{ is an order-} k \text{ polynomial.}$$ Again, if the objective $\|q_k(A)b\|$ goes to zero, then GMRES has found the exact solution at the $k$-th iteration.

Finally, we ask: what is a bound on $k$ that guarantees that the objective goes to zero? Well, with $k=n$, and the optimal polynomial $q_n(\cdot)$ for our polynomial optimization problem is just the characteristic polynomial of $A$. According to Cayley-Hamilton, $q_n(A)=0$, so $\|q_n(A)b\|=0$. Hence we conclude that GMRES always terminate with the exact solution at the $n$-th iteration.

This same argument can be repeated (with very minor modifications) for other optimal Krylov methods like conjugate gradients, conjugate residual / MINRES, etc. In each case, the Cayley-Hamilton forms the crux of the argument.

Answer 12

Cayley-Hamilton can be used to prove the classification of finite-dimensional real division algebras (though there are probably many other proofs).

Answer 13

There is a very important theorem by Procesi that derives all polynomial identities of the ring of matrices from the Cayley-Hamilton theorem. For a review of rings with polynomial identities see this paper by Procesi.

Answer 14

Resolution of (homogeneous) linear differential systems (HLDS). Unless I am wrong, nobody above mentioned the use of Cayley-Hamilton Theorem (CHT) in computing exp(A) (A a nxn complex martix). This is well known. So let me recall : 1)First of all, CHT shows that exp(A) is a linear combination of the matrices A^i (i=0,1,...,n-1). 2) Second,if A has exacty one eigenvalue t , then exp(A) is easy to compute since exp(A)=exp(t).exp(A-tI), and A-tI is nilpotent by CHT. This gives the general solution of the HLDS defined by A. ( In the general case, one consructs a basis made of eigenvectors and characteristic vectors to wich exp(xA) is applied to get the general solution of the HLDS defined by A. Here again the use of CHT is implicit).