Laplace expansion

선형 대수(linear algebra)에서, 라플라스 전개(Laplace expansion)는, 피에르-시몽 라플라스(Pierre-Simon Laplace)의 이름을 따서 지었으며, 역시 여인수 전개(cofactor expansion)라고 불리며, $n \times n$ 행렬 $B$ 의 행렬식(determinant)을 소행렬식(minors)의 가중된 합으로 표현한 것이며, 소행렬식은 $B$ 의 일부 $(n - 1) \times (n - 1)$ 부분행렬(submatrices)의 행렬식입니다. 구체적으로, 모든 각 $i$ 에 대해, ${\begin{aligned}\det(B)&=\sum _{j=1}^{n}(-1)^{i+j}b_{i,j}m_{i,j},\end{aligned}}$ 여기서 $b_{i,j}$ 는 $B$ 의 $i$ -번째 행과 $j$ -번째 열의 엔트리이고, $m_{i,j}$ 는 $B$ 의 $i$ -번째 행과 $j$ -번째 열을 제거함으로써 얻은 부분행렬의 행렬식입니다.

항 $(-1)^{i+j}M_{i,j}$ 는 $B$ 에서 $B_{i,j}$ 의 여인수(cofactor)라고 불립니다.

라플라스 전개는 종종, 예를 들어 행렬 크기에 대한 재귀(recursion)를 허용하는 것과 같이 증명에 유용합니다. 그것은 역시 단순함과 행렬식을 보고 계산하기 위한 여러 방법 중 하나라는 점에서 교훈적인 흥미를 불러일으킵니다. 큰 행렬에 대해, 그것은 가우스 소거법(Gaussian elimination)과 비교될 때 빠르게 계산하는 것이 비효율적입니다.

Examples

다음 행렬을 생각해 보십시오:

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

이 행렬의 행렬식은 해당 행 또는 열 중 임의의 하나를 따라 라플라스 전개를 사용함으로써 계산될 수 있습니다. 예를 들어, 첫 번째 행을 따라 전개는 다음을 산출합니다:

{\begin{aligned}|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{aligned}}

두 번째 열을 따라 라플라스를 전개는 같은 결과를 산출합니다:

{\begin{aligned}|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{aligned}}

결과가 올바른지 쉽게 확인할 수 있습니다: 행렬은 그것의 첫 번째 열과 세 번째 열의 합이 두 번째 열의 두 배이고, 따라서 그것의 행렬식은 영이므로 특이(singular)입니다.

Proof

$B$ 가 n × n 행렬이고 $i,j\in \{1,2,\dots ,n\}$ 라고 가정합니다. 명확성을 위해, 우리는 역시 $i,j$ 소행렬 $M_{ij}$ 를 다음으로 구성하는 $B$ 의 엔트리를 분류합니다:

(a_{st})

for

1\leq s,t\leq n-1.

$b_{ij}$ 를 인수로 가지는 $|B|$ 의 전개에서 항을 생각해 보십시오. 각각은 $\tau (i)=j$ 를 갖는 일부 순열 $τ \in S n$ , 및 $τ$ 와 같은 소행렬 엔트리를 선택하는 고유하고 명백하게 관련된 순열 $\sigma \in S_{n-1}$ 에 대해 다음 형식을 가지고 있습니다:

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

마찬가지로, $σ$ 의 각 선택은 대응하는 $τ$ 를 결정합니다. 즉, 대응 $\sigma \leftrightarrow \tau$ 는 $S_{n-1}$ 과 $\{\tau \in S_{n}\colon \tau (i)=j\}$ 사이의 전단사(bijection)입니다. 코시의 두-줄 표기법(Cauchy's two-line notation)을 사용하여, $\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보다 큰 모든 인덱스를 감소시킵니다.

순열 $τ$ 는 다음과 같이 $σ$ 에서 유도될 수 있습니다. $\sigma '\in S_{n}$ 를 $1\leq k\leq n-1$ 와 $\sigma '(n)=n$ 에 대해 $\sigma '(k)=\sigma (k)$ 로 정의합니다. 그런-다음 $\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$ 전치(transpositions)로 쓸 수 있으므로,

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

그리고 맵 $\sigma \leftrightarrow \tau$ 은 전단사이기 때문에,

{\begin{aligned}\sum _{i=1}^{n}\sum _{\tau \in S_{n}:\tau (i)=j}\operatorname {sgn} \tau \,b_{1,\tau (1)}\cdots b_{n,\tau (n)}&=\sum _{i=1}^{n}\sum _{\sigma \in S_{n-1}}(-1)^{i+j}\operatorname {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}}\operatorname {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{aligned}}

이것으로부터 결과가 따라옵니다. 유사하게, 그 결과는 만약 밖의 합의 인덱스가 $j$ 로 대체되면 유지됩니다.

Laplace expansion of a determinant by complementary minors

라플라스의 여인수 전개는 다음과 같이 일반화될 수 있습니다.

Example

다음 행렬을 생각해 보십시오:

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\}}=\operatorname {sgn} {\begin{bmatrix}1&2&3&4\\j&k&p&q\end{bmatrix}},{\text{ where }}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{aligned}|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{aligned}}

위와 같이, 결과가 올바른지 쉽게 확인할 수 있습니다: 첫 번째 열과 세 번째 열의 합이 두 번째 열의 두 배이기 때문에 행렬은 특이(singular)이고, 따라서 행렬식은 영입니다.

General statement

$B=[b_{ij}]$ 를 $n \times n$ 행렬이라고 놓고 $S$ 를 ${1, 2, ... , n}$ 의 k-원소 부분집합의 집합이라고 놓고, $H$ 를 그 안에 있는 원소라고 놓습니다. 그런-다음 $B$ 의 행렬식은 다음과 같이 $B$ 로 식별되는 $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$ 행에서 삭제함으로써 얻은 $B$ 의 정사각 소행렬과 각각 $H$ 와 $L$ 에 인덱스를 갖는 열, 및 $b_{H',L'}$ 로 정의된 $c_{H,L}$ ( $b_{H,L}$ 의 여라고 함), $H'$ 와 $L'$ 은 각각 $H$ 와 $L$ 의 여입니다.

이것은 $k=1$ 일 때 위의 정리와 일치합니다. 고정 $k$ 열에 대해서도 마찬가지입니다.

Computational expense

라플라스 전개는 $O (n!)$ 의 큰 O 표기법(big O notation)에서 시간 복잡도(time complexity)를 갖는 고차원 행렬에 대해 계산적으로 비효율적입니다. 대안적으로, LU 분해에서와 같이 삼각 행렬로의 분해를 사용하는 것은 $O (n 3)$ 의 시간 복잡도를 갖는 행렬식을 생성할 수 있습니다.^[1] 다음 Python 코드는 재귀적으로 라플라스 전개를 구현합니다:

def determinant(M):
    # Base case of recursive function: 1x1 matrix
    if len(M) == 1: 
        return M[0][0]

    total = 0
    for column, element in enumerate(M[0]):
        # Exclude first row and current column.
        K = [x[:column] + x[column + 1 :] for x in M[1:]]
        s = 1 if column % 2 == 0 else -1 
        total += s * element * determinant(K)
    return total

References

^ Stoer Bulirsch: Introduction to Numerical Mathematics

David Poole: Linear Algebra. A Modern Introduction. Cengage Learning 2005, ISBN 0-534-99845-3, pp. 265–267 (restricted online copy, p. 265, at Google Books)
Harvey E. Rose: Linear Algebra. A Pure Mathematical Approach. Springer 2002, ISBN 3-7643-6905-1, pp. 57–60 (restricted online copy, p. 57, at Google Books)

External links

Laplace expansion in C (in Portuguese)
Laplace expansion in Java (in Portuguese)

[1] Stoer Bulirsch: Introduction to Numerical Mathematics

[1]