naruhodou's blog

By naruhodou, 4 months 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://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

»
4 months 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?

»
4 months 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

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes because, once an absolute beginner like me can understand the Matrix exponentiation, its only a small step to take to learn advanced matrix exponentiation and then you know everything about matrix exponentiation, unlike in other areas like dp and graphs where the sky is the limit to how much you can learn about them.

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

Only if this had some explanation for 2nd part...