 5

# Find rank

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

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