행렬이 가역(invertible)인지, 즉 역행렬이 존재하는지 판단하는 가장 기본적인 방법은 행렬식(determinant)을 계산하는 것입니다. 행렬식이 0이 아니면 해당 행렬은 가역이며, 행렬식이 0이면 역행렬이 존재하지 않습니다.
예를 들어 다음과 같은 경우를 살펴보겠습니다.
주어진 행렬:
4 2 1
2 1 1
9 3 2
위 행렬의 행렬식: 3
따라서 이 행렬은 가역입니다.
C++ 가역성 판별 프로그램
아래 프로그램은 사용자로부터 행렬의 크기와 원소를 입력받아 행렬식을 재귀적으로 계산한 뒤, 그 값이 0인지 아닌지에 따라 행렬의 가역 여부를 출력합니다.
#include<iostream>
#include<math.h>
using namespace std;
int determinant( int matrix[10][10], int n) {
int det = 0;
int submatrix[10][10];
if (n == 2)
return ((matrix[0][0] * matrix[1][1]) - (matrix[1][0] * matrix[0][1]));
else {
for (int x = 0; x < n; x++) {
int subi = 0;
for (int i = 1; i < n; i++) {
int subj = 0;
for (int j = 0; j < n; j++) {
if (j == x)
continue;
submatrix[subi][subj] = matrix[i][j];
subj++;
}
subi++;
}
det = det + (pow(-1, x) * matrix[0][x] * determinant( submatrix, n - 1 ));
}
}
return det;
}
int main() {
int n, d, i, j;
int matrix[10][10];
cout << "Enter the size of the matrix:\n";
cin >> n;
cout << "Enter the elements of the matrix:\n";
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
cin >> matrix[i][j];
cout<<"The entered matrix is:"<<endl;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
cout << matrix[i][j] <<" ";
cout<<endl;
}
d = determinant(matrix, n);
cout<<"Determinant of the matrix is "<< d <<endl;
if( d == 0 )
cout<<"This matrix is not invertible as the determinant is zero";
else
cout<<"This matrix is invertible as the determinant is not zero";
return 0;
}
실행 결과
Enter the size of the matrix: 3
Enter the elements of the matrix:
1 2 3
2 1 2
1 1 4
The entered matrix is:
1 2 3
2 1 2
1 1 4
Determinant of the matrix is -7
This matrix is invertible as the determinant is not zero
코드 동작 원리
main() 함수 — 입력 및 판별
main() 함수에서는 먼저 행렬의 크기와 각 원소를 입력받고, 입력된 행렬을 화면에 출력합니다. 이후 determinant() 함수를 호출하여 행렬식을 구하고 그 결과를 변수 d에 저장합니다. 마지막으로 d가 0이면 "행렬식이 0이므로 가역이 아니다", 0이 아니면 "행렬식이 0이 아니므로 가역이다"라는 메시지를 출력합니다.
d = determinant(matrix, n);
cout<<"Determinant of the matrix is "<< d <<endl;
if( d == 0 )
cout<<"This matrix is not invertible as the determinant is zero";
else
cout<<"This matrix is invertible as the determinant is not zero";
determinant() 함수 — 2×2 행렬의 직접 계산
determinant() 함수 내부에서는 먼저 행렬의 크기가 2인지 확인합니다. 2×2 행렬이라면 별도의 재귀 호출 없이 공식(ad − bc)으로 행렬식을 바로 계산하여 반환합니다.
if (n == 2)
return ((matrix[0][0] * matrix[1][1]) - (matrix[1][0] * matrix[0][1]));
determinant() 함수 — 재귀적 여인수 전개
행렬의 크기가 2가 아니라면, 행렬식은 여인수 전개(cofactor expansion)를 통해 재귀적으로 계산됩니다. 세 개의 중첩 for 루프(x, i, j)를 사용하여 첫 번째 행의 각 원소에 대응하는 소행렬(submatrix)을 만들고, determinant() 함수를 재귀적으로 호출해 소행렬의 행렬식을 구한 뒤 부호와 원소 값을 곱하여 누적합니다.
for (int x = 0; x < n; x++) {
int subi = 0;
for (int i = 1; i < n; i++) {
int subj = 0;
for (int j = 0; j < n; j++) {
if (j == x)
continue;
submatrix[subi][subj] = matrix[i][j];
subj++;
}
subi++;
}
det = det + (pow(-1, x) * matrix[0][x] * determinant( submatrix, n - 1 ));
}이처럼 재귀 호출을 반복하면서 행렬의 크기를 하나씩 줄여가며 계산하기 때문에, 이 프로그램은 임의의 n×n 정방 행렬에 대해서도 행렬식을 구하고 가역 여부를 판별할 수 있습니다.