Skip to content
Tutorials Center
My learning

Topics

Lesson 38 of 62 ยท Eigenvalues and Decompositions

Cayley-Hamilton Theorem

Understand the Cayley-Hamilton theorem: every matrix satisfies its characteristic polynomial. Use it for inverses, powers and the minimal polynomial, with Python checks.

Here is a fact that sounds like a magic trick. Take any square matrix A. Compute its characteristic polynomial p(lambda) = det(lambda*I - A), the same polynomial whose roots are the eigenvalues. Now plug the matrix into that polynomial, with A**2 for lambda**2, A for lambda, and I times the constant for the constant term. The answer is the zero matrix. Always. That is the Cayley-Hamilton theorem: every square matrix satisfies its own characteristic equation.

The theorem is more than a curiosity. It turns the infinite family of matrix powers A, A**2, A**3, ... into a finite one (only I, A, ..., A**(n-1) are ever independent), it gives a formula for the inverse, and it underlies the computation of matrix functions. This lesson builds on eigenvalues and eigenvectors and diagonalization. For the engineering uses (matrix exponentials and linear ODE systems), see Cayley-Hamilton and matrix functions.

Statement and a first check

For an n-by-n matrix A, write the characteristic polynomial as

p(lambda) = lambda**n + c_(n-1)*lambda**(n-1) + ... + c_1*lambda + c_0.

The theorem says A**n + c_(n-1)*A**(n-1) + ... + c_1*A + c_0*I = 0. Two coefficients are always familiar: c_(n-1) = -trace(A) and c_0 = (-1)**n * det(A).

For a 2-by-2 matrix, p(lambda) = lambda**2 - trace(A)*lambda + det(A), so Cayley-Hamilton says

A**2 - trace(A)*A + det(A)*I = 0.

Test it on A = [[1, 2], [3, 4]]: trace 5, determinant -2. Then A**2 = [[7, 10], [15, 22]], 5*A = [[5, 10], [15, 20]], and A**2 - 5*A - 2*I = [[7-5-2, 0], [0, 22-20-2]] = 0.

Python Verify the theorem on random matrices

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why it is true

The cleanest argument is for diagonalizable matrices. If A = V * D * V**(-1) with D = diag(lambda_1, ..., lambda_n), then any polynomial q satisfies q(A) = V * q(D) * V**(-1) and q(D) = diag(q(lambda_1), ..., q(lambda_n)). Take q = p: each p(lambda_i) = 0 because lambda_i is a root of its own characteristic polynomial, so p(D) = 0, hence p(A) = 0.

Non-diagonalizable matrices are handled by a limiting argument (diagonalizable matrices are dense: any matrix is the limit of matrices with distinct eigenvalues, and p(A) depends continuously on the entries) or by an algebraic proof using the adjugate (see Cramer's rule and the adjugate). The trap to avoid is the "obvious" proof p(A) = det(A*I - A) = det(0) = 0: it substitutes A for lambda inside a determinant that also contains the matrix lambda*I, which is not legitimate.

Inverses from the polynomial

If det(A) != 0, then c_0 != 0. Rearrange p(A) = 0 as A*(A**(n-1) + c_(n-1)*A**(n-2) + ... + c_1*I) = -c_0*I, giving

A**(-1) = -(1/c_0) * (A**(n-1) + c_(n-1)*A**(n-2) + ... + c_1*I).

So the inverse is a polynomial in A of degree n - 1. For A = [[1, 2], [3, 4]]: c_1 = -5, c_0 = -2, so A**(-1) = -(1/(-2)) * (A - 5*I) = (1/2) * [[-4, 2], [3, -1]] = [[-2, 1], [1.5, -0.5]]. This agrees with the 2-by-2 inverse formula.

The Faddeev-LeVerrier algorithm turns this into a recipe that finds all coefficients using only matrix products and traces (no determinants, no eigenvalues), and returns the inverse as a by-product.

Python Faddeev-LeVerrier: characteristic polynomial and inverse

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Powers made finite

Since A**n equals a combination of lower powers, so does A**(n+1), and so on. Every power A**k is therefore a polynomial in A of degree below n. Equivalently, if you divide lambda**k by p(lambda), the remainder r(lambda) has degree below n and A**k = r(A).

A classic example is the Fibonacci matrix F = [[1, 1], [1, 0]]. Its characteristic polynomial is lambda**2 - lambda - 1, so F**2 = F + I. Repeated use gives F**k = Fib(k)*F + Fib(k-1)*I, where Fib denotes the Fibonacci numbers (F**10 = 55*F + 34*I = [[89, 55], [55, 34]]). Matrix powers are the Fibonacci recurrence.

Python Fibonacci powers from Cayley-Hamilton

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The minimal polynomial

The characteristic polynomial is not always the shortest polynomial that kills A. The minimal polynomial m(lambda) is the monic polynomial of lowest degree with m(A) = 0. It divides p(lambda), it has exactly the same roots (just with possibly smaller multiplicities), and it tells you whether A is diagonalizable: A is diagonalizable if and only if its minimal polynomial has no repeated roots.

Examples with p(lambda) = (lambda - 2)**2:

  • A = [[2, 0], [0, 2]] = 2*I: A - 2*I = 0, so m = lambda - 2. Diagonalizable.
  • B = [[2, 1], [0, 2]]: B - 2*I = [[0, 1], [0, 0]] != 0 but (B - 2*I)**2 = 0, so m = (lambda - 2)**2. Not diagonalizable: this is a Jordan block (see Jordan form).

A nilpotent matrix (N**k = 0 for some k) has p(lambda) = lambda**n, so Cayley-Hamilton immediately gives N**n = 0. That is why a strictly upper triangular n-by-n matrix has N**n = 0.

Python Minimal polynomial and diagonalizability

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • Using the false proof det(A*I - A) = 0. The theorem is true but that argument is not valid.
  • Reading p(A) = 0 as "A is a root, so A is an eigenvalue". The theorem concerns a matrix polynomial and says nothing about A being a scalar.
  • Forgetting the constant term: it multiplies the identity matrix I, not the number 1.
  • Assuming the minimal polynomial equals the characteristic polynomial. They coincide only when each eigenvalue has a single Jordan block.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the Cayley-Hamilton theorem say?

    If p(lambda) = det(lambda I - A), then replacing lambda by A (and the constant term by a multiple of I) gives the zero matrix.
  2. 2. For a 2 x 2 matrix, which identity follows from the theorem?

    The characteristic polynomial is lambda^2 - trace(A) lambda + det(A), so substituting A gives A^2 - trace(A) A + det(A) I = 0.
  3. 3. How does Cayley-Hamilton express A^-1 for an invertible n x n matrix?

    Rearranging p(A) = 0 with c_0 != 0 gives A^-1 = -(1/c_0)(A^(n-1) + c_(n-1) A^(n-2) + ... + c_1 I).
  4. 4. A 2 x 2 matrix has characteristic polynomial (lambda - 2)^2 but is not 2I. What is its minimal polynomial?

    Since A - 2I is non-zero, lambda - 2 does not annihilate A, so the minimal polynomial must be (lambda - 2)^2. Such a matrix is not diagonalizable.

Summary

  • Cayley-Hamilton: p(A) = 0 where p(lambda) = det(lambda*I - A); for 2-by-2, A**2 - trace(A)*A + det(A)*I = 0.
  • It follows by diagonalizing when possible and by continuity or an adjugate argument in general.
  • The inverse is a polynomial of degree n - 1 in A; every power A**k reduces to such a polynomial (for example the Fibonacci matrix).
  • The minimal polynomial is the shortest annihilating polynomial; A is diagonalizable exactly when it has no repeated roots.
  • The Faddeev-LeVerrier algorithm computes the characteristic polynomial and inverse with matrix products and traces only.

Next: continue with the structure behind non-diagonalizable matrices in Markov chains with matrices, then the Jordan form.