Matrix Game

Easy
0/40
Average time to solve is 15m
18 upvotes
Asked in companies
OYOYatraSnapdeal Ltd.

Problem statement

Ninja is a teacher at a school. He introduced a game of matrix. He gives a square matrix, i.e., NxN matrix, to all the school students and asks them to check if the matrix is idempotent or not.

A matrix is an idempotent matrix if a matrix multiplied by itself returns the same matrix. The matrix M is said to be an idempotent matrix if and only if M * M = M. In the idempotent matrix, M is a square matrix.

Among them, a student Ninja is new to programming; he doesn’t have much experience; he asks you to solve the problem. Can you help Ninja figure out whether the matrix is idempotent?

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T,’ denoting the number of test cases. The test cases follow.

The first line of each test case contains a number ‘N’ denoting the number of rows and columns of the matrix.

The next ‘N’ lines of each test case contain ‘N’ integers in each line.
Output Format: 
For each test case, if Ninja managed to solve the problem, print “True”. Otherwise, print “False”.

Print the output of each test case in a separate line.
Note: 
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints: 
1<= T <= 50
1<= N <= 100 

 Time Limit: 1 sec

Sample Input 1:

2
3
2 -2 -4
-1 3 4
1 -2 -3
2
1 1
1 1
Sample Output 1:
True
False
Explanation for Sample Input 1:
In the first test case, the matrix M = [[2,-2,-4],[-1,3,4],[1,-2,-3]] which on multiplying with itself yields the same matrix M. Hence the matrix is idempotent.

In the second test case, the matrix M = [[1,1],[1,1]] which on multiplying with itself does not yield the same matrix M. Hence the matrix is not idempotent.

Sample Input 2:

2
2
3 -6
1 -2
3
1 2 3
4 5 6
7 8 9
Sample Output 2:
True
False
Hint

Will it be feasible to multiply the matrices? 

Approaches (1)
Brute Force

The idea is to maintain a 2D array that will store the result of the multiplication of a given matrix.

 

The steps are as follows:

  • We will maintain an integer 2D array of size NxN initially empty, which will store the result of multiplication of a given matrix with itself.
  • We will initialize the resultant 2D array with 0.
  • We will iterate from i = 0 to i = N - 1:
    • For each row in the given matrix, we will perform the following operations:
    • We will iterate through from j=0 to j=N since we need to multiply the matrix by itself.
      • We will iterate through from k=0 to k=N and multiply the matrix by itself, storing the result of multiplication in the resultant 2D array.
  • After all the iteration is done, the resulting 2D array will multiply the given matrix by itself.
  • Now, we will check if the given resultant matrix matches the given matrix. If it does, then return true. Otherwise, return false.
Time Complexity

O(N^3), where N is the number of rows and columns of the given matrix.

 

We are traversing each row of the matrix that takes O(N) time complexity, and inside each loop, we are using an additional loop between the columns, which takes extra time (N). Again we are traversing to calculate matrix multiplication which takes additional O(N) time. Hence the overall time complexity is O(N^3).

Space Complexity

O(N^2), extra space required.

 

We are using a resultant matrix to store the result of the multiplication of matrices. Hence, the overall space complexity is O(N^2). 

Code Solution
(100% EXP penalty)
Matrix Game
Full screen
Console