Powers of Matrices, Putzer's Method

Date: 03/09/97 at 17:30:34
From: Dina Pesenson
Subject: Matrices and exponents

Hi, 

I'm a junior in college. In my elementary differential equations 
course, we received an interesting extra credit problem. I was 
wondering if you could tell me where to look for help.  Here's the 
problem: 

     3   0   0  -1  -2 
     1   3  -1   0  -3
     2   0   2  -2  -3
     1  -1   1   0   0
     0   0   0   0   2
   e^

I'm not supposed to use the Taylor expansion to approximate. The only 
other way I found so far is by diagonalizing the matrix.  The problem 
is that when you try to find the eigenvalues, you get 2,2,2,2,2 (I 
used Mathematica to find them).  This means that I cannot find 5 
linearly independent eigenvectors, which in turn means I cannot find 
an inverse to the matrix consisting of eigenvectors. Therefore, I 
cannot diagonalize the original matrix. I also tried to do the entire 
problem on Mathematica, but it wouldn't solve it - the most it offers 
is the Taylor approximation. In our class, we learned how to deal with 
eigenvalues of multiplicity 2 only. Where could I find more 
information on how to work with eigenvalues of higher multiplicity in 
a case like this? What would you do about this? 

Date: 03/10/97 at 14:54:16
From: Doctor Pete
Subject: Re: Matrices and exponents

Look for the following textbook in your university library:

Apostol, Tom M.  _Calculus_, Vol II, 2nd Ed.  pgs. 205-211

In case you cannot find this book (it is excellent), I will briefly 
describe what the above pages discuss, which is Putzer's method for 
calculating e^(tA), where t is a constant and A is an n x n matrix.  
In particular, a special case of Putzer's method applies, for, as you 
have noted, the matrix in question has equal eigenvalues.

First, the Cayley-Hamilton theorem states:

    Let A be an n x n matrix and let f(L) = det(LI-A)
    = L^n + c[n-1]L^(n-1) + c[n-2]L^(n-2) + ... + c[1]L + c[0] be its
    characteristic polynomial.  Then f(A) = 0.

I hope you are familiar with this statement, and better yet, its 
proof - though we won't go into it.  The basic idea we want to get 
out of this is that the (n)th power of any n x n matrix A is 
expressible as a linear combination of lower powers I, A, A^2, ... , 
A^(n-1).  Then it immediately follows that A^(n+1), A^(n+2), and in 
general, all higher powers of A are also expressible as linear 
combinations of these lower powers.  Since e^(tA) has a convergent 
Taylor series expansion as an infinite sum of powers of A, it is 
reasonable to expect that we can reexpress this infinite sum as a 
finite sum over powers of 0 to (n-1).  That is, we may have:

     e^(tA) = Sum[q[k,t]A^k,{k,0,n-1}]

(I am using a "pseudo-Mathematica" notation here) where q[k,t] are 
scalar coefficients which depend on t.  Putzer's method, then, is 
really a theorem which demonstrates that q[k,t] exists, and finds it.

In its general form, Putzer's method is outlined as follows:  let 
L[1], L[2], ... L[n] be the eigenvalues of the n x n matrix A.  Define 
a sequence of polynomials in A:

     P[0,A] = I,
     P[k,A] = Product[A-L[m]I,{m,1,k}],

for k = 1, 2, ..., n.  Then:

     e^(tA) = Sum[r[k+1,t]P[k,A],{k,0,n-1}]

where the scalar coefficients r[1,t], ..., r[n,t] are determined 
recursively from the system of linear differential equations:

     r'[1,t] = L[1]r[1,t], r[1,0] = 1,
     r'[k+1,t] = L[k+1]r[k+1,t]+r[k,t], r[k+1,0] = 0,

k = 1, 2, ..., n-1.  I will not prove this; try to prove it yourself 
(if you can, you'd probably get more than extra credit!), or refer to 
Apostol.

Now, this is not very convenient to work with; however, there is a 
special case of the above, when L[1] = L[2] = ... = L[n] = L; i.e., 
all the eigenvalues of A are equal.  If we call this common eigenvalue 
L, then we have:

     e^(tA) = e^(Lt) Sum[t^k/k! (A-LI)^k, {k,0,n-1}].

The proof of this is not too difficult--observe that the matrices LtI 
and t(A-LI) commute, and apply the Cayley-Hamilton theorem.

Of course, in your example, t=1, L=2.  Since I've essentially told you 
the answer, I would strongly suggest you find out more about Putzer's 
method, and take a whack at proving it.  It isn't extraordinarily 
difficult, but it's a bit computational.  I also highly recommend 
Apostol's text, both volumes - it is calculus done right.

Best wishes,

-Doctor Pete,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/