# Cayley-Hamilton revisited

Let $(A_i)_i$ be $n\times n$ matrices with entries in a field $K$ with characteristic $0$. We consider the equation (1) $f(X)=A_kX^k+\cdots+A_1X+A_0=0_n$ where $X\in\mathcal{M}_n(K)$ is unknown. Let $g = \det(\lambda^kA_k+\cdots+\lambda A_1+A_0)\in K[\lambda]$.

Question: is it true that, if $B$ is a solution of (1) ($f(B)=0_n$), then $g(B)=0$ ?

i) In 1884, Sylvester seemed to think that it is true, but, without proof (as often with him).

ii) This result is "proved" in: K. Kanwar. A generalization of the Cayley-Hamilton Theorem. Advances in PURE mathematics.2013. Yet, the proof is obviously false !! Recall that this journal has already been the subject of a scandal: http://boingboing.net/2012/10/19/math-journal-accepts-computer.html So the problem seems not settled.

• I'm not following. How can you apply $g$ to a matrix? The domain of $g$ is the ground field. – Todd Trimble Oct 25 '13 at 18:00
• @Todd: I think what was intended is that $\lambda^k A_k + ... + \lambda A_1 + A_0$ is a matrix with entries in $K[\lambda]$, so its determinant is an element of $K[\lambda]$, and we are applying this abstract polynomial to $B$. – Qiaochu Yuan Oct 25 '13 at 18:01
• @QiaochuYuan Ah yes; thanks. Wonder if I should edit. – Todd Trimble Oct 25 '13 at 18:04
• In applying g to B you need to decide on what side the matrix coefficients are... – Mariano Suárez-Álvarez Oct 25 '13 at 18:38
• @suv: neither, it's the thing I mentioned in my comment above. Your formulation of the problem makes it trivially true if the $A_k$ are chosen to be on the left. – Qiaochu Yuan Oct 25 '13 at 19:03

Yes, this follows from known facts on matrix polynomials. There is a full characterization of spectral divisors of matrix polynomials in Gohberg, Lancaster, Rodman, Matrix Polynomials. They treat monic polynomials (i.e., $A_k=1$), but this is not a restriction, since one can make a Möbius transform to enforce it unless $g(\lambda)\equiv 0$.

They introduce so-called standard pairs of a matrix polynomial $A(\lambda)$, which are in some sense a generalization of the companion matrix. Then they prove (Thm 3.12) that if a polynomial $Q(\lambda)$ is a right divisor of $P(\lambda)$ then the standard pair of $Q$ is a restriction of that of $P$; translating it to companion matrices, it would mean that the companion matrix of $Q$ can be obtained as a restriction of that of $P$ to an invariant subspace.

We apply that to $\lambda I - B$ (for which the "companion matrix" is $B$ itself) and $P(\lambda)=\sum_{i=0}^k A_i \lambda^i$. In particular, this means that the Jordan structure of $B$ is a substructure of that of the companion matrix of $P(\lambda)$, hence the algebraic multiplicities of the eigenvalues of $B$ are less or equal than those of $P(\lambda)$, that is, the characteristic polynomial of $B$ is a divisor of your $g(\lambda)$.

Not sure how much of this is understandable -- I must admit that book has not the reputation for being an easy-to-read one in the community. A more self-contained approach to these topics is in: I. Gohberg, M.A. Kaashoek and P. Lancaster, General theory of regular matrix polynomials and band Toeplitz operators.

• Incidentally, I searched for polynomial eigenvalue problems and ran into this reference just a minute ago :-) --- though somehow I'm still not sure if the claim holds without further qualification... – Suvrit Oct 25 '13 at 19:31
• Ok, now I am convinced :-) – Suvrit Oct 25 '13 at 20:48
• Federico, thanks for your first post ; Lancaster is a charming man but, unfortunately, his book (matrix polynomials) falls me hands. – loup blanc Oct 26 '13 at 17:07

Am I missing something or is Ilya Bogdanov's elimination of $A_0$ trick more or less a proof in itself?

Assume that $f\left(B\right) = 0_n$. Then, $0_n = f\left(B\right) = A_kB^k + A_{k-1}B^{k-1} + ... + A_0 = \sum\limits_{i=0}^k A_iB^i$. But

$\lambda^k A_k + \lambda^{k-1}A_{k-1} + ... + A_0 = \sum\limits_{i=0}^k \lambda^i A_i = \sum\limits_{i=0}^k \lambda^i A_i - \sum\limits_{i=0}^k A_iB^i$ (since $0 = \sum\limits_{i=0}^k A_iB^i$)

$= \sum\limits_{i=0}^k A_i \left(\lambda^i-B^i\right)$.

This polynomial is divisible by $\lambda-B$ on the right (because $\lambda^i-B^i$ is divisible by $\lambda-B$ for every $i$). Hence,

$\det\left(\lambda^k A_k + \lambda^{k-1}A_{k-1} + ... + A_0\right)$ is divisible by $\det\left(\lambda-B\right)$.

In other words, $g\left(\lambda\right)$ is divisible by $\det\left(\lambda-B\right)$ (since $\det\left(\lambda^k A_k + \lambda^{k-1}A_{k-1} + ... + A_0\right) = g\left(\lambda\right)$). Since $B$ is a root of the polynomial $\det\left(\lambda-B\right)$ (by the usual Cayley-Hamilton theorem), this yields that $B$ is a root of $g\left(\lambda\right)$, so that $g\left(B\right) = 0$, and we are done.

I agree with Yazdegerd III that the characteristic-$0$ assumption shouldn't be there. Even if my proof would use it, Ilya's observation that the result is a polynomial identity in the entries of $A_k$, $A_{k-1}$, ..., $A_1$ and $B$ should make it clear that it holds over any commutative ring.

To convince people that this is true, let me add a quick proof that works in the special case in which $B$ is diagonalizable with distinct eigenvalues.

By changing bases, we can assume it is in fact diagonal and equal to $\operatorname{diag}(\lambda_1,\lambda_2,\dots,\lambda_n)$. We have $0=\sum A_i B^i e_j=\sum A_i\lambda_j^i e_j$ for the $j$-th vector of the canonical basis $e_j$. Hence for each $\lambda_j$ the matrix $\sum A_i \lambda_j^i$ is singular, so the $\lambda_j$ are all roots of $g(\lambda)=\det p(\lambda)$. In particular, this means that $g(B)=0$.

More care is necessary if $B$ has multiple eigenvalues and Jordan blocks, of course.

• Since the generic matrix has distinct eigenvalues, the general case follows. Actually, you may take the coefficients of $B$ and $A_1,\dots,A_k$ as independent variables, then define $A_0$ from $f(B)=0$ and check only this case, all others being its images. – Ilya Bogdanov Oct 26 '13 at 7:52
• You are correct! This can be indeed turned into a complete proof with a genericity / continuity argument. Thanks for pointing it out, overall it's a much simpler solution than I expected at first. – Federico Poloni Oct 26 '13 at 9:52
• The result given by Federico is known. In fact, it is sufficient that $B$ is diagonalizable, because any eigenvalue of a solution is a root of $g$ and $g(B)=diag(g((\lambda_i))=0$. I thought that the previous result is not very interesting because, even if the roots of $g$ are simple, I do not see why the eigenvalues of any solution would be simple. But Ilya shows that I was wrong. About his comment, to fix the unknown and the constants, except one, as indeterminates, is a simple but great idea. Bravissimo... – loup blanc Oct 26 '13 at 17:09
• Federico writes "This can be indeed turned into a complete proof with a genericity / continuity argument" and he is right. Indeed we must specialize $B$ and $A_1,\cdots,A_k$ in $K$ (assumed to be algebraically closed). Thus the polynomial $g$ is zero out of an algebraic set, that is in a Zariski-dense set....This works in charateristic $0$. Yazdegerd III asks for characteristic $>0$. Perhaps it is sufficient that $K$ is infinite ?? – loup blanc Oct 26 '13 at 17:21

Yes, this is precisely Theorem 4 in Chapter VIII, $\S$5 of F. R. Gantmacher, The Theory of Matrices, Vol. 1. The proof seems to be essentially that in darij grinberg's answer.

Thanks for Federico for pointing out my stupid matlab typo :-) the counterexample below is false, so am deleting it.

I must be missing something or doing something silly, because I think it is false. Here is an explicit counterexample:

Let $k=2$. Let $A_2=I$, $A_1=\left( \begin{array}{cc} -1 & -6 \\ 2 & -9 \end{array} \right)$, and $A_0=\left( \begin{array}{cc} 0 & 12 \\ -2 & 14 \end{array} \right)$. Verify that

$B^2+A_1B+A_0=0$ for $B=\left( \begin{array}{cc} 1 & 0 \\ 0 & 2 \end{array} \right)$.

Also, note that $\det(\lambda^2 I_2 + \lambda A_1+A_0) = 24-50 \lambda +35 \lambda ^2-10 \lambda ^3+\lambda ^4$. But,

\begin{equation*} 24-50B + 35B^2 -10B^3 + B^4 = \left( \begin{array}{cc} 0 & 24 \\ 24 & 0 \end{array} \right). \end{equation*}

• $24-50B+35B^2-10B^3+B^4=0$ on my computer. I think you mistakenly ended your Matlab line with a "+24" rather than with a "+24*eye(2)". :) – Federico Poloni Oct 25 '13 at 20:24
• Indeed, Federico, I ended it with 24 instead of 24*eye!! aaarrgghh – Suvrit Oct 25 '13 at 20:46
• I've made the same error several times --- We should really blame this error-prone Matlab's syntax here. – Federico Poloni Oct 25 '13 at 20:49

Essentially darij grinberg's nice proof can be stated, without using cayley hamilton, and over any commutative ring K, briefly as follows: It suffices by the non commutative root factor theorem to show that f divides g from the right. But polynomials with matrix coefficients are isomorphic to matrices with polynomial entries, and the matrix corresponding to f does divide the matrix corresponding to g from the right (and from the left) by cramers rule. QED