Matrix Exponentiation

“A nice technique you will appreciate once known.”

Pre Requisites: Binary Exponentiation, Linear Recurrence relations, Matrices, Fibonacci Numbers
Topic Difficulty: Medium

In the previous post, we have seen that we can calculate the powers of integers in logarithm complexity. Are we only restricting this idea of binary exponentiation only to integers …… Can we go beyond this and extend this same idea to matrices?

It's a Yes. As the topic suggests, we can also calculate the powers of a matrix in logarithm complexity. But to note: If the matrix is of size K x K, then the multiplication of matrices costs O(k³) complexity.

Then raising the power of the matrix costs an overall complexity of
O(k³ logN), where K x K is the size of the matrix, and N is the power to be raised. (Refer to prev blog if you are not clear about this complexity)

But why are we so concerned about matrices? What problems does this technique actually solve? We shall see the answers to these questions soon below…

Note: We are dealing with only square matrices here of size K x K

Code snippet on matrix exponentiation:

For simplicity, all matrices are 2x2 in the below code, but they can be easily generalized to any K x K matrix.

I hope that the above snippet is clear. If not, compare this snippet's pow function with the pow function of the previous blog.

Let's deal with a problem now….

Find the Nth Fibonacci number in log(N) time complexity.

Yes, you heard it right. Till now, we would have only seen O(N) as an easy solution for finding the Nth Fibonacci number.

But the truth is that there exists an O(logN) solution that solves the same problem of just finding the Nth Fibonacci number.

Try to think intuitively about what happens at O(N) algorithm. We are computing all 1st, 2nd to …. N th Fibonacci numbers. But my problem requires only the Nth Fibonacci Number. We are doing unnecessary computation here. We can intuitively think there can be a better solution to directly finding the required Fibonacci number without computing all previous values.

And Yes, matrix exponentiation comes to the rescue.

Now let's see how my Fibonacci number problem can be converted to matrices and solved using this technique.

Consider f(n) = Nth fibonacci number. Look at below matrix equation carefully.

This matrix equation can be easily verified.
Consider RHS:
1 * f(n-1) + 1 * f(n-2) = f(n-1) + f(n-2) = f(n) by definition {1st value}
Similarly f(n-1) = f(n-1) {2nd value}

On going further, we can see that …

You would have got an idea of what we are doing here. Going on further, we can see that….

Here my base cases are f(1) = 1 and f(0) = 0

It's done…. We have somehow converted our problem into a problem of matrix exponentiation. We need to raise the {{11}{10}} base matrix to power N-1, which can be solved with matrix expo in complexity O(k³ logN).
{in this example k = 2}. O(8logN) will run faster.

NOTE:

• Fibonacci numbers are even larger for large N, which does not fit in integer datatype. So generally, problems are asked in this technique based on printing answers in modulo P. Also, use LONG LONG.

SUMMARY:
It is to be shown that any linear recurrence of form
f(n) = c1*f(n-1) + c2*f(n-2) + …..+ ck*f(n-k) where c1,..,ck are integers.
It can be solved with matrix expo taking k x k base matrix size.

Even popular linear-dp problems like dice rolling and Staircase Dp have a matrix expo solution running in O(logN) complexity.

Coming up with a correct base matrix is sometimes harder, but it can be easily framed by considering the recurrence relation.

This article is published as a part of the ‘Algo Reads’ under Spider Research and Development Club, NIT Trichy.

Resource: Usaco Guide