1.
Introduction
2.
Problem Statement
3.
Test Cases
3.1.
Test Case1
3.1.1.
Input
3.1.2.
Output
3.1.3.
Explanation
3.2.
Test Case2
3.2.1.
Input
3.2.2.
Output
3.2.3.
Explanation
4.
Solution
4.1.
Algorithm
4.2.
Implementation
4.2.1.
C++ Code
4.2.2.
Java Code
4.2.3.
Python Code
4.3.
Output
4.4.
Complexity Analysis
5.
5.1.
What are the ways we can traverse a matrix?
5.2.
Is Identity Matrix Idempotent Matrix?
5.3.
Is Null or Zero Matrix Idemoptent Matrix?
5.4.
What are the time and space complexity of traversing a matrix of size NxN?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Program to Check Idempotent Matrix

Aniket Majhi
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Welcome readers! We hope you are doing well.

Matrices are essential concepts for programmers, as they contribute to building the fundamental concepts of good programmers.

Today, we will be discussing the program to check whether a given Matrix is Idempotent or not.

From this article, the concept regarding the Idempotent matrix and how to implement it in different programming languages will be clear to you. So follow the article till the end.

So, without further ado, letâ€™s start our discussion.

Problem Statement

Given a matrix of size NxN. You need to check whether the given matrix is Idempotent or not.

Note that a matrix M is said to be an idempotent matrix, if we multiply the matrix by itself, it returns the same matrix. I.e, M2 = M.

Example,

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Test Cases

Following are the test cases,

Test Case1

Input

``````{
{2, -1, -3},
{-1, 2, 3},
{1, -1, -2}
}``````

Output

``Idempotent Matrix``

Explanation

Below is the explanation,

For the matrix

{

{2, -1, -3},

{-1, 2, 3},

{1, -1, -2}

}

After multiplying with itself, we are getting the same matrix back, as shown below.

So it is an Idempotent Matrix.

Test Case2

Input

``````{
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
}``````

Output

``Not Idempotent Matrix``

Explanation

{

{1, 2, 3},

{4, 5, 6},

{7, 8, 9}

}

After multiplying with itself, we are getting the same matrix back, as shown below.

So it is Not an Idempotent Matrix.

Solution

The solution is shown below,

Algorithm

• Take the matrix in a 2D array.
• Multiply the matrix with itself and store the result in another matrix.
• Then, check whether the initial and result matrix is the same.
• If they are the same, then the matrix is idempotent. Otherwise, not.

Implementation

Here in this section, we will implement the above algorithm in different languages.

C++ Code

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

#define n 3

// function to check for idempotent matrix
bool is_idempotent(int matrix[][n]) {
// stores the multiplication result
int result[n][n];

// matrix multiplication
for(int i = 0; i < n ; i++) {
for(int j = 0 ; j < n ; j++) {
result[i][j] = 0;
for(int k = 0; k < n ; k++) {
result[i][j] += (matrix[i][k] * matrix[k][j]);
}
}
}

// check whether we are getting same matrix after performing multiplication
for(int i = 0; i < n ; i++) {
for(int j = 0; j < n ; j++) {
if(matrix[i][j] != result[i][j])  return false;
}
}

return true;
}

int main()
{
int matrix[n][n] = {{2, -1, -3} , {-1, 2, 3} , {1, -1, -2}};
if(is_idempotent(matrix)) {
cout << "Idempotent Matrix";
}
else{
cout << "Not Idempotent Matrix";
}

return 0;

}``````

Java Code

``````class Main{
static int n = 3;
static boolean is_idempotent(int matrix[][]) {
// stores the multiplication result
int[][] result= new int[n][n];

// matrix multiplication
for(int i = 0; i < n ; i++) {
for(int j = 0 ; j < n ; j++) {
result[i][j] = 0;
for(int k = 0; k < n ; k++) {
result[i][j] += (matrix[i][k] * matrix[k][j]);
}
}
}

// check whether we are getting same matrix after performing multiplication
for(int i = 0; i < n ; i++) {
for(int j = 0; j < n ; j++) {
if(matrix[i][j] != result[i][j])  return false;
}
}

return true;
}

public static void main(String[] args) {
// given matrix
int[][] matrix = {{2, -1, -3} , {-1, 2, 3} , {1, -1, -2}};

// check for idempotent matrix
if(is_idempotent(matrix)) {
System.out.print("Idempotent Matrix");
}
else{
System.out.print("Not Idempotent Matrix");
}

}
}``````

Python Code

``````def is_idempotent(matrix):
# result matrix

n = len(matrix)

# store the result
result = [[0] * n for i in range(0 , n)]

# multipying the matrix with itself
for i in range(0 , n):
for j in range(0 , n):
# print(matrix[i][j], end=' ')
result[i][j] = 0
for k in range(0 , n):
result[i][j] += (matrix[i][k] * matrix[k][j])

# check for equality
for i in range(n):
for j in range(n):
if matrix[i][j] != result[i][j]:
return False
return True

matrix = [[2 , -1, -3],
[-1, 2, 3],
[1, -1, -2]]

if (is_idempotent(matrix)):
print("Idempotent Matrix")
else:
print("Not Idempotent Matrix")``````

Output

``Idempotent Matrix``

Complexity Analysis

Time Complexity: O(n2)

Space Complexity: O(n2)

What are the ways we can traverse a matrix?

There are mainly two ways to traverse a matrix:

• Row-wise traversal(Row-major Traversal)
• Column-wise traversal(Column-major Traversal)

Is Identity Matrix Idempotent Matrix?

We know that for Identity Matrix I, if we multiply the matrix by itself, it returns the same matrix, i.e. I2 = I, so Identity Matrix is Idempotent.

Is Null or Zero Matrix Idemoptent Matrix?

Null or Zero Matrix is an Idempotent Matrix. As When multiplying with itself, it returns the same matrix.

What are the time and space complexity of traversing a matrix of size NxN?

Time Complexity: O(N2)

Space Complexity: O(1)

Conclusion

In this article, we have discussed the Program to Check Idempotent Matrix.

We started with the basic introduction, then we discussed,

• Problem Statement
• What Idempotent Matrix is
• Solution
• Algorithm to follow
• Implementation of the algorithm in C++, Java, Python
• Complexity Analysis

We hope you have some idea from this article regarding the Program to Check Idempotent Matrix.

To learn more, follow our articles on Transpose of a Matrix in CBook Allocation Problem, Getch in C and Matrix in Zig-Zag Form.