이 글에서는 C++을 사용하여 주어진 행렬이 가역 행렬(invertible matrix), 즉 역행렬이 존재하는 행렬인지 확인하는 방법을 알아보겠습니다.
역행렬과 가역 조건
행렬 M의 역행렬 M⁻¹은 다음 공식으로 정의됩니다.
$$M^{-1}=\frac{adj(M)}{|M|}$$
여기서 adj(M)은 수반 행렬(adjugate), |M|은 행렬식(determinant)입니다. 공식에서 알 수 있듯이 행렬식이 0이 아닐 때만 역행렬을 구할 수 있습니다. 행렬식이 0이면 분모가 0이 되어 역행렬이 정의되지 않기 때문입니다.
따라서 행렬이 가역인지 판단하려면 행렬식이 0인지만 검사하면 됩니다.
행렬식 계산 원리
행렬식은 코팩터 전개(cofactor expansion)라는 재귀적 과정으로 계산할 수 있습니다. n×n 행렬의 경우 다음 단계를 따릅니다.
- 행렬 크기가 1×1이면 그 원소 값 자체가 행렬식입니다.
- 첫 번째 행의 각 원소에 대해, 해당 원소가 속한 행과 열을 제거한 소행렬(submatrix)을 만듭니다.
- 각 소행렬의 행렬식을 재귀적으로 계산합니다.
- 부호(+, −)를 교대로 적용하여 모두 더하면 최종 행렬식이 됩니다.
C++ 구현 예제
#include <iostream>
#define N 4
using namespace std;
// (p, q) 위치의 행과 열을 제거한 소행렬(코팩터) 생성
void findCoFactor(int mat[N][N], int mat2[N][N], int p, int q, int n) {
int i = 0, j = 0;
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
if (row != p && col != q) {
mat2[i][j++] = mat[row][col];
if (j == n - 1) {
j = 0;
i++;
}
}
}
}
}
// 재귀적으로 행렬식 계산
int getDeterminant(int mat[N][N], int n) {
int determinant = 0;
if (n == 1)
return mat[0][0];
int temp[N][N];
int sign = 1;
for (int f = 0; f < n; f++) {
findCoFactor(mat, temp, 0, f, n);
determinant += sign * mat[0][f] * getDeterminant(temp, n - 1);
sign = -sign;
}
return determinant;
}
// 행렬식이 0이 아니면 가역 행렬
bool isMatrixInvertible(int mat[N][N], int n) {
return getDeterminant(mat, N) != 0;
}
int main() {
int matrix[N][N] = {
{ 1, 0, 2, -1 },
{ 3, 0, 0, 5 },
{ 2, 1, 4, -3 },
{ 1, 0, 5, 0 }
};
if (isMatrixInvertible(matrix, N))
cout << "이 행렬은 가역입니다(역행렬 존재)";
else
cout << "이 행렬은 가역이 아닙니다(역행렬 없음)";
}
실행 결과
이 행렬은 가역입니다(역행렬 존재)
정리 및 참고 사항
위 코드는 4×4 행렬 기준으로 작성되었지만, 매크로 상수 N의 값을 변경하면 다른 크기의 정방 행렬에도 그대로 적용할 수 있습니다. 핵심 로직은 세 부분으로 나뉩니다.
findCoFactor(): 지정된 행과 열을 제외한 소행렬을 생성합니다.getDeterminant(): 코팩터 전개를 통해 행렬식을 재귀적으로 계산합니다.isMatrixInvertible(): 행렬식이 0이 아닌지 검사하여 가역 여부를 반환합니다.
다만 이 재귀적 방식은 시간 복잡도가 O(n!)으로 매우 높으므로, 차원이 큰 행렬에는 LU 분해나 가우스 소거법처럼 O(n³)에 처리 가능한 알고리즘을 사용하는 것이 효율적입니다.