연결 강의: MIT 18.06 Linear Algebra - Lecture 19: Determinant formulas and cofactors

1. 이번 강의의 목표

이번 강의는 determinant에 대한 두 번째 강의이다.

determinant는 선형대수학 안에서 크지는 않지만 꽤 정교한 주제이다. 예전에는 determinant가 선형대수학의 중심처럼 다뤄졌지만, 지금 관점에서는 정사각행렬을 이해하는 여러 도구 중 하나로 보는 편이 더 자연스럽다.

이번 강의의 목표는 determinant를 실제 entry들로 계산하는 공식을 얻는 것이다.

공식은 크게 두 가지이다.

1. permutation을 이용한 큰 공식
2. cofactor를 이용한 재귀적인 공식

첫 번째 공식은 determinant를 한 번에 펼쳐서 쓰는 방식이다. 다만 $n \times n$ 행렬에서는 항의 개수가 $n!$개라서 매우 커진다.

두 번째 공식은 determinant를 한 단계 작은 determinant들로 나누어 계산하는 방식이다. 특히 0이 많은 행렬에서 유용하다.

---

2. $2 \times 2$ determinant를 성질로부터 다시 얻기

먼저 가장 익숙한 $2 \times 2$ determinant를 다시 보자.

$$\left| \begin{matrix} a & b \\ c & d \end{matrix} \right|$$

결과가 $ad-bc$라는 것은 이미 알고 있다. 하지만 이번에는 이 공식을 외우는 것이 아니라, determinant의 세 기본 성질에서 어떻게 나오는지 확인하는 것이 목적이다.

determinant의 기본 성질은 다음 세 가지였다.

1. $\det I = 1$
2. 두 행을 교환하면 determinant의 부호가 바뀐다.
3. determinant는 각 행에 대해 따로 선형적이다.

세 번째 성질을 이용해서 행을 하나씩 쪼개보자.

첫 번째 행을 다음처럼 나눌 수 있다.

$$[a \ b] = [a \ 0] + [0 \ b]$$

두 번째 행도 다음처럼 나눌 수 있다.

$$[c \ d] = [c \ 0] + [0 \ d]$$

그러면 determinant는 네 개의 determinant로 쪼개진다.

$$\left| \begin{matrix} a & b \\ c & d \end{matrix} \right| = \left| \begin{matrix} a & 0 \\ c & 0 \end{matrix} \right| + \left| \begin{matrix} a & 0 \\ 0 & d \end{matrix} \right| + \left| \begin{matrix} 0 & b \\ c & 0 \end{matrix} \right| + \left| \begin{matrix} 0 & b \\ 0 & d \end{matrix} \right|$$

이 네 항 중 첫 번째와 네 번째는 바로 0이다.

첫 번째 항은 두 번째 열이 전부 0이다.

$$\left| \begin{matrix} a & 0 \\ c & 0 \end{matrix} \right| =0$$

네 번째 항은 첫 번째 열이 전부 0이다.

$$\left| \begin{matrix} 0 & b \\ 0 & d \end{matrix} \right| =0$$

남는 것은 두 항이다.

$$\left| \begin{matrix} a & 0 \\ 0 & d \end{matrix} \right| = ad$$

그리고,

$$\left| \begin{matrix} 0 & b \\ c & 0 \end{matrix} \right| = -bc$$

두 번째 determinant가 음수가 되는 이유는 이 행렬이 대각행렬로 가려면 행을 한 번 교환해야 하기 때문이다.

따라서 전체 determinant는 다음과 같다.

$$\left| \begin{matrix} a & b \\ c & d \end{matrix} \right| = ad-bc$$

중요한 것은 답 자체보다 방법이다. 행을 하나씩 쪼개고, 0이 되는 항을 버리고, 남는 항의 부호를 permutation으로 결정하는 방식이 모든 크기의 행렬로 확장된다.

---

3. $3 \times 3$ determinant에서는 어떤 일이 생기는가

$3 \times 3$ 행렬을 생각하자.

$$A = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix}$$

$2 \times 2$에서 했던 것처럼 각 행을 하나씩 쪼개면 항이 많이 생긴다.

첫 번째 행은 세 조각으로 나뉜다.

$$[a_{11} \ a_{12} \ a_{13}] = [a_{11} \ 0 \ 0] + [0 \ a_{12} \ 0] + [0 \ 0 \ a_{13}]$$

두 번째 행도 세 조각, 세 번째 행도 세 조각으로 나뉜다.

따라서 처음에는 총 $3^3=27$개의 determinant가 생긴다.

하지만 대부분은 0이 된다. 어떤 열이 전부 0이 되면 그 determinant는 바로 0이기 때문이다.

살아남는 항은 정확히 다음 조건을 만족한다.

1. 각 행에서 하나씩 entry를 고른다.
2. 각 열에서도 하나씩만 entry를 고른다.

즉, 살아남는 항은 row마다 하나, column마다 하나를 고른 곱이다.

$3 \times 3$에서는 이런 선택이 $3! = 6$개이다.

---

4. $3 \times 3$ determinant의 여섯 항

$3 \times 3$ determinant에서 살아남는 여섯 항을 쓰면 다음과 같다.

$$\det A = a_{11}a_{22}a_{33} -a_{11}a_{23}a_{32} -a_{12}a_{21}a_{33} +a_{12}a_{23}a_{31} +a_{13}a_{21}a_{32} -a_{13}a_{22}a_{31}$$

각 항은 행마다 하나씩, 열마다 하나씩 고른 entry들의 곱이다.

예를 들어 다음 항은 열을 $1,2,3$ 순서로 고른 것이다.

$$a_{11}a_{22}a_{33}$$

이것은 identity permutation에 해당하므로 부호가 $+$이다.

반면 다음 항은 열을 $1,3,2$ 순서로 고른 것이다.

$$a_{11}a_{23}a_{32}$$

이 순서는 $1,2,3$에서 $2$와 $3$을 한 번 바꾸면 되므로 한 번의 교환이 필요하다. 따라서 부호는 $-$이다.

다음 항도 보자.

$$a_{12}a_{23}a_{31}$$

이것은 열을 $2,3,1$ 순서로 고른 항이다. 이 permutation은 두 번의 교환으로 $1,2,3$으로 돌아갈 수 있으므로 부호가 $+$이다.

결국 determinant의 각 항에는 permutation의 부호가 붙는다.

---

5. 대각선 그림은 $3 \times 3$까지만 조심해서 쓸 수 있다

$3 \times 3$ determinant에서는 흔히 대각선 방향으로 외우는 방법을 사용한다.

아래 방향으로 내려가는 항들은 $+$, 반대 방향으로 내려가는 항들은 $-$라고 기억하는 방식이다.

하지만 이 그림식 기억법은 $3 \times 3$에서만 조심스럽게 쓸 수 있다. $4 \times 4$ 이상에서는 그대로 맞지 않는다.

예를 들어 $4 \times 4$ 행렬에서 counter diagonal에만 1이 있는 permutation matrix를 생각하자.

$$P = \begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix}$$

이 permutation은 열 순서로 보면 $4,3,2,1$이다.

이 행렬은 행을 두 번 교환하면 identity matrix가 된다. 예를 들어 첫 번째 행과 네 번째 행을 바꾸고, 두 번째 행과 세 번째 행을 바꾸면 된다.

행 교환 횟수가 2번이므로 determinant는 $+1$이다.

$$\det P = 1$$

즉, $4 \times 4$에서는 반대 대각선이라고 해서 무조건 음수가 되는 것이 아니다. 부호는 항상 permutation의 짝홀성으로 결정해야 한다.

---

6. determinant의 큰 공식

이제 일반적인 $n \times n$ determinant 공식을 쓸 수 있다.

$A$가 $n \times n$ 행렬이라고 하자.

$$A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix}$$

determinant는 다음과 같다.

$$\det A = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) a_{1\sigma(1)} a_{2\sigma(2)} \cdots a_{n\sigma(n)}$$

여기서 $S_n$은 $1,2,\dots,n$의 모든 permutation의 집합이다.

$\sigma$는 각 행에서 어떤 열을 고를지 정해준다.

예를 들어 $\sigma(1)=3$이면 첫 번째 행에서는 $a_{13}$을 고른다는 뜻이다.

중요한 조건은 각 열을 정확히 한 번씩만 사용한다는 점이다.

각 항은 다음 형태를 가진다.

$$a_{1\alpha}a_{2\beta}a_{3\gamma}\cdots a_{n\omega}$$

여기서 $\alpha,\beta,\gamma,\dots,\omega$는 $1,2,\dots,n$의 어떤 permutation이다.

항의 개수는 $n!$개이다.

첫 번째 행에서 고를 수 있는 열은 $n$개이고, 그 열을 사용하면 두 번째 행에서는 $n-1$개가 남는다. 이런 식으로 마지막까지 가면 총 개수는 다음과 같다.

$$n(n-1)(n-2)\cdots 1 = n!$$

부호는 permutation이 짝수 번의 교환으로 identity permutation이 되면 $+$, 홀수 번의 교환이 필요하면 $-$이다.

---

7. identity matrix에서 큰 공식 확인하기

큰 공식으로 $\det I = 1$도 확인할 수 있다.

항등행렬에서는 대각성분만 1이고 나머지는 모두 0이다.

따라서 permutation 공식의 거의 모든 항이 0이 된다.

살아남는 항은 identity permutation에 해당하는 항뿐이다.

$$a_{11}a_{22}\cdots a_{nn} = 1 \cdot 1 \cdots 1 = 1$$

그리고 identity permutation의 부호는 $+$이다.

따라서,

$$\det I = 1$$

이다.

이렇게 보면 큰 공식에서 determinant의 기본 성질들을 다시 확인할 수 있다. 다만 $\det(AB)=\det A\det B$ 같은 성질을 이 공식만으로 직접 증명하려면 계산이 매우 복잡해진다.

그래서 determinant는 공식보다 성질에서 출발하는 편이 훨씬 낫다.

---

8. $4 \times 4$ 예시: 0이 많을 때 큰 공식 사용하기

다음 $4 \times 4$ 행렬을 생각하자.

$$A = \begin{bmatrix} 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 \end{bmatrix}$$

$4 \times 4$ determinant의 큰 공식에는 원래 $4! = 24$개의 항이 있다.

하지만 이 행렬은 0이 많기 때문에 대부분의 항이 사라진다.

살아남는 항은 각 행과 각 열에서 1을 하나씩 골라야 한다.

가능한 선택은 두 가지뿐이다.

첫 번째 선택은 열 순서 $4,3,2,1$이다.

$$a_{14}a_{23}a_{32}a_{41} = 1$$

이 permutation은 두 번의 교환으로 identity permutation이 되므로 부호가 $+$이다.

따라서 이 항은 $+1$이다.

두 번째 선택은 열 순서 $3,2,1,4$이다.

$$a_{13}a_{22}a_{31}a_{44} = 1$$

이 permutation은 세 번의 교환이 필요하므로 부호가 $-$이다.

따라서 이 항은 $-1$이다.

나머지 22개 항은 모두 0이다.

따라서 전체 determinant는 다음과 같다.

$$\det A = 1 - 1 = 0$$

즉, 이 행렬은 singular matrix이다.

실제로 row relation도 바로 찾을 수 있다.

첫 번째 행과 세 번째 행을 더하면 다음과 같다.

$$R_1 + R_3 = [1 \ 1 \ 1 \ 1]$$

두 번째 행과 네 번째 행을 더해도 같다.

$$R_2 + R_4 = [1 \ 1 \ 1 \ 1]$$

따라서,

$$R_1 - R_2 + R_3 - R_4 = 0$$

이다.

행들 사이에 nonzero combination이 0을 만들기 때문에 행들은 독립이 아니다. 그래서 determinant가 0이 되는 것이 자연스럽다.

---

9. Cofactor의 아이디어

큰 공식은 determinant를 한 번에 펼쳐서 보여준다.

하지만 항이 $n!$개이므로 크기가 조금만 커져도 직접 쓰기 어렵다.

cofactor는 큰 공식을 조금 더 구조적으로 나누는 방법이다.

핵심은 $n \times n$ determinant를 $(n-1) \times (n-1)$ determinant들로 표현하는 것이다.

먼저 $3 \times 3$ 공식에서 첫 번째 행을 기준으로 항을 묶어보자.

$$\det A = a_{11}(a_{22}a_{33}-a_{23}a_{32}) -a_{12}(a_{21}a_{33}-a_{23}a_{31}) +a_{13}(a_{21}a_{32}-a_{22}a_{31})$$

여기서 $a_{11}$에 곱해진 부분을 보자.

$$a_{22}a_{33}-a_{23}a_{32}$$

이것은 다음 $2 \times 2$ 행렬의 determinant이다.

$$\left| \begin{matrix} a_{22} & a_{23} \\ a_{32} & a_{33} \end{matrix} \right|$$

이 행렬은 원래 $3 \times 3$ 행렬에서 첫 번째 행과 첫 번째 열을 지운 뒤 남은 행렬이다.

즉, $a_{11}$을 사용했다면 더 이상 첫 번째 행과 첫 번째 열은 사용할 수 없다. 남은 행과 열에서 determinant를 계산하는 것이 바로 cofactor의 핵심이다.

---

10. Minor와 Cofactor

entry $a_{ij}$를 생각하자.

$a_{ij}$가 있는 $i$번째 행과 $j$번째 열을 지우면 $(n-1) \times (n-1)$ 행렬이 남는다.

이 작은 행렬의 determinant를 minor라고 한다.

보통 다음처럼 쓴다.

$$M_{ij} = \det(\text{matrix obtained by deleting row } i \text{ and column } j)$$

cofactor는 이 minor에 부호를 붙인 것이다.

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

즉, $i+j$가 짝수이면 cofactor는 minor와 같은 부호이고, $i+j$가 홀수이면 cofactor는 minor에 음수를 붙인다.

부호 패턴은 checkerboard 모양이다.

$$\begin{bmatrix} + & - & + & - & \cdots \\ - & + & - & + & \cdots \\ + & - & + & - & \cdots \\ - & + & - & + & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{bmatrix}$$

minor는 작은 determinant이고, cofactor는 부호까지 포함한 값이다.

실제로 determinant 전개에서 곱해지는 것은 cofactor이다.

---

11. Cofactor formula

첫 번째 행을 기준으로 determinant를 전개하면 다음과 같다.

$$\det A = a_{11}C_{11} +a_{12}C_{12} +\cdots +a_{1n}C_{1n}$$

더 일반적으로는 어떤 행으로도 전개할 수 있다.

$i$번째 행을 기준으로 전개하면 다음과 같다.

$$\det A = a_{i1}C_{i1} +a_{i2}C_{i2} +\cdots +a_{in}C_{in}$$

또 전치해도 determinant가 변하지 않기 때문에, 행뿐 아니라 열을 기준으로도 전개할 수 있다.

$j$번째 열을 기준으로 전개하면 다음과 같다.

$$\det A = a_{1j}C_{1j} +a_{2j}C_{2j} +\cdots +a_{nj}C_{nj}$$

0이 많은 행이나 열을 선택하면 계산량이 크게 줄어든다.

---

12. $2 \times 2$ cofactor 전개

가장 작은 예시로 $2 \times 2$ 행렬을 보자.

$$A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}$$

첫 번째 행을 기준으로 cofactor 전개를 하면 다음과 같다.

$$\det A = aC_{11} + bC_{12}$$

$a$의 cofactor는 첫 번째 행과 첫 번째 열을 지우고 남은 값 $d$이다.

$$C_{11}=d$$

$b$의 cofactor는 첫 번째 행과 두 번째 열을 지우고 남은 값 $c$에 부호 $-$를 붙인 것이다.

$$C_{12}=-c$$

따라서,

$$\det A = a d + b(-c) = ad-bc$$

이다.

cofactor 전개가 기존의 $2 \times 2$ 공식과 정확히 일치한다.

---

13. 세 가지 determinant 계산 관점

지금까지 determinant를 계산하는 관점은 세 가지로 정리할 수 있다.

첫 번째는 pivot formula이다.

소거법으로 upper triangular matrix를 만들고 pivot들의 곱을 구한다.

$$\det A = (-1)^r d_1 d_2 \cdots d_n$$

계산 관점에서는 이 방식이 가장 효율적이다.

두 번째는 permutation formula이다.

$$\det A = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) a_{1\sigma(1)} a_{2\sigma(2)} \cdots a_{n\sigma(n)}$$

이 방식은 determinant의 모든 항을 한 번에 보여준다. 하지만 항의 개수가 $n!$개라서 실제 계산에는 비효율적이다.

세 번째는 cofactor formula이다.

$$\det A = a_{i1}C_{i1} +a_{i2}C_{i2} +\cdots +a_{in}C_{in}$$

이 방식은 determinant를 작은 determinant들로 쪼갠다. 0이 많은 행렬에서는 꽤 유용하다.

---

14. Tridiagonal matrix 예시

다음처럼 대각선과 그 바로 위아래에만 1이 있는 행렬을 생각하자.

$$A_4 = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{bmatrix}$$

일반적으로 $A_n$은 다음과 같은 tridiagonal matrix이다.

$$A_n = \begin{bmatrix} 1 & 1 & 0 & 0 & \cdots & 0 \\ 1 & 1 & 1 & 0 & \cdots & 0 \\ 0 & 1 & 1 & 1 & \cdots & 0 \\ 0 & 0 & 1 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \end{bmatrix}$$

이 행렬의 determinant를 $D_n$이라고 하자.

$$D_n = \det A_n$$

작은 경우부터 계산해보자.

$A_1$은 $[1]$이므로,

$$D_1 = 1$$

$A_2$는 다음과 같다.

$$A_2 = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}$$

따라서,

$$D_2 = 1 \cdot 1 - 1 \cdot 1 = 0$$

$A_3$은 다음과 같다.

$$A_3 = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \end{bmatrix}$$

이 determinant는 $-1$이다.

예를 들어 첫 번째 행으로 cofactor 전개를 하면,

$$D_3 = 1 \left| \begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix} \right| - 1 \left| \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right|$$

첫 번째 $2 \times 2$ determinant는 0이고, 두 번째 determinant는 1이다.

따라서,

$$D_3 = 0 - 1 = -1$$

---

15. Tridiagonal determinant의 재귀식

$A_n$의 첫 번째 행은 다음과 같다.

$$[1 \ 1 \ 0 \ \cdots \ 0]$$

첫 번째 행을 기준으로 cofactor 전개를 하면, 0인 항들은 모두 사라지고 앞의 두 항만 남는다.

첫 번째 entry $a_{11}=1$의 cofactor는 $A_{n-1}$의 determinant이다.

따라서 첫 번째 항은 다음과 같다.

$$D_{n-1}$$

두 번째 entry $a_{12}=1$의 cofactor는 부호가 음수이다. 첫 번째 행과 두 번째 열을 지우고 남은 determinant를 다시 보면, 첫 번째 열에 1 하나만 남는 구조가 된다.

그 열로 한 번 더 cofactor 전개를 하면 결국 $A_{n-2}$의 determinant가 남는다.

따라서 두 번째 항은 다음과 같다.

$$-D_{n-2}$$

결국 재귀식은 다음이다.

$$D_n = D_{n-1} - D_{n-2}$$

초기값은 다음과 같다.

$$D_1 = 1, \qquad D_2 = 0$$

그러면 차례대로 계산할 수 있다.

$$D_3 = D_2 - D_1 = 0 - 1 = -1$$ $$D_4 = D_3 - D_2 = -1 - 0 = -1$$ $$D_5 = D_4 - D_3 = -1 - (-1) = 0$$ $$D_6 = D_5 - D_4 = 0 - (-1) = 1$$ $$D_7 = D_6 - D_5 = 1 - 0 = 1$$

따라서 수열은 다음처럼 진행된다.

$$1,\ 0,\ -1,\ -1,\ 0,\ 1,\ 1,\ 0,\ -1,\ -1,\ 0,\ 1,\ \dots$$

이 determinant 수열은 주기 6을 가진다.

즉,

$$D_{n+6} = D_n$$

이다.

예를 들어,

$$D_{61} = D_1 = 1$$

이다.

이 예시는 cofactor 전개가 단순 계산 공식이 아니라, 행렬 크기에 따른 determinant의 패턴을 찾는 데에도 쓸 수 있음을 보여준다.

---

16. 핵심 정리

이번 강의의 핵심은 determinant를 실제 entry들로 표현하는 방법이다.

permutation formula는 determinant의 모든 항을 한 번에 보여준다.

$$\det A = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) a_{1\sigma(1)} a_{2\sigma(2)} \cdots a_{n\sigma(n)}$$

각 항은 각 행과 각 열에서 하나씩 entry를 고른 곱이고, 부호는 permutation의 짝홀성으로 정해진다.

cofactor formula는 determinant를 더 작은 determinant로 쪼갠다.

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

그리고,

$$\det A = a_{i1}C_{i1} +a_{i2}C_{i2} +\cdots +a_{in}C_{in}$$

이다.

정리하면 determinant 계산에는 다음 세 관점이 있다.

1. pivot 공식: 계산에 효율적이다.
2. permutation 공식: determinant의 모든 항을 직접 보여준다.
3. cofactor 공식: 큰 determinant를 작은 determinant로 나눈다.

특히 cofactor 공식은 0이 많은 행렬이나 특수한 패턴을 가진 행렬에서 매우 유용하다.