행렬의 랭크 구하기¶
행렬의 랭크는 행렬에서 선형 독립인 행/열의 최대 개수입니다. 랭크는 정사각 행렬에 대해서만 정의되는 것이 아닙니다.
행렬의 랭크는 행렬에서 0이 아닌 소행렬식의 최대 차수로 정의할 수도 있습니다.
행렬이 직사각형이고 크기가 $N \times M$이라고 합시다. 행렬이 정사각 행렬이고 행렬식이 0이 아니면 랭크는 $N$ ($=M$)이고, 그렇지 않으면 랭크는 이보다 작다는 점에 유의하십시오. 일반적으로 행렬의 랭크는 $\min (N, M)$을 넘지 않습니다.
알고리즘¶
가우스 소거법을 사용하여 랭크를 구할 수 있습니다. 연립방정식을 풀거나 행렬식을 구할 때와 같은 연산을 수행합니다. 하지만 어떤 단계에서 아직 선택하지 않은 행들 중에 $i$번째 열의 원소가 0이 아닌 행이 없으면 그 단계를 건너뜁니다. 그렇지 않고 $i$번째 단계에서 $i$번째 열의 원소가 0이 아닌 행을 찾았다면, 이 행을 선택된 행으로 표시하고 랭크를 1 증가시킨 다음(랭크의 초깃값은 $0$입니다), 나머지 행에서 이 행을 빼는 일반적인 연산을 수행합니다.
복잡도¶
이 알고리즘은 $\mathcal{O}(n^3)$ 시간에 동작합니다.
구현¶
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;
}