SCOREX - Problem in Getting to X

general
1

Problem: SCOREX
Can anyone please explain the matrix multiplication part in the problem.

2

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*Fi=Fi+1.

The transformation matrix T for Fibonacci numbers is :

alt text

Now, how to use this transformation matrix to determine the Nth Fibonacci number.
We can obtain Fn by applying this transformation matrix (n-1) times to F1 where F1 for Fibonacci numbers is [1,1]t where t denotes the transpose.

So, final relation becomes

Fn = Tn-1 * F1

So, to find the nth fibonacci number we multiply 1st row of Tn-1 with F1.

Next problem : How to find Tn-1 fast ??

For this we will use concept of power by exponentiation for matrices. The idea is the same extension of finding ab 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 An 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 F1 to get the nth 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 F1

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

Lets say coefficient of k terms are C1, C2, . . . . , Ck.

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 [Ck, Ck-1, Ck-2, . . . . . , C1]

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

F(n) = Tn-1 * F(1) to find the solution of n.

Therefore, the overall complexity for kxk will be k3*lg(n).

Problems related to the concept :

Will add after my AI quiz. :stuck_out_tongue:

1 Like
3

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

4

Initially yes. :slight_smile: