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