Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

lazyneuron's blog

By lazyneuron, 5 years ago, In English

Matrix Exponentiation

Introduction:

The concept of matrix exponentiation in its most general form is very useful in solving questions that involve calculating the $$$n^{th}$$$ term of a linear recurrence relation in time of the order of log(n).

First of all we should know what a linear recurrence relation is like:

$$$f_n = \sum_{i=1}^{k} c_{i} * f_{n-i}$$$ and some other terms(I will talk about them later)

Here each $$$c_i$$$ can be zero also, which simply means that $$$f_n$$$ doesn't simply depend on $$$f_{n - i}$$$.

So, as the name suggests we will be making use of matrices to compute the $$$n^{th}$$$ term for us.

First, consider the simple case: $$$f_n = \sum_{n=1}^{k} c_{k} * f_{n-k}$$$

Consider the following $$${k*k}$$$ matrix T: \begin{pmatrix} 0 & 1 & 0 & 0 & . & . \\ 0 & 0 & 1 & 0 & . & . \\ 0 & 0 & 0 & 1 & . & . \\ . & . & . & . & . & . \\ c_k & c_{k-1} & c_{k — 2} & . & . & c_1 \end{pmatrix} And the $$${k*1}$$$ column vector F: \begin{pmatrix} f_0 \\ f_1 \\ f_2 \\ . \\ . \\ . \\ f_{k — 1} \end{pmatrix} Why does the F vector have a dimension of $$$k*1$$$? Simple, because a recurrence relation is complete only with the first $$$k$$$ values(just like the base cases in recursion) given together with the general equation of the same degree.

The matrix $$$T*F$$$ = \begin{pmatrix} f_1 \\ f_2 \\ f_3 \\ . \\ . \\ . \\ f_{k} \end{pmatrix} It is easy to see for the first $$$k - 1$$$ entries of vector $$$C = T*F$$$. The $$$k^{th}$$$ entry is just the calculation of recurrence relation using the past $$$k$$$ values of the sequence. Throughout our discussion so far it has been assumed that the $$$n^{th}$$$ term depends on the previous $$$k$$$ terms where $$$n \ge k$$$(zero based indexing assumed). So, when we obtain $$$C = T * F$$$, the first entry gives $$$f_1$$$. It is easy to see that $$$f_n$$$ is the first entry of the vector: $$$C_n = T^n * F$$$(Here $$$T^n$$$ is the matrix multiplication of T with itself $$$n$$$ times).

Let's construct the same $$$T$$$ matrix for our favourite fibonacci sequence. Turns out it is equal to \begin{pmatrix} 0&1 \\ 1&1 \\ \end{pmatrix}

So we see it all boils down to getting the T matrix right.

A practice problem: Calculate the T matrix for this recurrence: $$$f_n = 2 * f_{i - 1} + 3 * f_{i - 2} + 4 * f_{i - 3}$$$.

Spoiler

This much concept will help you solve this problem: https://www.spoj.com/problems/SEQ/

Little Variations:

Let's talk about the "some other terms" thing I mentioned. Consider the recurrence: $$$f_n = 2 * f_{i - 1} + 3 * f_{i - 2} + 5$$$. The T matrix for the recurrence will be \begin{pmatrix} 0&1&0 \\ 3&2&5 \\ 0&0&1 \\ \end{pmatrix} But there will be a slight variation to the F matrix also. It will now be \begin{pmatrix} f_0 \\ f_1 \\ 1 \\ \end{pmatrix} And the $$$n^{th}$$$ term will still be the first entry of the vector $$$C = T^n*F$$$. One last variation that I want to discuss is in this recurrence: $$$f_i = f_{i - 1} + 2 * i^2 + 5$$$ The T matrix and F vector will be(Try if you want to):

Spoiler

Practice problem: $$$f_i = f_{i - 1} + 2 * i^2 + 3 * i + 5$$$

Spoiler

Complexity Analysis

If you know the concept of binary exponentiation, then you can see that $$$T^n$$$ can be calculated in $$$O(log(n))$$$. But here we are dealing with matrices of the order of $$$k*k$$$. So, in the squaring step, we are multiplying the $$$k*k$$$ T matrix with itself. The matrix multiplication algorithm will have a complexity of $$$O(k^3)$$$. Hence, the overall complexity turns out be $$$O(k^3 * log(n))$$$.

Conclusion

Finally, I would like you to try this problem: https://mirror.codeforces.com/contest/1182/problem/E. This concept coupled with knowledge of Fermat's theorem and logarithms will make this problem super easy in terms of idea and doable in terms of implementation. I hope, I was clear enough while expressing myself and you gained something new from this tutorial. I hope to come up with useful ideas to help the community. Constructive suggestions are welcome.

  • Vote: I like it
  • +127
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you explain how to extend it to multi-dimension, may be with this problem as an example https://community.topcoder.com/stat?c=problem_statement&pm=15135?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't understand anything about this tutorial tbh, as in you didn't explain how to get the T matrix, this blog does a good job of explaining tho:

http://zobayer.blogspot.com/2010/11/matrix-exponentiation.html

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Well i don't think so, i missed on explaining the actual theory. If you look at the spoilers, even they have decent explanations. I do believe this to be not the best one out there for absolute beginners. The only reason i didn't spoonfeed is because i want the reader to take out pen and paper to actually get the hang of it by following what i wrote. Thanks for the suggestions, i intend to target absolute beginners next time.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Title is misleading, it's not anywhere near of a "complete" guide. As a beginner, i could not understand how Tn's first entry is fn which is claimed to be easy to see and many other things :(

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It was easy to see, because I expected the reader to have some knowledge of matrix product. Also, the aim of the tutorial was to get you to use pen and notebook so that you wrote and verified everything as you moved along.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can anyone please give their snippet or template for matrix multiplication and matrix exponentiation. because my code is taking much time as other competitors. i have seen there code, but they have made template for 2 x 2 matrix.

Problem link

Efficient solution [0.1 sec]

My solution [1.5 sec]

i have made matrix expo and multiplication for all size of matrices. but efficient solution have made it only for 2 x 2 matrix.

so, if anyone can share their snippet or template would be helpful to me. btw!! good explanation on matrix expo. thank you !!

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks bro , it really helped a lot , specially the problems you have mentioned!!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to choose matrix for f(n)=f(n-1)+f(n-2)+f(n-1)*f(n-2) ?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This problem was recently asked in a CODECHEF contest . Here is my solution

    F[n] = F[n-1] + F[n-2] + F[n-1]*F[n-2]; F[n]+1 = F[n-1] +1 + F[n-2]*(F[n-1]+1) // add 1 on both sides F[n]+1 = (F[n-1] +1)*(F[n-2]+1)

    Now Let G[n] = F[n]+1; G[n] = G[n-1]*G[n-2];

    G[0] = P+1; G[1] = Q+1;

    After writing some terms of sequence G you will notice that G[n] = pow(G[0],fib(n-1))*pow(G[1],fib(n-2));

    where fib(n) is nth Fibonacci number

    Here is link to my solution : https://www.codechef.com/viewsolution/31944368

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey bro, Can you please tell the significance of using two mods in your solution? I have found it in many solutions but couldn't understand its use.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what will be the matrix T for this relation f(n) = f(n-1) — f(n-2) + n ?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    T = \begin{pmatrix} 0 & 1 & 0 & 0\\ -1 & 1 & 0 & 1\\ 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 1 \end{pmatrix}

    so it will transform

    \begin{pmatrix} f_{i — 2}\\ f_{i — 1}\\ 1\\ i \end{pmatrix} to \begin{pmatrix} f_{i — 1} \\ f_i \\ 1 \\ i + 1 \end{pmatrix}

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      correct me if i am wrong if we want to find s(n) = f(0)+f(1)+f(2)+f(3)+...+f(n): where f(0)=f(1)=1; then T = [0 1 0 0 0] [-1 1 0 1 0] [0 0 1 0 0] [0 0 1 1 0] [-1 1 1 1 1]

      so [f(n-2)] [f(n-1)] [1] [n] [s(n)]

      to [f(n-1)] [f(n)] [1] [n+1] [s(n+1)]

      and power of T is n-1

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Don't do it this way, instead make use of the original recurrence to simplify s(n), this would greatly simplify the problem. And s(n) won't come in the vector you can calculate s(n) using f(i) values only. Try thinking, hint: part of it is a telescopic series.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Yes got it.it is just simple pattern for s(n). Thank you very much

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What will be the matrix T for this relation f(n) = f(n-2)+f(n-4)-2n+3n^2 ?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try to define a matrix recurrence $$$v_{n + 1} = T v_{n}$$$ for the vector:

    $$$v_n = (f(n), f(n - 1), f(n - 2), f(n - 3), n^2, n, 1)^\text{T}$$$
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thank you a lot,it was like some black magic for me but know i understood it

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Great tutorial ! Also, this can be useful for beginners.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to use this method when some coefficients are not constant? For example: f(n) = n*f(n-1) + f(n-2)

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you, very helpful

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can you explain, how the matrix T is k*k, I think there would be k+1 columns ? and i think the limit would be for k not n in the summation fn. = summation(k = [1,n] , instead of fn = summation(n = [1, k]) ?