Using Cayley–Hamilton to Reduce Powers

From a Polynomial Identity to a Power Recurrence

A direct computation of \(\mathbf{A}^k\) requires multiplying the matrix repeatedly, and the entries can grow quickly. For a square matrix, the Cayley–Hamilton theorem provides another route: a polynomial equation satisfied by \(\mathbf{A}\) can be rearranged to express one power in terms of lower powers. Repeating that replacement reduces any high power to a combination of a fixed, finite list of powers.

Throughout, \(\mathbf{A}\in\mathbb{R}^{n\times n}\), where \(n\geq 1\). The same arguments hold over \(\mathbb{C}\). For a polynomial \(f(\lambda)=a_0+a_1\lambda+\cdots+a_m\lambda^m\), its evaluation at \(\mathbf{A}\) means \(f(\mathbf{A})=a_0\mathbf{I}_n+a_1\mathbf{A}+\cdots+a_m\mathbf{A}^m\). In particular, the constant term becomes a multiple of the identity matrix, not a multiple of the zero matrix.

We use the convention \(p_{\mathbf{A}}(\lambda)=\det(\mathbf{A}-\lambda\mathbf{I}_n)\). Write its coefficients as

The Cayley–Hamilton theorem states that \(p_{\mathbf{A}}(\mathbf{A})=\mathbf{O}\). This theorem, including its proof, was established in the earlier material on Cayley–Hamilton. Since multiplication by the nonzero scalar \((-1)^n\) does not change a zero matrix equation, substituting \(\mathbf{A}\) into the displayed polynomial gives

Proof. By Cayley–Hamilton, \(\mathbf{A}^n+\gamma_{n-1}\mathbf{A}^{n-1}+\cdots+\gamma_0\mathbf{I}_n=\mathbf{O}\). For \(k\geq n\), multiply this equation on the right by \(\mathbf{A}^{k-n}\). Matrix multiplication distributes over addition, and \(\mathbf{A}^i\mathbf{A}^{k-n}=\mathbf{A}^{i+k-n}\). The resulting equation is \(\mathbf{A}^k+\gamma_{n-1}\mathbf{A}^{k-1}+\cdots+\gamma_0\mathbf{A}^{k-n}=\mathbf{O}\). Moving all but the first term to the right gives the stated recurrence. \(\square\)

The recurrence starts at \(k=n\); its final term is then \(\mathbf{A}^0=\mathbf{I}_n\). Each later application replaces a power by terms with smaller exponents. The coefficients do not change from one step to another, but the powers do, so it is important to update every exponent carefully.

Reducing Powers Step by Step

For a two-by-two matrix, the recurrence always replaces powers of degree at least two by combinations of \(\mathbf{I}_2\) and \(\mathbf{A}\). A repeated root in the characteristic polynomial does not prevent the reduction: Cayley–Hamilton applies whether the roots are distinct or repeated.

All Powers Reduce to a Bounded List

The recurrence has a useful general consequence: after reduction, no power higher than \(\mathbf{A}^{n-1}\) is needed. This is a statement about spanning a set of matrices; it does not claim that the listed matrices are linearly independent.

Proof. We use induction on \(k\). For \(0\leq k<n\), the claim holds because \(\mathbf{A}^k\) is itself one of the listed matrices. Now let \(k\geq n\), and assume that every power with exponent less than \(k\) is a linear combination of the list. By the power recurrence, \(\mathbf{A}^k\) is a linear combination of powers with exponents \(k-1,k-2,\dots,k-n\), all of which are nonnegative and less than \(k\). By the induction hypothesis, each of those powers is itself a linear combination of \(\mathbf{I}_n,\mathbf{A},\dots,\mathbf{A}^{n-1}\). Substituting those combinations proves the claim for \(k\), completing the induction. \(\square\)

Because polynomial evaluation is linear in the coefficients, the same conclusion applies to any polynomial in \(\mathbf{A}\): if \(f(\lambda)\) is a polynomial, then \(f(\mathbf{A})\) can be expressed using powers only from \(\mathbf{I}_n\) through \(\mathbf{A}^{n-1}\). To see why, write \(f\) as a finite sum of scalar multiples of powers. Each power in that sum can be replaced by the combination guaranteed by the corollary, and then the resulting terms can be collected.

Coefficient Checks and Common Mistakes

A reliable reduction has two separate checks. First, verify the characteristic polynomial and its signs using the convention \(p_{\mathbf{A}}(\lambda)=\det(\mathbf{A}-\lambda\mathbf{I}_n)\). Second, verify that each use of the recurrence has the correct exponents and coefficients. The constant coefficient always multiplies the appropriate power, which is \(\mathbf{I}_n\) in the initial Cayley–Hamilton equation.

Common sign mistake: for the matrix \(\mathbf{A}\) in the first example, a wrong calculation might read \(\lambda^2-3\lambda+2=0\) as \(\mathbf{A}^2=3\mathbf{A}+2\mathbf{I}_2\). The constant term must instead move to the other side with a minus sign: \(\mathbf{A}^2-3\mathbf{A}+2\mathbf{I}_2=\mathbf{O}\), hence \(\mathbf{A}^2=3\mathbf{A}-2\mathbf{I}_2\). A quick check detects the error: the correct relation gives \(\begin{bmatrix}1&3\\0&4\end{bmatrix}\), which is the direct product \(\mathbf{A}\mathbf{A}\); the incorrect sign would give \(\begin{bmatrix}5&3\\0&8\end{bmatrix}\).

There is also a distinction between reducing to a short list and obtaining a unique expression. The corollary guarantees that some linear combination of \(\mathbf{I}_n,\mathbf{A},\dots,\mathbf{A}^{n-1}\) represents a given power. It does not guarantee that the coefficients are unique: the listed matrices may themselves satisfy additional linear relations. For this tutorial, the recurrence supplies a valid reduction; uniqueness is not needed.

Why the Reduction Is Useful

Once the recurrence is known, a high power can be computed by tracking a small number of coefficients rather than repeatedly multiplying full matrices. This is especially helpful when a later calculation needs \(\mathbf{A}^k\) for a large exponent, or when one wants a polynomial expression in \(\mathbf{A}\) in a lower-degree form. The method uses the characteristic polynomial and Cayley–Hamilton directly; it does not require that \(\mathbf{A}\) be diagonalizable.

For repeated calculations with the same matrix, record the recurrence beside the first reduced powers. For example, when the matrix size is three, every new power is obtained from the preceding three powers using the same coefficients. This makes the reduction systematic, while a final multiplication check helps catch arithmetic errors in the resulting matrix.