The Cayley-Hamilton Theorem

Definition Let $M$ be an $n \times n$ matrix whose entries lie in $\mathbb{F}$ or in the polynomial ring $\mathbb{F}[t]$. For $n \ge 2$ the cofactor $C_{ij}$ is $(-1)^{i+j}$ times the determinant of the $(n - 1) \times (n - 1)$ matrix obtained by deleting row $i$ and column $j$ of $M$, and for $n = 1$ the single cofactor is $1$. The adjugate of $M$ is the transpose of the cofactor matrix, $(\operatorname{adj} M)_{ij} = C_{ji}$. The adjugate identity says

Entry $(i, i)$ of $M \operatorname{adj}(M)$ is $\sum_k m_{ik} C_{ik}$, the cofactor expansion of $\det M$ along row $i$. For $i \ne j$, entry $(i, j)$ is $\sum_k m_{ik} C_{jk}$, which is the expansion along row $j$ of the matrix obtained from $M$ by replacing row $j$ with a copy of row $i$. That matrix has two equal rows, so the entry is $0$. Expansions along columns give the second product in the same way. The permutation formula for the determinant and every step of this argument use only sums and products of entries, so the identity also holds when the entries are polynomials in $t$. For $M = tI - A$ it reads

Definition A polynomial with matrix coefficients is an expression

with $B_0, \dots, B_k \in \mathbb{F}^{n \times n}$ and $t$ a scalar variable. Its entry $(i, j)$ is the scalar polynomial $\sum_r (B_r)_{ij}\, t^r$, so these expressions are the same objects as $n \times n$ matrices with entries in $\mathbb{F}[t]$. Two of them are equal exactly when they have the same coefficient matrix at every power of $t$. Since the scalar $t$ commutes with every matrix, products are formed by

with each $B_r$ kept to the left of $D_s$. For $n \ge 2$ every entry of $\operatorname{adj}(tI - A)$ is, up to sign, the determinant of an $(n - 1) \times (n - 1)$ matrix whose entries have degree at most one in $t$, and for $n = 1$ the adjugate is the constant $I$. In both cases there are matrices $B_0, \dots, B_{n-1} \in \mathbb{F}^{n \times n}$ with

Replacing $t$ by a matrix $X$ in an identity between such polynomials is not allowed in general, because $t$ commutes with every coefficient and $X$ need not.

Definition Let $\mathbb{F}$ be $\mathbb{R}$ or $\mathbb{C}$, let $n \ge 1$ and $A \in \mathbb{F}^{n \times n}$, and write $\chi_A(t) = t^n + c_{n-1}t^{n-1} + \cdots + c_1 t + c_0$. The Cayley-Hamilton theorem says that

The same holds for every operator $T$ on a nonzero finite-dimensional space, with $\chi_T$ computed from any matrix of $T$. For the proof, write $\operatorname{adj}(tI - A) = \sum_{j=0}^{n-1} B_j t^j$, multiply out $(tI - A)\operatorname{adj}(tI - A)$ and compare coefficients with $\chi_A(t)\, I$. The coefficient of $t^n$ gives $B_{n-1} = I$, the coefficient of $t^j$ for $1 \le j \le n - 1$ gives $B_{j-1} - AB_j = c_j I$, and the constant term gives $-AB_0 = c_0 I$. Multiply the equation for $t^j$ on the left by $A^j$, so that $c_j A^j = A^j B_{j-1} - A^{j+1} B_j$, and add all the terms of $\chi_A(A)$.

Every product $A^k B_{k-1}$ with $1 \le k \le n$ appears once with a plus sign and once with a minus sign, in the same factor order, so the sum telescopes to $0$. Reading $B_{j-1} = AB_j + c_j I$ downward from $B_{n-1} = I$ also shows that every $B_j$ is a polynomial in $A$. Since $\chi_A$ annihilates $A$, the minimal polynomial divides it, $\mu_A \mid \chi_A$, and in particular $\deg \mu_A \le n$.

Definition Let $m$ be any annihilating polynomial of $A$, for example $\chi_A$ by the Cayley-Hamilton theorem or $\mu_A$, and let $d = \deg m$. For $f \in \mathbb{F}[t]$, divide $f = qm + r$ with $r = 0$ or $\deg r < d$. Evaluating at $A$ gives

so every power $A^k$, and every polynomial in $A$, is a combination of $I, A, \dots, A^{d-1}$. For $n = 2$, with trace $\tau$ and determinant $\delta$, the theorem gives $A^2 = \tau A - \delta I$. Writing $A^k = \alpha_k A + \beta_k I$ with $\alpha_1 = 1$ and $\beta_1 = 0$, one more multiplication by $A$ gives $A^{k+1} = \alpha_k(\tau A - \delta I) + \beta_k A$, which is the recurrence

Definition For $A \in \mathbb{F}^{n \times n}$, the Cayley-Hamilton theorem and the divisibility theorem give $\mu_A \mid \chi_A$, so $\deg \mu_A \le n$. Both polynomials have the same roots in $\mathbb{F}$, namely the eigenvalues of $A$ in $\mathbb{F}$. Suppose $\chi_A$ splits into linear factors over $\mathbb{F}$, as it always does for $\mathbb{F} = \mathbb{C}$. Then $\mu_A$, a divisor of $\chi_A$, splits too. If $\lambda_1, \dots, \lambda_s$ are the distinct eigenvalues and $a_i$ is the algebraic multiplicity of $\lambda_i$, then

with $1 \le m_i \le a_i$ for every $i$. The upper bound comes from divisibility, and the lower bound from the fact that every eigenvalue is a root of $\mu_A$. In general $\chi_A$ does not determine the exponents $m_i$, although $a_i = 1$ forces $m_i = 1$. The two polynomials are equal exactly when $\deg \mu_A = n$.