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://mirror.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.