Skip to content

Commit 9dde8a7

Browse files
anupomkarAnup Omkarvil02siriak
authored
Add MatrixRank (TheAlgorithms#4571)
* feat: adding matrix rank algorithm * fix: formatting * fix: adding comments, refactor and handling edge cases * refactor: minor refactor * enhancement: check matrix validity * refactor: minor refactor and fixes * Update src/main/java/com/thealgorithms/maths/MatrixRank.java * feat: add unit test to check if input matrix is not modified while calculating the rank --------- Co-authored-by: Anup Omkar <anup_omkar@intuit.com> Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> Co-authored-by: Andrii Siriak <siryaka@gmail.com>
1 parent a4711d6 commit 9dde8a7

File tree

2 files changed

+209
-0
lines changed

2 files changed

+209
-0
lines changed

‎src/main/java/com/thealgorithms/maths/MatrixRank.java

Lines changed: 164 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,164 @@
1+
package com.thealgorithms.maths;
2+
3+
/**
4+
* This class provides a method to compute the rank of a matrix.
5+
* In linear algebra, the rank of a matrix is the maximum number of linearly independent rows or columns in the matrix.
6+
* For example, consider the following 3x3 matrix:
7+
* 1 2 3
8+
* 2 4 6
9+
* 3 6 9
10+
* Despite having 3 rows and 3 columns, this matrix only has a rank of 1 because all rows (and columns) are multiples of each other.
11+
* It's a fundamental concept that gives key insights into the structure of the matrix.
12+
* It's important to note that the rank is not only defined for square matrices but for any m x n matrix.
13+
*
14+
* @author Anup Omkar
15+
*/
16+
public final class MatrixRank {
17+
18+
private MatrixRank() {
19+
}
20+
21+
private static final double EPSILON = 1e-10;
22+
23+
/**
24+
* @brief Computes the rank of the input matrix
25+
*
26+
* @param matrix The input matrix
27+
* @return The rank of the input matrix
28+
*/
29+
public static int computeRank(double[][] matrix) {
30+
validateInputMatrix(matrix);
31+
32+
int numRows = matrix.length;
33+
int numColumns = matrix[0].length;
34+
int rank = 0;
35+
36+
boolean[] rowMarked = new boolean[numRows];
37+
38+
double[][] matrixCopy = deepCopy(matrix);
39+
40+
for (int colIndex = 0; colIndex < numColumns; ++colIndex) {
41+
int pivotRow = findPivotRow(matrixCopy, rowMarked, colIndex);
42+
if (pivotRow != numRows) {
43+
++rank;
44+
rowMarked[pivotRow] = true;
45+
normalizePivotRow(matrixCopy, pivotRow, colIndex);
46+
eliminateRows(matrixCopy, pivotRow, colIndex);
47+
}
48+
}
49+
return rank;
50+
}
51+
52+
private static boolean isZero(double value) {
53+
return Math.abs(value) < EPSILON;
54+
}
55+
56+
private static double[][] deepCopy(double[][] matrix) {
57+
int numRows = matrix.length;
58+
int numColumns = matrix[0].length;
59+
double[][] matrixCopy = new double[numRows][numColumns];
60+
for (int rowIndex = 0; rowIndex < numRows; ++rowIndex) {
61+
System.arraycopy(matrix[rowIndex], 0, matrixCopy[rowIndex], 0, numColumns);
62+
}
63+
return matrixCopy;
64+
}
65+
66+
private static void validateInputMatrix(double[][] matrix) {
67+
if (matrix == null) {
68+
throw new IllegalArgumentException("The input matrix cannot be null");
69+
}
70+
if (matrix.length == 0) {
71+
throw new IllegalArgumentException("The input matrix cannot be empty");
72+
}
73+
if (!hasValidRows(matrix)) {
74+
throw new IllegalArgumentException("The input matrix cannot have null or empty rows");
75+
}
76+
if (isJaggedMatrix(matrix)) {
77+
throw new IllegalArgumentException("The input matrix cannot be jagged");
78+
}
79+
}
80+
81+
private static boolean hasValidRows(double[][] matrix) {
82+
for (double[] row : matrix) {
83+
if (row == null || row.length == 0) {
84+
return false;
85+
}
86+
}
87+
return true;
88+
}
89+
90+
/**
91+
* @brief Checks if the input matrix is a jagged matrix.
92+
* Jagged matrix is a matrix where the number of columns in each row is not the same.
93+
*
94+
* @param matrix The input matrix
95+
* @return True if the input matrix is a jagged matrix, false otherwise
96+
*/
97+
private static boolean isJaggedMatrix(double[][] matrix) {
98+
int numColumns = matrix[0].length;
99+
for (double[] row : matrix) {
100+
if (row.length != numColumns) {
101+
return true;
102+
}
103+
}
104+
return false;
105+
}
106+
107+
/**
108+
* @brief The pivot row is the row in the matrix that is used to eliminate other rows and reduce the matrix to its row echelon form.
109+
* The pivot row is selected as the first row (from top to bottom) where the value in the current column (the pivot column) is not zero.
110+
* This row is then used to "eliminate" other rows, by subtracting multiples of the pivot row from them, so that all other entries in the pivot column become zero.
111+
* This process is repeated for each column, each time selecting a new pivot row, until the matrix is in row echelon form.
112+
* The number of pivot rows (rows with a leading entry, or pivot) then gives the rank of the matrix.
113+
*
114+
* @param matrix The input matrix
115+
* @param rowMarked An array indicating which rows have been marked
116+
* @param colIndex The column index
117+
* @return The pivot row index, or the number of rows if no suitable pivot row was found
118+
*/
119+
private static int findPivotRow(double[][] matrix, boolean[] rowMarked, int colIndex) {
120+
int numRows = matrix.length;
121+
for (int pivotRow = 0; pivotRow < numRows; ++pivotRow) {
122+
if (!rowMarked[pivotRow] && !isZero(matrix[pivotRow][colIndex])) {
123+
return pivotRow;
124+
}
125+
}
126+
return numRows;
127+
}
128+
129+
/**
130+
* @brief This method divides all values in the pivot row by the value in the given column.
131+
* This ensures that the pivot value itself will be 1, which simplifies further calculations.
132+
*
133+
* @param matrix The input matrix
134+
* @param pivotRow The pivot row index
135+
* @param colIndex The column index
136+
*/
137+
private static void normalizePivotRow(double[][] matrix, int pivotRow, int colIndex) {
138+
int numColumns = matrix[0].length;
139+
for (int nextCol = colIndex + 1; nextCol < numColumns; ++nextCol) {
140+
matrix[pivotRow][nextCol] /= matrix[pivotRow][colIndex];
141+
}
142+
}
143+
144+
/**
145+
* @brief This method subtracts multiples of the pivot row from all other rows,
146+
* so that all values in the given column of other rows will be zero.
147+
* This is a key step in reducing the matrix to row echelon form.
148+
*
149+
* @param matrix The input matrix
150+
* @param pivotRow The pivot row index
151+
* @param colIndex The column index
152+
*/
153+
private static void eliminateRows(double[][] matrix, int pivotRow, int colIndex) {
154+
int numRows = matrix.length;
155+
int numColumns = matrix[0].length;
156+
for (int otherRow = 0; otherRow < numRows; ++otherRow) {
157+
if (otherRow != pivotRow && !isZero(matrix[otherRow][colIndex])) {
158+
for (int col2 = colIndex + 1; col2 < numColumns; ++col2) {
159+
matrix[otherRow][col2] -= matrix[pivotRow][col2] * matrix[otherRow][colIndex];
160+
}
161+
}
162+
}
163+
}
164+
}

‎src/test/java/com/thealgorithms/maths/MatrixRankTest.java

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package com.thealgorithms.maths;
2+
3+
import static org.junit.jupiter.api.Assertions.assertEquals;
4+
import static org.junit.jupiter.api.Assertions.assertThrows;
5+
6+
import java.util.Arrays;
7+
import java.util.stream.Stream;
8+
import org.junit.jupiter.params.ParameterizedTest;
9+
import org.junit.jupiter.params.provider.Arguments;
10+
import org.junit.jupiter.params.provider.MethodSource;
11+
12+
class MatrixRankTest {
13+
14+
private static Stream<Arguments> validInputStream() {
15+
return Stream.of(Arguments.of(3, new double[][] {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}), Arguments.of(0, new double[][] {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}), Arguments.of(1, new double[][] {{1}}), Arguments.of(2, new double[][] {{1, 2}, {3, 4}}),
16+
Arguments.of(2, new double[][] {{3, -1, 2}, {-3, 1, 2}, {-6, 2, 4}}), Arguments.of(3, new double[][] {{2, 3, 0, 1}, {1, 0, 1, 2}, {-1, 1, 1, -2}, {1, 5, 3, -1}}), Arguments.of(1, new double[][] {{1, 2, 3}, {3, 6, 9}}),
17+
Arguments.of(2, new double[][] {{0.25, 0.5, 0.75, 2}, {1.5, 3, 4.5, 6}, {1, 2, 3, 4}}));
18+
}
19+
20+
private static Stream<Arguments> invalidInputStream() {
21+
return Stream.of(Arguments.of((Object) new double[][] {{1, 2}, {10}, {100, 200, 300}}), // jagged array
22+
Arguments.of((Object) new double[][] {}), // empty matrix
23+
Arguments.of((Object) new double[][] {{}, {}}), // empty row
24+
Arguments.of((Object) null), // null matrix
25+
Arguments.of((Object) new double[][] {{1, 2}, null}) // null row
26+
);
27+
}
28+
29+
@ParameterizedTest
30+
@MethodSource("validInputStream")
31+
void computeRankTests(int expectedRank, double[][] matrix) {
32+
int originalHashCode = Arrays.deepHashCode(matrix);
33+
int rank = MatrixRank.computeRank(matrix);
34+
int newHashCode = Arrays.deepHashCode(matrix);
35+
36+
assertEquals(expectedRank, rank);
37+
assertEquals(originalHashCode, newHashCode);
38+
}
39+
40+
@ParameterizedTest
41+
@MethodSource("invalidInputStream")
42+
void computeRankWithInvalidMatrix(double[][] matrix) {
43+
assertThrows(IllegalArgumentException.class, () -> MatrixRank.computeRank(matrix));
44+
}
45+
}

0 commit comments

Comments
 (0)