Page 296 - A Course in Linear Algebra with Applications

2oU Chapter Eight: Eigenvalues and Eigenvectors

n
n
d\ ', d2 n ..., d m . Since we know how to find S and D, all we
need do is compute the product Y n, and read off its entries to
m
obtain the functions y n^\ ..., j/ n ^ -*.
At this point the reader may ask: what if A is not di-
agonalizable? A complete discussion of this case would take
us too far afield. However one possible approach is to exploit
the fact that the coefficient matrix A is certainly triangular-
1
izable by 8.1.8. Thus we can find S such that S' AS = T is
1
upper triangular. Now write U n = S~ Y n, so that Y n — SU n.
Then the recurrence Y n+i = AY n becomes SU n+i = ASU n,
1
or U n+i = (S~ AS)U n = TU n. In principle this "triangular"
system of recurrence relations can be solved by a process of
back substitution: first solve the last recurrence for Un , then
substitute for Un in the second last recurrence and solve for
Un , and so on. What makes the procedure effective is the
fact that powers of a triangular matrix are easier to compute
than those of an arbitrary matrix.

Example 8.2.2
Consider the system of linear recurrences

Vn+l = Vn + Zn
z
Zn+1 = Vn i "-> n

The coefficient matrix A = I 1 is not diagonalizable,
but it was triangularized in Example 8.1.6; there it was found
that

1 2
T = S~ AS= ( Q ^ where S = (^ J

1
Put U n = S~ Y n; here the entries of U n and Y n are written u n,
and y n, respectively. The recurrence relation Y n+i =
v n z n
becomes U n+i = TU n. This system of linear recurrences
AY n