MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
6  
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. – Arturo Magidin Feb 25 at 17:58
5  
Nakayama's lemma is typically proven using a mild generalization of Cayley-Hamilton, and it's quite important. – Qiaochu Yuan Feb 25 at 18:13
2  
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?! – Nick Gill Feb 25 at 18:51
2  
@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. – paul garrett Feb 25 at 19:12
5  
@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. – Robert Israel Feb 25 at 21:07

13 Answers 13

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.
share|cite|improve this answer
3  
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}$) – Denis Nardin Feb 25 at 20:58
1  
@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! – darij grinberg Feb 26 at 0:47

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

share|cite|improve this answer

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

share|cite|improve this answer
    
Is it less work to calculate that product than it is to solve the relevant system of equations? – Gerry Myerson Feb 25 at 21:52
5  
@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. – Johannes Hahn Feb 25 at 22:05
3  
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. – Johannes Hahn Feb 25 at 22:07
    
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. – José Figueroa-O'Farrill Feb 26 at 0:22
    
This is a nice trick. Could you give a specific example where you find it useful (or “psychologically” easier to use)? – ACL Mar 1 at 18:46

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.

share|cite|improve this answer
1  
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. – Ian Morris Mar 1 at 19:08
    
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. – Denis Serre Mar 15 at 17:11
    
@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. – Jairo Bochi Mar 16 at 14:55

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

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer
    
I was about to mention this but then saw that you got there an hour before me. – Noam D. Elkies Feb 26 at 1:24

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.

share|cite|improve this answer

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.
share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer

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)

share|cite|improve this answer

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

share|cite|improve this answer
    
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. – Denis Serre Jul 5 at 16:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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