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.
- Advantages of using matrix form instead of the recurrence relationship itself
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 
I will try to illustrate this with an example, the Tribonacci Numbers.
- 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:
F(n) = F(n-1) + F(n-2) + F(n-3), F(1) = 1; F(2) = 1; F(3) = 2
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.
- Understanding Matrix exponentiation
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:
|f(4)| = MATRIX * |f(1)|
|f(3)| |f(2)|
|f(2)| |f(3)|
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:
|f(4)| = |1 1 1| * |f(1)|
|f(3)| |* * *| |f(2)|
|f(2)| |* * *| |f(3)|
For the second line, we want to obtain f(3), and the only possible way of doing it is by having:
|f(4)| = |1 1 1| * |f(1)|
|f(3)| |0 0 1| |f(2)|
|f(2)| |* * *| |f(3)|
To get the value of f(2), we can follow the same logic and get the final matrix:
|1 1 1|
|0 0 1|
|0 1 0|
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:
|f(n)| = |1 1 1|^(N-3) * |f(1)|
|f(n-1)| |0 0 1| |f(2)|
|f(n-2)| |0 1 0| |f(3)|
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.
def matrix_mult(A, B):
C = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
for i in range(3):
for j in range(3):
for k in range(3):
C[i][k] = (C[i][k] + A[i][j] * B[j][k]) % 1000000007
return C
def fast_exponentiation(A, n):
if n == 1:
return A
else:
if n % 2 == 0:
A1 = fast_exponentiation(A, n/2)
return matrix_mult(A1, A1)
else:
return matrix_mult(A, fast_exponentiation(A, n - 1))
def solve(n):
A = [[1,1,1],[0,0,1],[0,1,0]]
A_n = fast_exponentiation(A,n-3)
return A_n[0][0] + A_n[0][1] + A_n[0][2]*2
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
