## Matrix Exponentiation to Solve Example Problems

*Find f(n): n ^{th} Fibonacci number.* The problem is quite easy when

**n**is relatively small. We can use simple recursion,

`f(n) = f(n-1) + f(n-2)`

, or we can use dynamic programming approach to avoid the calculation of same function over and over again. But what will you do if the problem says, **Given 0 < n < 10⁹, find f(n) mod 999983?**Dynamic programming will fail, so how do we tackle this problem?

First let's see how matrix exponentiation can help to represent recursive relation.

**Prerequisites:**

- Given two matrices, know how to find their product. Further, given the product matrix of two matrices, and one of them, know how to find the other matrix.
- Given a matrix of size
**d X d**, know how to find its n^{th}power in**O(d**.^{3}log(n))

**Patterns:**

At first we need a recursive relation and we want to find a matrix **M** which can lead us to the desired state from a set of already known states. Let's assume that, we know the **k** states of a given recurrence relation and we want to find the **(k+1) ^{th}** state. Let

**M**be a

**k X k**matrix, and we build a matrix

**A:[k X 1]**from the known states of the recurrence relation, now we want to get a matrix

**B:[k X 1]**which will represent the set of next states, i. e.

**M X A = B**as shown below:

```
| f(n) | | f(n+1) |
| f(n-1) | | f(n) |
M X | f(n-2) | = | f(n-1) |
| ...... | | ...... |
| f(n-k) | |f(n-k+1)|
```

So, if we can design **M** accordingly, our job will be done! The matrix will then be used to represent the recurrence relation.

**Type 1:**

Let's start with the simplest one, `f(n) = f(n-1) + f(n-2)`

We get, `f(n+1) = f(n) + f(n-1)`

.

Let's assume, we know `f(n)`

and `f(n-1)`

; We want to find out `f(n+1)`

.

From the situation stated above, matrix **A** and matrix **B** can be formed as shown below:

```
Matrix A Matrix B
| f(n) | | f(n+1) |
| f(n-1) | | f(n) |
```

[Note: Matrix **A** will be always designed in such a way that, every state on which `f(n+1)`

depends, will be present]

Now, we need to design a **2X2** matrix **M** such that, it satisfies **M X A = B** as stated above.

The first element of **B** is `f(n+1)`

which is actually `f(n) + f(n-1)`

. To get this, from matrix **A**, we need, **1 X f(n)** and **1 X f(n-1)**. So the first row of **M** will be **[1 1]**.

```
| 1 1 | X | f(n) | = | f(n+1) |
| ----- | | f(n-1) | | ------ |
```

[Note: ----- means we are not concerned about this value.]

Similarly, 2nd item of **B** is `f(n)`

which can be got by simply taking **1 X f(n)** from **A**, so the 2nd row of **M** is [1 0].

```
| ----- | X | f(n) | = | ------ |
| 1 0 | | f(n-1) | | f(n) |
```

Then we get our desired **2 X 2** matrix **M**.

```
| 1 1 | X | f(n) | = | f(n+1) |
| 1 0 | | f(n-1) | | f(n) |
```

These matrices are simply derived using matrix multiplication.

**Type 2:**

Let's make it a little complex: find `f(n) = a X f(n-1) + b X f(n-2)`

, where **a** and **b** are constants.

This tells us, `f(n+1) = a X f(n) + b X f(n-1)`

.

By this far, this should be clear that the dimension of the matrices will be equal to the number of dependencies, i.e. in this particular example, again 2. So for **A** and **B**, we can build two matrices of size **2 X 1**:

```
Matrix A Matrix B
| f(n) | | f(n+1) |
| f(n-1) | | f(n) |
```

Now for `f(n+1) = a X f(n) + b X f(n-1)`

, we need [a, b] in the first row of objective matrix **M**. And for the 2nd item in **B**, i.e. `f(n)`

we already have that in matrix **A**, so we just take that, which leads, the 2nd row of the matrix M to [1 0]. This time we get:

```
| a b | X | f(n) | = | f(n+1) |
| 1 0 | | f(n-1) | | f(n) |
```

Pretty simple, eh?

**Type 3:**

If you've survived through to this stage, you've grown much older, now let's face a bit complex relation: find `f(n) = a X f(n-1) + c X f(n-3)`

?

Ooops! A few minutes ago, all we saw were contiguous states, but here, the state **f(n-2)** is missing. Now?

Actually this is not a problem anymore, we can convert the relation as follows: `f(n) = a X f(n-1) + 0 X f(n-2) + c X f(n-3)`

, deducing `f(n+1) = a X f(n) + 0 X f(n-1) + c X f(n-2)`

. Now, we see that, this is actually a form described in Type 2. So here the objective matrix **M** will be **3 X 3**, and the elements are:

```
| a 0 c | | f(n) | | f(n+1) |
| 1 0 0 | X | f(n-1) | = | f(n) |
| 0 1 0 | | f(n-2) | | f(n-1) |
```

These are calculated in the same way as type 2, if you find it difficult, try it on pen and paper.

**Type 4:**

Life is getting complex as hell, and Mr, Problem now asks you to find `f(n) = f(n-1) + f(n-2) + c`

where **c** is any constant.

Now this is a new one and all we have seen in past, after the multiplication, each state in **A** transforms to its next state in **B**.

```
f(n) = f(n-1) + f(n-2) + c
f(n+1) = f(n) + f(n-1) + c
f(n+2) = f(n+1) + f(n) + c
.................... so on
```

So , normally we can't get it through previous fashion, but how about we add **c** as a state:

```
| f(n) | | f(n+1) |
M X | f(n-1) | = | f(n) |
| c | | c |
```

Now, its not much hard to design **M**. Here's how its done, but don't forget to verify:

```
| 1 1 1 | | f(n) | | f(n+1) |
| 1 0 0 | X | f(n-1) | = | f(n) |
| 0 0 1 | | c | | c |
```

**Type 5:**

Let's put it altogether: find `f(n) = a X f(n-1) + c X f(n-3) + d X f(n-4) + e`

.
Let's leave it as an exercise for you. First try to find out the states and matrix **M**. And check if it matches with your solution. Also find matrix **A** and **B**.

```
| a 0 c d 1 |
| 1 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 0 0 |
| 0 0 0 0 1 |
```

**Type 6:**

Sometimes the recurrence is given like this:

```
f(n) = f(n-1) -> if n is odd
f(n) = f(n-2) -> if n is even
```

In short:

```
f(n) = (n&1) X f(n-1) + (!(n&1)) X f(n-2)
```

Here, we can split the functions in the basis of odd even and keep 2 different matrix for both of them and calculate them separately.

**Type 7:**

Feeling little too confident? Good for you. Sometimes we may need to maintain more than one recurrence, where they are interested. For example, let a recurrence re;atopm be:

```
g(n) = 2g(n-1) + 2g(n-2) + f(n)
```

Here, recurrence *g(n)* is dependent upon `f(n)`

and this can be calculated in the same matrix but of increased dimensions. From these let's at first design the matrices **A** and **B**.

```
Matrix A Matrix B
| g(n) | | g(n+1) |
| g(n-1) | | g(n) |
| f(n+1) | | f(n+2) |
| f(n) | | f(n+1) |
```

Here, `g(n+1) = 2g(n-1) + f(n+1) and f(n+2) = 2f(n+1) + 2f(n)`

.
Now, using the processes stated above, we can find the objective matrix **M** to be:

```
| 2 2 1 0 |
| 1 0 0 0 |
| 0 0 2 2 |
| 0 0 1 0 |
```

So, these are the basic categories of recurrence relations which are used to solveby this simple technique.