라플라스 전개

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

라플라스 전개는 정사각 행렬의 행렬식을 계산하는 방법으로, 특정 행 또는 열의 각 원소와 해당 여인자의 곱의 합으로 행렬식을 전개한다. 이 방법은 소행렬식과 여인자를 활용하며, 행렬식의 일반화된 형태로 여러 행 또는 열에 대해서도 적용할 수 있다. 라플라스 전개는 고전적 수반 행렬의 개념과도 관련 있으며, 행렬과 그 수반 행렬의 곱은 행렬식과 단위행렬의 곱과 같다. 하지만, 계산 복잡도가 높아 고차원 행렬에는 효율적이지 않다. 알렉상드르테오필 방데르몽드에 의해 처음 제시되었고, 피에르시몽 라플라스에 의해 일반화되었으며, 오귀스탱 루이 코시에 의해 현대적인 용어로 정리되었다.

라플라스 전개

📚 더 읽어볼만한 페이지

행렬식 - 부피 형식
부피 형식은 다양체의 방향 결정, 측도 정의, 벡터장 발산 계산에 사용되는 미분 형식의 일종으로, 유향 다양체에서는 밀도와 관련되며, 리 군, 심플렉틱 다양체, 준-리만 다양체 등에서 자연스럽게 정의된다.
행렬식 - 야코비 행렬
야코비 행렬은 열린 집합 U에서 정의된 함수 f의 각 성분 편도함수를 요소로 가지는 행렬이며, 함수가 미분 가능할 때 전미분을 나타내고, n=m일 경우 행렬식은 함수의 동작에 대한 정보를 제공하며 다양한 분야에 응용된다.
행렬론 - 행렬식
행렬식은 정사각 행렬에 대해 정의되는 값으로, 선형 방정식의 해를 구하고 선형 독립성을 확인하며 기저의 방향과 부피를 계산하는 데 사용되며, 가우스 소거법 등의 계산 기법과 가역성 판단, 고유값 연관성 등의 성질을 갖는다.
행렬론 - 행렬 분해
행렬 분해는 주어진 행렬을 특정 성질을 갖는 여러 행렬의 곱으로 표현하는 방법으로, 수치 해석에서 행렬 알고리즘 구현 및 선형 연립 방정식 해를 구하거나 행렬 특성 분석에 활용되며 LU 분해, QR 분해, 특잇값 분해 등이 있다.

1. 개요
2. 라플라스 전개의 정의
- 2.1. 소행렬식과 여인자
- 2.2. 라플라스 전개의 공식
3. 라플라스 전개의 일반화
- 3.1. 여러 행 또는 열에 대한 전개
4. 고전적 수반 행렬
5. 라플라스 전개의 예시
6. 라플라스 전개의 증명
7. 라플라스 전개의 계산 복잡도
8. 역사

2. 라플라스 전개의 정의

라플라스 전개는 주어진 정사각행렬에서 특정 행 또는 열을 선택하여, 각 원소와 그 원소에 대응하는 여인자의 곱을 모두 더하여 행렬식을 계산하는 방법이다.

다음과 같은 행렬 $B$ 를 예로 들어보자.

: $B = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}.$

이 행렬의 행렬식은 임의의 행이나 열을 따라 라플라스 전개를 사용하여 계산할 수 있다. 예를 들어 첫 번째 행을 따라 전개하면 다음과 같다.

: $\begin{align}|B| & = 1 \cdot \begin{vmatrix} 5 & 6 \\ 8 & 9 \end{vmatrix} - 2 \cdot \begin{vmatrix} 4 & 6 \\ 7 & 9 \end{vmatrix} + 3 \cdot \begin{vmatrix} 4 & 5 \\ 7 & 8 \end{vmatrix} \\[5pt]& = 1 \cdot (-3) - 2 \cdot (-6) + 3 \cdot (-3) = 0.\end{align}$

두 번째 열을 따라 전개해도 같은 결과를 얻는다.

이 행렬은 첫 번째 열과 세 번째 열의 합이 두 번째 열의 두 배이므로 특이 행렬이며, 따라서 행렬식은 0이다.

2.1. 소행렬식과 여인자

n × n 정사각행렬 A의 (i, j) 소행렬식(M_ij)은 A의 i행과 j열을 지워서 얻어진 행렬식이다. A의 여인자(C_ij)는 소행렬식에 (-1)^{i + j}를 곱한 값이다. 즉, 다음과 같다.

: $C_{ij} = (-1)^{i+j}M_{ij}$

예를 들어, 다음과 같은 행렬 A가 있다고 하자.

: $A =\begin{bmatrix}1 & 2 & 3 \\4 & 5 & 6 \\7 & 8 & 9\end{bmatrix}$

이 행렬의 (2, 3) 소행렬식과 여인자는 각각 다음과 같이 계산된다.

: $M_{23} =\begin{vmatrix}1 & 2 & \Box \\\Box & \Box & \blacksquare \\7 & 8 & \Box\end{vmatrix} = \begin{vmatrix}1 & 2 \\7 & 8\end{vmatrix} = -6$

: $C_{23} = (-1)^{2+3}\begin{vmatrix}1 & 2 \\7 & 8\end{vmatrix}= -\begin{vmatrix}1 & 2 \\7 & 8\end{vmatrix} = 6$

2.2. 라플라스 전개의 공식

n × n 행렬의 행렬식은 고정된 행의 각 항과 그의 여인자의 곱으로 전개할 수 있다.

: $|A| = \sum_{j=1}^n a_{ij}C_{ij}$

비슷하게, 고정된 열에 대하여 전개할 수도 있다.

: $|A| = \sum_{i=1}^n a_{ij}C_{ij}$

예를 들어 다음과 같은 행렬을 보자.

: $B = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}.$

이 행렬의 행렬식은 임의의 행이나 열을 따라 라플라스 전개를 사용하여 계산할 수 있다. 예를 들어, 첫 번째 행을 따라 전개하면 다음과 같다.

: $\begin{align}|B| & = 1 \cdot \begin{vmatrix} 5 & 6 \\ 8 & 9 \end{vmatrix} - 2 \cdot \begin{vmatrix} 4 & 6 \\ 7 & 9 \end{vmatrix} + 3 \cdot \begin{vmatrix} 4 & 5 \\ 7 & 8 \end{vmatrix} \\[5pt]& = 1 \cdot (-3) - 2 \cdot (-6) + 3 \cdot (-3) = 0.\end{align}$

두 번째 열을 따라 라플라스 전개를 해도 같은 결과를 얻는다.

: $\begin{align}|B| & = -2 \cdot \begin{vmatrix} 4 & 6 \\ 7 & 9 \end{vmatrix} + 5 \cdot \begin{vmatrix} 1 & 3 \\ 7 & 9 \end{vmatrix} - 8 \cdot \begin{vmatrix} 1 & 3 \\ 4 & 6 \end{vmatrix} \\[5pt]& = -2 \cdot (-6) + 5 \cdot (-12) - 8 \cdot (-6) = 0.\end{align}$

이 행렬은 첫 번째 열과 세 번째 열의 합이 두 번째 열의 두 배이므로 특이 행렬이며, 따라서 행렬식은 0이다.

3. 라플라스 전개의 일반화

라플라스 전개는 하나의 행이나 열뿐만 아니라, 여러 개의 행 또는 열에 대해서도 일반화할 수 있다.

$B=[b_{ij}]$ 를 $n \times n$ 행렬이라고 하고, $S$ 를 ${1, 2, ... , n}$ 의 $k$ -원소 부분 집합의 집합이라고 하자. $H$ 를 그 안에 있는 원소라고 하면, $B$ 의 행렬식은 $H$ 로 식별되는 $k$ 행을 따라 다음과 같이 전개될 수 있다.

: $|B| = \sum_{L\in S} \varepsilon^{H,L} b_{H,L} c_{H,L}$

여기서 $\varepsilon^{H,L}$ 는 $H$ 와 $L$ 에 의해 결정되는 순열의 부호로, $(-1)^{\left(\sum_{h\in H}h\right) + \left(\sum_{\ell\in L}\ell\right)}$ 와 같고, $b_{H,L}$ 는 $B$ 에서 $H$ 와 $L$ 에 있는 인덱스를 가진 행과 열을 제거하여 얻은 $B$ 의 정방 부분 행렬이며, $c_{H,L}$ ( $b_{H,L}$ 의 보수라고 함)는 $b_{H',L'}$ 로 정의되며, $H'$ 와 $L'$ 은 각각 $H$ 와 $L$ 의 보수이다.

이는 $k=1$ 일 때, 즉 하나의 행 또는 열에 대한 라플라스 전개와 일치한다. 고정된 모든 $k$ 열에 대해서도 동일하게 적용된다.

3.1. 여러 행 또는 열에 대한 전개

라플라스 전개는 임의의 k개의 행에 대한 전개로 일반화할 수 있다. I, J를 {1, ..., n}의 k원소 부분 집합이라고 하자. 즉, k개의 행과 열을 의미한다. A_I,J는 A에서 행 첨수가 I에, 열 첨수가 J에 있는 원소만을 골라내어 얻는 행렬식이다. M_I,J는 A에서 행 첨수가 I에, 열 첨수가 J에 있는 원소만을 제거하여 얻는 행렬식이다.

그렇다면, 행렬식은 고정된 k개의 행 I에 대하여 다음과 같이 전개된다.

: $|A| = \sum_{|J|=k} (-1)^{\sum I+\sum J} A_{I,J}M_{I,J}$

비슷하게, 행렬식은 고정된 k개의 열 J에 대하여 다음과 같이 전개된다.

: $|A| = \sum_{|I|=k} (-1)^{\sum I+\sum J} A_{I,J}M_{I,J}$

여러 행에 대한 라플라스 전개는 필산하기에 복잡하지만, 이론적으로 유용하다.

다음과 같은 행렬을 생각해보자.

: $A = \begin{bmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 \end{bmatrix}.$

이 행렬의 행렬식은 처음 두 행에 대한 라플라스 여인자 전개를 사용하여 계산할 수 있다. {1, 2, 3, 4}에는 6개의 서로 다른 두 숫자의 집합이 있다. 즉, $S=\left\{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}\right\}$ 이다.

보완 여인자를 다음과 같이 정의한다.

: $b_{\{j,k\}}=\begin{vmatrix} a_{1j} & a_{1k} \\ a_{2j} & a_{2k} \end{vmatrix},$
: $c_{\{p,q\}}=\begin{vmatrix} a_{3p} & a_{3q} \\ a_{4p} & a_{4q} \end{vmatrix},$

그리고 그들의 순열의 부호를 다음과 같이 정의한다.

: $\varepsilon^{\{j,k\},\{p,q\}} = \sgn\begin{bmatrix} 1 & 2 & 3 & 4 \\ j & k & p & q \end{bmatrix}, \text{ 여기서 } p\neq j,q\neq k.$

A의 행렬식은 다음과 같이 쓸 수 있다.

: $|A| = \sum_{H \in S} \varepsilon^{H,H^\prime}b_{H}c_{H^\prime},$

여기서 $H^{\prime}$ 는 $H$ 의 보완 집합이다.

위의 예시에서 계산하면 다음과 같다.

: $\begin{align}|A| &= b_{\{1,2\}}c_{\{3,4\}} -b_{\{1,3\}}c_{\{2,4\}} +b_{\{1,4\}}c_{\{2,3\}}+b_{\{2,3\}}c_{\{1,4\}} -b_{\{2,4\}}c_{\{1,3\}} +b_{\{3,4\}}c_{\{1,2\}} \\[5pt]&= \begin{vmatrix} 1 & 2 \\ 5 & 6 \end{vmatrix} \cdot \begin{vmatrix} 11 & 12 \\ 15 & 16 \end{vmatrix}- \begin{vmatrix} 1 & 3 \\ 5 & 7 \end{vmatrix} \cdot \begin{vmatrix} 10 & 12 \\ 14 & 16 \end{vmatrix}+ \begin{vmatrix} 1 & 4 \\ 5 & 8 \end{vmatrix} \cdot \begin{vmatrix} 10 & 11 \\ 14 & 15 \end{vmatrix}+ \begin{vmatrix} 2 & 3 \\ 6 & 7 \end{vmatrix} \cdot \begin{vmatrix} 9 & 12 \\ 13 & 16 \end{vmatrix}- \begin{vmatrix} 2 & 4 \\ 6 & 8 \end{vmatrix} \cdot \begin{vmatrix} 9 & 11 \\ 13 & 15 \end{vmatrix}+ \begin{vmatrix} 3 & 4 \\ 7 & 8 \end{vmatrix} \cdot \begin{vmatrix} 9 & 10 \\ 13 & 14 \end{vmatrix}\\[5pt]&= -4 \cdot (-4) -(-8) \cdot (-8) +(-12) \cdot (-4) +(-4) \cdot (-12) -(-8) \cdot (-8) +(-4) \cdot (-4)\\[5pt]&= 16 - 64 + 48 + 48 - 64 + 16 = 0.\end{align}$

행렬의 첫 번째 열과 세 번째 열의 합이 두 번째 열의 두 배이므로 행렬은 특이 행렬이며, 따라서 행렬식은 0이다.

B=[b_ij]를 n × n 행렬이라고 하고, S를 {1, 2, ... , n}의 k-원소 부분 집합의 집합이라고 하자. H를 그 안에 있는 원소라고 하면, B의 행렬식은 H로 식별되는 k 행을 따라 다음과 같이 전개될 수 있다.

: $|B| = \sum_{L\in S} \varepsilon^{H,L} b_{H,L} c_{H,L}$

여기서 $\varepsilon^{H,L}$ 는 H와 L에 의해 결정되는 순열의 부호로, $(-1)^{\left(\sum_{h\in H}h\right) + \left(\sum_{\ell\in L}\ell\right)}$ 와 같고, b_H,L는 B에서 H와 L에 있는 인덱스를 가진 행과 열을 제거하여 얻은 B의 정방 부분 행렬이며, c_H,L(b_H,L의 보수라고 함)는 b_H',L'로 정의되며, H'와 L'은 각각 H와 L의 보수이다.

이는 k=1일 때 위의 정리와 일치한다. 고정된 모든 k 열에 대해서도 동일하게 적용된다.

4. 고전적 수반 행렬

어떤 행렬의 각 항의 여인자를 그 항의 위치로 하여 얻는 행렬의 전치 행렬을 그 행렬의 고전적 수반 행렬이라고 한다. 행렬과 그 고전적 수반 행렬의 곱은 다음과 같다.

: $A\operatorname{adj}A=(\operatorname{adj}A)A=|A|I$

5. 라플라스 전개의 예시

3 × 3 행렬의 경우, 다음과 같이 계산할 수 있다.

: $A = \begin{bmatrix}1 & 2 & 3 \\4 & 5 & 6 \\7 & 8 & 9 \end{bmatrix}$

1행에 대한 라플라스 전개를 이용하면 다음과 같다.

: $\begin{align}|A|&= (-1)^{1+1}1\begin{vmatrix}5 & 6 \\8 & 9 \end{vmatrix}+(-1)^{1+2}2\begin{vmatrix}4 & 6 \\7 & 9 \end{vmatrix}+(-1)^{1+3}3\begin{vmatrix}4 & 5 \\7 & 8 \end{vmatrix} \\&= 1(-3) - 2(-6) + 3(-3) \\&= 0\end{align}$

2열에 대하여 전개하여도 같은 결과를 얻는다.

: $\begin{align}|A|&= (-1)^{2+1}2\begin{vmatrix}4 & 6 \\7 & 9 \end{vmatrix}+(-1)^{2+2}5\begin{vmatrix}1 & 3 \\7 & 9 \end{vmatrix}+(-1)^{2+3}8\begin{vmatrix}1 & 3 \\4 & 6 \end{vmatrix} \\&= - 2(-6) + 5(-12) - 8(-6) \\&= 0\end{align}$

A는 1행과 3행의 합이 2행의 2배이므로, 특이 행렬이다. 따라서 행렬식은 0이다.

4 × 4 행렬의 경우, 다음과 같이 계산할 수 있다.

: $A=\begin{bmatrix}1 & 2 & 1 & 4 \\0 & -1 & 2 & 1 \\1 & 0 & 1 & 3 \\0 & 1 & 3 & 1 \end{bmatrix}$

1행에 대한 라플라스 전개를 이용하면, 각 소행렬식은 다시 3 × 3 행렬식이므로, 이들 역시 라플라스 전개로 계산한다.

: $\begin{align}M_{11}&=\begin{vmatrix}-1 & 2 & 1 \\0 & 1 & 3 \\1 & 3 & 1 \end{vmatrix}=-1\begin{vmatrix}1 & 3 \\3 & 1 \end{vmatrix} -2\begin{vmatrix}0 & 3 \\1 & 1 \end{vmatrix} +1\begin{vmatrix}0 & 1 \\1 & 3 \end{vmatrix}\\&=-1(1-9)-2(0-3)+1(0-1)=13\end{align}$

: $\begin{align}M_{12}&=\begin{vmatrix}0 & 2 & 1 \\1 & 1 & 3 \\0 & 3 & 1 \end{vmatrix}=0\begin{vmatrix}1 & 3 \\3 & 1 \end{vmatrix} -2\begin{vmatrix}1 & 3 \\0 & 1 \end{vmatrix} +1\begin{vmatrix}1 & 1 \\0 & 3 \end{vmatrix}\\&=-2(1-0)+1(3-0)=1\end{align}$

: $\begin{align}M_{13}&=\begin{vmatrix}0 & -1 & 1 \\1 & 0 & 3 \\0 & 1 & 1 \end{vmatrix}=0\begin{vmatrix}0 & 3 \\1 & 1 \end{vmatrix}-(-1)\begin{vmatrix}1 & 3 \\0 & 1 \end{vmatrix}+1\begin{vmatrix}1 & 0 \\0 & 1 \end{vmatrix}\\&=1(1-0)+1(1-0)=2\end{align}$

: $\begin{align}M_{14}&=\begin{vmatrix}0 & -1 & 2 \\1 & 0 & 1 \\0 & 1 & 3 \end{vmatrix}=0\begin{vmatrix}0 & 1 \\1 & 3 \end{vmatrix}-(-1)\begin{vmatrix}1 & 1 \\0 & 3 \end{vmatrix}+2\begin{vmatrix}1 & 0 \\0 & 1 \end{vmatrix}\\&=1(3-0)+2(1-0)=5\end{align}$

따라서 행렬식은 다음과 같다.

: $|A| = 1M_{11} - 2M_{12} + 1M_{13} - 4M_{14} = 13 - 2 + 2 - 20 = -7$

4 × 4 행렬의 행렬식을 1행과 2행에 대한 라플라스 전개를 통해 계산하면 다음과 같다.

: $\begin{array}{rcl}|A|&=&(-1)^{1+2+1+2}\begin{vmatrix}1 & 2 \\ 0 & -1 \end{vmatrix}\begin{vmatrix}1 & 3 \\ 3 & 1 \end{vmatrix}+(-1)^{1+2+1+3}\begin{vmatrix}1 & 1 \\ 0 & 2 \end{vmatrix}\begin{vmatrix}0 & 3 \\ 1 & 1 \end{vmatrix}+(-1)^{1+2+1+4}\begin{vmatrix}1 & 4 \\ 0 & 1 \end{vmatrix}\begin{vmatrix}0 & 1 \\ 1 & 3 \end{vmatrix} \\& &{}+(-1)^{1+2+2+3}\begin{vmatrix}2 & 1 \\ -1 & 2 \end{vmatrix}\begin{vmatrix}1 & 3 \\ 0 & 1 \end{vmatrix}+(-1)^{1+2+2+4}\begin{vmatrix}2 & 4 \\ -1 & 1 \end{vmatrix}\begin{vmatrix}1 & 1 \\ 0 & 3 \end{vmatrix}+(-1)^{1+2+3+4}\begin{vmatrix}1 & 4 \\ 2 & 1 \end{vmatrix}\begin{vmatrix}1 & 0 \\ 0 & 1 \end{vmatrix} \\&=&(-1)(-8) - 2(-3) + 1(-1) + 5 -6 - 7\\&=&-7\end{array}$

6. 라플라스 전개의 증명

치환^한국어(순열)을 이용한 증명과 다중선형성을 이용한 증명을 제시한다.

; 치환을 이용한 증명

$k\in\{1,\ldots,n\}$ 에 대하여, 함수 $\mu_k$ 를 다음과 같이 정의한다.

: $\mu_k\colon\{1,\ldots,n-1\}\to\{1,\ldots,n\}$
: $\mu_k\colon x\mapsto\begin{cases}x&x\in\{1,\ldots,k-1\}\\x+1&x\in\{k,\ldots,n-1\}\end{cases}$

즉, $\mu_k$ 는 $k$ 이상의 원소들을 뒤로 한 칸 밀며, 나머지 원소들은 움직이지 않는다.

이때, 함수

: $\{\sigma\in S_n\colon\sigma_i=j\}\to S_{n-1}$
: $\sigma\mapsto\mu_j^{-1}\sigma\mu_i$

는 일대일 대응이다.

행렬식의 라이프니츠 공식에서 $a_{ij}$ 를 포함하는 항

: $\sgn\sigma\,a_{1\sigma_1}\cdots a_{ij}\cdots a_{n\sigma_n}$

을 생각하고, 다음과 같이 정의한다.

: $\tau=\mu_j^{-1}\sigma\mu_i\in S_{n-1}$
: $\tau'=\tau\mu_j^{-1}\sqcup\operatorname{id}_{\{j\}}\in S_n$

그러면,

: $\sgn\tau=\sgn\tau'$

이며,

: $\sigma=\nu\tau'$
: $\nu=\begin{cases}\operatorname{id}_{\{1,\ldots,n\}}& i=j\\(\sigma_j,\sigma_{j-1},\ldots,\sigma_{i+2},\sigma_{i+1},j)&i j\end{cases}\in S_n$

이다. 또한, $\nu$ 는 $|i-j|$ 개의 호환으로 표현할 수 있으므로,

: $\sgn\sigma=(-1)^$

👆

좌우로 밀어서 보기

\sgn\tau'=(-1)^{i+j}\sgn\tau

이다. 따라서,

:

\begin{align}|A|&=\sum_{\sigma\in S_n}\sgn\sigma\,a_{1\sigma_1}\cdots a_{n\sigma_n}\\&=\sum_{j=1}^n\sum_{\sigma_i=j}\sgn\sigma\,a_{1\sigma_1}\cdots a_{ij}\cdots a_{n\sigma_n}\\&=\sum_{j=1}^n\sum_{\tau\in S_{n-1}}(-1)^{i+j}\sgn\tau\,a_{1\sigma_1}\cdots a_{ij}\cdots a_{n\sigma_n}\\&=\sum_{j=1}^n(-1)^{i+j}a_{ij}\sum_{\tau\in S_{n-1}}\sgn\tau\,a_{1\sigma_1}\cdots a_{i-1,\sigma_{i-1}}a_{i+1,\sigma_{i+1}}\cdots a_{n\sigma_n}\\&=\sum_{j=1}^n(-1)^{i+j}a_{ij}M_{ij}\\&=\sum_{j=1}^na_{ij}C_{ij}\end{align}

이다.

위 증명과 비슷하게, 다음 대상들을 정의한다. (

[n]=\{1,\ldots,n\}

)

*

k

원소 집합

K\subseteq[n]

에 대하여,

\mu_K\colon[n-k]\to[n]

은

[n]\setminus K

의 원소들을 뒤로 밀어

K

의 원소들에 공백이 생기도록 하는 함수이다.
* 다음과 같은 일대일 대응이 존재한다.
*:

\{\sigma\in S_n\colon \sigma(I)=J\}\to S_k\times S_{n-k}

\sigma\mapsto(\mu_{\sigma([n]\setminus I)}^{-1}\sigma\mu_{[n]\setminus I},\mu_J^{-1}\sigma\mu_I)

행렬식의 라이프니츠 공식에서,

\sigma(I)=J

인 항

:

\sgn\sigma\,a_{1\sigma_1}\cdots a_{n\sigma_n}

을 생각하고 다음과 같이 정의한다.

:

\tau_1=\mu_{\sigma([n]\setminus I)}^{-1}\sigma\mu_{[n]\setminus I}\in S_k

\tau_2=\mu_J^{-1}\sigma\mu_I\in S_{n-k}

그러면,

\sigma

는 다음과 같이

\operatorname{id}_n

으로 환원된다.

*

\sigma(I)

의 원소를 순서대로 돌려 놓는다. 치환의 부호는

\sgn\tau_1

과 같다.
*

\sigma([n]\setminus I)

의 원소를 순서대로 돌려 놓는다. 치환의 부호는

\sgn\tau_2

와 같다.
*

i\in I

에 대하여,

\sigma(i)

를

i

번째로 돌려 놓는다. 치환의 부호는

(-1)^{\sum I+\sum J}

와 같다.

그러므로,

:

\sgn\sigma=(-1)^{\sum I+\sum J}\sgn\tau_1\sgn\tau_2

이며, 따라서

:

\begin{align}|A|&=\sum_{\sigma\in S_n}\sgn\sigma\,a_{1\sigma_1}\cdots a_{n\sigma_n}\\&=\sum_{|J|=k}\sum_{\sigma(I)=J}\sgn\sigma\,a_{1\sigma_1}\cdots a_{n\sigma_n}\\&=\sum_{|J|=k}\sum_{\sigma(I)=J}(-1)^{\sum I+\sum J}\sgn\tau_1\sgn\tau_2\,a_{1\sigma_1}\cdots a_{n\sigma_n}\\&=\sum_{|J|=k}(-1)^{\sum I+\sum J}\left(\sum_{\sigma(I)=J}\sgn\tau_1\prod_{i\in I}a_{i\sigma_i}\right)\left(\sum_{\sigma(I)=J}\sgn\tau_2\prod_{i\in[n]\setminus I}a_{i\sigma_i}\right)\\&=\sum_{|J|=k}(-1)^{\sum I+\sum J}\left(\sum_{\tau_1\in S_k}\sgn\tau_1\prod_{i\in I}a_{i\sigma_i}\right)\left(\sum_{\tau_2\in S_{n-k}}\sgn\tau_2\prod_{i\in[n]\setminus I}a_{i\sigma_i}\right)\\&=\sum_{|J|=k}(-1)^{\sum I+\sum J}A_{I,J}M_{I,J}\end{align}

; 다중선형성을 이용한 증명

B

가 n × n 행렬이고

i,j\in\{1,2,\dots,n\}

이라고 가정하고,

B

의

i,j

소행렬

M_{ij}

을 구성하는

B

의 항목을

(a_{st})

for

1 \le s,t \le n-1

로 표시한다.

|B|

의 전개식에서

b_{ij}

를 인수로 갖는 항들을 고려하면, 각 항은

:

\sgn \tau\,b_{1,\tau(1)} \cdots b_{i,j} \cdots b_{n,\tau(n)}= \sgn \tau\,b_{ij} a_{1,\sigma(1)} \cdots a_{n-1,\sigma(n-1)}

형태를 갖는다. 여기서

\tau\in S_n

는

\tau(i)=j

인 순열이고,

\tau

와 동일한 소행렬 항목을 선택하는 고유하고 분명히 관련된 순열

\sigma\in S_{n-1}

이 존재한다. 마찬가지로,

\sigma

의 각 선택은 해당

\tau

를 결정한다. 즉,

\sigma\leftrightarrow\tau

의 대응은

S_{n-1}

과

\{\tau\in S_n\colon\tau(i)=j\}

사이의 전단사이다.

코시의 두 줄 표기법을 사용하여,

\tau

와

\sigma

사이의 명시적 관계는 다음과 같이 쓸 수 있다.

:

\sigma = \begin{pmatrix} 1 & 2 & \cdots & i & \cdots &  n-1 \\ (\leftarrow)_j ( \tau(1) ) & (\leftarrow)_j ( \tau(2) ) & \cdots & (\leftarrow)_j ( \tau(i+1) ) & \cdots & (\leftarrow)_j ( \tau(n) ) \end{pmatrix}

여기서

(\leftarrow)_j

는 사이클

(n,n-1,\cdots,j+1,j)

에 대한 임시 약식 표기법이다.

이 연산은 모든 인덱스가 집합 {1,2,...,n-1}에 맞도록 j보다 큰 모든 인덱스를 감소시킨다.

순열

\tau

는 다음과 같이

\sigma

에서 파생될 수 있다.

\sigma'\in S_n

을

\sigma'(k) = \sigma(k)

for

1 \le k \le n-1

and

\sigma'(n) = n

으로 정의한다.

그러면

\sigma'

는 다음과 같이 표현된다.

:

\sigma' = \begin{pmatrix} 1 & 2 & \cdots & i & \cdots &  n-1 & n \\ (\leftarrow)_j ( \tau(1) ) & (\leftarrow)_j ( \tau(2) ) & \cdots & (\leftarrow)_j ( \tau(i+1) ) & \cdots & (\leftarrow)_j ( \tau(n) ) & n \end{pmatrix}

이제, 먼저

(\leftarrow)_i

를 적용한 다음

\sigma'

을 적용하는 연산은 (A를 B 전에 적용하는 것은 두 줄 표기법에서 B의 상단 행에 A의 역을 적용하는 것과 동일하다는 점에 유의)

:

\sigma' (\leftarrow)_i = \begin{pmatrix} 1 & 2 &  \cdots & i+1 & \cdots &  n & i \\ (\leftarrow)_j ( \tau(1) ) & (\leftarrow)_j ( \tau(2) ) & \cdots & (\leftarrow)_j ( \tau(i+1) ) & \cdots & (\leftarrow)_j ( \tau(n) ) & n \end{pmatrix}

여기서

(\leftarrow)_i

는

(n,n-1,\cdots,i+1,i)

에 대한 임시 약식 표기법이다.

\tau

를 먼저 적용한 다음

(\leftarrow)_j

를 적용하는 연산은 다음과 같다.

:

(\leftarrow)_j \tau = \begin{pmatrix} 1 & 2 & \cdots & i & \cdots &  n-1 & n \\ (\leftarrow)_j ( \tau(1) ) & (\leftarrow)_j ( \tau(2) ) & \cdots & n & \cdots & (\leftarrow)_j ( \tau(n-1) ) &(\leftarrow)_j ( \tau(n) ) \end{pmatrix}

위의 두 개는 같으므로,

:

(\leftarrow)_j \tau  = \sigma' (\leftarrow)_i

\tau =  (\rightarrow)_j \sigma' (\leftarrow)_i

여기서

(\rightarrow)_j

는

(\leftarrow)_j

의 역으로

(j,j+1,\cdots,n)

이다.

따라서

:

\tau\,=(j,j+1,\ldots,n)\sigma'(n,n-1,\ldots,i)

두 개의 사이클은 각각

n-i

와

n-j

전치로 쓸 수 있으므로,

:

\sgn\tau\,= (-1)^{2n-(i+j)} \sgn\sigma'\,= (-1)^{i+j} \sgn\sigma.

그리고

\sigma\leftrightarrow\tau

의 사상은 전단사이므로,

:

\begin{align}\sum_{i=1}^n\sum_{\tau \in S_n:\tau(i)=j} \sgn \tau\,b_{1,\tau(1)} \cdots b_{n,\tau(n)}&= \sum_{i=1}^{n}\sum_{\sigma \in S_{n-1}} (-1)^{i+j}\sgn\sigma\, b_{ij}a_{1,\sigma(1)} \cdots a_{n-1,\sigma(n-1)}\\&= \sum_{i=1}^{n}b_{ij}(-1)^{i+j} \sum_{\sigma \in S_{n-1}} \sgn\sigma\,a_{1,\sigma(1)} \cdots a_{n-1,\sigma(n-1)}\\&= \sum_{i=1}^{n} b_{ij} (-1)^{i+j} M_{ij}\end{align}

으로부터 결과가 도출된다. 마찬가지로, 외부 합의 인덱스를

j

로 바꾸어도 결과가 성립한다.

7. 라플라스 전개의 계산 복잡도

라플라스 전개는 고차원 행렬의 경우 계산 비용이 많이 든다. 이는 시간 복잡도가 점근 표기법으로 O(n!)이기 때문이다. 반면, LU 분해와 같이 삼각 행렬로 분해하는 방법을 사용하면 시간 복잡도가 O(n³)으로 결정될 수 있다.

여인자 전개는 고차 행렬에 대해서는 계산적으로 비효율적이다. 그 이유는 N차 정사각 행렬에 대해 계산의 오더는 N!이기 때문이다. 따라서, 여인자 전개는 큰 N에 대해서는 적절하지 않다. LU 분해에서처럼 삼각 행렬로 분해하면 행렬식을 N³/3의 오더로 결정할 수 있다.

8. 역사

알렉상드르테오필 방데르몽드는 행렬식의 두 행에 대한 전개를 제시하였다. 피에르시몽 라플라스는 1772년 논문 《Recherches sur Ie calcul integral et sur Ie systeme du monde,》에서 행렬식 전개를 임의 개수 행에 대한 전개로 일반화하였다. 오귀스탱 루이 코시는 라플라스의 전개 정리를 더 현대적인 용어로 서술·증명하였다.