As these new editorials for SEPT12 were released, the interest in matrix exponentiation grew a lot, and I will try to provide a relatively complete, yet simple tutorial on the most simple recurrence relationships and how they can be written in the matrix form.
To use matrix exponentiation it's first necessary to understand why we would want to use it... After all, methods such as classic DP and/or memoization are available and they are easier to code. The great advantage of matrix exponentiation is that its running time is simply O(k^3 * logN)(for a matrix of dimensions k*k) which is critical when we are dealing with values as large as 10^15, for example. It is used when the recursive relationship we derived is somehow entangled, in the sense that the values it takes depend on more than one of the previous values...Using the base cases of the recurrence relation and a repeated squaring/fast exponentiation algorithm, we have a very efficent way of dealing with large input values :D I will try to illustrate this with an example, the Tribonacci Numbers.
For those of you who had never heard the name before, this sequence of numbers is an "expansion" of the fibonacci sequence that includes a third term on the sum of the previous two, such that the formula looks like:
as stated on WolframMathworld. Of course, all the problems that arose when we tried to compute the fibonnaci numbers via dp or any other way become a lot more complicated with tribonacci numbers, and for N as large as 10^15, using dp will always be very slow, regardless of the time limit.
The basic idea behind matrix exponentiation, as stated earlier is to use the base cases of the recurrence relationship in order to assemble a matrix which will allow us to compute values fast. On our case we have: F(1) = 1 F(2) = 1 F(3) = 2 And we now have a relationship that will go like this:
Now all that is left is to assemble the matrix... and that is done based both on the rules of matrix multiplication and on the recursive relationship... Now, on our example we see that to obtain f(4), the 1st line of the matrix needs to be composed only of ones, as f(4) = 1 f(3) + 1 f(2) + 1* f(1). Now, denoting the unknown elements as *, we have:
For the second line, we want to obtain f(3), and the only possible way of doing it is by having:
To get the value of f(2), we can follow the same logic and get the final matrix:
To end it, we now need to generalize it, and, as we have 3 base cases, all we need to do to compute the Nth tribonacci number in O(logN) time, is to raise the matrix to the power N 3 to get:
The power of the matrix can now be computed in O(logN) time using repeated squaring applied to matrices and the method is complete... Below is the Python code that does this, computing the number modulo 10000000007.
I hope you have liked my tutorial!! Cheers, Bruno Oliveira Edit: As practice problems, CROWD, CSUMD and the problem Plants on the codeforces website are good starting places
This question is marked "community wiki".
asked 12 Sep '12, 04:05

"The great advantage of matrix exponentiation is that its running time is simply answered 12 Sep '12, 10:57

Thank you very much, the power is corrected... I guess I got confused starting with value 1... answered 12 Sep '12, 05:31

Thank you everyone for your corrections... As this article was inspired by some tutorials on specific problems and a mixture of my knowledge, it's natural that some things were not that accurate, so thank you for clearing them out both for me in particular and for everyone who reads the post!! Much appreciated!!! answered 12 Sep '12, 13:57

I will also add this tutorial to that list of links we are now compiling on that post :) @admin, it would be nice if you could pin that post :D Then we would be able to make a really good "reference book" to all these important topics! Best regards, Bruno answered 12 Aug '13, 23:11

Nice tutorial @kuruma......it helped me understand in simple terms...now i can implement it in C as your python code is pretty neat & clean.
I am glad I can help this wondeful community which has also given a lot to me in terms of learning computer programming techniques!!! It's a pleasure :D
Awesome tutorial . @kuruma it was really good and easy to learn .