Lecture 19. 행렬식 공식과 여인수 Determinant Formulas and Cofactors — 서술
지난 강의에서는 행렬식의 성질만 다뤘을 뿐 정의는 미뤄 두었다. 세 개의 공리를 만족하는 수가
정말 있는지, 있다면 그 공식이 무엇인지는 답하지 않았다. 이제 공리에서 실제 공식을 뽑아낼
차례이다.
그런데 미리 말해 두자. 이번에 유도할 공식은 실용적으로는 쓸모가 없다. n × n n \times n n × n n ! n! n ! n = 20 n = 20 n = 20 2.4 × 1 0 18 2.4 \times 10^{18} 2.4 × 1 0 18
그럼에도 이 공식을 배우는 이유가 있다. 계산하기 위해서가 아니라, 행렬식이 왜 그런 성질을
갖는지 이해하기 위해서이다. 지난 강의의 성질들이 어디서 왔는지가 이 공식을 보면 한눈에
보인다. 그리고 여기서 얻는 여인수는 다음 강의에서 역행렬의 공식이 된다.
1. 2 × 2 2 \times 2 2 × 2 ¶ L18의 마지막에서 2 × 2 2 \times 2 2 × 2
det [ a b c d ] = a c det [ 1 0 1 0 ] + a d det [ 1 0 0 1 ] + b c det [ 0 1 1 0 ] + b d det [ 0 1 0 1 ] = a d − b c \det\begin{bmatrix} a & b \\ c & d \end{bmatrix}
= ac \det\begin{bmatrix} 1 & 0 \\ 1 & 0 \end{bmatrix}
+ ad \det\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}
+ bc \det\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}
+ bd \det\begin{bmatrix} 0 & 1 \\ 0 & 1 \end{bmatrix}
= ad - bc det [ a c b d ] = a c det [ 1 1 0 0 ] + a d det [ 1 0 0 1 ] + b c det [ 0 1 1 0 ] + b d det [ 0 0 1 1 ] = a d − b c Figure 1: 두 행이 같은 방향을 고른 항은 죽고, 서로 다른 방향을 고른 항만 살아남는다.
여기서 눈여겨볼 것은 답이 아니라 살아남는 규칙 이다. 세 문장으로 줄일 수 있다.
각 행이 좌표축 방향을 하나씩 고른다. 곧 행마다 열을 하나씩 고른다.
두 행이 같은 열 을 고르면 그 항은 죽는다. 두 행이 같아져 성질 1에 걸리기 때문이다.
살아남은 항의 부호는, 남은 0-1 행렬을 I I I 행 교환 횟수의 홀짝 이다.
이 세 문장에는 “2” 라는 숫자가 한 번도 나오지 않는다. n × n n \times n n × n n n n 3 × 3 3 \times 3 3 × 3
2. 3 × 3 3 \times 3 3 × 3 ¶ A A A r 1 , r 2 , r 3 \vv{r}_1, \vv{r}_2, \vv{r}_3 r 1 , r 2 , r 3
r i = a i 1 ( 1 , 0 , 0 ) + a i 2 ( 0 , 1 , 0 ) + a i 3 ( 0 , 0 , 1 ) = ∑ k = 1 3 a i k e k \vv{r}_i = a_{i1}\,(1,0,0) + a_{i2}\,(0,1,0) + a_{i3}\,(0,0,1)
= \sum_{k=1}^{3} a_{ik}\,\vv{e}_k r i = a i 1 ( 1 , 0 , 0 ) + a i 2 ( 0 , 1 , 0 ) + a i 3 ( 0 , 0 , 1 ) = k = 1 ∑ 3 a ik e k 공리 ③을 첫 행에 쓰면 항이 셋, 각 항의 둘째 행에 또 쓰면 아홉, 각 항의 셋째 행에 또 쓰면
스물일곱이 된다. 3 3 = 27 3^3 = 27 3 3 = 27
det A = ∑ p = 1 3 ∑ q = 1 3 ∑ r = 1 3 a 1 p a 2 q a 3 r det [ e p e q e r ] \det A = \sum_{p=1}^{3}\sum_{q=1}^{3}\sum_{r=1}^{3}
a_{1p}\,a_{2q}\,a_{3r} \;
\det\begin{bmatrix} \vv{e}_p \\ \vv{e}_q \\ \vv{e}_r \end{bmatrix} det A = p = 1 ∑ 3 q = 1 ∑ 3 r = 1 ∑ 3 a 1 p a 2 q a 3 r det ⎣ ⎡ e p e q e r ⎦ ⎤ 남은 행렬은 각 행이 0 아니면 1인 행렬이고, 그 행렬식은 공리만으로 값이 정해진다.
p , q , r p, q, r p , q , r 같은 것이 둘 있으면 그 두 행이 똑같은 e \vv{e} e
p = q ⟹ det [ e p e p e r ] = 0 p = q
\quad\Longrightarrow\quad
\det\begin{bmatrix} \vv{e}_p \\ \vv{e}_p \\ \vv{e}_r \end{bmatrix} = 0 p = q ⟹ det ⎣ ⎡ e p e p e r ⎦ ⎤ = 0 그러므로 살아남는 것은 p , q , r p, q, r p , q , r 전부 다른 경우뿐이다. 1, 2, 3을 한 번씩 쓰는 배열,
곧 3 ! = 6 3! = 6 3 ! = 6
여섯 개를 하나씩 적어 보자. 남은 행렬은 I I I I I I
( p , q , r ) (p, q, r) ( p , q , r ) 남은 행렬의 행 I I I 행렬식 항 ( 1 , 2 , 3 ) (1,2,3) ( 1 , 2 , 3 ) e 1 , e 2 , e 3 \vv{e}_1, \vv{e}_2, \vv{e}_3 e 1 , e 2 , e 3 0번 +1 + a 11 a 22 a 33 +\,a_{11}a_{22}a_{33} + a 11 a 22 a 33 ( 2 , 3 , 1 ) (2,3,1) ( 2 , 3 , 1 ) e 2 , e 3 , e 1 \vv{e}_2, \vv{e}_3, \vv{e}_1 e 2 , e 3 , e 1 2번 +1 + a 12 a 23 a 31 +\,a_{12}a_{23}a_{31} + a 12 a 23 a 31 ( 3 , 1 , 2 ) (3,1,2) ( 3 , 1 , 2 ) e 3 , e 1 , e 2 \vv{e}_3, \vv{e}_1, \vv{e}_2 e 3 , e 1 , e 2 2번 +1 + a 13 a 21 a 32 +\,a_{13}a_{21}a_{32} + a 13 a 21 a 32 ( 1 , 3 , 2 ) (1,3,2) ( 1 , 3 , 2 ) e 1 , e 3 , e 2 \vv{e}_1, \vv{e}_3, \vv{e}_2 e 1 , e 3 , e 2 1번 -1 − a 11 a 23 a 32 -\,a_{11}a_{23}a_{32} − a 11 a 23 a 32 ( 2 , 1 , 3 ) (2,1,3) ( 2 , 1 , 3 ) e 2 , e 1 , e 3 \vv{e}_2, \vv{e}_1, \vv{e}_3 e 2 , e 1 , e 3 1번 -1 − a 12 a 21 a 33 -\,a_{12}a_{21}a_{33} − a 12 a 21 a 33 ( 3 , 2 , 1 ) (3,2,1) ( 3 , 2 , 1 ) e 3 , e 2 , e 1 \vv{e}_3, \vv{e}_2, \vv{e}_1 e 3 , e 2 , e 1 1번 -1 − a 13 a 22 a 31 -\,a_{13}a_{22}a_{31} − a 13 a 22 a 31
교환 횟수를 한 줄만 따라가 보자. ( 2 , 3 , 1 ) (2,3,1) ( 2 , 3 , 1 ) e 2 , e 3 , e 1 \vv{e}_2, \vv{e}_3, \vv{e}_1 e 2 , e 3 , e 1 e 3 , e 2 , e 1 \vv{e}_3, \vv{e}_2, \vv{e}_1 e 3 , e 2 , e 1 e 1 , e 2 , e 3 = I \vv{e}_1, \vv{e}_2, \vv{e}_3 = I e 1 , e 2 , e 3 = I det = ( − 1 ) 2 = + 1 \det = (-1)^2 = +1 det = ( − 1 ) 2 = + 1
여섯 항을 모으면 익숙한 공식이 나온다.
det A = a 11 a 22 a 33 + a 12 a 23 a 31 + a 13 a 21 a 32 − a 11 a 23 a 32 − a 12 a 21 a 33 − a 13 a 22 a 31 \det A =
a_{11}a_{22}a_{33} + a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32}
- a_{11}a_{23}a_{32} - a_{12}a_{21}a_{33} - a_{13}a_{22}a_{31} det A = a 11 a 22 a 33 + a 12 a 23 a 31 + a 13 a 21 a 32 − a 11 a 23 a 32 − a 12 a 21 a 33 − a 13 a 22 a 31 외운 공식이 아니라 27개에서 21개를 걷어 내고 남은 것이다.
3. 빅 포뮬러 ¶ 3 × 3 3 \times 3 3 × 3 n × n n \times n n × n
각 행을 n n n n × n × ⋯ × n = n n n \times n \times \cdots \times n = n^n n × n × ⋯ × n = n n 모든 행이 서로 다른 열을 고른 경우 뿐이다.
행마다 열을 하나씩, 겹치지 않게 고르는 방법이 몇 가지인가. 첫 행에 n n n n − 1 n-1 n − 1 n − 2 n-2 n − 2 n ! n! n !
n n 개에서 출발해 n ! 개가 남는다 n^n \text{ 개에서 출발해 } n! \text{ 개가 남는다} n n 개에서 출발해 n ! 개가 남는다 이것이 L5의 순열 이다. 순열 σ \sigma σ i i i σ ( i ) \sigma(i) σ ( i )
Figure 2: 행마다 하나씩, 열이 겹치지 않게 놓는 방법이 곧 순열이다. 체스판에서 서로 공격하지 않게
룩을 놓는 문제와 같다.
계수는 그 자리의 성분들을 곱한 a 1 σ ( 1 ) a 2 σ ( 2 ) ⋯ a n σ ( n ) a_{1\sigma(1)}a_{2\sigma(2)}\cdots a_{n\sigma(n)} a 1 σ ( 1 ) a 2 σ ( 2 ) ⋯ a nσ ( n ) 순열행렬 P σ P_\sigma P σ
det A = ∑ σ a 1 σ ( 1 ) a 2 σ ( 2 ) ⋯ a n σ ( n ) det P σ \det A = \sum_{\sigma} a_{1\sigma(1)}\, a_{2\sigma(2)} \cdots a_{n\sigma(n)}\;\det P_\sigma det A = σ ∑ a 1 σ ( 1 ) a 2 σ ( 2 ) ⋯ a nσ ( n ) det P σ 순열행렬의 행렬식은 왜 ± 1 \pm1 ± 1 ¶ P σ P_\sigma P σ I I I e 1 \vv{e}_1 e 1 e 2 \vv{e}_2 e 2 n − 1 n-1 n − 1 I I I
교환을 k k k k k k
det P σ = ( − 1 ) k det I = ( − 1 ) k \det P_\sigma = (-1)^k \det I = (-1)^k det P σ = ( − 1 ) k det I = ( − 1 ) k 이다. 짝수 번이면 +1, 홀수 번이면 -1 이다.
같은 P σ P_\sigma P σ k k k m m m det P σ \det P_\sigma det P σ P σ P_\sigma P σ 하나의 수 이므로
( − 1 ) k = det P σ = ( − 1 ) m ⟹ k 와 m 의 홀짝이 같다 (-1)^k = \det P_\sigma = (-1)^m
\qquad\Longrightarrow\qquad
k \text{ 와 } m \text{ 의 홀짝이 같다} ( − 1 ) k = det P σ = ( − 1 ) m ⟹ k 와 m 의 홀짝이 같다 이다. 홀짝이 잘 정의된다는 사실을 행렬식이 보증해 주는 셈이다.
이 부호를 sgn σ \operatorname{sgn}\sigma sgn σ (7)
합은 n ! n! n ! 빅 포뮬러 이다.
성질들이 여기서 다시 보인다 ¶ L18에서 공리로부터 유도했던 것들이 이 공식에서도 읽힌다. 같은 결론에 다른 길로 도착하는
셈이다.
0인 행이 있으면 0. i i i a i σ ( i ) = 0 a_{i\sigma(i)} = 0 a iσ ( i ) = 0 n ! n! n !
삼각행렬은 대각의 곱. 상삼각행렬에서는 i > j i > j i > j a i j = 0 a_{ij} = 0 a ij = 0 i i i σ ( i ) ≥ i \sigma(i) \ge i σ ( i ) ≥ i n n n σ ( n ) ≥ n \sigma(n) \ge n σ ( n ) ≥ n σ ( n ) = n \sigma(n) = n σ ( n ) = n σ ( n − 1 ) ≥ n − 1 \sigma(n-1) \ge n-1 σ ( n − 1 ) ≥ n − 1 n n n σ ( n − 1 ) = n − 1 \sigma(n-1) = n-1 σ ( n − 1 ) = n − 1 σ \sigma σ + + +
det U = a 11 a 22 ⋯ a n n \det U = a_{11}a_{22}\cdots a_{nn} det U = a 11 a 22 ⋯ a nn 같은 행이 둘이면 0. p p p q q q k k k a p k = a q k a_{pk} = a_{qk} a p k = a q k σ \sigma σ τ \tau τ
τ ( p ) = σ ( q ) , τ ( q ) = σ ( p ) , τ ( i ) = σ ( i ) ( i ≠ p , q ) \tau(p) = \sigma(q),
\qquad
\tau(q) = \sigma(p),
\qquad
\tau(i) = \sigma(i) \;\;(i \neq p, q) τ ( p ) = σ ( q ) , τ ( q ) = σ ( p ) , τ ( i ) = σ ( i ) ( i = p , q ) τ \tau τ σ \sigma σ
a p τ ( p ) a q τ ( q ) = a p σ ( q ) a q σ ( p ) = a q σ ( q ) a p σ ( p ) a_{p\tau(p)}\,a_{q\tau(q)}
= a_{p\sigma(q)}\,a_{q\sigma(p)}
= a_{q\sigma(q)}\,a_{p\sigma(p)} a p τ ( p ) a q τ ( q ) = a p σ ( q ) a q σ ( p ) = a q σ ( q ) a p σ ( p ) 가운데에서 오른쪽으로 갈 때 a p ⋅ = a q ⋅ a_{p\,\cdot} = a_{q\,\cdot} a p ⋅ = a q ⋅ σ \sigma σ τ \tau τ n ! n! n ! n ! / 2 n!/2 n ! /2
4. 여인수 전개 ¶ n ! n! n ! 첫 행에서 어느 열을 골랐는지 를
기준으로 묶어 보자. 고를 수 있는 열이 n n n n n n
j j j a 1 j a_{1j} a 1 j
det A = ∑ j = 1 n a 1 j D 1 j , D 1 j = ( j 열을 고른 뭉치에서 a 1 j 를 뺀 나머지의 합 ) \det A = \sum_{j=1}^{n} a_{1j}\,D_{1j},
\qquad
D_{1j} = (j \text{ 열을 고른 뭉치에서 } a_{1j} \text{ 를 뺀 나머지의 합}) det A = j = 1 ∑ n a 1 j D 1 j , D 1 j = ( j 열을 고른 뭉치에서 a 1 j 를 뺀 나머지의 합 ) 이제 남은 물음은 하나이다. D 1 j D_{1j} D 1 j
가장 쉬운 경우 — 첫 행이 1열을 골랐을 때 ¶ j = 1 j = 1 j = 1 2 , … , n 2, \dots, n 2 , … , n 2 , … , n 2, \dots, n 2 , … , n A A A ( n − 1 ) × ( n − 1 ) (n-1) \times (n-1) ( n − 1 ) × ( n − 1 )
부호도 그대로이다. σ ( 1 ) = 1 \sigma(1) = 1 σ ( 1 ) = 1 I I I
D 11 = det M 11 , M 11 = ( A 에서 1행과 1열을 지운 것 ) D_{11} = \det M_{11},
\qquad
M_{11} = (A \text{ 에서 1행과 1열을 지운 것}) D 11 = det M 11 , M 11 = ( A 에서 1 행과 1 열을 지운 것 ) 부호를 고칠 것이 없다. 첫 칸이 + + +
일반적인 j j j ¶ j ≠ 1 j \neq 1 j = 1 만들면 된다. j j j
옮기는 방법이 중요하다. 이웃끼리만 바꿔 가며 옮긴다. j j j j − 1 j-1 j − 1 j − 2 j-2 j − 2 j − 1 j-1 j − 1
( 1 , 2 , … , j − 1 , j , j + 1 , … ) ⟶ ( j , 1 , 2 , … , j − 1 , j + 1 , … ) (1, 2, \dots, j-1, \;j,\; j+1, \dots)
\;\longrightarrow\;
(j, \;1, 2, \dots, j-1,\; j+1, \dots) ( 1 , 2 , … , j − 1 , j , j + 1 , … ) ⟶ ( j , 1 , 2 , … , j − 1 , j + 1 , … ) 이웃 교환만 쓰는 데에는 이유가 있다. 이렇게 하면 j j j M 1 j M_{1j} M 1 j j j j j j j
열을 한 번 바꿀 때마다 행렬식의 부호가 뒤집힌다. 열에 대한 이 성질은 L18의
det A T = det A \det A^{\mathsf{T}} = \det A det A T = det A (24) A ′ A' A ′
det A ′ = ( − 1 ) j − 1 det A ⟺ det A = ( − 1 ) j − 1 det A ′ \det A' = (-1)^{\,j-1} \det A
\qquad\Longleftrightarrow\qquad
\det A = (-1)^{\,j-1} \det A' det A ′ = ( − 1 ) j − 1 det A ⟺ det A = ( − 1 ) j − 1 det A ′ 이다. ( − 1 ) j − 1 (-1)^{j-1} ( − 1 ) j − 1 ( − 1 ) j − 1 (-1)^{j-1} ( − 1 ) j − 1 ± 1 \pm1 ± 1
A ′ A' A ′ a 1 j a_{1j} a 1 j M 1 j M_{1j} M 1 j (15) A ′ A' A ′ a 1 j a_{1j} a 1 j + det M 1 j +\det M_{1j} + det M 1 j
D 1 j = ( − 1 ) j − 1 det M 1 j = ( − 1 ) 1 + j det M 1 j D_{1j} = (-1)^{\,j-1}\,\det M_{1j} = (-1)^{\,1+j}\,\det M_{1j} D 1 j = ( − 1 ) j − 1 det M 1 j = ( − 1 ) 1 + j det M 1 j 이다. j − 1 j - 1 j − 1 1 + j 1 + j 1 + j ( − 1 ) (-1) ( − 1 )
이 값에 이름을 붙이자.
(14) (18)
det A = a 11 C 11 + a 12 C 12 + ⋯ + a 1 n C 1 n \det A = a_{11}C_{11} + a_{12}C_{12} + \cdots + a_{1n}C_{1n} det A = a 11 C 11 + a 12 C 12 + ⋯ + a 1 n C 1 n 아무 행으로나 묶어도 된다 ¶ 첫 행이 특별한 이유는 없다. i i i i i i 이웃끼리만 바꾼다. i i i i − 1 i-1 i − 1 i − 2 i-2 i − 2 i − 1 i-1 i − 1
행 교환도 부호를 뒤집으므로 앞의 ( − 1 ) j − 1 (-1)^{j-1} ( − 1 ) j − 1 ( − 1 ) i − 1 (-1)^{i-1} ( − 1 ) i − 1
( − 1 ) i − 1 ( − 1 ) j − 1 = ( − 1 ) i + j − 2 = ( − 1 ) i + j (-1)^{\,i-1}\,(-1)^{\,j-1} = (-1)^{\,i+j-2} = (-1)^{\,i+j} ( − 1 ) i − 1 ( − 1 ) j − 1 = ( − 1 ) i + j − 2 = ( − 1 ) i + j 정확히 Definition 1
det A = ∑ j = 1 n a i j C i j ( 어느 행 i 를 골라도 된다 ) \det A = \sum_{j=1}^{n} a_{ij}C_{ij}
\qquad (\text{어느 행 } i \text{ 를 골라도 된다}) det A = j = 1 ∑ n a ij C ij ( 어느 행 i 를 골라도 된다 ) 아무 열로나 묶어도 된다 ¶ 열에 대한 전개는 따로 유도할 필요가 없다. det A T = det A \det A^{\mathsf{T}} = \det A det A T = det A A T A^{\mathsf{T}} A T A A A A T A^{\mathsf{T}} A T j j j A A A A A A j j j
det A = ∑ i = 1 n a i j C i j ( 어느 열 j 를 골라도 된다 ) \det A = \sum_{i=1}^{n} a_{ij}C_{ij}
\qquad (\text{어느 열 } j \text{ 를 골라도 된다}) det A = i = 1 ∑ n a ij C ij ( 어느 열 j 를 골라도 된다 ) (22) (23) 더하는 첨자가 다르다. 앞의 것은 j j j i i i
부호는 외울 것이 없다 ¶ ( − 1 ) i + j (-1)^{i+j} ( − 1 ) i + j + + +
[ + − + ⋯ − + − ⋯ + − + ⋯ ⋮ ⋱ ] \begin{bmatrix}
+ & - & + & \cdots \\
- & + & - & \cdots \\
+ & - & + & \cdots \\
\vdots & & & \ddots
\end{bmatrix} ⎣ ⎡ + − + ⋮ − + − + − + ⋯ ⋯ ⋯ ⋱ ⎦ ⎤ L18에서 쓰던 행렬로 해 보자.
A = [ 1 2 1 3 8 1 0 4 1 ] A = \begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix} A = ⎣ ⎡ 1 3 0 2 8 4 1 1 1 ⎦ ⎤ 먼저 첫 행으로 전개한다. 1행과 j j j 2 × 2 2 \times 2 2 × 2
C 11 = + det [ 8 1 4 1 ] = 8 − 4 = 4 , C 12 = − det [ 3 1 0 1 ] = − ( 3 − 0 ) = − 3 , C 13 = + det [ 3 8 0 4 ] = 12 − 0 = 12 C_{11} = +\det\begin{bmatrix} 8 & 1 \\ 4 & 1 \end{bmatrix} = 8 - 4 = 4,
\quad
C_{12} = -\det\begin{bmatrix} 3 & 1 \\ 0 & 1 \end{bmatrix} = -(3 - 0) = -3,
\quad
C_{13} = +\det\begin{bmatrix} 3 & 8 \\ 0 & 4 \end{bmatrix} = 12 - 0 = 12 C 11 = + det [ 8 4 1 1 ] = 8 − 4 = 4 , C 12 = − det [ 3 0 1 1 ] = − ( 3 − 0 ) = − 3 , C 13 = + det [ 3 0 8 4 ] = 12 − 0 = 12 det A = 1 ⋅ 4 + 2 ⋅ ( − 3 ) + 1 ⋅ 12 = 4 − 6 + 12 = 10 \det A = 1 \cdot 4 + 2 \cdot (-3) + 1 \cdot 12 = 4 - 6 + 12 = 10 det A = 1 ⋅ 4 + 2 ⋅ ( − 3 ) + 1 ⋅ 12 = 4 − 6 + 12 = 10 L18에서 피벗을 곱해 얻은 10과 같다.
Figure 3: 첫 행에서 하나를 고르고, 그 행과 열을 지우고, 남은 것의 행렬식을 구한다.
그 결과를 다시 같은 방법으로 구한다.
이번에는 3행 으로 전개해 보자. 3행에 0이 하나 있으니 계산이 하나 줄어든다.
C 31 = + det [ 2 1 8 1 ] = 2 − 8 = − 6 , C 32 = − det [ 1 1 3 1 ] = − ( 1 − 3 ) = 2 , C 33 = + det [ 1 2 3 8 ] = 8 − 6 = 2 C_{31} = +\det\begin{bmatrix} 2 & 1 \\ 8 & 1 \end{bmatrix} = 2 - 8 = -6,
\quad
C_{32} = -\det\begin{bmatrix} 1 & 1 \\ 3 & 1 \end{bmatrix} = -(1 - 3) = 2,
\quad
C_{33} = +\det\begin{bmatrix} 1 & 2 \\ 3 & 8 \end{bmatrix} = 8 - 6 = 2 C 31 = + det [ 2 8 1 1 ] = 2 − 8 = − 6 , C 32 = − det [ 1 3 1 1 ] = − ( 1 − 3 ) = 2 , C 33 = + det [ 1 3 2 8 ] = 8 − 6 = 2 det A = 0 ⋅ ( − 6 ) + 4 ⋅ 2 + 1 ⋅ 2 = 0 + 8 + 2 = 10 \det A = 0 \cdot (-6) + 4 \cdot 2 + 1 \cdot 2 = 0 + 8 + 2 = 10 det A = 0 ⋅ ( − 6 ) + 4 ⋅ 2 + 1 ⋅ 2 = 0 + 8 + 2 = 10 1열 로 전개해도 마찬가지이다. 1열에도 0이 하나 있다. 이번에는 i i i
det A = a 11 C 11 + a 21 C 21 + a 31 C 31 = 1 ⋅ 4 + 3 ⋅ 2 + 0 ⋅ ( − 6 ) = 4 + 6 + 0 = 10 \det A = a_{11}C_{11} + a_{21}C_{21} + a_{31}C_{31}
= 1 \cdot 4 + 3 \cdot 2 + 0 \cdot (-6) = 4 + 6 + 0 = 10 det A = a 11 C 11 + a 21 C 21 + a 31 C 31 = 1 ⋅ 4 + 3 ⋅ 2 + 0 ⋅ ( − 6 ) = 4 + 6 + 0 = 10 C 21 = − det [ 2 1 4 1 ] = − ( 2 − 4 ) = 2 C_{21} = -\det\begin{bmatrix} 2 & 1 \\ 4 & 1 \end{bmatrix} = -(2-4) = 2 C 21 = − det [ 2 4 1 1 ] = − ( 2 − 4 ) = 2
이것은 재귀이다 ¶ (20) n n n ( n − 1 ) (n-1) ( n − 1 ) n n n
계산량을 세어 보자. n n n T ( n ) T(n) T ( n ) ( n − 1 ) (n-1) ( n − 1 ) n n n
T ( n ) = n ⋅ T ( n − 1 ) , T ( 1 ) = 1 T(n) = n \cdot T(n-1),
\qquad
T(1) = 1 T ( n ) = n ⋅ T ( n − 1 ) , T ( 1 ) = 1 풀어 보면 계승이 그대로 나온다.
T ( n ) = n ⋅ ( n − 1 ) ⋅ ( n − 2 ) ⋯ 2 ⋅ 1 = n ! T(n) = n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1 = n! T ( n ) = n ⋅ ( n − 1 ) ⋅ ( n − 2 ) ⋯ 2 ⋅ 1 = n ! 당연한 결과이다. 빅 포뮬러의 n ! n! n ! 묶어 놓았을 뿐 없앤 것이 아니기 때문이다.
묶는다고 항이 사라지지는 않는다.
5. 그래서 실제로는 쓰지 않는다 ¶ n ! n! n ! n 3 n^3 n 3
Figure 4: n = 5 n = 5 n = 5 n = 20 n = 20 n = 20
n n n 여인수 전개 n ! n! n ! 소거 n 3 n^3 n 3 3 6 27 5 120 125 10 3,628,800 1,000 20 2.4 × 1 0 18 2.4 \times 10^{18} 2.4 × 1 0 18 8,000
n = 3 n = 3 n = 3 3 × 3 3 \times 3 3 × 3 n = 10 n = 10 n = 10
n = 20 n = 20 n = 20 109 개의 항을 처리하는 컴퓨터라 해도
2.4 × 1 0 18 2.4 \times 10^{18} 2.4 × 1 0 18 2.4 × 1 0 9 2.4 \times 10^9 2.4 × 1 0 9 76년 이 걸린다.
같은 행렬을 소거로 처리하면 8000번의 연산, 곧 백만분의 1초도 걸리지 않는다.
마치며... ¶ 이번 강의에서 다룬 것을 정리하면 다음과 같다.
대상 내용 쪼개기 각 행을 좌표축 방향으로 쪼개면 n n n^n n n 살아남는 항 행마다 서로 다른 열을 고른 것, 곧 순열. n ! n! n ! 3 × 3 3 \times 3 3 × 3 27개 중 21개가 죽고 6개가 남아 익숙한 공식이 된다 빅 포뮬러 det A = ∑ σ ( sgn σ ) a 1 σ ( 1 ) ⋯ a n σ ( n ) \det A = \sum_\sigma (\operatorname{sgn}\sigma)\, a_{1\sigma(1)}\cdots a_{n\sigma(n)} det A = ∑ σ ( sgn σ ) a 1 σ ( 1 ) ⋯ a nσ ( n ) 부호 순열행렬의 행렬식. 홀짝이 잘 정의되는 것도 행렬식이 보증한다 존재 빅 포뮬러가 세 공리를 만족하므로 행렬식은 실제로 존재한다 여인수 C i j = ( − 1 ) i + j M i j C_{ij} = (-1)^{i+j}M_{ij} C ij = ( − 1 ) i + j M ij 여인수 전개 어느 행으로도 어느 열로도 된다. 재귀이고 계산량은 n ! n! n ! 실제 계산 여전히 소거 후 피벗의 곱, n 3 n^3 n 3
두 가지 공식을 얻었지만 둘 다 계산에는 쓸 수 없다는 것도 함께 확인했다. 그렇다면 이번
강의는 헛수고였는가.
그렇지 않다. 두 가지를 얻었다. 첫째로 행렬식이 존재한다는 것 을 확인했다. L18에서는
값이 하나로 정해진다는 것만 알았지, 그런 함수가 정말 있는지는 몰랐다. 둘째로
여인수는 버려지지 않는다. 다음 강의에서 이 여인수들이 모여 역행렬의 공식을 이루는 것을
보게 된다. 그리고 그 과정에서 행렬식의 진짜 정체, 곧 부피 를 제대로 만나게 된다.
그 그림은 열 강의 뒤 특이값 분해에서 다시 우리를 찾아온다.
이번 강의의 내용을 파이썬으로 확인해 보려면 L19 실습 노트북 으로 넘어가면 된다.
빅 포뮬러를 순열로 직접 돌려 보고, 여인수 전개를 재귀 함수로 짜서 np.linalg.det 와 대조하며,
n n n
