27.30 행렬식의 재귀적 전개(Cofactor Expansion)와 성질

1. 소행렬과 여인자의 정의

$n \times n$ 행렬 $\mathbf{A}$ 에서 $i$ 행과 $j$ 열을 제거하여 얻은 $(n-1) \times (n-1)$ 부분 행렬을 $\mathbf{M}_{ij}$ 로 표기하고, 이 부분 행렬의 행렬식 $\det(\mathbf{M}_{ij})$ 를 $(i,j)$ 소행렬식(minor)이라 한다.

$(i,j)$ 여인자(cofactor) $C_{ij}$ 는 소행렬식에 부호 인자를 곱한 것이다.

$C_{ij} = (-1)^{i+j} \det(\mathbf{M}_{ij})$

부호 인자 $(-1)^{i+j}$ 는 체커보드 패턴을 따른다.

$\begin{pmatrix} + & - & + & \cdots \\ - & + & - & \cdots \\ + & - & + & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix}$

예를 들어, $3 \times 3$ 행렬 $\mathbf{A}$ 에서 $C_{12} = (-1)^{1+2}\det(\mathbf{M}_{12}) = -\det\begin{pmatrix} a_{21} & a_{23} \\ a_{31} & a_{33} \end{pmatrix}$ 이다.

2. 여인자 전개(라플라스 전개)

행렬식의 여인자 전개(cofactor expansion), 또는 라플라스 전개(Laplace expansion)는 $n \times n$ 행렬의 행렬식을 $(n-1) \times (n-1)$ 행렬식들의 선형 결합으로 표현하는 재귀적 공식이다.

$i$ 번째 행에 대한 전개:

$\det(\mathbf{A}) = \sum_{j=1}^{n} a_{ij} C_{ij} = \sum_{j=1}^{n} (-1)^{i+j} a_{ij} \det(\mathbf{M}_{ij})$

$j$ 번째 열에 대한 전개:

$\det(\mathbf{A}) = \sum_{i=1}^{n} a_{ij} C_{ij} = \sum_{i=1}^{n} (-1)^{i+j} a_{ij} \det(\mathbf{M}_{ij})$

어떤 행 또는 열을 선택하더라도 동일한 결과를 준다. 실용적으로는 0 원소가 가장 많은 행 또는 열을 선택하면 계산량을 줄일 수 있다.

$3 \times 3$ 행렬의 첫 번째 행에 대한 전개를 구체적으로 쓰면 다음과 같다.

$\det\begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix} = a_{11}\det\begin{pmatrix} a_{22} & a_{23} \\ a_{32} & a_{33} \end{pmatrix} - a_{12}\det\begin{pmatrix} a_{21} & a_{23} \\ a_{31} & a_{33} \end{pmatrix} + a_{13}\det\begin{pmatrix} a_{21} & a_{22} \\ a_{31} & a_{32} \end{pmatrix}$

이를 전개하면 $a_{11}(a_{22}a_{33} - a_{23}a_{32}) - a_{12}(a_{21}a_{33} - a_{23}a_{31}) + a_{13}(a_{21}a_{32} - a_{22}a_{31})$ 이 되어, 순열 공식에 의한 결과와 일치한다.

3. 재귀적 구조와 계산 복잡도

여인자 전개는 본질적으로 재귀적 알고리즘이다. $n \times n$ 행렬의 행렬식을 $n$ 개의 $(n-1) \times (n-1)$ 행렬식으로 분해하고, 각 $(n-1) \times (n-1)$ 행렬식을 다시 $(n-2) \times (n-2)$ 행렬식으로 분해하는 과정을 반복한다. 기저 사례(base case)는 $1 \times 1$ 행렬로서 $\det(a) = a$ 이다.

이 재귀의 시간 복잡도를 $T(n)$ 으로 놓으면 점화식은 다음과 같다.

$T(n) = n \cdot T(n-1) + O(n)$

이로부터 $T(n) = O(n!)$ 이 도출된다. $n = 20$ 이면 $20! \approx 2.4 \times 10^{18}$ 으로, 현대 컴퓨터로도 계산 불가능한 규모이다. 따라서 여인자 전개는 이론적 도구로서의 가치는 높지만, 수치 계산에는 부적합하다. 실제 행렬식 계산에는 $O(n^3)$ 복잡도의 가우스 소거법 기반 방법이 사용된다.

4. 여인자 전개의 확장 성질

여인자 전개와 관련된 중요한 정리가 있다.

동일 행(열)에 대한 전개: 이미 설명한 대로, $\sum_{j=1}^{n} a_{ij}C_{ij} = \det(\mathbf{A})$ 이다.

다른 행(열)에 대한 전개: $i \neq k$ 이면, $\sum_{j=1}^{n} a_{ij}C_{kj} = 0$ 이다. 이는 $\mathbf{A}$ 의 $k$ 행을 $i$ 행과 같은 값으로 대체한 행렬의 행렬식을 계산하는 것과 동일하며, 두 행이 동일한 행렬의 행렬식은 0이기 때문이다.

이 두 결과를 통합하면 다음과 같이 쓸 수 있다.

$\sum_{j=1}^{n} a_{ij}C_{kj} = \delta_{ik}\det(\mathbf{A})$

행렬 형태로 표현하면 $\mathbf{A} \cdot \text{adj}(\mathbf{A}) = \det(\mathbf{A})\mathbf{I}$ 이다. 여기서 $\text{adj}(\mathbf{A})$ 는 여인자 행렬의 전치, 즉 수반 행렬(adjugate matrix)이다. $(\text{adj}(\mathbf{A}))_{ij} = C_{ji}$ 이다. $\det(\mathbf{A}) \neq 0$ 이면 양변을 $\det(\mathbf{A})$ 로 나누어 역행렬 공식 $\mathbf{A}^{-1} = \frac{1}{\det(\mathbf{A})}\text{adj}(\mathbf{A})$ 를 얻는다.

5. 행렬식의 추가 성질

블록 삼각 행렬의 행렬식: 블록 상삼각 또는 하삼각 구조의 행렬에서,

$\det\begin{pmatrix} \mathbf{A} & \mathbf{B} \\ \mathbf{O} & \mathbf{D} \end{pmatrix} = \det(\mathbf{A}) \cdot \det(\mathbf{D})$

이 성질은 블록 대각 행렬에도 적용되어, $\det(\text{diag}(\mathbf{A}_1, \ldots, \mathbf{A}_k)) = \prod_{i=1}^{k}\det(\mathbf{A}_i)$ 이다.

행렬식과 고유값: $n \times n$ 행렬 $\mathbf{A}$ 의 고유값이 $\lambda_1, \ldots, \lambda_n$ 이면 (중복도 포함),

$\det(\mathbf{A}) = \prod_{i=1}^{n} \lambda_i$

이는 특성 다항식 $\det(\mathbf{A} - \lambda\mathbf{I}) = \prod_{i=1}^{n}(\lambda_i - \lambda)$ 에서 $\lambda = 0$ 을 대입하면 얻어진다.

행렬식과 트레이스: 트레이스와 행렬식은 특성 다항식의 계수로서 연결된다. $\text{tr}(\mathbf{A}) = \sum_{i=1}^{n}\lambda_i$ 이고 $\det(\mathbf{A}) = \prod_{i=1}^{n}\lambda_i$ 이다.

크라메르 공칙(Cramer’s Rule): 연립방정식 $\mathbf{A}\mathbf{x} = \mathbf{b}$ 에서 $\det(\mathbf{A}) \neq 0$ 이면, 해의 $i$ 번째 성분은 다음과 같다.

$x_i = \frac{\det(\mathbf{A}_i)}{\det(\mathbf{A})}$

여기서 $\mathbf{A}_i$ 는 $\mathbf{A}$ 의 $i$ 번째 열을 $\mathbf{b}$ 로 대체한 행렬이다. 크라메르 공칙은 이론적으로 중요하지만, $n+1$ 번의 행렬식 계산이 필요하므로 계산 효율성 면에서 가우스 소거법에 비해 불리하다.

6. 행렬식 관련 항등식

코시-비네 공식(Cauchy-Binet Formula): $\mathbf{A} \in \mathbb{R}^{m \times n}$ , $\mathbf{B} \in \mathbb{R}^{n \times m}$ 에서 $m \leq n$ 이면,

$\det(\mathbf{A}\mathbf{B}) = \sum_{S} \det(\mathbf{A}_S)\det(\mathbf{B}_S)$

여기서 합은 $\{1, \ldots, n\}$ 에서 크기 $m$ 인 모든 부분집합 $S$ 에 대하여 이루어지고, $\mathbf{A}_S$ 는 $S$ 에 해당하는 열만 선택한 부분 행렬, $\mathbf{B}_S$ 는 $S$ 에 해당하는 행만 선택한 부분 행렬이다. $m = n$ 이면 $\det(\mathbf{A}\mathbf{B}) = \det(\mathbf{A})\det(\mathbf{B})$ 로 환원된다.

행렬식의 미분(야코비 공식): 행렬 $\mathbf{A}(t)$ 가 매개변수 $t$ 에 대해 미분 가능할 때,

$\frac{d}{dt}\det(\mathbf{A}(t)) = \det(\mathbf{A}(t)) \cdot \text{tr}\left(\mathbf{A}(t)^{-1}\frac{d\mathbf{A}(t)}{dt}\right)$

이 공식은 $\mathbf{A}$ 가 가역인 경우에 성립하며, 로그 행렬식의 미분 $\frac{d}{dt}\log\det(\mathbf{A}) = \text{tr}(\mathbf{A}^{-1}\dot{\mathbf{A}})$ 로 간결하게 표현된다.

7. 딥러닝에서의 여인자 전개의 의의

여인자 전개의 직접적 계산은 딥러닝에서 사용되지 않으나, 그 이론적 구조는 여러 기법의 수학적 기반을 이룬다.

자동 미분(automatic differentiation) 시스템에서 $\log\det(\mathbf{A})$ 의 기울기를 계산할 때, 야코비 공식에 의하여 $\nabla_{\mathbf{A}}\log\det(\mathbf{A}) = \mathbf{A}^{-\top}$ 이 사용된다. 이 결과는 수반 행렬과 여인자 전개의 이론으로부터 도출된 것이다. 정규화 흐름, 변분 추론, 가우시안 과정 등 행렬식이 등장하는 모든 확률 모델의 학습에서 이 기울기 공식이 역전파의 핵심 구성 요소가 된다.

또한 행렬식 추정(determinant estimation) 기법에서 확률적 추적 추정량(stochastic trace estimator) $\text{tr}(\mathbf{A}) \approx \mathbf{z}^\top\mathbf{A}\mathbf{z}$ (Hutchinson, 1989)을 활용하여 $\log\det(\mathbf{A}) = \text{tr}(\log\mathbf{A})$ 를 근사하는 방법이 대규모 모델에서 활용된다. 이는 여인자 전개의 $O(n!)$ 복잡도를 우회하면서도 행렬식의 수학적 성질을 보존하는 실용적 접근이다.