### naruhodou's blog

By naruhodou, 10 months ago, ,

# 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

## 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.

• +127

 » 10 months ago, # |   0 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?
•  » » 10 months ago, # ^ |   0 Give me the name of the problem. The link isn't opening.
•  » » » 10 months ago, # ^ | ← Rev. 3 →   0 LongPalindromes.
 » 10 months ago, # |   0 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
•  » » 10 months ago, # ^ |   +5 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.
•  » » » 10 months ago, # ^ |   0 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.
 » 8 months ago, # |   0 Only if this had some explanation for 2nd part...
 » 4 months ago, # |   0 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 :(
•  » » 4 months ago, # ^ |   0 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.
•  » » » 4 months ago, # ^ |   0 well , atlast i have figured out why Tn's first entry is fn, Anyways thanks :)
 » 6 weeks ago, # | ← Rev. 2 →   0 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 linkEfficient 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 !!