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}$$$.
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):
Practice problem: $$$f_i = f_{i - 1} + 2 * i^2 + 3 * i + 5$$$
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.
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?
Give me the name of the problem. The link isn't opening.
LongPalindromes.
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
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.
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.
Only if this had some explanation for 2nd part...
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 :(
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.
well , atlast i have figured out why Tn's first entry is fn, Anyways thanks :)
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 !!
Thanks bro , it really helped a lot , specially the problems you have mentioned!!
Thank you very much.
how to choose matrix for f(n)=f(n-1)+f(n-2)+f(n-1)*f(n-2) ?
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
thanks bro
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.
If p is prime then pow(A,p-1)%p=1 . This is Fermat's Theorem . Using this if power of a number is very big then we can take modulo of power with (p-1).In my solution mod2 is prime number and mod=mod2-1 .
You can learn it from here https://en.wikipedia.org/wiki/Fermat%27s_little_theorem
Ohh...Thanks a lot
what will be the matrix T for this relation f(n) = f(n-1) — f(n-2) + n ?
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}
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
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.
Yes got it.it is just simple pattern for s(n). Thank you very much
What will be the matrix T for this relation f(n) = f(n-2)+f(n-4)-2n+3n^2 ?
Try to define a matrix recurrence $$$v_{n + 1} = T v_{n}$$$ for the vector:
thank you a lot,it was like some black magic for me but know i understood it
Great tutorial ! Also, this can be useful for beginners.
https://discuss.codechef.com/t/linear-recurrence-using-cayley-hamilton-theorem/6776
Can anyone explain in more detail regarding the transition matrix for recurrence f(i)=f(i-1)+2*i^2+5?
Thank you
UPD:Understood it!
How exactly, can you explain ?
Assume T*F1=F2 and F1=[f0 1 i i^2]^T then F2 should be F2=[f1 1 (i+1) (i+1)^2]^T Now try to form the transformation matrix T.
Proof for choosing F1: F1 is in the above form because we need to make i to (i+1) after one multiplication with T matrix , constant term will only appear if we have 1 in the F1 column matrix.Similarly i^2 can be changed to (i+1)^2 after multiplying with T only if we have i^2,i and 1 in F1 column matrix as [(i+1)^2=i^2+2*i+1].So i gave the reasons for choosing 1,i,i^2 in F1 Column matrix.
thanks!