5

Find rank

Difficulty: EASY
Contributed By
Ankit Kharb
Avg. time to solve
15 min
Success Rate
85%

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. 
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.
Reset Code
Full screen
copy-code
Console