응집 방법(condensation method)을 통한 행렬식 계산

주어진 $n\times n$ 정사각행렬 $A$의 행렬식_{(determinant)}를 $\left|A\right|$ 나타내기로 하자. 이번 글에서는 $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^{\prime },B^{\prime })$을 구하는 과정을 알려준다.

1. $A^{\prime }$의 $(i,j)$ 원소는 다음과 같이 계산된다.
   $$A_{i,j}^{\prime }=\frac{A_{i,j}{A}_{i+1,j+1}-A_{i,j+1}{A}_{i+1,j}}{B_{i,j}}\text{for}i,j=1,2,\dots ,k-1$$
   이 과정을 통해 $(k-1)\times (k-1)$ 정사각행렬 $A^{\prime }$을 얻는다. 여기서 좌변의 분자를 보면 행렬 $\left[\begin{array}{cc}{A}_{i,j}& A_{i,j+1}\\ A_{i+1,j}& A_{i+1,j+1}\end{array}\right]$의 행렬식과 같음을 알 수 있다.
2. $B^{\prime }$의 $(i,j)$ 원소는 다음과 같이 계산된다.
   $$B_{i,j}=A_{i+1,j+1}\text{for}i,j=1,2,\dots ,k-2$$
   즉, $B^{\prime }$은 행렬 $A$의 제일 처음과 마지막 행과 열을 제외한 $(k-2)\times (k-2)$ 정사각행렬이다. 이 행렬 $B^{\prime }$을 $A$의 내부_(interior) $\text{int}(A)$로 정의하기도 하는데, 이 경우 $B^{\prime }=\text{int}(A)$이다.

위 과정을 예를 통해서 살펴보도록 하자. 만약

$$A=\left[\begin{array}{rrr}5& 3& 1\\ -3& -1& 1\\ 1& 3& -1\end{array}\right],B=\left[\begin{array}{rr}1& -1\\ -2& 1\end{array}\right]$$

과 같이 주어졌다면,

$$A^{\prime }=\left[\begin{array}{rr}4& -4\\ 4& -2\end{array}\right],B^{\prime }=[-1]$$

으로 계산된다. 예를 들어 $A^{\prime }$의 $(2,1)$ 원소인 $4$의 경우,

$$A_{2,1}^{\prime }=\frac{\left|\begin{array}{rr}{A}_{2,1}& A_{2,2}\\ A_{3,1}& A_{3,2}\end{array}\right|}{B_{2,1}}=\frac{\left|\begin{array}{rr}-3& -1\\ 1& 3\end{array}\right|}{-2}=\frac{(-3)(3)-(-1)(1)}{-2}=4$$

와 같이 계산되는 식이다.

$n\times n$ 정사각행렬 $A=[A_{i,j}]$가 주어졌을 때 대하여 행렬식 $\left|A\right|$의 값을 구하는 과정은 다음과 같다. 우선 $A^{(1)}=A$로 정의하고, $B^{(1)}$은 모든 원소가 $1$인 $(n-1)\times (n-1)$ 정사각행렬로 정의하자. 그 다음으로는 귀납적으로 $A^{(i+1)}=(A^{(i)}{)}^{\prime }$, $B^{(i+1)}=(B^{(i)}{)}^{\prime }=\text{int}(A^{(i)})$와 같이 정의한다. 그러면 $A^{(1)},A^{(2)},\dots$를 구해감에 따라 행렬의 크기가 $1$씩 줄어드므로, $A^{(n)}$은 $1\times 1$ 행렬이 됨을 알 수 있는데, 이 값이 우리가 구하고자 하는 $\left|A\right|$의 값이 된다. 이 과정을 예를 들어 보면 다음과 같다.

$$\begin{array}{rl}{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]& B^{(1)}=\left[\begin{array}{rrr}1& 1& 1\\ 1& 1& 1\\ 1& 1& 1\end{array}\right],\\ & \Downarrow \\ A^{(2)}=\left[\begin{array}{rrr}5& 3& 1\\ -3& -1& 1\\ 1& 3& -1\end{array}\right]& B^{(2)}=\left[\begin{array}{rr}1& -1\\ -2& 1\end{array}\right],\\ & \Downarrow \\ A^{(3)}=\left[\begin{array}{rr}4& -4\\ 4& -2\end{array}\right]& B^{(3)}=[-1],\\ & \Downarrow \\ A^{(4)}=[-8],& B^{(4)}=\varnothing \end{array}$$

따라서 이 경우, $\left|A\right|=-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{array}{rl}{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]& B^{(1)}=\left[\begin{array}{rrr}1& 1& 1\\ 1& 1& 1\\ 1& 1& 1\end{array}\right],\\ & \Downarrow \\ A^{(2)}=\left[\begin{array}{rrr}0& -6& -4\\ 3& 0& 2\\ -4& -4& 2\end{array}\right]& B^{(2)}=\left[\begin{array}{rr}2& 2\\ 1& 1\end{array}\right],\\ & \Downarrow \\ A^{(3)}=\left[\begin{array}{rr}9& -6\\ -12& 8\end{array}\right]& B^{(3)}=\left[0\right],\\ & \Downarrow ??\end{array}$$

이므로 더이상 응집 방법을 진행할 수 없게 된다. 이러한 경우, 처음 시작하는 행렬 $A^{(1)}=A$의 행 또는 열을 적당히 교환함으로써 $B^{(i)}$가 $0$인 원소를 포함하지 않도록 해 줄 수 있다. 예를 들어 위와 같은 경우, $3$번의 행 연산을 통하여 행렬 $A$의 첫번째 행을 마지막으로 보내고 나머지 행들은 한 행씩 위로 올린 행렬 $\overline{A}$을 구한 후에 응집 방법을 적용하면 다음의 결과를 얻는다.

$$\begin{array}{rl}{\overline{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]& {\overline{B}}^{(1)}=\left[\begin{array}{rrr}1& 1& 1\\ 1& 1& 1\\ 1& 1& 1\end{array}\right],\\ & \Downarrow \\ {\overline{A}}^{(2)}=\left[\begin{array}{rrr}3& 0& 2\\ -4& -4& 2\\ -5& -5& -5\end{array}\right]& {\overline{B}}^{(2)}=\left[\begin{array}{rr}1& 1\\ 1& -3\end{array}\right],\\ & \Downarrow \\ {\overline{A}}^{(3)}=\left[\begin{array}{rr}-12& 8\\ 0& -10\end{array}\right]& {\overline{B}}^{(3)}=[-4],\\ & \Downarrow \\ {\overline{A}}^{(4)}=[-30],& B^{(4)}=\varnothing \end{array}$$

따라서 $det(\overline{A})=-30$이고 $det(A)=(-1{)}^{3}det(\overline{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$이며, 라플라스 전개등을 통해 간단히 계산할 수 있다.)