C 언어로 특이 행렬 판별하기 – 행렬식 계산 프로그램 구현

행렬이 mat[row][column] 형태로 주어졌을 때, 함수를 통해 해당 행렬이 특이 행렬(singular matrix)인지 아닌지를 판별하고 그 결과를 출력하는 것이 이 글의 목표입니다.

특이 행렬이란 행렬식(determinant)의 값이 0인 행렬을 말하며, 행렬식이 0이 아니라면 비특이 행렬(non-singular matrix)이라고 부릅니다.

따라서 행렬이 특이 행렬인지 여부를 판단하려면 먼저 행렬식을 계산해야 합니다. 3×3 행렬의 행렬식은 다음과 같이 구할 수 있습니다.

$$M1[3][3]\:=\:\begin{bmatrix}a & b & c \\d & e & f \\g & h & i \end{bmatrix}$$

|m1| = a(e·i − f·h) − b(d·i − f·g) + c(d·h − e·g)

즉, 첫 번째 행의 각 원소에 대해 소행렬을 곱한 뒤 부호를 교대로 바꾸어 더하는 소행렬 전개(cofactor expansion) 방식을 사용합니다.

예시

입력: mat[3][3] = { 4, 10, 1 },
          { 0, 2, 3 },
          { 1, 4, -3 }
출력: 행렬은 비특이 행렬(non-singular)

입력: mat[3][3] = { 0, 0, 0 },
          { 10, 20, 30 },
          { 1, 4, -3 }
출력: 행렬은 특이 행렬(singular)

두 번째 예시에서는 첫 번째 행 전체가 0이므로 나머지 값에 상관없이 행렬식이 반드시 0이 되어 특이 행렬로 판정됩니다.

알고리즘

시작
함수 cofactor(int matrix[N][N], int matrix2[N][N], int p, int q, int n)
{
    단계 1 -> i = 0, j = 0을 선언·초기화하고 row, col 선언
    단계 2 -> row = 0부터 row < n일 때까지 row++ 반복
        col = 0부터 col < n일 때까지 col++ 반복
            row != p && col != q 이면,
                matrix2[i][j++]에 matrix[row][col] 대입
                j == n - 1 이면,
                    j = 0으로 설정
                    i를 1 증가
            내부 반복 종료
        외부 반복 종료
}
함수 check_singular(int matrix[N][N], int n)
{
    단계 1 -> int D = 0 선언 및 초기화
    단계 2 -> n == 1 이면,
        matrix[0][0] 반환
    단계 3 -> matrix2[N][N], sign = 1 선언
    단계 4 -> f = 0부터 f < n일 때까지 f++ 반복
        cofactor(matrix, matrix2, 0, f, n) 호출
        D += sign * matrix[0][f] * check_singular(matrix2, n - 1)
        sign = -sign 대입
        반복 종료
    단계 5 -> D 반환
}
main()
{
    단계 1 -> matrix[N][N] 선언 및 초기화
    단계 2 -> check_singular(matrix, N)의 반환값이 0이 아니면,
        "행렬은 특이 행렬입니다" 출력
    단계 3 -> 그렇지 않으면,
        "행렬은 비특이 행렬입니다" 출력
종료

C 코드 구현

#include <stdio.h>
#define N 4

// 소행렬(cofactor)을 구하는 함수
int cofactor(int matrix[N][N], int matrix2[N][N], int p, int q, int n) {
    int i = 0, j = 0;
    int row, col;
    // 행렬의 각 원소를 순회
    for (row = 0; row < n; row++) {
        for (col = 0; col < n; col++) {
            // 주어진 행(p)과 열(q)에 속하지 않는
            // 원소만 임시 행렬에 복사
            if (row != p && col != q) {
                matrix2[i][j++] = matrix[row][col];
                // 한 행이 가득 차면 행 인덱스를 증가시키고
                // 열 인덱스는 0으로 초기화
                if (j == n - 1) {
                    j = 0;
                    i++;
                }
            }
        }
    }
    return 0;
}

/* matrix[][]가 특이 행렬인지 재귀적으로 검사하는 함수 */
int check_singular(int matrix[N][N], int n) {
    int D = 0; // 결과값 초기화
    // 기저 사례: 행렬에 원소가 하나만 남은 경우
    if (n == 1)
        return matrix[0][0];
    int matrix2[N][N]; // 소행렬 저장용 배열
    int sign = 1;      // 부호 배율 저장용 변수
    // 첫 번째 행의 각 원소에 대해 순회
    for (int f = 0; f < n; f++) {
        // matrix[0][f]의 소행렬 구하기
        cofactor(matrix, matrix2, 0, f, n);
        D += sign * matrix[0][f] * check_singular(matrix2, n - 1);
        // 항마다 부호를 교대로 변경하여 더함
        sign = -sign;
    }
    return D;
}

// 위 함수들을 테스트하는 드라이버 프로그램
int main() {
    int matrix[N][N] = { { 4, 10, 1 },
                         { 0, 2, 3 },
                         { 1, 4, -3 } };
    if (check_singular(matrix, N))
        printf("Matrix is Singular\n");
    else
        printf("Matrix is non-Singular\n");
    return 0;
}

참고: 매크로 N의 값은 실제 테스트할 행렬의 크기와 일치해야 합니다. 위 예제처럼 3×3 행렬을 사용한다면 #define N 3으로 설정하는 것이 안전합니다. N이 행렬 크기보다 크면 빈 행이 0으로 채워져 행렬식이 0으로 잘못 계산될 수 있습니다.

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Matrix is non-Singular

실제로 입력된 3×3 행렬의 행렬식을 손으로 계산해 보면 4×((2×(−3) − 3×4)) − 10×((0×(−3) − 3×1)) + 1×((0×4 − 2×1)) = −72 + 30 − 2 = −44로 0이 아니므로, 이 행렬은 비특이 행렬임을 확인할 수 있습니다.