*Linear recurrence relations revisited*
We have already discussed linear recurrence relations in the Counting and Generating functions chapter. We shall study it again using matrices. Consider the Fibonacci numbers
- 1, 1, 2, 3, 5, 8, 13, 21...
where each number is the sum of two preceding numbers. Let xn be the (n + 1)th Fibonacci number, we can write:

In fact many linear recurrence relations can be expressed in matrix form , e.g.



can be expressed as

and therefore

So if we knew how to compute the powers of matrices quickly then we can work out the (n + 1)th Fibonacci number rather quickly!
Computing Powers Quickly
Note that from now on we emphasise if a matrix is a vector by writing an arrow on top of it.
Consider



Something interesting happens when you multiply A by either
or
(Try it). In fact

and
.
Generally for a matrix B, if a vector w ≠ 0 (the matrix with all entries zero) such that

for some scalar λ, then
is called a eigenvector of B and λ the eigenvalue of B (corresponding to w).
This is a feature of matrices that be exploited to compute powers easily. Here's how, using A, x and y from above, we write the two pieces of information together in matrix form:

or written completely in numeral form

you are encouraged to check the above is correct. What we did was we merged
and
into a matrix using each vector as a column, next we multiplied it by the diagonal matrix whose entries are the eigenvalue of each eigenvector correspondingly.
How to now exploit this matrix form to calculate powers of A quickly? We require a simple but ingenius step -- post-multiply (i.e. multiply from the right) both sides by the inverse of

we have

Now to calculate An, we need only to do


but inverses multiply to give I, so we are left with

which is very easy to compute since powers of a diagonal matrix are easy to compute (just take each entry to the power).
Example 1
Compute A5 where A is given above.
Solution
We do



Example 2
Let

and its eigenvectors are
and 
Calculate B5 directly (optional), and again using the method above.
Solution
We need to first determine its eigenvalues. We do

so the eigenvalue corresponding to

is 1.
Similarly,

so the other eigenvalue is 3.
Now we write them in the form:

now make B the subject

Now

- so multiplying the right hand side out, we get
Summary -- compute powers quickly
Given eigenvectors of a matrix A
- Compute the eigenvalues (if not given)
- Write in the form A = PDP-1, where D is a diagonal matrix of the eigenvalues, and P the eigenvectors as columns
- Compute An using the right hand side equivalent
Exercises
1. The eigenvectors of

are
and 
calculate B5
2. The eigenvectors of

are
and 
calculate B5
3. The eigenvectors of

are
and 
calculate B5
Eigenvector and eigenvalue
We know from the above section that for a matrix if we are given its eigenvectors, we can find the corresponding eigenvalues, and then we can compute its powers quickly. So the last hurdle becomes finding the eigenvectors.
An eigenvectors
of a matrix A and its corresponding eigenvalue λ are related by the following expression:

where x ≠ 0 where 0 is the zero matrix (all entries zero). We can safely assume that A is given so there are two unknowns --
and λ. We have enough information now to be able to work out the eigenvalues (and from that the eigenvectors):



The matrix (A - λI) must NOT have an inverse, because if it does then
= 0. Therefore det(A - λI) = 0.
Suppose

then


Now we see det(A-λI) is a polynomial in λ and det(A-λI) = 0. We are already well-trained in solving quadratics, so it's easy to work out the values of λ. Once we've worked out the values of λ, we can work out
(see examples).
Example 1
Find the eigenvalues and eigenvectors of

and then find D and P such that A = P-1DP.
Solution
We aim to find
and λ such that
- A
= λ
we proceed

(**)
- det(A - λI) =
- 0 = (-4 - λ)(7 - λ) + 30
- 0 = -28 - 3λ + λ2 + 30
- 0 = λ2 - 3λ + 2
- 0 = (λ - 1)(λ - 2)
- λ = 1, 2
Now for each eigenvalue we will get a different corresponding eigenvector. So we consider the case λ = 1 and λ = 2 separately.
Consider first λ = 1, from (**) we get

i.e.

where
since det(A - λI) = 0, we know that there is no unique solution to the above equation. But we note that:

for any real number t is a solution, and we choose t = 1 as our solution because it's the simpliest. Therefore

is the eigenvector corresponding to λ = 1. (***)
Similarly, if λ = 2, from (**) we get

i.e.

where
we note that:

for any real number t is a solution, as before we choose t = 1 as our solution. Therefore
is the eigenvector corresponding to λ = 2. (****)
We summarise the result of (***) and (****), we have


we combine the results into one

and so

Example 2
- a) Diagonalize A, i.e find P (invertible) and B (diagonal) such that AP = PB
- b) Compute A5

Solution a) We are solving Ax = λx, where λ is a constant and x′ a column vector.
Firstly


since 'x′ ≠ 0 we have

i.e.



For λ = 3,


Clearly

is a solution. Note that we do not accept x = 0 as an solution, because we assume x ≠ 0. Note also that

for some constant t is also a solution. Indeed we could use x = y = 2, 3 or 4 as a solution, but for convenience we choose the simplest i.e. x = y = 1.
For λ = 2,


Clearly

is a solution.
Therefore

is a solution and

is also a solution.
- b)




Example 3
Solve the linear recurrence relation

Solution

We need to diagonalize

we proceed:

we get
- λ = 2, 3
For λ = 2


For λ = 3


Therefore

Now



Therefore


i.e

Exercises
1. Compute A5 where

2. Compute A5 where

3. Solve the following recurrence relations



Solutions
1.

2.

More Applications
...more to come
Problem Set > High_School_Mathematics_Extensions/Matrices/Problem Set
Project > High_School_Mathematics_Extensions/Matrices/Project/Elementary_Matrices
Feedback
What do you think? Too easy or too hard? Too much information or not enough? How can we improve? Please let us know by leaving a comment in the discussion tab. Better still, edit it yourself and make it better.