Find rank

Posted: 27 Nov, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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. 
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
Approach 1

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.
Try Problem