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$