# Putzer Algorithm for Matrix Exponentials

## Algorithm

The **Putzer Algorithm** is a method for analytically evaluating Matrix Exponentials using only eigenvalues and components in the solution of a relatively simple linear system. It is particularly useful for matrices that cannot be diagonalized because it avoids the use of Jordan-Canonical Form.

## Method

Let $\lambda_1 , \lambda_2, \dots, \lambda_n$ be the (not necessarily distinct) eigenvalues of the matrix $A$. Then:

- $e^{At} = \sum_{k=0}^{n-1} p_{k+1}(t) M_k$.

This formula is constructed by setting $M_0 = I$ (the identity matrix),

- $M_k = \prod_{i=1}^k (A - \lambda_i I)$;

and the functions $p_1(t), p_2(t), \dots, p_n(t)$ are taken to be components of the vector function solution to the IVP

- $p' = \begin{pmatrix} \lambda_1 & 0 & 0 & \cdots & 0 \\ 1 & \lambda_2 & 0 & \cdots & 0 \\ 0 & 1 & \lambda_3 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & 1 & \lambda_n \end{pmatrix} p, \, \, \, p(0) = \begin{pmatrix} 1 \\ 0 \\ 0 \\ \vdots\\ 0 \end{pmatrix}$.

## Proof of Validity

Let $\Phi(t)$ represent the finite matrix sum, devised above, as the candidate for $e^{At}$.

By the uniqueness theorem, it suffices to show that $\Phi$ satisfies the IVP,

- $X' = AX, \, \, X(0) = I$.

By definition,

- $p_1'(t) = \lambda_1 p_1(t)$,
- $p_i'(t) = p_{i-1}(t) + \lambda_i p_i(t), \, \, i > 1$,

and,

- $M_0 = I$,
- $M_k = (A-\lambda_k I)M_{k-1}$.

Note also that $M_n = 0$ by the Cayley-Hamilton Theorem.

Then:

- $\Phi'(t) - A\Phi(t)$
- $= \sum_{k=0}^{n-1} p_{k+1}'(t)M_k - A\sum_{k=0}^{n-1}p_{k+1}(t)M_k$
- $= \lambda_1 p_1(t) M_0 + \sum_{k=1}^{n-1} \left( \lambda_{k+1}p_{k+1}(t)+p_k(t)\right)M_k - \sum_{k=0}^{n-1} p_{k+1}(t) \left( M_{k+1} + \lambda_{k+1} M_k \right)$
- $= \sum_{k=1}^{n-1} p_k(t)M_k - \sum_{k=0}^{n-1}p_{k+1}(t)M_{k+1}$
- $= -p_n(t)M_n$
- $= 0$.

$\blacksquare$