Skip to content
Tutorials Center
My learning

Topics

Lesson 48 of 68 ยท Linear Algebra and Numerical Methods

Cayley-Hamilton Theorem and Matrix Functions

Use the Cayley-Hamilton theorem to find inverses and high powers of a matrix, define functions of matrices such as exp(At) and solve linear ODE systems in Python.

Engineers constantly ask questions like "what is A**100?", "what is e raised to a matrix?" and "how do I solve x' = A*x?". Each question asks you to apply a function to a matrix. Squaring a matrix is easy, but a power series, an exponential or an inverse looks like an unbounded amount of work. The Cayley-Hamilton theorem is the key that makes all of these finite: every square matrix satisfies its own characteristic equation, so every power of A, however high, can be reduced to a short polynomial in A.

This lesson states the theorem and checks it numerically, uses it for matrix inverses and powers, extends the idea to matrix functions such as e**(A*t), and solves a system of linear ODEs. It builds on eigenvalues for engineers and matrices and systems. The proof-level treatment lives in the linear-algebra track: Cayley-Hamilton in Linear Algebra.

The theorem

For a square matrix A, the characteristic polynomial is p(lambda) = det(lambda*I - A). For a 2-by-2 matrix this is

p(lambda) = lambda**2 - trace(A)*lambda + det(A).

Cayley-Hamilton theorem. Substituting the matrix A itself for lambda (and I for the constant term) gives the zero matrix: p(A) = 0.

Take A = [[2, 1], [1, 3]]. Its trace is 5 and its determinant is 5, so p(lambda) = lambda**2 - 5*lambda + 5. The theorem says A**2 - 5*A + 5*I = 0, i.e. A**2 = 5*A - 5*I. Check it by hand: A**2 = [[5, 5], [5, 10]], 5*A - 5*I = [[10, 5], [5, 15]] - [[5, 0], [0, 5]] = [[5, 5], [5, 10]]. It works.

A warning about a tempting wrong proof: "p(A) = det(A*I - A) = det(0) = 0." This confuses a matrix with a number. Substituting a matrix into a determinant of matrices is not the same as taking the determinant first. The theorem is true, but its proof needs more care (it is in the linear-algebra lesson).

Python Check Cayley-Hamilton on a 2x2 and a 3x3 matrix

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 inverse from the characteristic equation

If A is invertible, its constant term det(A) is not zero, and you can rearrange p(A) = 0 to solve for A**(-1). For a 2-by-2: from A**2 - t*A + d*I = 0 (with t the trace, d the determinant), factor out A: A*(A - t*I) = -d*I, so

A**(-1) = (t*I - A) / d.

For our example: A**(-1) = (5*I - A)/5 = [[3, -1], [-1, 2]] / 5. That is the familiar 2-by-2 inverse formula, now explained: it is Cayley-Hamilton in disguise. For an n-by-n matrix the same trick expresses A**(-1) as a polynomial of degree n - 1 in A.

Reducing high powers

Because A**2 = 5*A - 5*I, every higher power collapses back to the form alpha*A + beta*I. Multiply by A again: A**3 = 5*A**2 - 5*A = 5*(5*A - 5*I) - 5*A = 20*A - 25*I. A pattern emerges: A**k = a_k*A + b_k*I, and multiplying by A once more gives the recurrence a_(k+1) = 5*a_k + b_k, b_(k+1) = -5*a_k. Equivalently, divide lambda**k by the characteristic polynomial and keep the remainder a_k*lambda + b_k; because p(A) = 0, the quotient part vanishes.

flowchart LR
    A["want A^k, A^-1 or f(A)"] --> B["characteristic polynomial p"]
    B --> C["divide lambda^k (or f)<br/>by p: remainder r(lambda)"]
    C --> D["p(A) = 0, so<br/>A^k = r(A)"]
    D --> E["a short polynomial<br/>of degree n - 1"]

Remainders modulo the characteristic polynomial replace infinite work with a short polynomial.

Python Inverse and A^10 from the characteristic equation

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.

Functions of a matrix

A matrix function f(A) is defined by the power series of f: for instance

e**A = I + A + A**2/2! + A**3/3! + ...

For a series to be useful you need it to converge, and then Cayley-Hamilton collapses it to a polynomial of degree n - 1. In practice you evaluate f(A) by one of three routes:

  1. Diagonalization. If A = V * D * V**(-1) with D diagonal (see eigenvalues for engineers), then f(A) = V * f(D) * V**(-1), where f(D) just applies f to each eigenvalue.
  2. Cayley-Hamilton / polynomial interpolation. Find r(lambda) = c0 + c1*lambda + ... of degree n - 1 with r(lambda_i) = f(lambda_i) at every eigenvalue, then f(A) = r(A).
  3. Library routines. scipy.linalg.expm, sqrtm, logm, funm use robust algorithms that also work for non-diagonalizable matrices.

For a rotation generator A = [[0, 1], [-1, 0]], the powers repeat every four steps (A**2 = -I), and e**(A*t) = cos(t)*I + sin(t)*A, a rotation matrix. This is the matrix version of Euler's formula from complex numbers.

Python Matrix functions three ways

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.

Solving x' = Ax with the matrix exponential

The scalar equation x' = a*x has the solution x(t) = e**(a*t) * x(0). The system x' = A*x has exactly the same form:

x(t) = e**(A*t) * x(0).

The matrix exponential is the "propagator" that carries any initial state forward by time t. Note that d/dt e**(A*t) = A*e**(A*t), just as in one variable, which you can verify from the series.

Example: a damped oscillator y'' + 2*y' + 5*y = 0 becomes a first-order system for x = (y, y') with A = [[0, 1], [-5, -2]]. The eigenvalues of A are -1 +/- 2i: the system oscillates while its amplitude decays like e**(-t). The ODE basics and second-order ODEs lessons derive this closed form; here we find it by matrix methods and compare it with the closed-form solution y(t) = e**(-t) * (cos(2t) + sin(2t)/2) for y(0) = 1, y'(0) = 0.

Python The damped oscillator through expm

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

  • Assuming e**(A + B) = e**A * e**B. It holds only when A and B commute (A*B = B*A).
  • Computing the matrix exponential by taking e to each entry (np.exp(A) is not expm(A)).
  • Dividing the characteristic polynomial by the wrong convention: use det(lambda*I - A), which always starts with lambda**n.
  • Using diagonalization on a non-diagonalizable matrix; use expm or the Jordan form instead.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

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

    Substituting the matrix A into its characteristic polynomial gives the zero matrix.
  2. 2. For a 2x2 matrix with trace t and determinant d, which formula gives the inverse from Cayley-Hamilton?

    From A^2 - t A + d I = 0 we get A (t I - A) = d I, so A^-1 = (t I - A)/d.
  3. 3. Why does Cayley-Hamilton make A^k easy for large k?

    Because p(A) = 0, any multiple of p vanishes. Only the remainder of lambda^k divided by p matters, and that has degree below n.
  4. 4. Which is the solution of x' = A x with initial state x(0)?

    The matrix exponential e^(At) is the propagator for linear constant-coefficient systems; it is not computed entry by entry.

Summary

  • Cayley-Hamilton: p(A) = 0 for the characteristic polynomial p(lambda) = det(lambda*I - A).
  • It gives A**(-1) as a polynomial in A (for 2-by-2: (t*I - A)/d) and reduces any power A**k to a polynomial of degree at most n - 1.
  • Matrix functions are defined by power series and computed via eigen-decomposition, polynomial interpolation or scipy.linalg.expm, sqrtm, funm.
  • x' = A*x has the solution x(t) = e**(A*t) * x(0); e**(A+B) = e**A * e**B only for commuting matrices.

Next: see how infinite series also solve differential equations in Power-Series Solutions: Bessel and Legendre.