$A \in \rR^{n\times n}$, $B\in\rR^{n\times 1}\; (n \in \nN)$라 하자.
$A$를 가우스 소거 한다는 것은 $A$에 기본행작업을 반복 적용하여 $I_n$으로 변환한다는 뜻이다. $I_n$으로 변환하지 못하는 경우 $A$를 특이행렬(singular matrix)이라고 한다. $A$가 특이행렬이 아닐 때 우리는 $A$가 가우스 소거를 받아들인다(admit Gaussian elimination)고 말한다.
기본행작업을 $A$에 반복 적용한다는 것은 곧 기본행 작업 행렬을 $A$의 왼편에 계속 곱한다는 것과 같다. 따라서 $A$가 가우스 소거를 받아들인다는 것은 곧 다음과 같이 쓸 수 있다는 뜻이다. \[ E_m \cdots E_2 E_1 A = I_n\quad(\text{단, $E_i$들은 기본행작업 행렬})\quad(*1) \]
기본행작업 행렬 $E$는 역행렬 $E^{-1}$을 가지며 이때 $E^{-1}$의 타입은 $E$의 타입과 동일하다. 다음을 쉽게 확인할 수 있다. \begin{align*} & P_{ij}^{-1} = P_{ij} \\[1.5ex] & E_{n,i}(k)^{-1} = \textstyle E_{n,i}(\frac{1}{k}),\quad(k\ne 0) \\[1.5ex] & E_{ij}(k)^{-1} = E_{ij}(-k) \end{align*}
$(*1)$은 $A = E_1^{-1}\cdots E_m^{-1}$과 동등하다. $E_i^{-1}$들은 모두 기본행렬이므로 다음과 같이 말할 수 있다. \begin{align*} A\text{는 가우스} &\text{소거를 받아들인다.} \\[1.5ex] & \Leftrightarrow A\text{는 기본행렬들의 곱으로 나타낼 수 있다.} \\[1.5ex] & \Leftrightarrow A\text{에 기본행렬들을 왼쪽에서 곱하여 단위행렬로 변환할 수 있다.} \\[1.5ex] & \Leftrightarrow A^{-1}\text{가 존재한다.} \end{align*} 마지막 $\Leftrightarrow$의 $\Leftarrow$는 증명이 필요하다. 다음에 하나의 증명을 보였다.
(증명) $A^{-1}$이 존재한다고 가정한다. 그러면 $A$의 열벡터 중에 $\vec 0$는 없다. 그렇지 않다면, 예를 들어 $A^j = \vec 0$라면, $I_n = A^{-1} A$의 $j$번째 열은 $A^{-1} A^j = \vec 0$이다. 이것은 $I_n^j \ne \vec 0$에 모순된다. (이것은 행렬곱을 보는 2번째 관점에서 보면 이해하기 쉽다.)
적당한 타입 1 기본행렬을 $A$의 왼쪽에 곱하여 $a_{11} \ne 0$로 만들 수 있다. 결과로 얻은 행렬의 왼쪽에 적당한 타입 3 행렬들을 곱하여 1째 행을 제외한 모든 행의 1열의 원소가 0이 되도록 할 수 있다. 이때 결과로 얻은 행렬 $A_{[1]}$의 2번째 열의 원소들을 보면, \[ A_{[1]}(2,2),\ldots,A_{[1]}(n,2)\text{들 중에 적어도 하나는 0이 아니다.} \quad{(*1)} \] 이는 만일 이 모든 원소들이 0이라면 다음과 같은 모순이 얻어질 것이기 때문이다.
$A_{[1]}$은 $A$에 가역행렬을 곱하여 얻은 것이므로 랭크가 $n$이어야 한다. 그러나 $A_{[1]}^1$과 $A_{[1]}^2$는 선형종속이므로 $A_{[1]}$의 랭크는 $n$보다 작아야 한다. $\;(\contradiction)$
$A_{[1]}$울 $A$로 rename 하고, 여기에 적당한 타입 1 기본행렬을 곱하여 $a_{22} \ne 0$가 되도록 한 다음, 결과로 얻은 행렬에 적당한 타입 3 행렬들을 곱하여 2째 행을 제외한 모든 행의 2열의 원소가 0이 되도록 할 수 있다. 이때 결과로 얻은 행렬 $A_{[2]}$의 3번째 열의 원소들을 보면, \[ A_{[2]}(3,3),\ldots,A_{[2]}(n,3)\text{들 중에 적어도 하나는 0이 아니다.} \quad{(*1)} \] 이는 만일 이 모든 원소들이 0이라면 다음과 같은 모순이 얻어질 것이기 때문이다.
$A_{[2]}$는 $A$에 가역행렬을 곱하여 얻은 것이므로 랭크가 $n$이어야 한다. 그러나 $A_{[2]}^1$, $A_{[2]}^2$, $A_{[2]}^3$는 선형종속이므로 $A_{[2]}$의 랭크는 $n$보다 작아야 한다. $\;(\contradiction)$
이런 식으로 계속하면 결국 $A$에 기본행렬들을 곱하여 대각원소에 0이 없는 대각행렬을 얻을 수 있다. 이 대각행렬에 타입 2 기본행렬들을 곱하여 $I_n$을 얻을 수 있다.
이것으로써 $A$가 가우스 소거를 받아들임이 증명되었다. $\;\Box$
가우스 소거를 알았으니 이제 LDU 분해정리를 공부할 좋은 시점이다.
선형방정식 $AX = B$의 해를 구할 때는 가우스 소거를 $A$에 대해서 하는 것이 아니라 $[A \:|\: B] \in \rR^{n\times (n+1)}$에 대해서 한다. 이렇게 하면 가우스 소거의 결과는 \[ [I \:|\: A^{-1}B] \] 가 된다. 즉, 이 방정식의 해 $X = A^{-1}B$가 결과로 얻은 행렬의 맨 오른쪽 열에 나타나게 된다.
두 선형방정식 $AX = B_1$, $AX = B_1$의 해를 구할 때는 가우스 소거를 2번 하는 것이 아니라 $[A \:|\: B_1 \:|\: B_2] \in \rR^{n\times (n+2)}$에 대해서 한다. 이렇게 하면 가우스 소거의 결과는 \[ [I \:|\: A^{-1}B_1 \:|\: A^{-1}B_2] \] 가 되어 두 방정식의 해를 동시에 구할 수 있다.
$n$개의 선형방정식 $AX = \vec e_1, \ldots, AX = \vec e_n$의 해를 구할 때는 가우스 소거를 $[A \:|\: I_n] \in \rR^{n\times 2n)}$에 대해서 한다. 이렇게 하면 가우스 소거의 결과는 \[ [I \:|\: A^{-1}] \] 가 되어 $A$의 역행렬을 구할 수 있다.
가우스-조던 소거는 가우스 소거와 혼용하여 쓰이는 용어인데, 대체로 $M$이 2개 이상의 열벡터를 가지는 행렬일 때 $[A \:|\: M]$에 대해서 행하는 가우스 소거를 가우스-조던 소거라고 부른다고 생각하면 될 것이다. 예를 들어 $[A \:|\: I]$의 가우스 소거는 대부분 가우스-조던 소거라고 부른다.
$B$가 열벡터이고 $[A \:|\: B]$를 가우스 소거하여 $AX = B$의 해 $(x_1,\ldots,x_n)^T$를 구할 때 다음과 같은 단계를 거치는 경우가 많다: 먼저 $A$를 상삼각행렬로 만든다. 여기까지를 forward elimination이라고 부른다. 그 다음은 \begin{align*} x_n &= b_n / a_{nn} \\[1.5ex] x_{n-1} &= (b_{n-1} - a_{n-1,n}x_n)/a_{n-1,n-1} \\[1.5ex] &\vdots \\[1.5ex] x_1 &= (b_1 - a_{12}x_2 - \cdots - a_{1n}x_n)/a_{11} \end{align*} 와 같이 계산하여 $x_n, \ldots, x_1$을 구하며, 이 과정을 back substitution이라고 부른다.
[홈으로]