Last modified on 27 October 2005, at 10:13

# High School Mathematics Extensions/Matrices/Linear Recurrence Relations Revisited

Content HSME Matrices Recurrence Relations Problem Set Project Exercises Solutions Problem Set Solutions Definition Sheet Full Version

## *Linear recurrence relations revisited*Edit

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:

$\begin{matrix} \begin{pmatrix} x_n\\ x_{n-1} \end{pmatrix} & = & \begin{pmatrix} x_{n-1} + x_{n-2}\\ x_{n-1} \end{pmatrix} \\ \\ & = & \begin{pmatrix} 1 &1\\ 1 &0 \end{pmatrix} \begin{pmatrix} x_{n-1}\\ x_{n-2} \end{pmatrix} \\ \\ & = & \begin{pmatrix} 1 &1\\ 1 &0 \end{pmatrix}^2 \begin{pmatrix} x_{n-2}\\ x_{n-3} \end{pmatrix} \\ \\ &... \\ \\ & = & \begin{pmatrix} 1 &1\\ 1 &0 \end{pmatrix}^{n-1} \begin{pmatrix} x_{1}\\ x_{0} \end{pmatrix} \\ \\ & = & \begin{pmatrix} 1 &1\\ 1 &0 \end{pmatrix}^{n-1} \begin{pmatrix} 1\\ 1 \end{pmatrix} \end{matrix}$

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

$x_n = 2x_{n-1} + x_{n-2}; \ \mbox{if n} \ge 2$
$x_1 = 1$
$x_0 = 1$

can be expressed as

$\begin{pmatrix} x_n\\ x_{n-1} \end{pmatrix} = \begin{pmatrix} 2&1\\ 1&0 \end{pmatrix} \begin{pmatrix} x_{n-1}\\ x_{n-2} \end{pmatrix}$

and therefore

$\begin{pmatrix} x_n\\ x_{n-1} \end{pmatrix} = \begin{pmatrix} 2&1\\ 1&0 \end{pmatrix} ^{n-1} \begin{pmatrix} 1\\ 1 \end{pmatrix}$

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 QuicklyEdit

Note that from now on we emphasise if a matrix is a vector by writing an arrow on top of it.

Consider

$A = \begin{pmatrix} 1 & -2\\ 1 & 4 \end{pmatrix}$
$\overrightarrow{x} = \begin{pmatrix} 2 \\ -1 \end{pmatrix}$
$\overrightarrow{y} = \begin{pmatrix} -1 \\ 1 \end{pmatrix}$

Something interesting happens when you multiply A by either $\overrightarrow{x}$ or $\overrightarrow{y}$ (Try it). In fact

$A\overrightarrow{x} = 2\overrightarrow{x}$

and

$A\overrightarrow{y} = 3\overrightarrow{y}$.

Generally for a matrix B, if a vector w0 (the matrix with all entries zero) such that

$B\overrightarrow{ w } = \lambda \overrightarrow{ w }$

for some scalar λ, then $\overrightarrow{ w }$ 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:

$A\begin{pmatrix}\overrightarrow{x} & \overrightarrow{y}\end{pmatrix} = \begin{pmatrix}\overrightarrow{x} & \overrightarrow{y}\end{pmatrix} \begin{pmatrix}2 & 0\\ 0 & 3\end{pmatrix}$

or written completely in numeral form

$\begin{pmatrix} 1 & -2\\ 1 & 4 \end{pmatrix} \begin{pmatrix} 2 & -1\\ -1 & 1 \end{pmatrix} = \begin{pmatrix} 2 & -1\\ -1 & 1 \end{pmatrix} \begin{pmatrix} 2 & 0\\ 0 & 3 \end{pmatrix}$

you are encouraged to check the above is correct. What we did was we merged $\overrightarrow{x}$ and $\overrightarrow{y}$ 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

$\begin{pmatrix} 2 & -1\\ -1 & 1 \end{pmatrix}$

we have

$\begin{pmatrix} 1 & -2\\ 1 & 4 \end{pmatrix} = \begin{pmatrix} 2 & -1\\ -1 & 1 \end{pmatrix} \begin{pmatrix}2 & 0\\ 0 & 3\end{pmatrix} \begin{pmatrix} 2 & -1\\ -1 & 1 \end{pmatrix}^{-1}$

Now to calculate An, we need only to do

$A^n = \begin{pmatrix} 1 & -2\\ 1 & 4 \end{pmatrix}^n =$
$\begin{pmatrix} 2 & -1\\ -1 & 1 \end{pmatrix} \begin{pmatrix}2 & 0\\ 0 & 3\end{pmatrix} \begin{pmatrix} 2 & -1\\ -1 & 1 \end{pmatrix}^{-1} ... \begin{pmatrix} 2 & -1\\ -1 & 1 \end{pmatrix} \begin{pmatrix}2 & 0\\ 0 & 3\end{pmatrix} \begin{pmatrix} 2 & -1\\ -1 & 1 \end{pmatrix}^{-1}$

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

$A^n = \begin{pmatrix} 1 & -2\\ 1 & 4 \end{pmatrix}^n = \begin{pmatrix} 2 & -1\\ -1 & 1 \end{pmatrix} \begin{pmatrix}2 & 0\\ 0 & 3\end{pmatrix}^n \begin{pmatrix} 2 & -1\\ -1 & 1 \end{pmatrix}^{-1}$

which is very easy to compute since powers of a diagonal matrix are easy to compute (just take each entry to the power).

#### Example 1Edit

Compute A5 where A is given above.

Solution We do

$A^5 = \begin{pmatrix} 2 & -1\\ -1 & 1 \end{pmatrix} \begin{pmatrix}2 & 0\\ 0 & 3\end{pmatrix}^5 \begin{pmatrix} 2 & -1\\ -1 & 1 \end{pmatrix}^{-1}$
$A^5 = \begin{pmatrix} 2 & -1\\ -1 & 1 \end{pmatrix} \begin{pmatrix}2^5 & 0\\ 0 & 3^5\end{pmatrix} \begin{pmatrix} 1 & 1\\ 1 & 2 \end{pmatrix}$
$A^5 = \begin{pmatrix} 2^6-3^5 & 2^6-2\times 3^5\\ -2^5+3^5 & -2^5 + 2\times 3^5 \end{pmatrix}$

#### Example 2Edit

Let

$B = \begin{pmatrix} -13 & 28\\ -8 & 17 \end{pmatrix}$

and its eigenvectors are

$\begin{pmatrix} 2\\ 1 \end{pmatrix}$ and $\begin{pmatrix} 7\\ 4 \end{pmatrix}$

Calculate B5 directly (optional), and again using the method above.

Solution We need to first determine its eigenvalues. We do

$\begin{pmatrix} -13 & 28\\ -8 & 17 \end{pmatrix} \begin{pmatrix} 2\\ 1 \end{pmatrix} = \begin{pmatrix} 2\\ 1 \end{pmatrix}$

so the eigenvalue corresponding to

$\begin{pmatrix} 2\\ 1 \end{pmatrix}$

is 1.

Similarly,

$\begin{pmatrix} -13 & 28\\ -8 & 17 \end{pmatrix} \begin{pmatrix} 7\\ 4 \end{pmatrix} = \begin{pmatrix} 21\\ 12 \end{pmatrix} = 3\begin{pmatrix} 7\\ 4 \end{pmatrix}$

so the other eigenvalue is 3.

Now we write them in the form:

$\begin{pmatrix} -13 & 28\\ -8 & 17 \end{pmatrix} \begin{pmatrix} 2 & 7\\ 1 & 4 \end{pmatrix} = \begin{pmatrix} 2 & 7\\ 1 & 4 \end{pmatrix} \begin{pmatrix} 1 & 0\\ 0 & 3 \end{pmatrix}$

now make B the subject

$\begin{pmatrix} -13 & 28\\ -8 & 17 \end{pmatrix} = \begin{pmatrix} 2 & 7\\ 1 & 4 \end{pmatrix} \begin{pmatrix} 1 & 0\\ 0 & 3 \end{pmatrix} \begin{pmatrix} 4 & -7\\ -1 & 2 \end{pmatrix}$

Now

$\begin{pmatrix} -13 & 28\\ -8 & 17 \end{pmatrix}^5 = \begin{pmatrix} 2 & 7\\ 1 & 4 \end{pmatrix} \begin{pmatrix} 1^5 & 0\\ 0 & 3^5 \end{pmatrix} \begin{pmatrix} 4 & -7\\ -1 & 2 \end{pmatrix}$
so multiplying the right hand side out, we get

$\begin{pmatrix} -13 & 28\\ -8 & 17 \end{pmatrix}^5 = \begin{pmatrix} 8-7\times 3^5 & 14(3^5-1)\\ 4(3^5-1) & -7+8\times 3^5 \end{pmatrix}$

#### Summary -- compute powers quicklyEdit

Given eigenvectors of a matrix A

1. Compute the eigenvalues (if not given)
2. Write in the form A = PDP-1, where D is a diagonal matrix of the eigenvalues, and P the eigenvectors as columns
3. Compute An using the right hand side equivalent

#### ExercisesEdit

1. The eigenvectors of

$B = \begin{pmatrix} -8&6\\ -15&11 \end{pmatrix}$

are

$\begin{pmatrix} 2\\ 3 \end{pmatrix}$ and $\begin{pmatrix} 3\\ 5 \end{pmatrix}$

calculate B5

2. The eigenvectors of

$B = \begin{pmatrix} -8&6\\ -9&7 \end{pmatrix}$

are

$\begin{pmatrix} 1\\ 1 \end{pmatrix}$ and $\begin{pmatrix} 2\\ 3 \end{pmatrix}$

calculate B5

3. The eigenvectors of

$B = \begin{pmatrix} 177&-140\\ 225&-178 \end{pmatrix}$

are

$\begin{pmatrix} 4\\ 5 \end{pmatrix}$ and $\begin{pmatrix} 7\\ 9 \end{pmatrix}$

calculate B5

### Eigenvector and eigenvalueEdit

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 $\overrightarrow{x}$ of a matrix A and its corresponding eigenvalue λ are related by the following expression:

$A\overrightarrow{x} = \lambda \overrightarrow{x}$

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 -- $\overrightarrow{x}$ and λ. We have enough information now to be able to work out the eigenvalues (and from that the eigenvectors):

$A\overrightarrow{x} - \lambda \overrightarrow{x} = 0$
$A\overrightarrow{x} - \lambda I \overrightarrow{x} = 0$
$(A - \lambda I) \overrightarrow{x} = 0$

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

$A = \begin{pmatrix} a&b\\ c&d \end{pmatrix}$

then

$A-\lambda I = \begin{pmatrix} a - \lambda&b\\ c&d - \lambda \end{pmatrix}$
$0 = \det(A-\lambda I) = (a - \lambda)(d - \lambda) - bc$

Now we see det(A-λI) is a polynomial in λ and det(AI) = 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 $\overrightarrow{x}$ (see examples).

#### Example 1Edit

Find the eigenvalues and eigenvectors of

$A = \begin{pmatrix} -4&15\\ -2&7 \end{pmatrix}$

and then find D and P such that A = P-1DP.

Solution

We aim to find $\overrightarrow{x}$ and λ such that

A$\overrightarrow{x}$ = λ$\overrightarrow{x}$

we proceed

$\begin{pmatrix} -4&15\\ -2&7 \end{pmatrix} \overrightarrow{x} = \lambda \overrightarrow{x}$
$\begin{pmatrix} -4 - \lambda &15\\ -2&7 - \lambda \end{pmatrix} \overrightarrow{x} = 0$ (**)
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

$\begin{pmatrix} -4 - 1 &15\\ -2&7 - 1 \end{pmatrix} x = 0$

i.e.

$\begin{pmatrix} -5&15\\ -2& 6 \end{pmatrix} \begin{pmatrix} u\\ v \end{pmatrix} = 0$

where $x = \begin{pmatrix} u\\ v \end{pmatrix}$ since det(A - λI) = 0, we know that there is no unique solution to the above equation. But we note that:

$x = \begin{pmatrix} 3t\\ 1t \end{pmatrix}$

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

$x = \begin{pmatrix} 3\\ 1 \end{pmatrix}$

is the eigenvector corresponding to λ = 1. (***)

Similarly, if λ = 2, from (**) we get

$\begin{pmatrix} -4 - 2 &15\\ -2&7 - 2 \end{pmatrix} x = 0$

i.e.

$\begin{pmatrix} -6&15\\ -2& 5 \end{pmatrix} \begin{pmatrix} u\\ v \end{pmatrix} = 0$

where $x = \begin{pmatrix} u\\ v \end{pmatrix}$ we note that:

$x = \begin{pmatrix} 5t\\ 2t \end{pmatrix}$

for any real number t is a solution, as before we choose t = 1 as our solution. Therefore

$x = \begin{pmatrix} 5\\ 2 \end{pmatrix}$ is the eigenvector corresponding to λ = 2. (****)

We summarise the result of (***) and (****), we have

$A \begin{pmatrix} 3\\ 1 \end{pmatrix} = \begin{pmatrix} 3\\ 1 \end{pmatrix}$
$A \begin{pmatrix} 5\\ 2 \end{pmatrix} = 2 \begin{pmatrix} 5\\ 2 \end{pmatrix}$

we combine the results into one

$A \begin{pmatrix} 3&5\\ 1&2 \end{pmatrix} = \begin{pmatrix} 3&5\\ 1&2 \end{pmatrix} \begin{pmatrix} 1&0\\ 0&2 \end{pmatrix}$

and so

$A = \begin{pmatrix} 3&5\\ 1&2 \end{pmatrix} \begin{pmatrix} 1&0\\ 0&2 \end{pmatrix} \begin{pmatrix} 3&5\\ 1&2 \end{pmatrix}^{-1}$

#### Example 2Edit

a) Diagonalize A, i.e find P (invertible) and B (diagonal) such that AP = PB
b) Compute A5
$A = \begin{pmatrix} 1&2\\ -1&4 \end{pmatrix}$

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

$Ax - \lambda Ix = 0$
$(A - \lambda I)x = 0$

since x ≠ 0 we have

$det(A - \lambda I) = 0$

i.e.

$\det\begin{pmatrix} 1-\lambda&2\\ -1&4-\lambda \end{pmatrix} = 0$

$\begin{matrix} (1-\lambda)(4-\lambda) + 2 &=& 0\\ \lambda^2-5\lambda + 6 &=& 0 \end{matrix}$

$\lambda = 3,\ 2$

For λ = 3,

$(A-3I)x = 0$

$\begin{pmatrix} -2&2\\ -1&1 \end{pmatrix} \begin{pmatrix} x\\ y \end{pmatrix} = 0$

Clearly

$\begin{pmatrix} x\\ y \end{pmatrix} = \begin{pmatrix} 1\\ 1 \end{pmatrix}$

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

$\begin{pmatrix} x\\ y \end{pmatrix} = \begin{pmatrix} t\\ t \end{pmatrix}$

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,

$(A-2I)x = 0$

$\begin{pmatrix} -1&2\\ -1&2 \end{pmatrix} \begin{pmatrix} x\\ y \end{pmatrix} = 0$

Clearly

$\begin{pmatrix} x\\ y \end{pmatrix} = \begin{pmatrix} 2\\ 1 \end{pmatrix}$

is a solution.

Therefore

$A \begin{pmatrix} 1&2\\ 1&1 \end{pmatrix} = \begin{pmatrix} 1&2\\ 1&1 \end{pmatrix} \begin{pmatrix} 3&0\\ 0&2 \end{pmatrix}$

is a solution and

$A \begin{pmatrix} 2&1\\ 1&1 \end{pmatrix} = \begin{pmatrix} 2&1\\ 1&1 \end{pmatrix} \begin{pmatrix} 2&0\\ 0&3 \end{pmatrix}$

is also a solution.

b)
$A^5 = \begin{pmatrix} \begin{pmatrix} 2&1\\ 1&1 \end{pmatrix} \begin{pmatrix} 2&0\\ 0&3 \end{pmatrix} \begin{pmatrix} 2&1\\ 1&1 \end{pmatrix}^{-1} \end{pmatrix} ^5$

$A^5 = \begin{pmatrix} 2&1\\ 1&1 \end{pmatrix} \begin{pmatrix} 2&0\\ 0&3 \end{pmatrix}^5 \begin{pmatrix} 2&1\\ 1&1 \end{pmatrix}^{-1}$

$A^5 = \begin{pmatrix} 2&1\\ 1&1 \end{pmatrix} \begin{pmatrix} 2^5&0\\ 0&3^5 \end{pmatrix} \begin{pmatrix} 1&-1\\ -1&2 \end{pmatrix}$

$A^5 = \begin{pmatrix} 2^6-3^5&2^6-2\times 3^5\\ 2^5-3^5&-2^5+2\times 3^5 \end{pmatrix}$

#### Example 3Edit

Solve the linear recurrence relation

$\begin{matrix} x_n &=& 5x_{n-1}& -& 6x_{n-2}; \ \mbox{if n} \ge 2\\ x_1 &=& 1\\ x_0 &=& 0\\ \end{matrix}$

Solution

$\begin{pmatrix} x_n\\ x_{n-1} \end{pmatrix} = \begin{pmatrix} 5&-6\\ 1&0 \end{pmatrix}^{n-1} \begin{pmatrix} 1\\ 0 \end{pmatrix}$

We need to diagonalize

$A = \begin{pmatrix} 5&-6\\ 1&0 \end{pmatrix}$

we proceed:

$\det{(A - \lambda I)} = 0 \!$

we get

λ = 2, 3

For λ = 2

$(A - 2I)x = 0 \!$
$x= \begin{pmatrix} 2\\ 1 \end{pmatrix}$

For λ = 3

$(A - 3I)x = 0 \!$
$x= \begin{pmatrix} 3\\ 1 \end{pmatrix}$

Therefore

$A = \begin{pmatrix} 2&3\\ 1&1 \end{pmatrix} \begin{pmatrix} 2&0\\ 0&3 \end{pmatrix} \begin{pmatrix} 2&3\\ 1&1 \end{pmatrix}^{-1}$

Now

$A^{n-1} = \begin{pmatrix} 2&3\\ 1&1 \end{pmatrix} \begin{pmatrix} 2&0\\ 0&3 \end{pmatrix}^{n-1} \begin{pmatrix} -1&3\\ 1&-2 \end{pmatrix}$
$A^{n-1} = \begin{pmatrix} 2&3\\ 1&1 \end{pmatrix} \begin{pmatrix} 2^{n-1}&0\\ 0&3^{n-1} \end{pmatrix} \begin{pmatrix} -1&3\\ 1&-2 \end{pmatrix}$
$A^{n-1} = \begin{pmatrix} -2^n+3^n&3\times 2^n-2\times 3^n\\ -2^{n-1}+3^{n-1}&3\times 2^{n-1}-2\times 3^{n-1} \end{pmatrix}$

Therefore

$\begin{pmatrix} x_n\\ x_{n-1} \end{pmatrix} = \begin{pmatrix} -2^n+3^n&3\times 2^n-2\times 3^n\\ -2^{n-1}+3^{n-1}&3\times 2^{n-1}-2\times 3^{n-1} \end{pmatrix} \begin{pmatrix} 1\\ 0 \end{pmatrix}$
$\begin{pmatrix} x_n\\ x_{n-1} \end{pmatrix} = \begin{pmatrix} -2^n+3^n\\ -2^{n-1}+3^{n-1} \end{pmatrix}$

i.e

$x_n = -2^n + 3^n \!$

### ExercisesEdit

1. Compute A5 where

$A = \begin{pmatrix} -12 & 10\\ -21 & 17 \end{pmatrix}$

2. Compute A5 where

$A = \begin{pmatrix} -6 & 28\\ -2 & 9 \end{pmatrix}$

3. Solve the following recurrence relations

$x_n = 3x_{n-1} - x_{n-2} \!$
$x_1 = 1 \!$
$x_0 = 0 \!$

Solutions

1.

$A^5 = \begin{pmatrix} -2922 & 2110\\ -4431 & 3197 \end{pmatrix}$

2.

$A^5 = \begin{pmatrix} -216 & 868\\ -62 & 249 \end{pmatrix}$

...more to come

# FeedbackEdit

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 section. Better still, edit it yourself and make it better.

To tell the truth ,I haven't finished it. The theories included are not difficult for me because I have studied a little game theory. But, the passage is a little long for me, and I am not very interested in certain parts. It's maybe a little too much information for me. I will try to finish it. Thank you!

I was directed here for information before taking cryptography I. This was a good review of probability rules. A little disappointed that author didn't get back to the definition of independent events and continuous probability. And I don't know what happen at the end; it looked kind of cut off. But, overall it was a nice guide and thanks! - undergrad

Around the middle of the article, you introduced the notation of two numbers — one over the other — inside of parenthesis. There was no description of the meaning of this notation or how it is used.

I do not have a background in mathematics (In Fact, I was never any good at it). However, I have found this quite understandable for my novice capabilities. I was too referred here by my cryptography teacher. Now, I can look at his presentation with only one eye crossed. I am still a little confused about some of the information, such as binomial distribution. However, I will reread and see if I can understand.

Some sections got way to complex for me, with the info dumps.

I didn't get why the article started using a variable and "(1')" behind it. That was so confusing. The passage does not explain an actual use for matrices. I do know a little bit of vector math, but this wiki-book went from properties of matrices all the way to determinants way to fast.