Given a square matrix mat[][] and an integer N, the task is to print the matrix after multiplying the matrix N times.
Examples:
Input: mat[][] = {{1, 2, 3}, {3, 4, 5}, {6, 7, 9}}, N = 2
Output:
25 31 40
45 57 74
81 103 134Input: mat[][] = {{1, 2}, {3, 4}}, N = 3
Output:
37 54
81 118
Approach: The idea is to use the Matrix Multiplication identity matrix. i.e., A = IA and A = AI, where A is a matrix of N * M order dimensions and I is the identity matrix of dimensions M * N, where N is the total number of rows and M is the total number of columns in a matrix.
The idea is to iterate over the range [1, N] and update the Identity Matrix with A.I so that after calculating the value of A2 = A.A, A3 can be calculated as A.A2 and so on till AN.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function for matrix multiplicationvoid power(vector<vector<int>>& I, vector<vector<int>>& a, int rows, int cols){ // Stores the resultant matrix // after multiplying a[][] by I[][] vector<vector<int>> res(rows, vector<int>(cols)); // Matrix multiplication for(int i = 0; i < rows; ++i) { for(int j = 0; j < cols; ++j) { for(int k = 0; k < rows; ++k) { res[i][j] += a[i][k] * I[k][j]; } } } // Updating identity element // of a matrix for(int i = 0; i < rows; ++i) { for(int j = 0; j < cols; ++j) { I[i][j] = res[i][j]; } }}// Function to print the given matrixvoid print(vector<vector<int> >& a){ // Traverse the row for(int i = 0; i < a.size(); ++i) { // Traverse the column for(int j = 0; j < a[0].size(); ++j) { cout << a[i][j] << " "; } cout << "\n"; }}// Function to multiply the given// matrix N timesvoid multiply(vector<vector<int> >& arr, int N){ // Identity element of matrix vector<vector<int>> I(arr.size(), vector<int>(arr[0].size())); // Update the Identity Matrix for(int i = 0; i < arr.size(); ++i) { for(int j = 0; j < arr[0].size(); ++j) { // For the diagonal element if (i == j) { I[i][j] = 1; } else { I[i][j] = 0; } } } // Multiply the matrix N times for(int i = 1; i <= N; ++i) { power(I, arr, arr.size(), arr[0].size()); } // Update the matrix arr[i] to // to identity matrix for(int i = 0; i < arr.size(); ++i) { for(int j = 0; j < arr[0].size(); ++j) { arr[i][j] = I[i][j]; } } // Print the matrix print(arr);}// Driver Codeint main(){ // Given 2d array vector<vector<int>> arr = { { 1, 2, 3 }, { 3, 4, 5 }, { 6, 7, 9 } }; // Given N int N = 2; // Function Call multiply(arr, N); return 0;}// This code is contributed by akhilsaini |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function for matrix multiplication static void power(int I[][], int a[][], int rows, int cols) { // Stores the resultant matrix // after multiplying a[][] by I[][] int res[][] = new int[rows][cols]; // Matrix multiplication for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { for (int k = 0; k < rows; ++k) { res[i][j] += a[i][k] * I[k][j]; } } } // Updating identity element // of a matrix for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { I[i][j] = res[i][j]; } } } // Function to print the given matrix static void print(int a[][]) { // Traverse the row for (int i = 0; i < a.length; ++i) { // Traverse the column for (int j = 0; j < a[0].length; ++j) { System.out.print(a[i][j] + " "); } System.out.println(); } } // Function to multiply the given // matrix N times public static void multiply( int arr[][], int N) { // Identity element of matrix int I[][] = new int[arr.length][arr[0].length]; // Update the Identity Matrix for (int i = 0; i < arr.length; ++i) { for (int j = 0; j < arr[0].length; ++j) { // For the diagonal element if (i == j) { I[i][j] = 1; } else { I[i][j] = 0; } } } // Multiply the matrix N times for (int i = 1; i <= N; ++i) { power(I, arr, arr.length, arr[0].length); } // Update the matrix arr[i] to // to identity matrix for (int i = 0; i < arr.length; ++i) { for (int j = 0; j < arr[0].length; ++j) { arr[i][j] = I[i][j]; } } // Print the matrix print(arr); } // Driver Code public static void main(String[] args) { // Given 2d array int arr[][] = { { 1, 2, 3 }, { 3, 4, 5 }, { 6, 7, 9 } }; // Given N int N = 2; // Function Call multiply(arr, N); }} |
Python3
# Python3 program for the above approach# Function for matrix multiplicationdef power(I, a, rows, cols): # Stores the resultant matrix # after multiplying a[][] by I[][] res = [[0 for i in range(cols)] for j in range(rows)] # Matrix multiplication for i in range(0, rows): for j in range(0, cols): for k in range(0, rows): res[i][j] += a[i][k] * I[k][j] # Updating identity element # of a matrix for i in range(0, rows): for j in range(0, cols): I[i][j] = res[i][j]# Function to print the given matrixdef prints(a): # Traverse the row for i in range(0, len(a)): # Traverse the column for j in range(0, len(a[0])): print(a[i][j], end = ' ') print()# Function to multiply the given# matrix N timesdef multiply(arr, N): # Identity element of matrix I = [[1 if i == j else 0 for i in range( len(arr))] for j in range( len(arr[0]))] # Multiply the matrix N times for i in range(1, N + 1): power(I, arr, len(arr), len(arr[0])) # Update the matrix arr[i] to # to identity matrix for i in range(0, len(arr)): for j in range(0, len(arr[0])): arr[i][j] = I[i][j] # Print the matrix prints(arr)# Driver Codeif __name__ == '__main__': # Given 2d array arr = [ [ 1, 2, 3 ], [ 3, 4, 5 ], [ 6, 7, 9 ] ] # Given N N = 2 # Function Call multiply(arr, N)# This code is contributed by akhilsaini |
C#
// C# program for the above approachusing System;class GFG{// Function for matrix multiplicationstatic void power(int[,] I, int[,] a, int rows, int cols){ // Stores the resultant matrix // after multiplying a[][] by I[][] int[,] res = new int[rows, cols]; // Matrix multiplication for(int i = 0; i < rows; ++i) { for(int j = 0; j < cols; ++j) { for(int k = 0; k < rows; ++k) { res[i, j] += a[i, k] * I[k, j]; } } } // Updating identity element // of a matrix for(int i = 0; i < rows; ++i) { for(int j = 0; j < cols; ++j) { I[i, j] = res[i, j]; } }}// Function to print the given matrixstatic void print(int[, ] a){ // Traverse the row for(int i = 0; i < a.GetLength(0); ++i) { // Traverse the column for(int j = 0; j < a.GetLength(1); ++j) { Console.Write(a[i, j] + " "); } Console.WriteLine(); }}// Function to multiply the given// matrix N timespublic static void multiply(int[, ] arr, int N){ // Identity element of matrix int[, ] I = new int[arr.GetLength(0), arr.GetLength(1)]; // Update the Identity Matrix for(int i = 0; i < arr.GetLength(0); ++i) { for(int j = 0; j < arr.GetLength(1); ++j) { // For the diagonal element if (i == j) { I[i, j] = 1; } else { I[i, j] = 0; } } } // Multiply the matrix N times for(int i = 1; i <= N; ++i) { power(I, arr, arr.GetLength(0), arr.GetLength(1)); } // Update the matrix arr[i] to // to identity matrix for(int i = 0; i < arr.GetLength(0); ++i) { for(int j = 0; j < arr.GetLength(1); ++j) { arr[i, j] = I[i, j]; } } // Print the matrix print(arr);}// Driver Codepublic static void Main(){ // Given 2d array int[, ] arr = { { 1, 2, 3 }, { 3, 4, 5 }, { 6, 7, 9 } }; // Given N int N = 2; // Function Call multiply(arr, N);}}// This code is contributed by akhilsaini |
Javascript
// JavaScript program for the above approach// Function for matrix multiplicationfunction power(I, a, rows, cols){ // Stores the resultant matrix // after multiplying a[][] by I[][] let res = new Array(rows) for (var i = 0; i < rows; i++) res[i] = new Array(cols).fill(0) // Matrix multiplication for (var i = 0; i < rows; i++) { for (var j = 0; j < cols; j++) { for (var k = 0; k < rows; k++) res[i][j] += a[i][k] * I[k][j] } } // Updating identity element // of a matrix for (var i = 0; i < rows; i++) for (var j = 0; j < cols; j++) I[i][j] = res[i][j]}// Function to print the given matrixfunction prints(a){ // Traverse the row for (let row of a) console.log(row.join(" ")) }// Function to multiply the given// matrix N timesfunction multiply(arr, N){ // Identity element of matrix let I = [] for (var i = 0; i < arr.length; i++) { let row = [] for (var j = 0; j < arr[0].length; j++) { if (i == j) row.push(1) else row.push(0) } I.push(row) } // Multiply the matrix N times for (var i = 1; i <= N; i++) power(I, arr, arr.length, arr[0].length) // Update the matrix arr[i] to // to identity matrix for (var i = 0; i < arr.length; i++) for (var j = 0; j < arr[0].length; j++) arr[i][j] = I[i][j] // Print the matrix prints(arr)}// Driver Code // Given 2d array let arr = [ [ 1, 2, 3 ], [ 3, 4, 5 ], [ 6, 7, 9 ] ] // Given N let N = 2 // Function Call multiply(arr, N)// This code is contributed by phasing17 |
Output:
25 31 40 45 57 74 81 103 134
Time Complexity: O(N3)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!