JavaScript Program to Find the Rank of a Matrix
Given a matrix of size M x N, your task is to find the rank of a matrix using JavaScript.
Example:
Input: mat[][] = [[10, 20, 10],
[20, 40, 20],
[30, 50, 0]]
Output: Rank is 2
Explanation: Ist and 2nd rows are linearly dependent.
But Ist and 3rd or 2nd and 3rd are independent.
Input: mat[][] = [[10, 20, 10],
[-20, -30, 10],
[ 30, 50, 0]]
Output: Rank is 2
Explanation: Ist and 2nd rows are linearly independent.
So rank must be atleast 2. But all three rows are linearly dependent
(the first is equal to the sum of the second and third)
so the rank must be less than 3.
Table of Content
- Using Minor Method
- Using Row echelon form
- Using the Normal Form Method
Using Minor Method
In this approach, we determine the rank of the matrix by analyzing the linear independence of its rows or columns. We start by converting the matrix to reduced row echelon form using elementary row operations and then count the number of non-zero rows or columns. This count gives us the rank of the matrix.
Example: The example below shows how to find the rank of a matrix using the Minor Method.
function det(matrix) {
if (matrix.length === 1) {
return matrix[0][0];
}
if (matrix.length === 2) {
return matrix[0][0] * matrix[1][1] -
matrix[0][1] * matrix[1][0];
}
let determinant = 0; // Renamed to avoid conflict
for (let i = 0; i < matrix.length; i++) {
const sign = i % 2 === 0 ? 1 : -1;
const minor = matrix.slice(1).map(row =>
row.filter((_, j) => j !== i));
determinant += sign * matrix[0][i] * det(minor);
}
return determinant;
}
function rank(matrix) {
const numRows = matrix.length;
const numCols = matrix[0].length;
const minDim = Math.min(numRows, numCols);
let rank = 0;
for (let i = 1; i <= minDim; i++) {
const submatrices = genSubs(matrix, i);
for (const submatrix of submatrices) {
if (det(submatrix) !== 0) {
rank = i;
break;
}
}
if (rank !== i) {
break;
}
}
return rank;
}
function genSubs(matrix, size) {
const submatrices = [];
for (let i = 0; i <= matrix.length - size; i++) {
for (let j = 0; j <= matrix[0].length - size; j++) {
const submatrix = [];
for (let k = i; k < i + size; k++) {
submatrix.push(matrix[k].slice(j, j + size));
}
submatrices.push(submatrix);
}
}
return submatrices;
}
const matrix = [
[10, 20, 10],
[20, 40, 20],
[30, 50, 0]
];
console.log("Rank is", rank(matrix));
Output
Rank is 2
Time Complexity: O(M3N3) where M is the number of rows and N is the number of columns in the matrix.
Space Complexity: O(M2N2)
Using Row echelon form
In this approach, we follow the row echelon form technique to reduce the matrix to its row echelon form, where each leading entry of a row is 1, and zeros appear below the leading entry. The rank of the matrix is then determined by the number of non-zero rows in the row echelon form.
Example: The example below shows how to find the rank of a matrix using the Row echelon form.
function findRank(mat) {
const rows = mat.length;
const cols = mat[0].length;
let rank = cols;
// Iterate over each row
for (let row = 0; row < rank; row++) {
if (mat[row][row] !== 0) {
for (let i = 0; i < rows; i++) {
if (i !== row) {
const multiplier = mat[i][row] / mat[row][row];
for (let j = row; j < cols; j++) {
mat[i][j] -= multiplier * mat[row][j];
}
}
}
} else {
let reduce = true;
for (let i = row + 1; i < rows; i++) {
if (mat[i][row] !== 0) {
[mat[row], mat[i]] = [mat[i], mat[row]];
reduce = false;
break;
}
}
if (reduce) {
rank--;
for (let i = 0; i < rows; i++) {
mat[i][row] = mat[i][rank];
}
}
row--;
}
}
return rank;
}
const matrix1 = [
[10, 20, 10],
[20, 40, 20],
[30, 50, 0]
];
console.log("Rank of matrix 1:", findRank(matrix1));
const matrix2 = [
[10, 20, 10],
[-20, -30, 10],
[30, 50, 0]
];
console.log("Rank of matrix 2:", findRank(matrix2));
Output
Rank of matrix 1: 2 Rank of matrix 2: 2
Time complexity: O(M×N×min(M, N)), where M is the number of rows and N is the number of columns in the matrix.
Auxiliary Space: O(1)
Using the Normal Form Method
The Normal Form Method involves reducing the matrix to its normal form, where each leading entry of a row is 1, and zeros appear below the leading entry. The rank of the matrix is then determined by the number of non-zero rows in the normal form.
Example: The example below shows how to find the rank of a matrix using the Normal Form Method.
function rank(matrix) {
// Get the number of rows and columns in the matrix
const num_rows = matrix.length;
const num_cols = matrix.length > 0 ? matrix[0].length : 0;
let rank = 0;
for (let i = 0; i < num_rows; i++) {
let pivot_found = false;
// Iterate over each column of the matrix
for (let j = 0; j < num_cols; j++) {
if (matrix[i][j] !== 0) {
pivot_found = true;
rank++; // Increment rank
for (let k = 0; k < num_rows; k++) {
if (k !== i) {
const ratio =
matrix[k][j] / matrix[i][j];
for (let l = 0; l < num_cols; l++) {
matrix[k][l] -= ratio * matrix[i][l];
}
}
}
break;
}
}
if (!pivot_found) {
break;
}
}
return rank;
}
const matrix = [[10, 20, 10],
[-20, -30, 10],
[30, 50, 0]];
console.log("Rank is", rank(matrix));
Output
Rank is 2
Time Complexity: O(M×N×min(M, N)), where M is the number of rows and N is the number of columns in the matrix.
Space Complexity: O(1)
Contact Us