Gauss 방법을 이용한 행렬식 계산¶
문제: 크기가 $N \times N$인 행렬 $A$가 주어집니다. 이 행렬의 행렬식을 계산하십시오.
알고리즘¶
연립 일차방정식을 푸는 가우스 방법의 아이디어를 사용합니다.
연립 일차방정식을 풀 때와 같은 단계를 수행하되, 현재 행을 $a_{ij}$로 나누는 과정만 제외합니다. 이 연산들은 행렬식의 절댓값을 바꾸지 않습니다. 그러나 행렬의 두 행을 교환하면 행렬식의 부호가 바뀔 수 있습니다.
행렬에 Gauss 방법을 적용하면 대각 행렬을 얻게 되며, 그 행렬식은 대각선 위 원소들의 곱과 같습니다. 앞서 언급했듯이, 부호는 교환한 행의 수로 결정할 수 있습니다(홀수이면 행렬식의 부호를 반대로 바꿔야 합니다). 따라서 Gauss 알고리즘을 사용하면 행렬의 행렬식을 $O(N^3)$의 복잡도로 계산할 수 있습니다.
어느 시점에서든 현재 열에서 0이 아닌 칸을 찾지 못하면 알고리즘을 멈추고 0을 반환해야 한다는 점에 유의하십시오.
구현¶
const double EPS = 1E-9;
int n;
vector < vector<double> > a (n, vector<double> (n));
double det = 1;
for (int i=0; i<n; ++i) {
int k = i;
for (int j=i+1; j<n; ++j)
if (abs (a[j][i]) > abs (a[k][i]))
k = j;
if (abs (a[k][i]) < EPS) {
det = 0;
break;
}
swap (a[i], a[k]);
if (i != k)
det = -det;
det *= a[i][i];
for (int j=i+1; j<n; ++j)
a[i][j] /= a[i][i];
for (int j=0; j<n; ++j)
if (j != i && abs (a[j][i]) > EPS)
for (int k=i+1; k<n; ++k)
a[j][k] -= a[i][k] * a[j][i];
}
cout << det;