Find f(n): nth 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 nth power in O(d3log(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: