Last Updated: 27 Nov, 2020

# Find rank

Easy

## Problem statement

#### 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

## Approaches

### 01 Approach

#### 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.