1 이 절의 위치
§5.1에서 세 공리와 열 성질을 정립했고, 이 과정에서 첫 번째 계산 공식(피벗 공식)이 부록처럼 따라나왔다. §5.2는 나머지 두 가지 계산 공식을 본격적으로 유도한다.
§5.1 행렬식의 성질
↓ [부산물: det A = ±(피벗 곱)]
§5.2 순열과 여인수 ← 지금 여기
↓ 두 가지 공식 추가:
- 빅 공식 (Leibniz, n! 항)
- 여인수 공식 (Laplace, 재귀)
↓
§5.3 Cramer 공식·역행렬·부피§5.2의 핵심 메시지:
피벗 공식은 빠르지만 성분과 직접 연결되지 않는다. 빅 공식은 성분의 조합을 명시하고, 여인수 공식은 재귀 구조를 보여준다. 세 공식이 같은 값을 주는 것은 공리가 유일함을 보장하기 때문이다.
2 세 가지 공식: 한눈에 비교
공식 1 — 피벗 공식(Pivot Formula):
\[\det \mathbf{A} = (\det \mathbf{P}) \cdot (d_1 d_2 \cdots d_n)\]
소거법으로 얻은 피벗들의 곱, 행 교환 수에 따른 부호 \(\pm\).
공식 2 — 빅 공식(Big Formula / Leibniz):
\[\det \mathbf{A} = \sum_{\sigma \in S_n} (\text{sign}\,\sigma) \cdot a_{1\sigma(1)} a_{2\sigma(2)} \cdots a_{n\sigma(n)}\]
모든 순열 \(\sigma\) 에 대한 곱의 부호 있는 합. 총 \(n!\) 개 항.
공식 3 — 여인수 공식(Cofactor Formula / Laplace):
\[\det \mathbf{A} = \sum_{j=1}^n a_{ij} C_{ij}, \quad C_{ij} = (-1)^{i+j} \det \mathbf{M}_{ij}\]
\(i\) 번째 행(또는 \(j\) 번째 열)을 따라 한 성분과 작은 행렬식의 곱 \(n\) 개의 합. \(\mathbf{M}_{ij}\) 는 \(i\) 행과 \(j\) 열을 제거한 \((n-1) \times (n-1)\) 부분행렬.
2.1 용도 비교
| 공식 | 연산량 | 최적 용도 |
|---|---|---|
| 피벗 | \(\mathcal{O}(n^3)\) | 컴퓨터 계산 (실무 표준) |
| 빅 | \(\mathcal{O}(n \cdot n!)\) | 이론 증명, 성분 의존성 분석 |
| 여인수 | \(\mathcal{O}(n!)\) | 손 계산 (희소 행렬), 재귀 증명 |
직관: 피벗은 “빠르지만 불투명”, 빅은 “느리지만 투명”, 여인수는 “재귀적이고 희소 행렬에 강하다”. 세 공식이 각자 다른 장점을 가지므로 상황에 맞게 선택한다.
3 기준 예시: Strang의 \(-1, 2, -1\) 삼대각 행렬
앞으로 계속 쓸 예시를 먼저 소개한다. 이 행렬은 세 가지 공식 모두로 \(\det = 5\) 를 준다.
\[\mathbf{A}_4 = \begin{bmatrix} 2 & -1 & 0 & 0 \\ -1 & 2 & -1 & 0 \\ 0 & -1 & 2 & -1 \\ 0 & 0 & -1 & 2 \end{bmatrix}\]
세 공식으로 계산:
피벗: 피벗들이 \(2, \frac{3}{2}, \frac{4}{3}, \frac{5}{4}\). 곱하면 분자·분모가 줄줄이 상쇄되어 5.
빅 공식: \(4! = 24\) 개 항 중 \(5\) 개만 0이 아니다. \(16 - 4 - 4 - 4 + 1 = 5\).
여인수 공식: 1행에 따라 전개. \(2 \cdot C_{11} + (-1) \cdot C_{12} = 2 \cdot 4 - 1 \cdot 3 = 5\).
세 공식이 모두 같은 5를 주는 것이 공리의 유일성이 만들어내는 결과다. 아래에서 하나씩 상세히 본다.
4 공식 1 복습: 피벗 공식
§5.1의 결론을 다시 확인한다.
4.1 유도
소거법으로 \(\mathbf{A}\) 를 상삼각 \(\mathbf{U}\) 로 변환. 행 교환이 없다면 \(\mathbf{A} = \mathbf{L}\mathbf{U}\), 성질 9 (곱셈 규칙):
\[\det \mathbf{A} = \det \mathbf{L} \cdot \det \mathbf{U} = 1 \cdot (d_1 d_2 \cdots d_n)\]
\(\det \mathbf{L} = 1\) 은 하삼각이면서 대각 1인 LU의 \(\mathbf{L}\) 성질 (성질 7).
행 교환이 있으면 \(\mathbf{P}\mathbf{A} = \mathbf{L}\mathbf{U}\), 그러면:
\[\det \mathbf{P} \cdot \det \mathbf{A} = \det \mathbf{L} \cdot \det \mathbf{U} = d_1 d_2 \cdots d_n\]
\(\det \mathbf{P} = \pm 1\) (짝수/홀수 교환), 따라서 \(\det \mathbf{A} = \pm (d_1 \cdots d_n)\).
4.2 중요한 따름정리 — 좌상단 부분행렬
관찰: 행 교환 없이 소거할 때, 첫 \(k\) 개 피벗은 오직 좌상단 \(k \times k\) 부분행렬 \(\mathbf{A}_k\) 에만 의존한다.
\[\det \mathbf{A}_k = d_1 d_2 \cdots d_k\]
왜: 소거법의 \(k\) 번째 피벗을 만드는 데 쓰이는 원소들은 모두 좌상단 \(k \times k\) 사각형 안에 있다. 오른쪽이나 아래의 원소들은 아직 개입하지 않는다.
결론 — 피벗의 비율 공식:
\[d_k = \frac{\det \mathbf{A}_k}{\det \mathbf{A}_{k-1}}\]
직관: “전체 곱 / 이전 곱 = 새로 추가된 항”. 새로운 피벗은 행렬식을 얼마나 “증가시키는가”의 척도다.
예시 — 삼대각 \(-1, 2, -1\): \(\det \mathbf{A}_1 = 2\), \(\det \mathbf{A}_2 = 3\), \(\det \mathbf{A}_3 = 4\), \(\det \mathbf{A}_4 = 5\). 일반적으로 \(\det \mathbf{A}_n = n + 1\).
피벗: \(d_1 = \frac{2}{1} = 2\), \(d_2 = \frac{3}{2}\), \(d_3 = \frac{4}{3}\), \(d_4 = \frac{5}{4}\). 곱 = \(5\).
import numpy as np
# -1, 2, -1 삼대각 행렬 생성
def tridiag_minus_plus(n):
A = 2 * np.eye(n) - np.eye(n, k=1) - np.eye(n, k=-1)
return A
# 크기별 행렬식 확인
for n in range(1, 7):
A = tridiag_minus_plus(n)
print(f"n={n}: det = {np.linalg.det(A):.4f}")
# 결과: 2, 3, 4, 5, 6, 7 → det Aₙ = n+1
# 피벗 확인 (부분 행렬식 비율)
print("\n피벗 비율 확인 (n=5):")
A = tridiag_minus_plus(5)
for k in range(1, 6):
Ak = A[:k, :k]
det_k = np.linalg.det(Ak)
print(f" det A_{k} = {det_k:.4f}")5 공식 2: 빅 공식 (Leibniz)
5.1 동기: 성분 \(a_{ij}\) 와 직접 연결
피벗 공식은 소거법을 거친 결과를 쓴다. 원래 성분 \(a_{ij}\) 와 어떤 관계인지 한눈에 보이지 않는다. 빅 공식은 정반대의 접근 — \(a_{ij}\) 들의 직접적인 곱 합으로 행렬식을 표현한다.
5.2 2×2 유도: 선형성으로 분해
\[\begin{bmatrix} a & b \\ c & d \end{bmatrix}\]
1행을 기저 벡터로 분해: \((a, b) = (a, 0) + (0, b)\). 선형성(공리 3)으로:
\[\det\begin{bmatrix} a & b \\ c & d \end{bmatrix} = \det\begin{bmatrix} a & 0 \\ c & d \end{bmatrix} + \det\begin{bmatrix} 0 & b \\ c & d \end{bmatrix}\]
각각의 2행도 같은 방식으로 분해:
\[\det\begin{bmatrix} a & 0 \\ c & d \end{bmatrix} = \det\begin{bmatrix} a & 0 \\ c & 0 \end{bmatrix} + \det\begin{bmatrix} a & 0 \\ 0 & d \end{bmatrix}\]
\[\det\begin{bmatrix} 0 & b \\ c & d \end{bmatrix} = \det\begin{bmatrix} 0 & b \\ c & 0 \end{bmatrix} + \det\begin{bmatrix} 0 & b \\ 0 & d \end{bmatrix}\]
총 \(2^2 = 4\) 개 항. 이 중 두 개는 같은 열에 비영 원소가 몰려있어 0이 된다 (두 행이 같은 방향이므로).
\[\det\begin{bmatrix} a & 0 \\ c & 0 \end{bmatrix} = 0, \quad \det\begin{bmatrix} 0 & b \\ 0 & d \end{bmatrix} = 0\]
(두 행의 두 번째 성분이 0이거나 첫 번째 성분이 0 → 두 행이 한 축 위에 있음 → 종속)
남는 두 항:
\[\det\begin{bmatrix} a & 0 \\ 0 & d \end{bmatrix} = ad \cdot \det\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = ad\]
\[\det\begin{bmatrix} 0 & b \\ c & 0 \end{bmatrix} = bc \cdot \det\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = bc \cdot (-1) = -bc\]
(두 번째는 행을 교환하면 \(\mathbf{I}\) 가 되므로 부호 반전)
합치면: \(\det = ad - bc\). 공리만으로 공식이 유도됨 — 어떤 공식도 미리 알 필요 없었다.
5.3 핵심 관찰: “서로 다른 열에서 하나씩”
분해 후 살아남은 항들은 모두 “행 \(i\) 에서 어느 열 \(\sigma(i)\) 를 택한 성분 \(a_{i\sigma(i)}\) 들의 곱”인데, \(\sigma\) 는 \(\{1, 2, \ldots, n\}\) 의 순열 — 즉 각 열이 정확히 한 번씩 선택된다.
열이 중복되면 같은 열에 비영이 몰려서 해당 행들이 선형 종속이 되어 \(\det = 0\).
5.4 3×3 유도와 순열
\(n = 3\) 에서는 각 행을 3개로 분해, 총 \(3^3 = 27\) 개 항. 이 중 “모든 열이 다 다른” 항만 살아남는다. 그런 항의 수 = \(3! = 6\) 개, 즉 3개 열의 모든 순열:
\[(1,2,3), (2,3,1), (3,1,2), (1,3,2), (2,1,3), (3,2,1)\]
앞 세 개는 짝(even) 순열, 뒤 세 개는 홀(odd) 순열.
3×3 빅 공식:
\[\det \mathbf{A} = a_{11}a_{22}a_{33} + a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32} - a_{13}a_{22}a_{31} - a_{11}a_{23}a_{32} - a_{12}a_{21}a_{33}\]
3×3에서 유명한 Sarrus 법칙이 바로 이것이다 — “주대각선 방향은 \(+\), 반대 방향은 \(-\)”.
경고: Sarrus 법칙은 오직 3×3 에서만 성립한다. 4×4 이상에서는 “대각선 8개”로 계산하면 틀린다 (실제로는 24개 항 필요). Sarrus를 일반화하지 말 것.
5.5 \(n\) 차 빅 공식 (일반)
\[\boxed{\det \mathbf{A} = \sum_{\sigma \in S_n} (\text{sign}\,\sigma) \prod_{i=1}^n a_{i, \sigma(i)}}\]
- \(S_n\): \(\{1, 2, \ldots, n\}\) 의 모든 순열의 집합, \(|S_n| = n!\)
- \(\sigma(i)\): 행 \(i\) 가 선택하는 열
- \(\text{sign}(\sigma) = \pm 1\): 짝 순열이면 \(+\), 홀 순열이면 \(-\)
5.6 순열의 부호: 짝 vs 홀
정의: 순열 \(\sigma\) 를 항등 순열 \((1, 2, \ldots, n)\) 로 되돌리는 데 필요한 행 교환 횟수의 홀짝성.
- 짝수 번 교환 → 짝 순열, \(\text{sign} = +1\)
- 홀수 번 교환 → 홀 순열, \(\text{sign} = -1\)
직관: 행 교환 1번 = 부호 반전 1번 (공리 2). 따라서 “항등 → \(\sigma\)” 경로의 교환 횟수가 부호를 결정한다.
독립성: 같은 순열을 만드는 교환 경로는 여러 가지지만, 홀짝성은 항상 같다. 이것이 부호 정의가 잘 정의됨을 보장한다.
5.7 왜 순열 행렬의 행렬식이 \(\pm 1\) 인가
순열 행렬 \(\mathbf{P}\) 는 \(\mathbf{I}\) 에서 행을 교환해 만든 행렬. 한 번 교환할 때마다 \(\det\) 가 \(-1\) 을 곱한다. \(k\) 번 교환하면 \(\det \mathbf{P} = (-1)^k\). 이것이 순열의 부호 \(\text{sign}(\sigma)\) 이다.
5.8 삼각 행렬에서 빅 공식 검증
상삼각 \(\mathbf{U}\): 항등 순열 \(\sigma = (1, 2, \ldots, n)\) 일 때만 비영. 다른 순열에서는 어떤 \(a_{ij}\) 가 하삼각 부분(영)을 선택한다.
\[\det \mathbf{U} = (+1) \cdot u_{11} u_{22} \cdots u_{nn}\]
한 항만 남아서 간단히 대각 곱이 된다. 성질 7과 일치.
5.9 희소 행렬의 이점
\(\mathbf{A}\) 의 대부분 원소가 0이면 빅 공식에서 살아남는 항도 극소수다.
예시 — Strang의 \(-1, 2, -1\) 삼대각 행렬 \(\mathbf{A}_4\):
비영 원소 위치: \((1,1), (1,2), (2,1), (2,2), (2,3), (3,2), (3,3), (3,4), (4,3), (4,4)\).
이 중 “각 행과 열이 정확히 한 번씩”인 선택은 오직 몇 개뿐. 직접 열거하면:
- \(\sigma = (1,2,3,4)\): \(a_{11}a_{22}a_{33}a_{44} = 2 \cdot 2 \cdot 2 \cdot 2 = 16\). 부호 \(+\).
- \(\sigma = (2,1,3,4)\): \(a_{12}a_{21}a_{33}a_{44} = (-1)(-1)(2)(2) = 4\). 1↔︎2 교환 1번, 부호 \(-\).
- \(\sigma = (1,3,2,4)\): \(a_{11}a_{23}a_{32}a_{44} = (2)(-1)(-1)(2) = 4\). 2↔︎3 교환 1번, 부호 \(-\).
- \(\sigma = (1,2,4,3)\): \(a_{11}a_{22}a_{34}a_{43} = (2)(2)(-1)(-1) = 4\). 3↔︎4 교환 1번, 부호 \(-\).
- \(\sigma = (2,1,4,3)\): \(a_{12}a_{21}a_{34}a_{43} = (-1)(-1)(-1)(-1) = 1\). 두 교환 (1↔︎2, 3↔︎4), 부호 \(+\).
합: \(16 - 4 - 4 - 4 + 1 = 5\) ✓
이것이 Strang이 “5개 항만 비영”이라 한 이유. 24개 중 19개는 어떤 \(a_{ij}\) 가 영 원소를 선택해 전체 곱이 0이 된다.
6 공식 3: 여인수 공식 (Laplace)
6.1 동기: 재귀적 환원
빅 공식은 \(n!\) 개 항 — 너무 많다. \(n\) 차 행렬식을 더 작은 \((n-1)\) 차 행렬식들의 조합으로 환원하면 재귀적으로 문제 크기를 줄일 수 있다. 이것이 Laplace의 아이디어다.
6.2 3×3에서 유도
3×3 빅 공식의 6개 항을 \(a_{1j}\) 로 묶는다 (1행의 성분별 인수분해):
\[\det \mathbf{A} = a_{11}(a_{22}a_{33} - a_{23}a_{32}) + a_{12}(a_{23}a_{31} - a_{21}a_{33}) + a_{13}(a_{21}a_{32} - a_{22}a_{31})\]
각 괄호 안은 2×2 행렬식이다.
\[= a_{11} \det\begin{bmatrix} a_{22} & a_{23} \\ a_{32} & a_{33} \end{bmatrix} - a_{12} \det\begin{bmatrix} a_{21} & a_{23} \\ a_{31} & a_{33} \end{bmatrix} + a_{13} \det\begin{bmatrix} a_{21} & a_{22} \\ a_{31} & a_{32} \end{bmatrix}\]
관찰: - 첫 항: \(a_{11}\) 을 제거하고 남는 2×2 = 1행과 1열을 제거한 부분행렬 \(\mathbf{M}_{11}\) - 둘째 항: \(\mathbf{M}_{12}\) (1행, 2열 제거), 부호가 반전됨 - 셋째 항: \(\mathbf{M}_{13}\) (1행, 3열 제거)
부호 패턴: \(+, -, +, -, \ldots\) 교대.
6.3 부호 \((-1)^{i+j}\) 의 기원
질문: 왜 \(a_{12}\) 에는 음수 부호가 붙는가?
답: 빅 공식에서 \(a_{12}\) 를 포함하는 순열은 1행이 2열을 선택한 것. 이를 항등 순열로 되돌리려면 1↔︎2 열을 한 번 교환해야 한다. 즉 홀 순열이므로 부호 \(-\).
일반화: \(a_{ij}\) 를 포함하는 항의 부호는 행 \(i\) 가 열 \(j\) 를 선택하는 순열의 부호와 연결된다. 정확한 규칙: \((-1)^{i+j}\).
- \((i+j)\) 짝수 → \(+\)
- \((i+j)\) 홀수 → \(-\)
시각적으로는 체스판 패턴:
\[\text{sign} \text{ pattern} = \begin{bmatrix} + & - & + & - \\ - & + & - & + \\ + & - & + & - \\ - & + & - & + \end{bmatrix}\]
6.4 여인수 정의
\(\mathbf{A}\) 의 \((i, j)\) 여인수 \(C_{ij}\) 는:
\[C_{ij} = (-1)^{i+j} \det \mathbf{M}_{ij}\]
여기서 \(\mathbf{M}_{ij}\) 는 \(\mathbf{A}\) 에서 \(i\) 번째 행과 \(j\) 번째 열을 제거한 \((n-1) \times (n-1)\) 부분행렬.
\(\det \mathbf{M}_{ij}\) 자체를 “소행렬식(minor)”이라 하고, 부호까지 붙인 \(C_{ij}\) 를 “여인수”라 한다.
6.5 여인수 공식
임의의 행 \(i\) 를 따라 전개:
\[\det \mathbf{A} = a_{i1}C_{i1} + a_{i2}C_{i2} + \cdots + a_{in}C_{in} = \sum_{j=1}^n a_{ij} C_{ij}\]
성질 10 (\(\det \mathbf{A}^\top = \det \mathbf{A}\))에 의해 열을 따라서도 전개 가능:
\[\det \mathbf{A} = \sum_{i=1}^n a_{ij} C_{ij} \quad (j \text{ 고정, 임의의 열})\]
6.6 어느 행/열을 선택할 것인가
핵심 팁: 0이 많은 행이나 열을 선택한다. 0인 \(a_{ij}\) 항은 계산할 필요가 없으므로 비영 성분의 수만큼만 작은 행렬식을 계산하면 된다.
예: 1행이 \((5, 0, 0, 3, 0)\) 이라면 다섯 개 중 두 개만 비영. 두 개의 4×4 여인수만 계산하면 끝.
7 3×3 예시: Strang 기준
\[\mathbf{A} = \begin{bmatrix} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 1 & 0 & 6 \end{bmatrix}\]
7.1 1행을 따라 여인수 전개
\[\det \mathbf{A} = 1 \cdot C_{11} + 2 \cdot C_{12} + 3 \cdot C_{13}\]
\(C_{11}\): 1행, 1열 제거, 부호 \((-1)^{1+1} = +\)
\[C_{11} = + \det\begin{bmatrix} 4 & 5 \\ 0 & 6 \end{bmatrix} = 24 - 0 = 24\]
\(C_{12}\): 1행, 2열 제거, 부호 \((-1)^{1+2} = -\)
\[C_{12} = -\det\begin{bmatrix} 0 & 5 \\ 1 & 6 \end{bmatrix} = -(0 - 5) = 5\]
\(C_{13}\): 1행, 3열 제거, 부호 \((-1)^{1+3} = +\)
\[C_{13} = + \det\begin{bmatrix} 0 & 4 \\ 1 & 0 \end{bmatrix} = 0 - 4 = -4\]
종합:
\[\det \mathbf{A} = 1 \cdot 24 + 2 \cdot 5 + 3 \cdot (-4) = 24 + 10 - 12 = 22\]
7.2 2열을 따라 여인수 전개 (검증)
2열이 0을 포함하므로 계산이 짧아진다. \(a_{12} = 2, a_{22} = 4, a_{32} = 0\).
\[\det \mathbf{A} = 2 \cdot C_{12} + 4 \cdot C_{22} + 0 \cdot C_{32}\]
마지막 항은 자동으로 0이므로 두 개만 계산한다.
- \(C_{12} = -\det\begin{bmatrix} 0 & 5 \\ 1 & 6 \end{bmatrix} = 5\) (위에서 계산)
- \(C_{22} = +\det\begin{bmatrix} 1 & 3 \\ 1 & 6 \end{bmatrix} = 6 - 3 = 3\)
\[\det \mathbf{A} = 2 \cdot 5 + 4 \cdot 3 + 0 = 10 + 12 = 22 \checkmark\]
A = np.array([[1, 2, 3],
[0, 4, 5],
[1, 0, 6]], dtype=float)
print(f"NumPy det(A) = {np.linalg.det(A):.4f}") # 22
# 수동 여인수 전개 (1행)
def cofactor(A, i, j):
"""A의 (i,j) 여인수 계산"""
M = np.delete(np.delete(A, i, axis=0), j, axis=1)
return (-1)**(i+j) * np.linalg.det(M)
# 1행 기준 전개
det_row1 = sum(A[0, j] * cofactor(A, 0, j) for j in range(3))
print(f"1행 전개: {det_row1:.4f}")
# 2열 기준 전개
det_col2 = sum(A[i, 1] * cofactor(A, i, 1) for i in range(3))
print(f"2열 전개: {det_col2:.4f}")
# 두 방식 모두 22 ✓8 Strang 4×4 삼대각 행렬 완전 풀이
\[\mathbf{A}_4 = \begin{bmatrix} 2 & -1 & 0 & 0 \\ -1 & 2 & -1 & 0 \\ 0 & -1 & 2 & -1 \\ 0 & 0 & -1 & 2 \end{bmatrix}\]
8.1 1행을 따라 여인수 전개
1행 = \((2, -1, 0, 0)\). 뒤의 두 0은 자동 소거, 두 개만 계산.
\[\det \mathbf{A}_4 = 2 \cdot C_{11} + (-1) \cdot C_{12}\]
\(C_{11}\): 1행 1열 제거:
\[\mathbf{M}_{11} = \begin{bmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{bmatrix} = \mathbf{A}_3\]
놀랍게도 \(\mathbf{M}_{11}\) 이 같은 패턴의 작은 행렬이다! \(\det \mathbf{A}_3 = 4\) (앞서 계산).
따라서 \(C_{11} = +4\).
\(C_{12}\): 1행 2열 제거:
\[\mathbf{M}_{12} = \begin{bmatrix} -1 & -1 & 0 \\ 0 & 2 & -1 \\ 0 & -1 & 2 \end{bmatrix}\]
\(\mathbf{M}_{12}\) 의 1열이 \((-1, 0, 0)^\top\) — 하나만 비영. 1열을 따라 다시 전개:
\[\det \mathbf{M}_{12} = (-1) \cdot (-1)^{1+1} \det\begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix} = (-1)(4-1) = -3\]
그러면 \(C_{12} = (-1)^{1+2} \cdot (-3) = -(-3) = 3\).
종합:
\[\det \mathbf{A}_4 = 2 \cdot 4 + (-1) \cdot 3 = 8 - 3 = 5 \checkmark\]
8.2 재귀 관계 유도
일반적으로 \(-1, 2, -1\) 삼대각의 \(n \times n\) 행렬식을 \(D_n\) 이라 하자. 위의 여인수 전개에서 발견한 패턴:
\[D_n = 2 D_{n-1} - D_{n-2}\]
검증: \(D_1 = 2, D_2 = 3\) 에서 시작하면: - \(D_3 = 2 \cdot 3 - 2 = 4\) - \(D_4 = 2 \cdot 4 - 3 = 5\) - \(D_5 = 2 \cdot 5 - 4 = 6\) - \(D_n = n + 1\) (수학적 귀납법)
왜 이 재귀가 의미 있는가: 삼대각 행렬의 행렬식을 \(\mathcal{O}(n)\) 에 계산할 수 있다 (빅 공식은 \(n!\), 여인수 재귀도 일반적으로 \(n!\), 그러나 이 특수한 구조 덕분에 두 개의 이전 값만으로 다음 값 계산).
# 재귀 D_n = 2 D_{n-1} - D_{n-2} 확인
D = [None, 2, 3] # D_0는 사용 안 함
for n in range(3, 8):
D.append(2 * D[n-1] - D[n-2])
print("재귀 관계 D_n = 2 D_{n-1} - D_{n-2}:")
for n in range(1, 8):
A = tridiag_minus_plus(n)
print(f" n={n}: 재귀={D[n]}, NumPy det={np.linalg.det(A):.4f}")9 Hessenberg 행렬과 피보나치 (Strang 5.2 A)
9.1 Hessenberg 행렬 정의
Hessenberg 행렬은 상삼각 행렬에 한 개의 추가 하위 대각선이 있는 형태.
\[\mathbf{H}_4 = \begin{bmatrix} 2 & 1 & 1 & 1 \\ 1 & 2 & 1 & 1 \\ 0 & 1 & 2 & 1 \\ 0 & 0 & 1 & 2 \end{bmatrix}\]
주대각선 아래는 한 줄의 대각선만 살아있고, 그 아래는 모두 0.
9.2 여인수 전개로 피보나치 발견
1행을 따라 전개. Strang의 트릭으로 1행을 두 부분으로 선형 분해:
\[\begin{bmatrix} 2 & 1 & 1 & 1 \end{bmatrix} = \begin{bmatrix} 2 & 1 & 0 & 0 \end{bmatrix} + \begin{bmatrix} 0 & 0 & 1 & 1 \end{bmatrix}\]
첫 번째 부분: \((2, 1, 0, 0)\) 은 \(\mathbf{A}_4\) 의 1행과 같다 (본문 삼대각 행렬)! 나머지 3행은 \(\mathbf{H}_4\) 의 행들. 하지만 2~4행에서 \(\mathbf{H}_4\) 와 \(\mathbf{A}_4\) 의 관계가 복잡해지므로 정공법으로 여인수 전개해 본다.
실제로는 다음과 같이 더 직접적으로 유도 가능 (\(C_{11}\), \(C_{12}\) 계산):
\(C_{11}\): 1행 1열 제거 → \(\mathbf{M}_{11}\) = 3×3 Hessenberg 형태로 \(|\mathbf{H}_3|\).
\[\mathbf{H}_3 = \begin{bmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 0 & 1 & 2 \end{bmatrix}, \quad |\mathbf{H}_3| = 5\]
\(C_{12}\): 1행 2열 제거. 계산 후 \(|\mathbf{H}_2| - |\mathbf{H}_3|\) 형태로 정리됨 (Strang의 트릭).
결과:
\[|\mathbf{H}_4| = 2 |\mathbf{H}_3| + 1 \cdot (|\mathbf{H}_2| - |\mathbf{H}_3|) = |\mathbf{H}_3| + |\mathbf{H}_2|\]
이것이 피보나치 점화식!
\[|\mathbf{H}_n| = |\mathbf{H}_{n-1}| + |\mathbf{H}_{n-2}|\]
초기값: \(|\mathbf{H}_1| = 2, |\mathbf{H}_2| = 3\). 피보나치 수열 \(F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8, \ldots\) 과 맞춰보면:
\[|\mathbf{H}_n| = F_{n+2}\]
즉 \(|\mathbf{H}_1| = F_3 = 2\), \(|\mathbf{H}_2| = F_4 = 3\), \(|\mathbf{H}_3| = F_5 = 5\), \(|\mathbf{H}_4| = F_6 = 8\).
직관: 행렬식이 피보나치 수열을 만들어낸다는 것은 놀랍다. 이 예시는 “여인수 전개가 재귀 구조를 드러낸다”는 사실의 대표적인 증거다.
def hessenberg(n):
"""Strang 5.2 A의 Hessenberg 행렬"""
H = np.triu(np.ones((n, n))) # 상삼각 1
for i in range(n):
H[i, i] = 2 # 대각 2
for i in range(n-1):
H[i+1, i] = 1 # 서브 대각
return H
print("Hessenberg 행렬식과 피보나치:")
for n in range(1, 8):
H = hessenberg(n)
print(f" n={n}: |H_n| = {np.linalg.det(H):.0f}")
# 2, 3, 5, 8, 13, 21, 34 → F_3, F_4, F_5, ...10 Strang 5.2 B: 전원 1인 행렬
질문: 10×10 행렬 \(\mathbf{A}\) 의 모든 성분이 1이면 빅 공식으로 어떻게 \(\det = 0\) 을 얻는가?
풀이: 모든 \(a_{ij} = 1\) 이므로 빅 공식의 각 항:
\[a_{1\sigma(1)} a_{2\sigma(2)} \cdots a_{n\sigma(n)} = 1 \cdot 1 \cdots 1 = 1\]
모든 항이 정확히 1. 부호만 다르다.
- 짝 순열: \(n!/2\) 개, 부호 \(+\) → \(+n!/2\)
- 홀 순열: \(n!/2\) 개, 부호 \(-\) → \(-n!/2\)
총합: \(n!/2 - n!/2 = 0\).
다른 관점: 전원 1 행렬은 모든 행이 같으므로 성질 4에 의해 \(\det = 0\). 빅 공식은 이 사실을 부호 상쇄의 언어로 말한다.
교훈: 빅 공식은 명시적 부호 상쇄로 특이성을 증명하는 도구. 이것이 이론적 유도에서 빅 공식이 선호되는 이유다.
11 세 공식이 같은 값을 주는 이유
11.1 유일성 논증
§5.1에서 “세 공리를 만족하는 함수는 유일하다”고 했다. 따라서:
- 피벗 공식이 세 공리를 만족한다면 → 그것은 \(\det\)
- 빅 공식이 세 공리를 만족한다면 → 그것은 \(\det\)
- 여인수 공식이 세 공리를 만족한다면 → 그것은 \(\det\)
셋 모두가 같은 \(\det\) 을 표현하므로 수치가 같을 수밖에 없다.
11.2 각 공식이 공리를 만족함을 간단히 확인
빅 공식 → 공리 1: \(\mathbf{I}\) 일 때 \(a_{ii} = 1\), 다른 성분 0. 항등 순열만 비영이고 그 항은 \(1 \cdot 1 \cdots 1 = 1\), 부호 \(+\). 합 = 1. ✓
빅 공식 → 공리 2 (부호 반전): 두 행 교환 = 모든 순열 \(\sigma\) 를 “해당 두 값을 교환한 \(\sigma'\)”로 대응. 부호는 반대. 합 전체가 부호 반전. ✓
빅 공식 → 공리 3 (선형성): 한 행 (예: 1행)에 \(t\) 를 곱하면 모든 항에서 \(a_{1\sigma(1)}\) 이 \(t\) 배 → 합이 \(t\) 배. ✓
세 공리 모두 만족하므로 빅 공식 = \(\det\). 유사한 검증이 여인수 공식에도 적용된다 (여인수 공식은 빅 공식에서 한 행을 인수분해해 얻으므로 더 직접적).
12 실무 주의사항
12.1 1. 실제 계산에서는 피벗 공식을 쓴다
NumPy, MATLAB의 det() 는 내부적으로 LU 분해 후 피벗의 곱으로 계산한다. \(\mathcal{O}(n^3)\) 이라서 큰 행렬에서도 빠르다.
12.2 2. 빅 공식과 여인수 공식은 수치 계산용이 아니다
\(n = 10\) 만 되어도 \(10! = 3{,}628{,}800\) 개 항. \(n = 20\) 이면 \(20! \approx 2.4 \times 10^{18}\) — 우주 나이보다 더 오래 걸린다.
12.3 3. 여인수가 여전히 쓰이는 곳
- 손 계산: 3×3, 4×4 에서 0이 많은 행렬
- 이론 증명: 재귀 구조, 특히 특수 행렬(삼대각, Hessenberg, Vandermonde)
- Cramer 공식: 역행렬 공식에 여인수 행렬이 직접 등장 (§5.3)
- 수학 소프트웨어의 기호 계산(symbolic): Mathematica, SymPy 등
12.4 4. 부동소수점 주의
큰 행렬의 행렬식은 수치적으로 매우 불안정하다. 대각 성분이 \(10^{10}\) 이고 \(n = 100\) 이면 \(\det \approx 10^{1000}\) — 오버플로우. 실무에서는 \(\log|\det|\) 를 계산하거나 (여러 특수 목적 알고리즘 사용), 정말 필요한 건 가역성뿐이면 조건수나 랭크를 본다.
13 핵심 요약
행렬식 계산 세 공식
┌─────────────┬─────────┬──────────────┬─────────────┐
│ 공식 │ 연산량 │ 근거 │ 실전 용도 │
├─────────────┼─────────┼──────────────┼─────────────┤
│ 피벗 │ O(n³) │ 소거 → LU │ 컴퓨터 계산 │
│ 빅 (Leibniz)│ O(n·n!) │ 순열 부호 │ 이론 증명 │
│ 여인수 │ O(n!) │ 재귀 환원 │ 손 계산 │
└─────────────┴─────────┴──────────────┴─────────────┘
빅 공식 (Leibniz)
det A = Σ_σ sign(σ) · a_{1σ(1)} a_{2σ(2)} ··· a_{nσ(n)}
- 모든 열을 정확히 한 번씩 선택
- 짝 순열 +, 홀 순열 -
- 2x2: ad - bc, 3x3: Sarrus (4x4 이상에는 Sarrus 금지!)
여인수 공식 (Laplace)
det A = Σ_j a_{ij} · C_{ij} (임의 행 i)
C_{ij} = (-1)^{i+j} · det(M_{ij})
- 체스판 부호 패턴
- 0이 많은 행/열 선택이 핵심
- 재귀 구조: n차 → (n-1)차
- 삼대각, Hessenberg 등에서 간결한 점화식 유도
피벗 비율 공식
d_k = det A_k / det A_{k-1}
핵심 예시
-1,2,-1 삼대각: D_n = 2 D_{n-1} - D_{n-2}, D_n = n+1
Hessenberg: H_n = H_{n-1} + H_{n-2}, H_n = F_{n+2}
세 공식의 결과가 같은 이유
세 공리를 만족하는 함수는 유일하다 (§5.1)
→ 세 공식 모두 공리를 만족하므로 같은 값14 관련 주제
선행 지식
- Ch.5 Overview — Determinants 개요 — 세 공식 한눈에 보기
- Ch.5 §5.1 — 행렬식의 성질 — 공리와 열 성질
챕터 내 후속
후속 주제
- Vandermonde 행렬식 — 여인수 공식의 유명한 응용
- 야코비안 (다변수 적분) — 변환의 국소 부피 배율