Problem: SCOREX

Can anyone please explain the matrix multiplication part in the problem.

Hi Rajat.

Let first define the Fibonnaci problem using a matrix.

To define the problem we create a 2 X 2 transformation matrix T such that T*F_{i}=F_{i+1}.

The transformation matrix T for Fibonacci numbers is :

Now, how to use this transformation matrix to determine the N^{th} Fibonacci number.

We can obtain F_{n} by applying this transformation matrix (n-1) times to F_{1} where F_{1} for Fibonacci numbers is [1,1]^{t} where t denotes the transpose.

So, final relation becomes

F_{n} = T^{n-1} * F_{1}

So, to find the n^{th} fibonacci number we multiply 1st row of T^{n-1} with F_{1}.

Next problem : How to find T^{n-1} fast ??

For this we will use concept of power by exponentiation for matrices. The idea is the same extension of finding a^{b} in lg(b) time.

Pseudocode for that is :

```
def matrix_pow(matrix A, int n):
matrix res;
while(n):
if(n&1):
multiply(A,res)
multiply(A,A)
n>>=1
return res
```

The complexity to compute A^{n} is |A|^{3}*lg(n), where |A| denotes the dimension of A.

Note: A is a square matrix.

Now, as we have computed the res matrix we can multiply its first row with F_{1} to get the n^{th} Fibonacci number.

So, far we used this concept for Fibonacci numbers. How to extend this idea further for any recurrence.

Say, our recurrence relation is :

F(i) = F(i-1) + F(i-2) + . . . . . +F(i-k)

i.e F(i) depends on k terms.

Note: even if coefficient of any term is 0 but it depends on kth term which is the last, than also the number of terms F(i) depends is k.

For ex :

F(i) = F(i-1) + F(i-2) depends on 2 terms

F(i) = F(i-1) + F(i-4) depends on 4 terms where coefficient of F(i-2) and F(i-3) is 0.

Now, we define our initial vector F_{1}

Now, we need to find the transformation matrix of size kxk which I defined above.

Lets say coefficient of k terms are C_{1}, C_{2}, . . . . , C_{k}.

1st row of our transformation matrix will be [0, 1, 0, 0 , . . . . . 0] where no.of elements in any row are k.

2nd row will be [0, 0, 1, 0 , . . . . . 0]

3rd row will be [0, 0, 0, 1 , . . . . . 0]

.

.

.

kth row will be [C_{k}, C_{k-1}, C_{k-2}, . . . . . , C_{1}]

Now, we got our transformation matrix for the recurrence. Now just use the formula

F(n) = T^{n-1} * F(1) to find the solution of n.

Therefore, the overall complexity for kxk will be k^{3}*lg(n).

Problems related to the concept :

Will add after my AI quiz.

the matrix res is initialized with identity matrix or all 1s ?

Initially yes.