Матрицын рангийг олох¶
Матрицын ранг гэдэг нь матрицын шугаман хамааралгүй мөр/баганын хамгийн их тоо юм. Ранг нь зөвхөн квадрат матрицын хувьд тодорхойлогддоггүй.
Матрицын рангийг мөн матриц дахь дурын тэг биш минорын хамгийн их эрэмбэ гэж тодорхойлж болно.
Матриц тэгш өнцөгт бөгөөд $N \times M$ хэмжээтэй байг. Хэрэв матриц квадрат бөгөөд түүний тодорхойлогч тэг биш бол ранг нь $N$ ($=M$) болохыг анхаарна уу; эс бөгөөс энэ нь бага байна. Ерөнхийдөө матрицын ранг $\min (N, M)$-ээс хэтрэхгүй.
Алгоритм¶
Та Гауссын аргаар рангийг олж болно. Бид системийг бодох буюу түүний тодорхойлогчийг олохтой ижил үйлдлүүдийг гүйцэтгэнэ. Гэвч хэрэв ямар нэг алхамд $i$ дугаар баганад аль хэдийн сонгоогүй мөрүүдийн дунд тэг биш утгатай мөр байхгүй бол бид энэ алхамыг алгасна. Эс бөгөөс хэрэв бид $i$ дугаар алхамд $i$ дугаар баганад тэг биш элементтэй мөр олсон бол энэ мөрийг сонгосон гэж тэмдэглэж, рангийг нэгээр нэмэгдүүлээд (эхэндээ ранг $0$-тэй тэнцүү тавигдана), энэ мөрийг бусдаас нь хасах ердийн үйлдлүүдийг гүйцэтгэнэ.
Complexity¶
Энэ алгоритм $\mathcal{O}(n^3)$-д ажиллана.
Implementation¶
const double EPS = 1E-9;
int compute_rank(vector<vector<double>> A) {
int n = A.size();
int m = A[0].size();
int rank = 0;
vector<bool> row_selected(n, false);
for (int i = 0; i < m; ++i) {
int j;
for (j = 0; j < n; ++j) {
if (!row_selected[j] && abs(A[j][i]) > EPS)
break;
}
if (j != n) {
++rank;
row_selected[j] = true;
for (int p = i + 1; p < m; ++p)
A[j][p] /= A[j][i];
for (int k = 0; k < n; ++k) {
if (k != j && abs(A[k][i]) > EPS) {
for (int p = i + 1; p < m; ++p)
A[k][p] -= A[j][p] * A[k][i];
}
}
}
}
return rank;
}