Matrix Exponentiation – A Complete guide

Hello guys, welcome back to “code with asharam”. This has been a long break. I guess my last post by almost 16 days ago. I am sorry for such a long break but there has been many events such as Google Codejam Qualification and Round 1A. And there was Codechef April long challenge. So, I was occupied for most of the time in last 16 days. But now you can relax as I am back with another informative post. In this post, I will discuss the basic concepts of matrix exponentiation. This is one of the most useful techniques in competitive programming and can convert an O(n) looking solution to O(logn) solution in no time. So, without any further delay, let’s take a dive into deep oceans of Matrix Exponentiation.

Matrices in Computer Science

I am sure that all of you would have heard of 2-dimensional arrays if you had a little programming experience. You can think of 2-d arrays as a rectangular grid with N rows and M columns and an element is kept at each intersection of a row and column. Matrices defined in mathematics is equivalent to 2-d arrays in computer science. Now, performing addition on 2-d arrays is a usual thing to do. We just have to add corresponding elements of 2 matrices to add them. But I can say that most of you would not have performed 2-d array multiplication. Therefore, before reading about Matrix Exponentiation, I will discuss 2-d array/Matrix multiplication. You can skip this section if you are already familiar with matrix multiplication.

Multiplying 2 Matrices

Before moving forward, you must know that you cannot multiply any random pair of matrices. A matrix having number of columns M can only be multiplied with another Matrix having M rows. You can perform matrix multiplication by considering the points given below:

  1. Multiplying matrix A of size NxM with another matrix B of size MxK will result in matrix C of size NxK.
  2. Cij = sum of Aik*Bkj, where k varies from 1 to M. In simple words, you have to calculate the sum of multiplication of corresponding elements of ith row of A and jth column of B.
  3. A*B is not always equal to B*A.
  4. A*(B*C) = (A*B)*C. This equation forms the essence of Matrix Exponentiation.
  5. Brute force multiplication of 2 square matrices of size KxK will take O(K3) time. You can optimize this but it is not required in this post.

I have not discussed this topic in detail and will advice you to read more theory if you want to know more. Now, I will move to matrix exponentiation.

Matrix Exponentiation

Exponentiation! Exponents!! sound familiar, yeah? You heard it right, it is nothing but evaluating exponent of a matrix. Suppose that we have a square matrix A of size KxK, then, our goal is to find the value of An. You can do it easily by multiplying A n times. But this is not much efficient. So, let’s discuss some efficient method:

Let pow(A, n) denotes An
=> If n is even, then, An = An/2*An/2
   Hence, pow(A, n) = pow(A, n/2)*pow(A, n/2) if n is even
=> If n is odd, then, An = An/2*An/2*A
   Hence, pow(A, n) = pow(A, n/2)*pow(A, n/2)*A if n is odd
=> If n is 1, then, pow(A, n) = A

Let's define our final algorithm
pow(A, n):
      if n==1 then A
      else:
         B = pow(A, n/2)
         if n is even then B*B
         else B*B*A

Above algorithm runs in O(K3*logn) time and is quite similar to the fast power algorithm which runs in O(logn) time.

Applications of Matrix Exponentiation

If you know basics of linear algebra, then, everything I will write from now on will sound familiar to you. But don’t worry even if you are not familiar with even algebra as I will write everything from a beginner perspective. So, All of you are familiar with the famous Fibonacci Sequence and its O(n) solution using recursive relation fib(n) = fib(n-1) + fib(n-2). Now, I will give you a O(logn) solution for this problem using matrix exponentiation.

\[
\left\{
\begin{array}{c}
F_n = 1*F_{n-1} + 1*F_{n-2} \\
F_{n-1} = 1*F_{n-1} + 0*F_{n-2}
\end{array}
\right.
\]
Now, get ready to see the magic of matrix multiplication. You can represent above two recursive relation in form of matrices as follows:
\[
\begin{bmatrix}
F_n \\ F_{n-1}
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\ 1 & 0
\end{bmatrix}
*
\begin{bmatrix}
F_{n-1} \\ F_{n-2}
\end{bmatrix}
\]
Now, above realtion is true for all $n>2$, hence, for $F_{n-1}$, we can write
\[
\begin{bmatrix}
F_{n-1} \\ F_{n-2}
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\ 1 & 0
\end{bmatrix}
*
\begin{bmatrix}
F_{n-2} \\ F_{n-3}
\end{bmatrix}
\]
Similarly, we can find above matrix equation for $F_{n-3}$….till $F_3$ and substitute them in our main equation. Finally, we will get following equation:
\[
\begin{bmatrix}
F_n \\ F_{n-1}
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\ 1 & 0
\end{bmatrix}^{n-2}
*
\begin{bmatrix}
F_2 \\ F_1
\end{bmatrix}
\]
Initially in this article, I have shown you how to calculate exponents of square matrices in $O(log(n)*K^3)$ time. For square matrix of size $2$, $K^2 = 4$ which can be treated as a constant in time complexity expression and hence, we can calculate $n_{th}$ term of Fibonacci sequence in $O(log(n))$ time.

How to find matrix equation for any linear recursive relation?

So, now you feel excited and want to know how to extend this method to a general recursive relation. I will give you an example for a linear relations having $3$ variables with $1$ constant and you can similarly apply this method for any general relation.
Suppose you are given following equation: $$F_n = 8*F_{n-2} + 9*F_{n-3} + 2*F_{n-5} + C$$
It is equivalent to: $$F_n = 8*F_{n-2} + 9*F_{n-3} + 0*F_{n-4} + 2*F_{n-5} + C$$
Now, we can write following system of equations:
\[
\left\{
\begin{array}{c}\
F_n = 8*F_{n-2} + 9*F_{n-3} + 0*F{n-4} + 2*F_{n-5} + 1*C \\
F_{n-2} = 1*F_{n-2} + 0*F_{n-3} + 0*F_{n-4} + 0*F_{n-5} + 0*C \\
F_{n-3} = 0*F_{n-2} + 1*F_{n-3} + 0*F_{n-4} + 0*F_{n-5} + 0*C \\
F_{n-4} = 0*F_{n-2} + 0*F_{n-3} + 1*F_{n-4} + 0*F_{n-5} + 0*C \\
C = 0*F_{n-2} + 0*F_{n-3} + 0*F_{n-4} + 0*F_{n-5} + 1*C
\end{array}
\right.
\]
In matrix form, above system of equation will look like as follows:
\[
\begin{bmatrix}
F_n \\ F_{n-2} \\ F_{n-3} \\ F_{n-4} \\ C
\end{bmatrix} =
\begin{bmatrix}
8 & 9 & 0 & 2 & 1 \\
1 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1
\end{bmatrix} *
\begin{bmatrix}
F_{n-2} \\ F_{n-3} \\ F_{n-4} \\ F_{n-5} \\ C
\end{bmatrix}
\]
You can appreciate the fact of making initial recursive relation continuous in nature by adding the term $F_{n-4}$ and giving preference to constant $C$. In this way, you can convert any linear recursive relation to matrix equation. There are some tricky equations which require slight modifications to convert them to matrix form and you can get hold upon them only through practice. Give a try to pk and interesting language and many more problems on online judges.
So, that’s it guys for today. I hope you would have enjoyed this tutorial. If you liked this tutorial, then, please follow my blog and share it with your friends.
You can subscribe to my YouTube channel for video tutorials on competitive programming.
You can connect with me on LinkedIn. To get all of your queries answered, you can message me on Quora. Follow me on medium for more of my writings.

2 thoughts on “Matrix Exponentiation – A Complete guide”

    1. Just like there is no Fn-2 on left hand side in the Fibonacci sequence. If we include Fn-5 on left hand side, then, we have to add Fn-6 on right hand side which will only increase the size of matrix.

Leave a Reply

%d bloggers like this: