**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

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 😊

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

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

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 **
**😊**