Home » Interview coding problems/challenges

Matrix Exponentiation

Matrix Exponentiation: You will be given a square matrix M and a positive integer power N. You will have to compute M raised to the power N. (that is, M multiplied with itself N times.)
Submitted by Divyansh Jaipuriyar, on August 22, 2020

Problem statement

You will be given a square matrix M and a positive integer power N. You will have to compute M raised to the power N. (that is, M multiplied with itself N times.)

Problem description

The problem wants you to multiply matrix to itself n times which is a difficult job if you perform it by normal iteration method so you are required to think an approach such that it provides correct solution with minimum time ,think some logic similar to binary exponentiation technique that we use to calculate power of number n times as power(x, n) such that we use logarithmic time.

Input

The first line of input is T (number of test-cases) First line of each test case contains two integer M, N where M is the size of the square matrix that we have to exponent and N is the power to which we have to, exponent.

Next M lines describe the input matrix. Each line contains exactly M elements corresponding to each array

Output

Output M line corresponding to each row of resultant matrix Each line must have M integers where j^th element of i^th line is jth element of resultant matrix taken modulo with 1000000007 (10^9+7).

Examples

Input:
T=1
M=2,N=3
1 0
1 1

Output:
1 0
3 1

Input:
T=1
M=3,N=3
1 0 4
1 2 2
0 4 4

Output:
17 112 116
15 88 100
28 144 160

Solution Approach

(a) Brute Force Approach:

In this approach, we will multiply the given matrix M, N number of times. Each time the multiplication will cost O(M^3) time in the worst case and we multiplied it N numbers of times so the overall time complexity will be O(N*M^3) which will be huge.

Since the given operation is on the matrix so we cant multiply it similar to normal mathematical variables, we will multiply it with its Identity matrix of the same size as of given matrix M, we will store the result in the final result in the given matrix after performing all multiplication.

Here we are using function multiply which will take two matrices and multiply them and store the result in the first matrix, solve function which will take matrix as given in the question and all the operation from creating identity matrix and calling multiply function and then storing the final result in the given matrix. The print function will print the final matrix that we get after all operations.

Time Complexity for the above operation in the worst case is: O((M^3)*N)
Space Complexity for above operation in the worst case is: O(M*M)

(b) Matrix Exponentiation Method:

In this approach all operation is the same except the multiplication operation, instead of traversing from 1 to N, we will multiply matrix using binary exponentiation logic. That is each when our power (N) is odd we multiply Identity matrix with the given matrix that is (I*A) and decrease power variable N--, and in even condition, we will multiply a matrix with itself, that is (A*A) and divide power by 2 i.e (N/2).

So we can multiply the given matrix N number of times in log(N) time.

So overall we saved a lot of time.

Time Complexity for the above approach in worst case: O((M^3)*(log(N))
Space Complexity for the above approach in worst case: O(M*M)

C++ Implementation (Brute Force Approach):

#include <bits/stdc++.h>
using namespace std;

#define mod 1000000007

//define size for 2-D
//matrix function pass.
#define NN 52
typedef long long ll;

//declare matrix arr and I.
ll arr[NN][NN], I[NN][NN];

//multiply function to
//multiply two matrix.
void multiply(ll A[][NN], ll B[][NN], ll M)
{
    //declare temporary matrix
    //which will store the multiplied
    //result of size M+1 because we are
    //using 1 index based calculation.
    ll res[M + 1][M + 1];
    
    for (ll i = 1; i <= M; i++) {
        for (ll j = 1; j <= M; j++) {
            //initially it is 0.
            res[i][j] = 0;
            //multiply accordingly matrix
            //multiplication rule.
            for (ll k = 1; k <= M; k++)
                res[i][j] = ((res[i][j] % mod) + ((A[i][k] % mod) * (B[k][j] % mod)) % mod) % mod;
        }
    }
    
    //finally store the multiplied
    //matrix result in A matrix.
    for (ll i = 1; i <= M; i++)
        for (ll j = 1; j <= M; j++)
            A[i][j] = res[i][j];
}

//solve function which will
//perform matrix multiplication N times.
void solve(ll A[][NN], ll M, ll N)
{
    //make diagonal elements as 1
    //and others element as 0.
    for (ll i = 1; i <= M; i++)
        for (ll j = 1; j <= M; j++) {
            if (i == j)
                I[i][j] = 1;
            else
                I[i][j] = 0;
        }
    
    //multiply matrix linearly from
    //power 1 to N
    for (ll i = 1; i <= N; i++)
        multiply(I, A, M); //i=I*A on each operation

    //finally store the
    // multiplied matrix result.
    for (ll i = 1; i <= M; i++)
        for (ll j = 1; j <= M; j++)
            A[i][j] = I[i][j];
}

//print function which will print
//the final multiplied matrix.
void print(ll A[][NN], ll M)
{
    for (ll i = 1; i <= M; i++) {
        for (ll j = 1; j <= M; j++)
            cout << A[i][j] << " ";
        cout << "\n";
    }
}

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size and power: ";
        ll M, N;
        cin >> M >> N;

        cout << "Enter elements:\n";
        for (ll i = 1; i <= M; i++)
            for (ll j = 1; j <= M; j++)
                cin >> arr[i][j];
        solve(arr, M, N);
        cout << "Final matrix:\n";
        print(arr, M);
    }

    return 0;
}

Output

Enter number of test cases: 2
Enter size and power: 2 2
Enter elements:
1 1 
1 1
Final matrix:
2 2 
2 2 
Enter size and power: 2 3
Enter elements:
1 1
1 1
Final matrix:
4 4 
4 4 

C++ Implementation (Optimized Method - Matrix Exponentiation)

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007

//define size for 2-D
//matrix function pass.
#define NN 52

typedef long long ll;

//declare matrix arr and I.
ll arr[NN][NN], I[NN][NN];

//multiply function to
//multiply two matrix.
void multiply(ll A[][NN], ll B[][NN], ll M)
{
    //declare temporary matrix
    //which will store the multiplied
    //result of size M+1 because we are
    //using 1 index based calculation.
    ll res[M + 1][M + 1];

    for (ll i = 1; i <= M; i++) {
        for (ll j = 1; j <= M; j++) {
            //initially it is 0.
            res[i][j] = 0;
            //multiply accordingly matrix
            //multiplication rule.
            for (ll k = 1; k <= M; k++)
                res[i][j] = ((res[i][j] % mod) + ((A[i][k] % mod) * (B[k][j] % mod)) % mod) % mod;
        }
    }

    //finally store the multiplied
    //matrix result in A matrix.
    for (ll i = 1; i <= M; i++)
        for (ll j = 1; j <= M; j++)
            A[i][j] = res[i][j];
}

//solve function which will
//perform matrix multiplication N times.
void solve(ll A[][NN], ll M, ll N)
{
    //make diagonal elements as 1
    //and others element as 0.
    for (ll i = 1; i <= M; i++)
        for (ll j = 1; j <= M; j++) {
            if (i == j)
                I[i][j] = 1;
            else
                I[i][j] = 0;
        }

    //binary exponentiation logic.
    while (N > 0) {
        //if odd power
        if (N % 2)
            multiply(I, A, M), N--;
        else //even power condition.
            multiply(A, A, M), N /= 2;
    }

    //finally store the
    // multiplied matrix result.
    for (ll i = 1; i <= M; i++)
        for (ll j = 1; j <= M; j++)
            A[i][j] = I[i][j];
}

//print function which will print
//the final multiplied matrix.
void print(ll A[][NN], ll M)
{
    for (ll i = 1; i <= M; i++) {
        for (ll j = 1; j <= M; j++)
            cout << A[i][j] << " ";
        cout << "\n";
    }
}

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size and power: ";
        ll M, N;
        cin >> M >> N;

        cout << "Enter elements:\n";
        for (ll i = 1; i <= M; i++)
            for (ll j = 1; j <= M; j++)
                cin >> arr[i][j];

        solve(arr, M, N);

        cout << "Final matrix:\n";
        print(arr, M);
    }

    return 0;
}

Output

Enter number of test cases: 3
Enter size and power: 3 4
Enter elements:
1 2 3
4 5 6
7 8 9
Final matrix:
7560 9288 11016 
17118 21033 24948 
26676 32778 38880 
Enter size and power: 2 2
Enter elements:
1 1
1 1
Final matrix:
2 2 
2 2 
Enter size and power: 3 2
Enter elements:
1 0 4
1 2 2
0 4 4
Final matrix:
1 16 20 
3 12 16 
4 24 24