Find rank

Easy
0/40
Average time to solve is 15m
profile
Contributed by
44 upvotes
Asked in companies
Goldman SachsAtlassianMicrosoft

Problem statement

You are given a matrix ‘ARR’ having dimensions ‘N*M’. Your task to find the rank of the matrix ‘ARR’.

The rank of a matrix is defined as:

(a) The maximum number of linearly independent column vectors in the matrix.
OR
(b) The maximum number of linearly independent row vectors in the matrix.
Both definitions are equivalent.

Linear independence is defined as:

In the theory of vector spaces, a set of vectors is said to be linearly dependent if there is a nontrivial linear combination of the vectors that equals the zero vector. If no such linear combination exists, then the vectors are said to be linearly independent.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of every test case contains two space-separated integers, ‘N’ and ‘M’, denoting the number of rows and the number of columns respectively.

Then each of the next ‘N’ rows contains ‘M’ elements.
Output format: 
For each test case, return the rank of the matrix.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N , M <= 500
-10^4 <= Arr[i][j] <= 10^4

Where ‘ARR[i][j]’ denotes the matrix element at the jth column in the ith row of ‘ARR’

Time Limit: 1 sec
Sample Input 1:
2
3 3
1 0 1
-2 -3 1
3 3 0
3 3
0 1 2   
1 2 1
2 7 8
Sample Output 1:
2
2
Explanation for Sample input 1:
For the first test case:
The 1st row and 2nd row are linearly independent but the third row can be represented as a linear combination of 1st and 2nd row as row3 = row1 - row2. Therefore, there are 2 linearly independent rows. So the rank is 2.

For the second test case:
The 1st row and 2nd row are linearly independent but the third row can be represented as a linear combination of 1st and 2nd row as row3 = (3*row1) + (2*row2). Therefore, there are 2 linearly independent rows. So the rank is 2.
Sample Input 2:
2
2 3
1 2 3   
2 4 6
2 4
1 2 4 4 
3 4 8 0
Sample Output 2:
1
2
Explanation for sample input 2:
For the first test case:
The 1st row and 2nd row are linearly dependent as the second row is a scaler multiple of row1 i.e. row2 = 2*row1. Therefore, there is 1 linearly independent row. So the rank is 1.

For the second test case:
Since neither row is linearly dependent on the other row, the matrix has 2 linearly independent rows. So the rank is 2.
Hint

Try to use the concept of row echelon form in matrices.

Approaches (1)
Row Echelon Form

Approach:

  • The idea is based on converting the given input matrix ARR into row echelon form.
  • Since we know that the rank of the matrix can not be greater than min(N, M). So we will check if N > M then we will transpose the input matrix ARR since we are using row echelon form so the matrix has to be transformed in such a way that in each row all the elements to the left of the diagonal element must be zero. And the count of non-zero diagonal elements in each row will be equal to our rank of the matrix.
  • Otherwise, we will proceed with the next step without performing the transpose of the given matrix ARR.
  • Now we will traverse over each row and perform the following operations:
    • If the diagonal element is non-zero then we will make all the elements in that column as zero except the diagonal element by finding the appropriate multiplier.
    • If it is zero then two cases arise:
    • case1: If there is a row below the current row with a non - zero entry in the same column then we will swap both of these rows.
    • case2: if we are unable to find a row with a non -zero entry in the current column then we will swap this current column with the last column.
    • Now we will decrement the number of rows by one so that the row can be processed again.
  • Now we will iterate through all the rows and count the diagonal element which is equal to our rank of the matrix.



 

Algorithm:

  • First, check if the N is greater than M then transpose the given input matrix ARR. Otherwise, proceed to the next step without performing transpose of the given matrix ARR.
  • Now create a variable swapCol equal to M - 1 which will be used when we have to swap the columns.
  • Now iterate through each row from i = 0 to i = N-1 and perform the following operations:
    • If the diagonal element ARR[i][i] is not zero then we have to make all the elements in the current column i to zero except the diagonal element. For this, we will iterate through each row again from j = 0 to j =N-1 and for the element where j is not equal to i we will perform:
      • We will calculate the appropriate multiplier for that row i.e multiplier = (double)ARR[j][i]/ARR[i][i].
      • Now update the whole row j as ARR[j][k] -= multiplier*ARR[i][k]  where k = 0 to k = M. 
    • Otherwise, perform the following operations:
      • we will create a variable isSwapped equal to false initially which will denote whether we have swapped two rows.
      • Now traverse through all rows below the current row i and if we are able to find a non-zero entry in the ARR in the same column i then we have to swap these two rows and update isSwapped as true and break the loop.
      • Now check if isSwapped is equal to false then swap the current column i with the column represented by swapCol and decrement the value of swapCol by one.
      • Now decrease the value of i by one so that the row can be processed again.  
  • Create a variable rank initialized to 0.
  • Now traverse through all rows again and increment the rank by one if there exits a non - zero diagonal element in each row.
  • Finally, return the rank as the required answer.
Time Complexity

O((N^2)*M), where N is the number of rows and M is the number of columns.

 

Since we are traversing over each row which takes O(N) time and while traversing each row two conditions are there which takes O(N*M) time each. So the overall time complexity will be O((N^2)*M).   

Space Complexity

O(N*M), where N is the number of rows and M is the number of columns.


Since a temporary matrix will be created while doing transpose which takes O(N*M) space. So the overall space complexity will be O(N*M).  

Code Solution
(100% EXP penalty)
Find rank
Full screen
Console