| 선형대수학 Linear Algebra | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#006ab8> 기본 대상 | 일차함수 · 벡터 · 행렬 · 선형 변환 | |
| 대수적 구조 | 가군(모듈) · 벡터 공간 · 내적 공간 · 노름 공간 | ||
| 선형 연산자 | <colbgcolor=#006ab8> 기본 개념 | 연립방정식(1차 · 2차) · 행렬곱 · 단위행렬 · 역행렬과 크라메르 공식 · 가역행렬 · 전치행렬 · 행렬식(라플라스 전개) · 주대각합 | |
| 선형 시스템 | 기본행연산과 기본행렬 · 가우스-조르당 소거법 · 행사다리꼴 · 행렬표현 · 라그랑주 보간법 | ||
| 주요 정리 | 선형대수학의 기본정리 · 차원 정리 · 가역행렬의 기본정리 · 스펙트럼 정리 | ||
| 기타 | 제곱근행렬 · 멱등행렬 · 멱영행렬 · 에르미트 행렬 · 야코비 행렬 · 방데르몽드 행렬 · 아다마르 행렬 변환 · 노름(수학) | ||
| 벡터공간의 분해 | 상사 · 고유치 문제 · 케일리-해밀턴 정리 · 대각화(대각행렬) · 삼각화 · 조르당 분해 | ||
| 벡터의 연산 | 노름 · 거리함수 · 내적 · 외적(신발끈 공식) · 다중선형형식 · ∇ · 크로네커 델타 | ||
| 내적공간 | 그람-슈미트 과정 · 수반 연산자(에르미트 내적) | ||
| 다중선형대수 | 텐서 · 텐서곱 · 레비치비타 기호 | }}}}}}}}} | |
1. 개요
Laplace Expansion선형대수학에서 라플라스 전개 혹은 여인수 전개(Cofactor Expansion)는 피에르시몽 라플라스가 고안한 행렬식의 표현이자 행렬식 전개의 기초적인 계산법중 하나이다. [math(n×n)] 행렬에서 부분 행렬인 [math((n-1)×(n-1))] 행렬식과 소행렬[1]의 곱으로 이루어지는 전개이다.
2. 정의
[math(n×n)] 행렬을 [math(A)]라고 하자. 라플라스 전개에 의해 행렬식 [math(A)]는 다음과 같이 급수 형태로 정의 된다.[math(\displaystyle \det A=\sum_{j=1}^n a_{ij}C_{ij}=\sum_{j=1}^n \left(-1\right)^{i+j}a_{ij}M_{ij})]
[math(A)]의 한 열을 선택하면
[math(\displaystyle \det A=\sum_{i=1}^n a_{ij}C_{ij}=\sum_{i=1}^n \left(-1\right)^{i+j}a_{ij}M_{ij})]
고로, 열과 행의 라플라스 전개 정의는 같다.
[math(a_{ij})]는 [math(A)]의 부분행렬이고 [math(M_{ij})]는 소행렬(小行列, Minor)이다. 고로, [math(C_{ij} = \left(-1\right)^{i+j} M_{ij})]는 여인수(餘因數, Cofactor)이다. ||
참고로 라플라스 전개는 행렬식의 정의가 아니다.[2] 가끔 공학 쪽에서 alternative multilinear form을 소개하기 어렵다든가 하는 이유에서인지 이걸 행렬식의 정의처럼 소개하는 경우가 있지만 (혹은 독자가 그렇게 오해한다든가) 적어도 수학에서 이건 성질이지 정의가 아니다. 성질이다 보니 물론 증명이 존재하며, 이는 다음 단락에서 확인할 수 있다.
3. 증명
3.1. 행, 열 선택에 대한 독립성
이처럼 라플라스 전개를 했을때 행 아무거나 혹은 열 아무거나 선택해도 똑같은 결과가 나오는 게 희한할 수 있는데, 이는 행렬식의 몇 가지 성질로부터 간단하게 구할 수 있다. 먼저 행을 가지고 계산이 되는 성질이 증명됐다고 하자. 그러면 전치행렬(transpose matrix)의 행렬식이 동일하다는 것으로부터 열을 가지고도 계산이 된다는 성질이 만족된다는 것을 바로 알 수 있다. 한편, 예를 들어 맨 마지막 행, 즉 [math(n)]번째 행을 가지고 위 성질을 증명했다고 하자. 이제 다음과 같이 주어진 행렬 [math(U)]를 생각해 보자.[math(\begin{pmatrix} \ddots & \vdots & \vdots & \vdots & \vdots & \cdots & \vdots & \vdots & \vdots \\ \cdots & 1 & 0 & 0 & 0 & \cdots & 0 & 0 & 0 \\ \cdots & 0 & 0 & 0 & 0 & \cdots & 0 & 0 & 1 \\ \cdots & 0 & 0 & 1 & 0 & \cdots & 0 & 0 & 0 \\ \cdots & 0 & 0 & 0 & 1 & \cdots & 0 & 0 & 0 \\ \cdots & 0 & 0 & 0 & 0 & \cdots & 1 & 0 & 0 \\ \cdots & 0 & 0 & 0 & 0 & \cdots & 0 & 1 & 0 \\ \cdots & 0 & 1 & 0 & 0 & \cdots & 0 & 0 & 0 \end{pmatrix})]
즉, 단위행렬에서 [math((i, \ i))], [math((n, \ n))] 성분을 [math(0)]으로 바꾸고 대신 [math((i, \ n))], [math((n, \ i))] 성분을 [math(1)]로 둔 것이다. 그러면 [math(UA)]는 [math(A)]의 [math(i)]번째 행과 [math(n)]번째 행이 뒤바뀐 행렬이 된다. 이 행렬의 [math(n)]번째 행을 가지고 여인수 전개를 하면 [math(\displaystyle \det \left(UA \right) = \sum_{j=1}^n \left(-1\right)^{n+j}a_{ij}M_{ij})]가 된다는 것을 알 수 있다. ([math(UA)]의 [math(n)]번째 행을 지우고 남은 행렬이 [math(A)]의 [math(i)]번째 행을 지우고 남은 행렬과 같다는 것을 유념해 두자.) 그런데 사실 [math(\det U = \left(-1\right)^{i+n})]이고 [math(\det \left(UA\right) = \det U \det A)]이므로 결국 우리가 원하는 [math(i)]번째 행에 대한 여인수 전개 결과를 얻을 수 있다.
3.2. 정말로 라플라스 전개는 행렬식과 같은가
이제 하나 중요한 게 남았다. 맨 마지막 행, 즉 [math(n)]-번째 행을 가지고 라플라스 전개를 한 것이 정말 행렬식과 같은가 하는 것이다. 이는 행렬식의 정의를 이용하면 어렵지 않게 할 수 있다. 그냥 각 [math(j)]에 대하여 [math(a_{nj})]들이 포함된 항들을 묶으면 뭐가 나오는지 고민해 보면 금방 나온다. 다만 대칭군의 부분대칭군에서 부호가 어떻게 바뀌는지 고민을 좀 해 봐야 하는 게 사실 상 유일한 난관이다. 이어지는 내용의 대부분이 이 고민에 대한 풀이라는 것을 염두에 두자.[math(a_{nj})]들로 일단 묶어 보자. 그러면 다음을 얻는다. 여기서 [math(a_{i, \sigma(i)})]들 중에 [math(a_{nj})]가 포함되어 있는 항에 대해 [math(\sigma(n) = j)]가 성립한다는 걸 유념에 두도록 하자. 즉, 실질적으로는 [math(a_{n, \sigma(n)})]으로 묶는 것이다.
[math(\displaystyle \det{A} = \sum_{j = 1}^{n} a_{nj} \sum_{\sigma \in S_{n; j}} \mathrm{sgn}(\sigma) \prod_{r = 1}^{n - 1} a_{r, \sigma(r)})].[3]
여기서 [math(S_{n; j})]는 [math(\sigma(n) = j)]인 [math(\sigma)]들을 모아둔 집합이다. 이제 관건은 [math(S_{n; j})]에 대한 저 합 부분이 [math(C_{nj})]와 같다는 것을 보이는 것이다.
[math(S_{n; j})]의 원소들을 보면 이들이 이미 [math(n \mapsto j)] 하나가 고정되어 있고 나머지는 임의로 섞는 식으로 되어 있음을 알 수 있다. 가만 보면 [math(S_{n - 1})]의 원소와 비슷해 보인다. 특히 [math(j = n)]인 경우면 (정의역과 공역이 조금 다른 거 빼면) 아예 똑같다고 봐도 무방하다. 그러면 [math(S_{n; j})]의 원소들을 [math(S_{n - 1})]로 변환하는 방법을 생각해 보자.
방법은 간단하다. [math(S_{n; j})]의 원소들은 [math(\{1, 2, \cdots, n - 1\})]을 [math(\{1, 2, \cdots, n\})]에서 [math(j)]를 제외한 집합으로 일대일 대응시킨다. 두 집합의 차이점은 [math(n)]이 빠졌는가 [math(j)]가 빠졌는가 정도이다. 그러면 [math(\{1, 2, \cdots, n\})]에서 [math(j)]를 제외한 집합을 [math(\{1, 2, \cdots, n - 1\})]로 보내는 적당한 [math(S_{n})]의 원소를 생각해 보는 것이 좋겠다. 이런 걸 생각해 보자.
[math(\displaystyle \tau_j(r) = \left\{ \begin{array}{ll} r & (r < j) \\ r + 1 & (j \le r < n) \\ j & (r = n) \end{array} \right.)].
그러면 [math((\tau_j)^{-1})]는 [math(\{1, 2, \cdots, n\})]에서 [math(j)]를 제외한 집합을 [math(\{1, 2, \cdots, n - 1\})]로 보내는 (그리고 [math(j)]를 [math(n)]으로 보내는) 적당한 [math(S_{n})]의 원소이다. ([math(\tau_j)] 말고 [math((\tau_j)^{-1})]가 이를 만족하도록 설정한 이유는 다음에 이어질 식들을 좀 더 간단하게 하도록 하기 위함이다.) 그러면 모든 [math(S_{n; j})]의 원소 [math(\sigma)]에 대해 [math((\tau_j)^{-1} \sigma)]는 [math(\{1, 2, \cdots, n - 1\})]을 [math(\{1, 2, \cdots, n - 1\})]로 보낸다는 것을 알 수 있다. [math(n \mapsto n)]이 추가된 것만 빼면 완전히 [math(S_{n - 1})]의 원소와 똑같이 군다. 그러면 역으로 이런 걸 생각할 수 있다. [math(\sigma \in S_{n - 1})]에 대해 [math(\sigma^+(r) = \sigma(r))] [math((r < n))], [math(\sigma^+(n) = n)]인 [math(\sigma^+ \in S_n)]을 찾을 수 있을 것이다. 그러면 조금 전에 확인한 바로부터 [math(S_{n; j} = \{ \tau_j \sigma^+ \; | \; \sigma \in S_{n - 1} \})]임을 알 수 있다. 이를 이용해 [math(\det{A})]를 다음과 같이 쓸 수 있다.
[math(\displaystyle \det{A} = \sum_{j = 1}^{n} a_{nj} \sum_{\sigma \in S_{n - 1}} \mathrm{sgn}(\tau_j \sigma^+) \prod_{r = 1}^{n - 1} a_{r, (\tau_j \sigma^+)(r)})]
[math(\displaystyle = \sum_{j = 1}^{n} \mathrm{sgn}(\tau_j) a_{nj} \sum_{\sigma \in S_{n - 1}} \mathrm{sgn}(\sigma) \prod_{r = 1}^{n - 1} a_{r, (\tau_j \sigma^+)(r)})].
이제 [math(a_{r, (\tau_j \sigma^+)(r)})]이 뭔지 보도록 하자. 여기서 [math(\tau_j(r))]이 [math(1, 2, \cdots, j - 1, j, j + 1, \cdots, n - 1)]을 순서 대로 [math(1, 2, \cdots, j - 1, j + 1, \cdots, n - 1, n)]에 보낸다는 것을 상기하자. 마치 [math(j)]번째를 건너뛰고 가는 것 같은 모양이다. 혹은 [math(j)]번째를 지우고 뒤의 것들을 땡겨서 붙이는 모양으로도 볼 수 있다. 그런데 그러고 보면 [math(M_{ni})]를 만들기 위해 원래 행렬에서 ([math(n)]번째 행과) [math(j)]번째 열을 지우고 남은 걸 잘 땡겨서 [math((n - 1) \times (n - 1))]-행렬을 만들었다. 이제 이 행렬의 [math((r, \; s))]-성분을 [math(a^{(j)}_{rs})]라고 표기하면, 다음이 성립한다는 것을 방금 설명한 바에 입각했을 때 생각해 낼 수 있다.
[math(\displaystyle a^{(j)}_{rs} = a_{r, \tau_j(s)})].
따라서 [math(\det{A})]를 다음과 같이 쓸 수 있다.
[math(\displaystyle \det{A} = \sum_{j = 1}^{n} \mathrm{sgn}(\tau_j) a_{nj} \sum_{\sigma \in S_{n - 1}} \mathrm{sgn}(\sigma) \prod_{r = 1}^{n - 1} a^{(j)}_{r, \sigma(r)})]
[math(\displaystyle = \sum_{j = 1}^{n} \mathrm{sgn}(\tau_j) a_{nj} \det{(a^{(j)}_{rs})} = \sum_{j = 1}^{n} \mathrm{sgn}(\tau_j) a_{nj} M_{nj})].
원하는 식과 거의 비슷해졌다. 이제 남은 건 [math(\mathrm{sgn}(\tau_j))]를 계산하는 것이다. 사실 [math(\tau_j)]는 다음과 같은 호환들의 곱으로 쓸 수 있다.
[math(\displaystyle \tau_j = (j \;\; j + 1) (j + 1 \;\; j + 2) \cdots (n - 1 \;\; n))].
보다시피 [math((n - j))]-개의 호환들의 곱으로 표현된다. 따라서 [math(\mathrm{sgn}(\tau_j) = (-1)^{n - j})]이다. 한편, [math((-1)^{n - j} = (-1)^{n - j} (-1)^{2j} = (-1)^{n + j})]이므로 결국 다음을 얻게 되는 것으로 증명을 끝낼 수 있다.
그리고 앞에서 지적했던 것처럼 [math(n)]번째 행 말고 다른 행을 택해도, 아니면 아예 행 말고 열을 택해도 행렬식의 성질 덕분에 여인수 전개가 잘 성립한다는 것을 알 수 있다.
[math(\displaystyle \det{A} = \sum_{j = 1}^{n} (-1)^{n + j} a_{nj} M_{nj} = \sum_{j = 1}^{n} a_{nj} C_{nj})].
4. 쉬운 예시
[math(B = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix})]라고 하자.정의에서 나왔던 것처럼 라플라스 전개는 아무 행이나 열을 minor로 지정해서 부분 행렬과 곱해도 항상 같은 값이 나온다.
4.1. 라플라스 열 전개
행인 1,2,3을 지정해서 전개하는 경우,[math(\det B = 1 \begin{pmatrix} & 5 & 6 & \\ & 8 & 9 & \end{pmatrix} -2 \begin{pmatrix} & 4 & 6 & \\ & 7 & 9 & \end{pmatrix} +3 \begin{pmatrix} & 4 & 5 & \\ & 7 & 8 & \end{pmatrix})]
[math(\det B = 1 (45-48) -2 (36-42) +3 (32 - 35) = 0 )]
4.2. 라플라스 행 전개
열인 2,5,8을 지정해서 전개하는 경우,[math(\det B = -2 \begin{pmatrix} & 4 & 6 & \\ & 7 & 9 & \end{pmatrix} +5 \begin{pmatrix} & 1 & 3 & \\ & 7 & 9 & \end{pmatrix} -8 \begin{pmatrix} & 1 & 3 & \\ & 4 & 6 & \end{pmatrix})]
[math(\det B = -2 (36-42) +5 (9-21) -8 (6-12) = 0 )]
5. 활용
라플라스 전개의 의의는 [math(n)]차 정사각행렬의 행렬식을 [math((n-1))]차 정사각행렬의 행렬식으로 쪼개어 계산할 수 있다는 점이다. 이를 계속 적용시켜서 계산이 비교적 쉬운 [math(2)]차 정사각행렬이나 [math(3)]차 정사각행렬을 여러 번 계산하는 방법으로 임의의 정사각행렬의 행렬식을 계산할 수 있다는 것이다. 혹은, 하나 더 작은 행렬식들로 쪼개진다는 점을 이용하여 어떤 성질을 수학적 귀납법으로 증명하고자 할 때 써먹을 수 있다. 실제로 행렬식의 성질들 중 하나로 소개된 [math(\det \begin{pmatrix} A & B \\ O & C \end{pmatrix}=\det A\det C)]라든가 삼각행렬의 행렬식에 대한 성질 같은 것들을 라플라스 전개로 손쉽게 증명할 수 있음을 보였다.하지만 증명 외에 구체적인 계산을 하기 위해서는 가급적 안 쓰는 게 좋은데, 여인수 전개를 이용해서 직접 [math(n)]차 정사각행렬의 행렬식을 구하려고 하면 계산량이 무려 [math(\boldsymbol{n!})]에 비례하게 된다! 물론 연습문제에서는 무식하게 큰 행렬을 계산하는 경우가 거의 없고, 있더라도 성분 중에 [math(0)]이 많거나 어떤 패턴이 존재하여 쉽게 풀리는 경우가 대부분이다. 부득이하게 이 방법을 써서 컴퓨터로 계산한다면, 그리고 메모리를 많이 쓸 수 있다면, 작은 행렬식 계산이 반복된다는 점을 이용해 메모이제이션 기법으로 성능을 개선할 수 있다. 그리고 이렇게 하면 해당 매트릭스가 포함된 더 큰 매트릭스에서 다시 행렬식을 계산해야 할 경우 이미 계산된 행렬식을 캐시처럼 이용할 수 있다.
[1] 1,2개 정도의 열과 행을 제거한 정방 행렬이다. 보통 [math(i)]행, [math(j)]열을 해당 행렬에서 제거한다.[2] 물론. 주로 사용되지 않을 뿐이지 [math(\det \begin{bmatrix} \end{bmatrix}=1)]과 여인수 전개로 정의하고 다른 성질을 증명해도 문제가 생기진 않는다.즉 정의로 봐도 무방하긴 하다.[3] [math({\rm sgn})]은 부호 함수이다.