주어진 $n \times n$ 정사각행렬 $A$의 행렬식(determinant)를 $\abs{A}$ 나타내기로 하자. 이번 글에서는 $2 \times 2$ 행렬의 행렬식을 구하는 계산만을 반복하여 $A$의 행렬식을 구하는 도지슨의 응집 방법(condensation method)에 대하여 알아볼 것이다. 여기서 찰스 럿위지 도지슨(Charles Lutwidge Dodgson)은 소설 "이상한 나라의 앨리스(Alice's Adventures in Wonderland)"의 저자로 잘 알려진 루이스 캐럴(Lewis Carroll)의 본명이다.
$ $
도지슨의 응집 방법(condensation method)
도지슨의 응집 방법(condensation method)은 주어진 행렬쌍 $k \times k$ 정사각행렬 $A$와 어떤 원소도 $0$이 아닌 $(k-1) \times (k-1)$ 정사각행렬 $B$가 주어졌을 때, 행렬쌍 $(A,\, B\,)$로 부터 $(A',\, B'\,)$을 구하는 과정을 알려준다.
- $A'$의 $(i,\, j)$ 원소는 다음과 같이 계산된다.
\[ A'_{i,\, j} = \frac{A_{i,\, j} A_{i+1,\, j+1} - A_{i,\, j+1} A_{i+1,\, j}}{B_{i,\, j}} \quad \text{for} \;\; i,\, j = 1,\, 2,\, \ldots,\, k-1 \]
이 과정을 통해 $(k-1) \times (k-1)$ 정사각행렬 $A'$을 얻는다. 여기서 좌변의 분자를 보면 행렬
\[ \begin{bmatrix} A_{i,\, j} & A_{i,\, j+1} \\ A_{i+1,\, j} & A_{i+1,\, j+1} \end{bmatrix} \]
의 행렬식과 같음을 알 수 있다.
- $B'$의 $(i,\, j)$ 원소는 다음과 같이 계산된다.
\[ B_{i,\, j} = A_{i+1,\, j+1} \quad \text{for} \;\; i,\, j = 1,\, 2,\, \ldots,\, k-2 \]
즉, $B'$은 행렬 $A$의 제일 처음과 마지막 행과 열을 제외한 $(k-2) \times (k-2)$ 정사각행렬이다. 이 행렬 $B'$을 $A$의 내부(interior) $\text{int}(A)$로 정의하기도 하는데, 이 경우 $B' = \text{int}(A)$이다.
위 과정을 예를 통해서 살펴보도록 하자. 만약
\[ A = \left[ \begin{array}{rrr} 5 & 3 & 1 \\ -3 & -1 & 1 \\ 1 & 3 & -1 \end{array}\, \right], \quad
B = \left[ \begin{array}{rr} 1 & -1 \\ -2 & 1 \end{array}\, \right] \]
과 같이 주어졌다면,
\[ A' = \left[ \begin{array}{rr} 4 & -4 \\ 4 & -2 \end{array}\, \right], \quad
B' = \left[ -1\, \right] \]
으로 계산된다. 예를 들어 $A'$의 $(2,\, 1)$ 원소인 $4$의 경우,
\[ A'_{2,\, 1} = \frac{\abs{\begin{array}{rr} A_{2,\, 1} & A_{2,\, 2} \\ A_{3,\, 1} & A_{3,\, 2} \end{array}\,}}{B_{2,\, 1}} = \frac{\abs{\begin{array}{rr} -3 & -1 \\ 1 & 3 \end{array}\,}}{-2} = \frac{(-3)(3) - (-1)(1)}{-2} = 4 \]
와 같이 계산되는 식이다.
$ $
$n \times n$ 정사각행렬 $A = [A_{i,\, j}]$가 주어졌을 때 대하여 행렬식 $\abs{A}$의 값을 구하는 과정은 다음과 같다. 우선 $A^{(1)} = A$로 정의하고, $B^{(1)}$은 모든 원소가 $1$인 $(n-1) \times (n-1)$ 정사각행렬로 정의하자. 그 다음으로는 귀납적으로 $A^{(i+1)} = (A^{(i)})'$, $B^{(i+1)} = (B^{(i)})' = \text{int}(A^{(i)})$와 같이 정의한다. 그러면 $A^{(1)},\, A^{(2)}, \ldots$를 구해감에 따라 행렬의 크기가 $1$씩 줄어드므로, $A^{(n)}$은 $1 \times 1$ 행렬이 됨을 알 수 있는데, 이 값이 우리가 구하고자 하는 $\abs{A}$의 값이 된다. 이 과정을 예를 들어 보면 다음과 같다.
\[ \begin{align*}
A^{(1)} = \left[ \begin{array}{rrrr} 1 & -2 & -1 & 3 \\ 2 & 1 & -1 & 2 \\ -1 & -2 & 1 & -3 \\ 0 & -1 & -1 & 2 \end{array}\, \right] \quad & \qquad
B^{(1)} = \left[ \begin{array}{rrr} \,1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array}\, \right], \\[3px]
& \Downarrow \\[3px]
A^{(2)} = \left[ \begin{array}{rrr} 5 & 3 & 1 \\ -3 & -1 & 1 \\ 1 & 3 & -1 \end{array}\, \right] \quad & \qquad
B^{(2)} = \left[ \begin{array}{rr} 1 & -1 \\ -2 & 1 \end{array}\, \right], \\[3px]
& \Downarrow \\[3px]
A^{(3)} = \left[ \begin{array}{rr} 4 & -4 \\ 4 & -2 \end{array}\, \right] \quad & \qquad
B^{(3)} = \left[ -1\, \right], \\[3px]
& \Downarrow \\[3px]
A^{(4)} = \left[ -8\, \right], \quad & \qquad B^{(4)} = \varnothing
\end{align*} \]
따라서 이 경우, $\abs{A} = -8$을 얻을 수 있다.
$ $
도지슨의 응집 방법의 장점은 다음과 같다.
- 행렬 $A$의 모든 원소가 정수라면, 도지슨의 응집 방법을 통한 계산 과정에서 나타나는 모든 수들 또한 정수이다. 이는 $A$의 행렬식을 컴퓨터가 아닌 손으로 직접 구해야 할 때 장점이 될 수 있다.
- 라플라스 전개(Laplace expansion)을 통해서 행렬 $A$의 행렬식을 구하는 것보다 계산량이 훨씬 적다. 라플라스 전개 또한 $2 \times 2$ 행렬의 행렬식을 구하는 계산을 반복하여 $A$의 행렬식을 구하게 되는데, 라플라스 전개는 최악의 경우 $\frac{n!}{2}$번의 $2 \times 2$ 행렬식을 구해야 하는 반면, 도지슨의 응집 방법의 경우 $\frac{1}{6}n(n-1)(2n-1)$의 $2 \times 2$ 행렬식 계산만을 필요로 한다.
위와 같은 장점에도 불구하고 도지슨의 응집 방법이 널리 이용되지 않는 이유는 다음과 같다. 주어진 행렬 $A$에 대하여 $\text{int}(A)$가 $0$인 원소를 가지고 있거나, 응집 방법을 사용하면서 계산되는 행렬 $B^{(i)}$, 즉, 행렬 $\text{int}(A^{(i+1)})$가 $0$인 원소를 단 하나라도 가지고 있으면 더 이상 이 방법을 진행할 수 없다. 예를 들어 아래와 같이 주어진 행렬 $A = A^{(1)}$에 응집 방법을 적용하면,
\[ \begin{align*}
A^{(1)} = \left[ \begin{array}{rrrr} 1 & -2 & 1 & 2 \\ -1 & 2 & 2 & 0 \\ -2 & 1 & 1 & 1 \\ 2 & 1 & -3 & -1 \end{array}\, \right] \quad & \qquad
B^{(1)} = \left[ \begin{array}{rrr} \,1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array}\, \right], \\[3px]
& \Downarrow \\[3px]
A^{(2)} = \left[ \begin{array}{rrr} 0 & -6 & -4 \\ 3 & 0 & 2 \\ -4 & -4 & 2 \end{array}\, \right] \quad & \qquad
B^{(2)} = \left[ \begin{array}{rr} \,2 & 2 \\ 1 & 1 \end{array}\, \right], \\[3px]
& \Downarrow \\[3px]
A^{(3)} = \left[ \begin{array}{rr} 9 & -6 \\ -12 & 8 \end{array}\, \right] \quad & \qquad
B^{(3)} = \left[ \,0\, \right], \\[3px]
& \Downarrow \, ??
\end{align*} \]
이므로 더이상 응집 방법을 진행할 수 없게 된다. 이러한 경우, 처음 시작하는 행렬 $A^{(1)} = A$의 행 또는 열을 적당히 교환함으로써 $B^{(i)}$가 $0$인 원소를 포함하지 않도록 해 줄 수 있다. 예를 들어 위와 같은 경우, $3$번의 행 연산을 통하여 행렬 $A$의 첫번째 행을 마지막으로 보내고 나머지 행들은 한 행씩 위로 올린 행렬 $\bar{A}$을 구한 후에 응집 방법을 적용하면 다음의 결과를 얻는다.
\[ \begin{align*}
\bar{A}^{(1)} = \left[ \begin{array}{rrrr} -1 & 2 & 2 & 0 \\ -2 & 1 & 1 & 1 \\ 2 & 1 & -3 & -1 \\ 1 & -2 & 1 & 2 \end{array}\, \right] \quad & \qquad
\bar{B}^{(1)} = \left[ \begin{array}{rrr} \,1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array}\, \right], \\[3px]
& \Downarrow \\[3px]
\bar{A}^{(2)} = \left[ \begin{array}{rrr} 3 & 0 & 2 \\ -4 & -4 & 2 \\ -5 & -5 & -5 \end{array}\, \right] \quad & \qquad
\bar{B}^{(2)} = \left[ \begin{array}{rr} \,1 & 1 \\ 1 & -3 \end{array}\, \right], \\[3px]
& \Downarrow \\[3px]
\bar{A}^{(3)} = \left[ \begin{array}{rr} -12 & 8 \\ 0 & -10 \end{array}\, \right] \quad & \qquad
\bar{B}^{(3)} = \left[ -4\, \right], \\[3px]
& \Downarrow \\[3px]
\bar{A}^{(4)} = \left[ -30\, \right], \quad & \qquad B^{(4)} = \varnothing
\end{align*} \]
따라서 $\det(\bar{A}) = -30$이고 $\det(A) = (-1)^{3}\det(\bar{A}) = 30$을 얻는다.
$ $
하지만 다음과 같이 주어진 행렬
\[ A = \left[ \begin{array}{rrrr} 1 & 0 & 3 & 0 \\ 0 & -1 & 0 & 1 \\ -1 & 1 & -2 & 0 \\ 0 & 2 & 0 & -1 \end{array}\, \right] \]
의 경우, 모든 행과 열에 $0$인 원소를 가지고 있기 때문에, 행 또는 열을 어떻게 교환하더라도 $\text{int}(A)$에 $0$인 원소가 항상 존재하게 되고 따라서 응집 방법을 적용할 수 없다. (참고로 $\det(A) = 3$이며, 라플라스 전개등을 통해 간단히 계산할 수 있다.)