[ algorithm] 라플라스 전개

들어가며

라플라스 전개(Laplace Expansion) 또는 여인수 전개(Cofactor Expansion)는 행렬식(determinant)을 계산하는 가장 기본적이고 중요한 방법입니다. 프랑스 수학자 피에르 시몽 라플라스(Pierre-Simon Laplace)의 이름을 따서 명명되었으며, 선형대수학의 핵심 개념 중 하나입니다.

1. 행렬식(Determinant)이란?

1.1 행렬식의 기본 개념

행렬식은 정사각 행렬에 대해 정의되는 스칼라 값으로, det(A) 또는 |A|로 표기합니다.

2×2 행렬의 행렬식:

A = [a b]

[c d]

det(A) = ad - bc

기하학적 의미:

• 2차원: 행렬의 열벡터가 이루는 평행사변형의 넓이(부호 포함)
• 3차원: 행렬의 열벡터가 이루는 평행육면체의 부피(부호 포함)
• n차원: n차원 공간에서의 "부피"

행렬식의 의미:

• det(A) = 0: 행렬이 특이(singular), 역행렬이 존재하지 않음
• det(A) ≠ 0: 행렬이 비특이(non-singular), 역행렬이 존재

• det(A)	: 선형 변환에 의한 부피의 확대/축소 비율

2. 소행렬식과 여인수

2.1 소행렬식(Minor)

정의: n×n 행렬 A의 (i,j) 소행렬식 M_ij는 A에서 i번째 행과 j번째 열을 제거한 (n-1)×(n-1) 행렬의 행렬식입니다.

예제:

A = [1 2 3]

[4 5 6]

[7 8 9]

M_11 (1행 1열을 제거):

[5 6]

[8 9]

M_11 = 5×9 - 6×8 = 45 - 48 = -3

M_12 (1행 2열을 제거):

[4 6]

[7 9]

M_12 = 4×9 - 6×7 = 36 - 42 = -6

2.2 여인수(Cofactor)

정의: (i,j) 여인수 C_ij는 소행렬식에 부호를 붙인 것입니다:

C_ij = (-1)^(i+j) × M_ij

부호 패턴 (체스판 패턴):

n=3일 때:

[+ - +]

[- + -]

[+ - +]

n=4일 때:

[+ - + -]

[- + - +]

[+ - + -]

[- + - +]

여인수 계산 예제:

C_11 = (-1)^(1+1) × M_11 = (+1) × (-3) = -3

C_12 = (-1)^(1+2) × M_12 = (-1) × (-6) = 6

3. 라플라스 전개의 정의

3.1 행에 대한 전개

n×n 행렬 A의 행렬식은 임의의 행 i에 대해 다음과 같이 전개할 수 있습니다:

det(A) = Σ(j=1 to n) a_ij × C_ij

= a_i1×C_i1 + a_i2×C_i2 + ... + a_in×C_in

첫 번째 행으로 전개 (가장 일반적):

det(A) = a_11×C_11 + a_12×C_12 + ... + a_1n×C_1n

3.2 열에 대한 전개

마찬가지로 임의의 열 j에 대해서도 전개 가능합니다:

det(A) = Σ(i=1 to n) a_ij × C_ij

= a_1j×C_1j + a_2j×C_2j + ... + a_nj×C_nj

3.3 중요한 성질

어느 행/열로 전개해도 결과는 동일합니다. 이는 라플라스 전개의 가장 중요한 성질로, 계산을 효율적으로 할 수 있게 해줍니다. 일반적으로 0이 많은 행이나 열을 선택하면 계산이 간단해집니다.

4. 라플라스 전개 계산 예제

4.1 3×3 행렬 예제

A = [2 1 3]

[0 4 5]

[1 -2 6]

첫 번째 행으로 전개:

det(A) = a_11×C_11 + a_12×C_12 + a_13×C_13

= 2×C_11 + 1×C_12 + 3×C_13

C_11 계산:

M_11 = |4 5| = 4×6 - 5×(-2) = 24 + 10 = 34

-2 6

C_11 = (-1)^(1+1) × 34 = 34

C_12 계산:

M_12 = |0 5| = 0×6 - 5×1 = -5

1 6

C_12 = (-1)^(1+2) × (-5) = 5

C_13 계산:

M_13 = |0 4| = 0×(-2) - 4×1 = -4

1 -2

C_13 = (-1)^(1+3) × (-4) = -4

최종 계산:

det(A) = 2×34 + 1×5 + 3×(-4)

= 68 + 5 - 12

= 61

4.2 두 번째 행으로 전개 (0이 있어서 더 효율적)

det(A) = a_21×C_21 + a_22×C_22 + a_23×C_23

= 0×C_21 + 4×C_22 + 5×C_23

= 4×C_22 + 5×C_23

첫 번째 항이 0이므로 계산이 생략됩니다!

C_22 계산:

M_22 = |2 3| = 2×6 - 3×1 = 12 - 3 = 9

1 6

C_22 = (-1)^(2+2) × 9 = 9

C_23 계산:

M_23 = |2 1| = 2×(-2) - 1×1 = -4 - 1 = -5

1 -2

C_23 = (-1)^(2+3) × (-5) = 5

최종 계산:

det(A) = 4×9 + 5×5 = 36 + 25 = 61

동일한 결과가 나왔습니다!

4.3 4×4 행렬 예제

A = [1 2 0 3]

[0 4 5 0]

[2 0 3 1]

[0 1 0 2]

두 번째 행으로 전개 (0이 2개):

det(A) = 0×C_21 + 4×C_22 + 5×C_23 + 0×C_24

= 4×C_22 + 5×C_23

C_22 계산 (3×3 행렬식):

M_22 = |1 0 3|

2 3 1
0 0 2

세 번째 행으로 전개 (0이 2개):

M_22 = 0×... + 0×... + 2×|1 0|

2 3

= 2 × (1×3 - 0×2) = 2 × 3 = 6

C_22 = (-1)^(2+2) × 6 = 6

C_23 계산 (3×3 행렬식):

M_23 = |1 2 3|

2 0 1
0 1 2

첫 번째 열로 전개:

M_23 = 1×|0 1| - 2×|2 3| + 0×...

1 2		1 2

= 1×(0-1) - 2×(4-3)

= -1 - 2 = -3

C_23 = (-1)^(2+3) × (-3) = 3

최종 계산:

det(A) = 4×6 + 5×3 = 24 + 15 = 39

5. 라플라스 전개 실전 팁

5.1 효율적인 전개 방법

1. 0이 많은 행/열 선택

A = [1 2 3 4]

[0 0 5 0] ← 이 행으로 전개!

[6 7 8 9]

[0 1 0 2]

두 번째 행은 0이 3개이므로, 이 행으로 전개하면 계산량이 크게 줄어듭니다.

2. 재귀적 사고

큰 행렬의 행렬식 계산:

• n×n 행렬 → (n-1)×(n-1) 행렬들로 분해
• (n-1)×(n-1) → (n-2)×(n-2) ...
• 최종적으로 2×2 또는 3×3까지 도달

3. 삼각 행렬의 경우

상삼각 또는 하삼각 행렬의 행렬식은 대각 원소의 곱:

A = [2 3 1] det(A) = 2 × 4 × 5 = 40

[0 4 6]

[0 0 5]

5.2 특수한 경우들

1. 대각 행렬:

det(diag(d_1, d_2, ..., d_n)) = d_1 × d_2 × ... × d_n

2. 블록 삼각 행렬:

A = [B C] det(A) = det(B) × det(D)

[0 D]

3. 전치 행렬:

det(A^T) = det(A)

4. 곱셈:

det(AB) = det(A) × det(B)

5. 스칼라 곱:

det(kA) = k^n × det(A) (n×n 행렬)

6. 라플라스 전개의 응용

6.1 역행렬 계산

수반 행렬(Adjugate Matrix)을 이용한 역행렬:

A^(-1) = (1/det(A)) × adj(A)

여기서 adj(A)는 여인수 행렬의 전치 행렬입니다.

예제:

A = [1 2]

[3 4]

det(A) = 4 - 6 = -2

여인수 행렬:

C = [ 4 -3]

[-2 1]

adj(A) = C^T = [ 4 -2]

[-3 1]

A^(-1) = (1/-2) × [ 4 -2] = [-2 1]

[-3 1][3/2 -1/2]

6.2 크래머의 공식(Cramer's Rule)

연립 방정식 Ax = b의 해:

x_i = det(A_i) / det(A)

여기서 A_i는 A의 i번째 열을 b로 치환한 행렬입니다.

예제:

2x + y = 5

x + 3y = 8

A = [2 1] b = [5]

[1 3][8]

det(A) = 6 - 1 = 5

A_1 = [5 1] det(A_1) = 15 - 8 = 7

[8 3]

A_2 = [2 5] det(A_2) = 16 - 5 = 11

[1 8]

x = 7/5 = 1.4

y = 11/5 = 2.2

6.3 면적과 부피 계산

삼각형의 넓이:

세 점 (x_1, y_1), (x_2, y_2), (x_3, y_3)로 이루어진 삼각형의 넓이:

넓이 = (1/2) |det([x_1 y_1 1])|

[x_2 y_2 1]
[x_3 y_3 1]

사면체의 부피:

네 점으로 이루어진 사면체의 부피:

부피 = (1/6) |det([x_1 y_1 z_1 1])|

[x_2 y_2 z_2 1]
[x_3 y_3 z_3 1]
[x_4 y_4 z_4 1]

6.4 선형 독립성 판별

벡터 v_1, v_2, ..., v_n이 선형 독립인지 확인:

det([v_1 v_2 ... v_n]) ≠ 0 ⟺ 선형 독립

7. 계산 복잡도와 한계

7.1 시간 복잡도

라플라스 전개의 시간 복잡도: O(n!)

이는 매우 비효율적입니다!

n×n 행렬의 경우:

• n=3: 6번의 2×2 행렬식 계산
• n=4: 24번의 3×3 행렬식 계산
• n=5: 120번의 4×4 행렬식 계산
• n=10: 3,628,800번의 9×9 행렬식 계산!

7.2 더 효율적인 방법들

1. LU 분해: O(n³)

A = LU (L: 하삼각, U: 상삼각)

det(A) = det(L) × det(U) = (대각원소의 곱)

2. 가우스 소거법: O(n³)

3. QR 분해: O(n³)

실용적 사용:

• 작은 행렬 (n ≤ 4): 라플라스 전개
• 큰 행렬 (n > 4): LU 분해 또는 가우스 소거법

8. 프로그래밍 구현

8.1 Python 구현

def laplace_expansion(matrix):
    """
    라플라스 전개를 이용한 행렬식 계산
    """
    n = len(matrix)
    
    # 기저 사례: 1x1 행렬
    if n == 1:
        return matrix[0][0]
    
    # 기저 사례: 2x2 행렬
    if n == 2:
        return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0]
    
    # 재귀적 계산
    determinant = 0
    
    # 첫 번째 행으로 전개
    for j in range(n):
        # 소행렬 생성 (첫 번째 행과 j번째 열 제거)
        minor = []
        for i in range(1, n):
            row = []
            for k in range(n):
                if k != j:
                    row.append(matrix[i][k])
            minor.append(row)
        
        # 여인수 계산
        cofactor = ((-1) ** j) * matrix[0][j]
        
        # 재귀적으로 소행렬식 계산
        determinant += cofactor * laplace_expansion(minor)
    
    return determinant

# 테스트
A = [[2, 1, 3],
     [0, 4, 5],
     [1, -2, 6]]

print(f"det(A) = {laplace_expansion(A)}")  # 61

8.2 최적화된 버전 (0 활용)

def optimized_laplace(matrix):
    """
    0이 가장 많은 행/열을 선택하여 전개
    """
    n = len(matrix)
    
    if n == 1:
        return matrix[0][0]
    
    if n == 2:
        return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0]
    
    # 0이 가장 많은 행 찾기
    max_zeros = -1
    best_row = 0
    for i in range(n):
        zeros = sum(1 for x in matrix[i] if x == 0)
        if zeros > max_zeros:
            max_zeros = zeros
            best_row = i
    
    # 선택한 행으로 전개
    determinant = 0
    for j in range(n):
        if matrix[best_row][j] == 0:
            continue  # 0인 항은 건너뛰기
        
        # 소행렬 생성
        minor = []
        for i in range(n):
            if i == best_row:
                continue
            row = []
            for k in range(n):
                if k != j:
                    row.append(matrix[i][k])
            minor.append(row)
        
        cofactor = ((-1) ** (best_row + j)) * matrix[best_row][j]
        determinant += cofactor * optimized_laplace(minor)
    
    return determinant

8.3 NumPy 활용

import numpy as np

# 간단한 방법
A = np.array([[2, 1, 3],
              [0, 4, 5],
              [1, -2, 6]])

det_A = np.linalg.det(A)
print(f"det(A) = {det_A}")  # 61.0

9. 연습 문제

문제 1

다음 행렬의 행렬식을 라플라스 전개로 계산하세요:

A = [3 0 2]

[1 4 0]

[0 5 1]

힌트: 0이 가장 많은 행/열을 선택하세요.

문제 2

매개변수 λ를 포함한 행렬의 행렬식을 구하세요:

A = [λ-2 1 0]

[0 λ-3 1]

[0 0 λ-4]

문제 3

다음 4×4 행렬의 행렬식을 계산하세요:

A = [1 0 2 0]

[0 3 0 4]

[5 0 6 0]

[0 7 0 8]

10. 마무리

라플라스 전개는 행렬식을 계산하는 기본적이면서도 강력한 방법입니다. 비록 큰 행렬에서는 계산 복잡도가 높지만, 다음과 같은 장점이 있습니다:

장점:

• 수학적으로 명확하고 이해하기 쉬움
• 작은 행렬에서는 매우 효과적
• 여인수와 소행렬식의 개념을 이해하는 데 필수적
• 역행렬 계산, 크래머의 공식 등 다양한 응용

실전 활용:

• 이론적 증명과 수학적 이해를 위해 사용
• 3×3 이하의 작은 행렬 계산
• 0이 많은 희소 행렬
• 교육 목적

큰 행렬의 경우 LU 분해나 가우스 소거법 같은 더 효율적인 알고리즘을 사용하는 것이 좋지만, 라플라스 전개는 선형대수학의 기초를 이해하는 데 필수적인 개념입니다.