45
$\begingroup$

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$.

$\endgroup$
  • 6
    $\begingroup$ It establishes the relation between the minimal polynomial (in fact, the existence of a minimal polynomial) and the characteristic polynomial, which in turn is key to the development of canonical forms for the matrix. $\endgroup$ – Arturo Magidin Feb 25 '16 at 17:58
  • 5
    $\begingroup$ Nakayama's lemma is typically proven using a mild generalization of Cayley-Hamilton, and it's quite important. $\endgroup$ – Qiaochu Yuan Feb 25 '16 at 18:13
  • 4
    $\begingroup$ I always get my students to use CH to write down a formula for $A^{-1}$, in terms of $I, A, A^2$ etc. I then tell them that this is very useful in practice because it allows you to compute an inverse in a fashion that is not computationally intensive. I must admit, though, that I don't know if this is used in the real world... But, if so, that might be an important application, no?! $\endgroup$ – Nick Gill Feb 25 '16 at 18:51
  • 3
    $\begingroup$ @ArturoMagidin, well, it's not strictly necessary to use C-H to prove there's a minimal poly, because the homomorphism from polynomials to endomorphisms is a map from an infinite-dimensional to finite-dimensional vector space. So canonical forms can be developed without C-H, and then used, if one wants, to prove C-H. $\endgroup$ – paul garrett Feb 25 '16 at 19:12
  • 5
    $\begingroup$ @NickGill In the "real world" of numerical computations involving large matrices, you want to avoid if possible computing the characteristic polynomial, which can involve very large numbers. Finding $A^{-1}$ by standard methods is much less computationally intensive. $\endgroup$ – Robert Israel Feb 25 '16 at 21:07

14 Answers 14

18
$\begingroup$

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.
$\endgroup$
  • 5
    $\begingroup$ The most surprising part is that the corresponding statement for an injective module map is trivially false (e.g. $2:\mathbb{Z}\to \mathbb{Z}$) $\endgroup$ – Denis Nardin Feb 25 '16 at 20:58
  • 2
    $\begingroup$ @DenisNardin: Surjectivity being somehow stronger than injectivity (not as a rule, of course, but as a heuristic) is a common thread in algebra. There is a similar result about algebras instead of modules: math.stackexchange.com/questions/1217452 , but this one is waiting for its Cayley-Hamilton theorem to give it a constructive proof! $\endgroup$ – darij grinberg Feb 26 '16 at 0:47
17
$\begingroup$

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

$\endgroup$
14
$\begingroup$

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.)

$\endgroup$
  • 1
    $\begingroup$ Is it less work to calculate that product than it is to solve the relevant system of equations? $\endgroup$ – Gerry Myerson Feb 25 '16 at 21:52
  • 5
    $\begingroup$ @GerryMyerson If the $\lambda_i$ are pairwise distinct, the expression $(A-\lambda_1)\cdots(A-\lambda_{i-1})(A-\lambda_{i+1})\cdots(A-\lambda_n)$ is an almost-idempotent. In fact $\prod_{j\neq i} \frac{A-\lambda_j}{\lambda_i-\lambda_j}$ is the projection onto the $\lambda_i$-eigenspace. Therefore you can read off a generating set of the eigenspace from this matrix without solving any linear equations. The assumption that the $\lambda_i$ are distinct actually makes the eigenspaces one-dimensional so that any non-zero column is basis for the eigenspace. $\endgroup$ – Johannes Hahn Feb 25 '16 at 22:05
  • 3
    $\begingroup$ But of course, this is not less work in the sense of complexity. It takes $O(n^{1+\omega})$ to compute the product ($\omega$ being the optimal exponent for matrix multiplication. In particular $2\leq \omega < 3$) but only $O(n^3)$ to solve the equation with Gauß's algorithm. $\endgroup$ – Johannes Hahn Feb 25 '16 at 22:07
  • $\begingroup$ I'm not sure if it's "less" work that solving the system of equations, but in the few occasions where I've had to use this, I find it "psychologically" easier perhaps to use Cayley-Hamilton. Anyway, as I said, it's perhaps too trivial an application, but I thought I'd mention it. $\endgroup$ – José Figueroa-O'Farrill Feb 26 '16 at 0:22
  • $\begingroup$ This is a nice trick. Could you give a specific example where you find it useful (or “psychologically” easier to use)? $\endgroup$ – ACL Mar 1 '16 at 18:46
14
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The continuity of $\rho(A)$ in the matrix entries is a trivial corollary: $\rho(A)=\lim_{n\to\infty}\|A^n\|^{1/n}=\inf_{n \geq 1}\|A^n\|^{1/n}$ is obviously upper semi-continuous, and $\rho(A)=\lim_{n \to\infty}\left(\frac{\|A^{nd}\|}{C\|A^n\|^{d-1}}\right)^{1/n}=\sup_{n \geq 1}\left(\frac{\|A^{nd}\|}{C\|A^n\|^{d-1}}\right)^{1/n}$ is obviously lower semi-continuous. $\endgroup$ – Ian Morris Mar 1 '16 at 19:08
  • $\begingroup$ I feel dubious. Gelfand's Formula holds true in every unital Banach algebra $\cal A$. If the dimension of $\cal A$ is infinite, CH is not valid. Therefore, the natural proof of Gelfand's Formula must not involve CH. It involves instead the elementary theory of holomorphic functions. $\endgroup$ – Denis Serre Mar 15 '16 at 17:11
  • 3
    $\begingroup$ @DenisSerre I don't believe in a total order on the set of proofs. BTW, the inequality in my proof can be extended to sets of matrices and, among other applications, used to prove a version of the Gelfand formula in this setting, namely, the Berger-Wang theorem. $\endgroup$ – Jairo Bochi Mar 16 '16 at 14:55
12
$\begingroup$

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$.

$\endgroup$
11
$\begingroup$

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}$.

$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I was about to mention this but then saw that you got there an hour before me. $\endgroup$ – Noam D. Elkies Feb 26 '16 at 1:24
10
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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)

$\endgroup$
5
$\begingroup$

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.
$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I like this explanation of GMRES. What is the optimization problem solved at the $k$th iteration of the conjugate gradient method? $\endgroup$ – littleO Jun 29 '17 at 5:15
  • 1
    $\begingroup$ For CG, the optimization problem at the $k$-th iteration is to minimize the dual A-norm of the residual (equal to the A-norm of the error), that is, define $\|z\|_{A*}^2 \equiv z^T A^{-1} z$, then we wish to minimize $\|Ax_k - b\|_{A*}$ at the $k$-th iteration. Evidently, this only makes sense if $A$ is symmetric posdef. $\endgroup$ – Richard Zhang Apr 10 '18 at 19:04
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ You present this application as if it was a practicle one, but it is not. Because if $n\ge5$, you cannot write in close form the eigenvalues (the roots of the characteristic polynomial), and therefore you have no access to the eigenvectors. $\endgroup$ – Denis Serre Jul 5 '16 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.