(정리) $A\in\rR^{n\times n}$이 가역행렬이면 \[ PA = LDU \] 가 성립하는 순열행렬 $P$, 하삼각행렬 $L$, 대각행렬 $D$ 및 상삼각행렬 $U$가 존재한다. 여기서 $L$과 $U$의 모든 대각원소는 값이 1이라는 조건을 추가하면 이들 3개의 행렬은 유일하게 결정된다. ($A$가 가역행렬이 아니거나 정방행렬이 아닌 경우에도 LDU 분해 정리, 혹은 LU 분해 정리의 버전이 있다. 물론 유일성 등 세부 사항은 다르다.)
(용어) 순열행렬이란 타입 1 기본행렬들의 곱으로 얻어지는 행렬을 뜻한다. 타입 1 기본행렬들을 맞바꿈행렬이라고 부르기로 한다. (통상 순열행열은 치환행렬(permutation matrix), 맞바꿈행렬은 호환행렬(transposition matrix)이라고 부른다. Transposition matrix를 transpose of a matrix(전치행렬)과 혼동하지 않도록 주의할 것.)
순열행렬은 정방행렬들 중에서 ① 모든 원소는 0 아니면 1이다, ② 각 열마다 1이 딱 1개 있다, ③ 각 행마다 1이 딱 1개 있다는 조건을 만족하는 것이다. \[ \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0\end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0\end{pmatrix} \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{pmatrix} \]
팩트: 순열행렬의 디터미넌트는 $\pm 1$이다. 순열행렬의 역행렬은 순열행렬이다. 맞바꿈행렬의 디터미넌트는 $-1$이다. 맞바꿈행렬의 역행렬은 자기자신이다.
(유일성의 증명) $A$의 2개의 분해 $L_1D_1U_1 = L_2D_2U_2$가 주어졌다고 하자. 양변의 왼쪽에 $L_2^{-1}$, 오른쪽에 $U_1^{-1}$을 곱하면 다음 등식을 얻는다. \begin{align*} L_2^{-1}&L_1D_1U_1U_1^{-1} = L_2^{-1}L_2D_2U_2U_1^{-1} \\[1.5ex] &\Rightarrow L_2^{-1}L_1D_1 = D_2U_2U_1^{-1} \quad(*1) \end{align*} $(*1)$의 좌변은 하삼각행렬이고 우변은 상삼각행렬이므로 이들은 대각행렬일 수밖에 없다.
$L_2^{-1}L_1$가 진삼각행렬이라면 [보조정리 4]에 의하여 $L_2^{-1}L_1D_1$도 그러하다는 모순을 얻는다. 그러므로 $L_2^{-1}L_1$는 대각행렬이다. 또한 이 행렬은 [보조정리 3]에 의하여 대각원소가 모두 1이므로 결국 단위행렬 $I_n$일 수 밖에 없다. 이는 $L_1 = L_2$를 함의한다. 같은 방법으로 $U_2U_1^{-1} = I_n$일 것이고 $U_1 = U_2$를 얻는다. $D_1 = D_2$도 쉽게 얻어진다. $\quad\Box$
(보조정리 1) 하삼각행렬들의 곱은 하삼각 행렬이다. 상삼각행렬들의 곱은 상삼각 행렬이다.
(보조정리 2) 가역 하삼각행렬의 역행렬은 하삼각 행렬이다. 가역 상삼각행렬의 역행렬은 상삼각 행렬이다.
(보조정리 3) 보조정리 1과 2에서 주어진 행렬(들)의 대각원소가 모두 1이라면 결과로 얻은 행렬도 대각원소가 모두 1이다.
(보조정리 4) 대각행렬이 아닌 삼각행렬을 "진삼각행렬"이라고 부르기로 하자. 진삼각행렬과 가역 대각행렬의 곱은 항상 진삼각행렬이다.
(존재성의 증명) 가역행렬 $A$가 주어지면 타입 1 기본행작업을 통하여 $a_{11} \ne 0$로 만든다. 이 작업은 적당한 맞바꿈 행렬 $P_1$을 왼쪽에서 곱하는 것과 같다. $A$의 rank가 $n$이므로 이것이 가능하다. 그리고 각 $i=2,\ldots,n$에 대하여 기본행작업 $[A_i \to A_i - \frac{a_{i1}}{a_{11}}A_1]$을 적용하여 $i$째 행의 첫 원소를 0으로 만든다. 이 $n-1$개의 작업은 타입 3 기본행렬들을 왼쪽에서 곱하여 수행할 수 있다. 이 기본행렬들의 곱은 대각원소가 전부 0인 하삼각행렬이고 1-기반이다. ('기반'이라는 용어는 이 웹페이지의 맨 뒷 부분에 설명되어 있다.) 이 행렬을 $L_1$이라고 하자.
$L_1 P_1 A$를 $A$로 rename한다. $A$의 rank는 바뀌지 않아 $n$이다. $A^2$에서 $a_{22}$ 이하에 0아닌 원소가 반드시 존재한다. 그렇지 않으면 $A^1, A^2$가 선형종속이 되어 랭크가 $n$이라는 사실에 모순된다. 적당한 맞바꿈 행렬 $P_2$를 왼쪽에서 곱하여 $a_{22} \ne 0$로 만든다. $P_2$는 2-기반이다. 그리고 각 $i=3,\ldots,n$에 대하여 기본행작업 $[A_i \to A_i - \frac{a_{i2}}{a_{22}}A_2]$를 적용하여 $i$째 행의 두번 째 원소를 0으로 만든다. 이 $n-2$개의 작업은 타입 3 기본행렬들을 왼쪽에서 곱하여 수행할 수 있다. 이 기본행렬들의 곱은 대각원소가 전부 0인 하삼각행렬이고 2-기반이다. 이 행렬을 $L_2$라고 하자.
이런 식으로 진행하여 상삼각행렬 $U_a$를 얻는다. $U_a$는 대각원소 중에 1이 아닌 것이 있을 수 있으므로, 대각행렬 $D$를 $d_{ii} = U_a(i,i)$로 두면 $DU = U_a$로 쓸 수 있다. 여기서 $U$는 대각원소들이 모두 1인 상삼각행렬이다. 이제 다음의 등식을 얻는다. \[ L_{n-1} P_{n-1} \cdots L_2 P_2 L_1 P_1 A = D U\quad(*1) \] 우리는 이 식의 좌변을 $L_a P A$ 형식으로 바꾸기를 원한다. 이렇게 되면 $L := L_a^{-1}$으로 두었을 때 우리의 목표였던 $PA = LDU$를 얻을 수 있다.
$L' = PLP^{-1}$으로 두면 $PL = L'P$가 되는데 이때 $L$과 $P$가 모두 어떤 $k < n$에 대해서 $k$-기반이면 [보조정리 5]에 의하여 $L'$도 $k$-기반이 된다.
$(*1)$에서 $L_i$와 $P_{i+1}$은 모두 $i$-기반이다. $n=4$인 경우에 대해서 설명을 하겠다. 다음과 같이 $L'_i$를 정의하면 \begin{align*} L'_3 &:= L_3 \\[1.5ex] L'_2 &:= P_3 L_2 P_3^{-1} \\[1.5ex] L'_1 &:= P_3 P_2 L_1 P_2^{-1} P_3^{-1} \end{align*} $(*1)$의 좌변을 원하는 형식 $L_a P A$로 고쳐 쓸 수 있다. \begin{align*} L'_3 L'_2 & L'_1 P_3 P_2 P_1 = L_3(P_3 L_2 P_3^{-1})(P_3 P_2 L_1 P_2^{-1} P_3^{-1} )P_3 P_2 P_1 \\[1.5ex] &= L_3P_3L_2P_2L_1P_1 = L_a P,\text{ where} \\[1.5ex] L_a &:= L'_3 L'_2 L'_1, \\[1.5ex] P &:= P_3 P_2 P_1. \end{align*} 이제 $L = L_a^{-1}$으로 두면 $P A = L D U$가 성립한다. $\quad$ Q.E.D.
조금 더 쉽게 $n=3$ 경우를 보자. $L_2P_2L_1P_1A = L'_2L'_1P_2P_1A = L_aPA$ 형태로 쓰고 싶다. 다음과 같이 두면 된다. \begin{align*} L'_2 &:= L_2 \\[1.5ex] L'_1 &:= P_2 L_1 P_2^{-1} \\[1.5ex] \end{align*} 그러면 $L'_2L'_1P_2P_1A = L_2P_2L_1P_2^{-1}P_2P_1A = L_2P_2L_1P_1A$가 된다.
이제 $L_a = L'_2L'_1$, $P = P_2P_1$으로 두면 $L_2P_2L_1P_1A = DU$는 $L_aPA = DU$가 되고 양변에 $L := L_a^{-1}$을 왼쪽에서 곱하면 바라던 대로 $PA = LDU$를 얻는다. $\;\checkmark$
(문제) 다음의 가우스 소거를 보고 처음에 주어진 행렬 $A$의 $LDU$ 분해를 구하여라. 즉, $PA = LDU$를 만족하는 $P, L, D, U$를 구하여라.
\begin{align*} \begin{pmatrix} 0 & 2 & -1 \\ 1 & 3 & - 2 \\ 1 & 5 & 0 \end{pmatrix} & \Rightarrow \begin{pmatrix} 1 & 3 & - 2 \\ 0 & 2 & -1 \\ 1 & 5 & 0 \end{pmatrix} \Rightarrow \begin{pmatrix} 1 & 3 & - 2 \\ 1 & 5 & 0 \\ 0 & 2 & -1 \end{pmatrix} \Rightarrow \begin{pmatrix} 1 & 3 & - 2 \\ 0 & 2 & 2 \\ 0 & 2 & -1 \end{pmatrix} \\[1.5ex] & \Rightarrow \begin{pmatrix} 1 & 3 & - 2 \\ 0 & 2 & 2 \\ 0 & 0 & -3 \end{pmatrix} \Rightarrow \begin{pmatrix} 1 & 3 & - 2 \\ 0 & 1 & 1 \\ 0 & 0 & -3 \end{pmatrix} \Rightarrow \begin{pmatrix} 1 & 3 & - 2 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \\[1.5ex] & \Rightarrow \begin{pmatrix} 1 & 0 & - 5 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \Rightarrow \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \Rightarrow \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \end{align*}이 가우스 소거는 9단계로 이루어져 있다. $P$, $L$, $D$, $U$를 찾기 위해서는 이 단계들 중 첫 6단계만 사용한다. 왜냐하면 6단계 만에 대각원소들이 모두 1인 상삼각행렬을 얻었기 때문이다.
각 단계에서 사용된 기본행렬은 다음과 같다.
$n=3$이므로 LDU 정리의 증명에서 사용한 식 $(*1)$은 다음과 같이 된다. \[ L_2 P_2 L_1 P_1 A = D U = \begin{pmatrix} 1 & 3 & - 2 \\ 0 & 2 & 2 \\ 0 & 0 & -3 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & -3 \end{pmatrix} \begin{pmatrix} 1 & 3 & - 2 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \] 여기서 \begin{align*} P_1 &= P_{23} P_{12} = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix} \\[1.5ex] L_1 &= E_{2,1}(-1) \\[1.5ex] P_2 &= I_3 = P_{11} \\[1.5ex] L_2 &= E_{3,2}(-1) \end{align*} $L_1'$, $L_2'$, $L_a$, $L$은 다음과 같다. \begin{align*} L_2' &= L_2 = E_{3,2}(-1) \\[1.5ex] L_1' &= P_2 L_1 P_2^{-1} = L_1 = E_{2,1}(-1) \\[1.5ex] L_a &= L_2' L_1' = E_{3,2}(-1) E_{2,1}(-1) \\[1.5ex] L &= L_a^{-1} = E_{2,1}(1) E_{3,2}(1) = \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix} \end{align*} 이제 $PA = LDU$는 다음과 같이 확인된다. \[ \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 2 & -1 \\ 1 & 3 & - 2 \\ 1 & 5 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & -3 \end{pmatrix} \begin{pmatrix} 1 & 3 & - 2 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \]
$n=4$인 경우의 LDU 분해 문제이다.
\[ P = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix} \qquad A = \begin{pmatrix} 0 & 1 & 1 & 3 \\ 2 & 4 & -1 & 0 \\ 1 & 2 & 0 & 1 \\ 1 & 0 & 0 & 1 \end{pmatrix} \]인 경우에 $PA = LDU$인 $L, D, U$를 각각 구하여라.
(용어 정의) 기반이라는 용어는 하삼각 행렬, 또는 순열행렬에 대해서 사용되며 각 경우에 대한 정의가 따로 있다.
$L \in \rR^{n\times n}$이 하삼각행렬이며 대각원소들의 모두 1이라고 하자. $L^j \ne \vec e_j$가 성립하는 $j$가 $j=k$로 유일할 때 $L$을 $k$-기반이라고 한다.
$P\in \rR^{n\times n}$가 순열행렬이며 $P^j \ne \vec e_j$가 성립하는 모든 $j$가 $j > k$를 만족할 때 $P$를 $k$-기반이라고 한다.
다음의 식 $PLP^{-1} = L'$에서 $P$, $L$, $P^{-1}$, $L'$은 모두 2-기반이다. \[ \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 2 & 1 & 0 & 0 \\ 0 & 3 & 0 & 1 & 0 \\ 0 & 4 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 3 & 1 & 0 & 0 \\ 0 & 4 & 0 & 1 & 0 \\ 0 & 2 & 0 & 0 & 1 \end{pmatrix} \]
(보조정리 5) $L$과 $P$가 모두 $k$-기반이면 $P^{-1}$는 $k$기반 순열행렬이고 $P L P^{-1}$는 대각원소가 모두 1인 $k$-기반 하삼각행렬이다.
(증명) 생략
[홈으로]