__Number Theory - Matrix Exponentiation__

__Number Theory - Matrix Exponentiation__

**Note: **
It is recommended to read our previous article on Binary Exponentiation, as
we will be using concept of binary exponentiation in this article. If you
have not yet read it click here to
read it.

So, after reading our previous article lets continue with our next article
on Matrix Exponentiation.

**1. So, What is Matrix Exponentiation ?**
**
**

Matrix Exponentiation is basically calculating powers of a matrix efficiently, yes you read it right we will be calculating powers of matrix efficiently.

In simple words you are given a matrix ‘A’ and an integer ‘N’ and we need to calculate A

^{N}. (Note A is a 2d-array or matrix here)

So, As always we think of a naïve approach (Brute force) first and then we
will optimize it with some cool observations.

**2. Naïve Approach**
**
**
In this we will do multiplication of matrix with itself ‘N’ times as we do
normal matrix multiplication.

Solution for naïve approach is left to you, we know you can code it. Just go on we are always with you 😊

**Time Complexity: O(M**here M is order of matrix.

^{3}* N)

**3. Matrix Exponentiation**

**So, here comes our real hero for this article, yeah !! Matrix Exponentiation is here to improve time complexity of naïve approach.**

Idea behind matrix exponentiation is very simple we will be just as we were calculating a

^{n}in our previous article we will calculate A

^{N }here.

**
Algorithm for Matrix exponentiation:
Step1:
**
Iterate till n > 0

**Step2:**In each iteration we will check if our power (i.e. N) is even then we will

**multiply matrix with itself and do N = N / 2**.

**Step3:**else we will

**multiply matrix with identity matrix and do N = N – 1**

Below is the implementation of optimized approach:

**
Time Complexity: O( M ^{3} * Log(n) )
**

It is always better to solve a question after you learn a new concept as it
helps in making concrete concepts.

So, below are problems which are handpicked by Programmers Army to make your concept more solid which you learned.

1. **Problem from SPOJ: **
https://www.spoj.com/problems/MPOW/

2. **Problem from CodeChef:**
https://www.codechef.com/problems/
CBARS

We highly recommend to solve above problems if you got stuck read editorials for guidance.

So that’s it for this article we will be coming up with our next article on further topics of number theory very soon till then keep learning, keep coding, keep reading and keep improving !!

**
**

**Happy Coding **

**By Programmers Army **
**😊**