가우스 소거법(Gaussian elimination)

미지수가 같은 1차 연립방정식은 하나의 체계를 이룬다. 1차 연립방정식이 이루고 있는 체계를 연구하는 것이 선형대수(Linear Algebra)다.

먼저 연립방정식을 쉽게 풀어보자.

\begin{alignat}{7} x &&\; + \;&& 3y &&\; - \;&& 2z &&\; = \;&& 5 & \\ 3x &&\; + \;&& 5y &&\; + \;&& 6z &&\; = \;&& 7 & \\ 2x &&\; + \;&& 4y &&\; + \;&& 3z &&\; = \;&& 8 & \end{alignat}

첫째 식에서 $x = 5 + 2z − 3y$을 나머지 식에 대입한다.

\begin{alignat}{5} -4y &&\; + \;&& 12z &&\; = \;&& -8 & \\ -2y &&\; + \;&& 7z &&\; = \;&& -2 & \end{alignat}

다시 정리하여 $y = 2 + 3z$를 대입하여 $z=2$를 구한다.

\begin{alignat}{7} x &&\; = \;&& 5 &&\; + \;&& 2z &&\; - \;&& 3y & \\ y &&\; = \;&& 2 &&\; + \;&& 3z && && & \\ z &&\; = \;&& 2 && && && && & \end{alignat}

연립방정식은 다음과 같은 방법으로 푼다.

1. 방정식의 순서를 바꾼다.

2. 양변에 0이 아닌 상수를 곱한다.

3. 양변에 상수를 곱한 방정식을 더한다.

위 연립방정식을 행렬로 나타내면 아래와 같다.

$$\left(\begin{array}{rrr} 1 & 3 & -2  \\ 3 & 5 & 6  \\ 2 & 4 & 3  \end{array}\right) \left(\begin{array}{r} x \\ y \\ z \end{array} \right)=\left(\begin{array}{r}5 \\ 7 \\ 8 \end{array} \right)$$

풀이 과정을 확장된 행렬로 나타내면 왼쪽 행렬을 단위행렬로 만드는 것과 같다.

아래와 같은 행 연산으로 해가 달라지지 않는다. 이 방법이 가우스 소거법이다.

1. 행렬의 두 행을 바꾼다.                                             $E_{ij}$ : $i$행과 $j$행을 바꾼다.          

2. 한 행의 모든 성분에 0이 아닌 상수를 곱한다.             $E_i(c)$ : $i$행에 상수 $c$를 곱한다. (단, $c\not=0$)

3. 상수를 곱한 행을 다른 행에 더한다.                          $E_{ij}(d)$ : $j$행에 상수 $d$를 곱해서 $i$행에 더한다.  (단, $d\not=0$)

이제 가우스 소거법으로 문제를 풀어보자. 미지수 $x,y,z$는 별다른 역할을 하지 않고 자리만 차지하고 있다.

$$\left[\begin{array}{rrr|r} 1 & 3 & -2 & 5 \\ 3 & 5 & 6 & 7 \\ 2 & 4 & 3 & 8 \end{array}\right]$$

\begin{align}&\left[\begin{array}{rrr|r} 1 & 3 & -2 & 5 \\ 3 & 5 & 6 & 7 \\ 2 & 4 & 3 & 8 \end{array}\right]E_{21}(-3)\sim \left[\begin{array}{rrr|r} 1 & 3 & -2 & 5 \\ 0 & -4 & 12 & -8 \\ 2 & 4 & 3 & 8 \end{array}\right]E_{31}(-2)\sim \left[\begin{array}{rrr|r} 1 & 3 & -2 & 5 \\ 0 & -4 & 12 & -8 \\ 0 & -2 & 7 & -2 \end{array}\right]\\ &E_{2}(-\frac{1}{4})\sim \left[\begin{array}{rrr|r} 1 & 3 & -2 & 5 \\ 0 & 1 & -3 & 2 \\ 0 & -2 & 7 & -2 \end{array}\right] E_{32}(2)\sim \left[\begin{array}{rrr|r} 1 & 3 & -2 & 5 \\ 0 & 1 & -3 & 2 \\ 0 & 0 & 1 & 2 \end{array}\right]E_{23}(3)\sim \left[\begin{array}{rrr|r} 1 & 3 & -2 & 5 \\ 0 & 1 & 0 & 8 \\ 0 & 0 & 1 & 2 \end{array}\right]\\&E_{13}(2)\sim \left[\begin{array}{rrr|r} 1 & 3 & 0 & 9 \\ 0 & 1 & 0 & 8 \\ 0 & 0 & 1 & 2 \end{array}\right]E_{12}(-3)\sim \left[\begin{array}{rrr|r} 1 & 0 & 0 & -15 \\ 0 & 1 & 0 & 8 \\ 0 & 0 & 1 & 2 \end{array}\right]\end{align}

마지막을 정리하여 아래와 같은 해를 구할 수 있다.

$$x=-15,~y=8,~z=2$$

이 가우스 소거법을 이용하여 역행렬을 구한다.

$$A = \begin{pmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{pmatrix}$$

의 역행렬을 $A^{-1}$라고 하면 아래와 같이 곱해서 단위행렬 $I$가 되는 행렬이다.

$$AA^{-1}=A^{-1}A=I$$

$$AA^{-1} = \begin{pmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{pmatrix} \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$$

$$ [ A | I ] = \left[ \begin{array}{rrr|rrr} 2 & -1 & 0 & 1 & 0 & 0\\ -1 & 2 & -1 & 0 & 1 & 0\\ 0 & -1 & 2 & 0 & 0 & 1 \end{array} \right]$$

$$[ I | A^{-1} ] = \left[ \begin{array}{rrr|rrr} 1 & 0 & 0 & \frac{3}{4} & \frac{1}{2} & \frac{1}{4}\\[3pt] 0 & 1 & 0 & \frac{1}{2} & 1 & \frac{1}{2}\\[3pt] 0 & 0 & 1 & \frac{1}{4} & \frac{1}{2} & \frac{3}{4} \end{array} \right]$$

번거롭지만 아래를 가우스 소거법으로 정리하면 3차 행렬의 역행렬을 구할 수 있다.

$$ [ A | I ] = \left[ \begin{array}{rrr|rrr} a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\  a_{21} & a_{22} & a_{23} & 0 & 1 & 0\\ a_{31} & a_{32} & a_{33}& 0 & 0 & 1 \end{array} \right]$$

편의를 위해 행렬 $A$에서 $i$행, $j$열을 지운 행렬을 $M_{ij}$라고 하자. 참고 작은(minor) 행렬 

$$ \sim\left[ \begin{array}{rrr|rrr} a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & |M_{33}| & |M_{32}| & -a_{21} & a_{11} & 0\\ 0 & |M_{23}| & |M_{22}|& -a_{31} & 0 & a_{11} \end{array} \right]$$

$$ \sim\left[ \begin{array}{rrr|rrr} a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & |M_{33}| & |M_{32}| & -a_{21} & a_{11} & 0\\ 0 & 0 & |M_{33}||M_{22}|-|M_{23}||M_{32}|& -a_{31}|M_{33}|+a_{21}|M_{23}| & -a_{11}|M_{23}| & a_{11}|M_{33}| \end{array} \right]$$

여기서 잠깐 숨을 고르며 아래를 계산해보자.

$|M_{33}||M_{22}|-|M_{23}||M_{32}|$

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

$=a_{11}a_{22}a_{11}a_{33}-a_{11}a_{22}a_{13}a_{31}-a_{12}a_{21}a_{11}a_{33}+a_{12}a_{21}a_{13}a_{31}$

$-(a_{11}a_{32}a_{11}a_{23}-a_{11}a_{32}a_{13}a_{21}-a_{31}a_{12}a_{11}a_{23}+a_{31}a_{12}a_{13}a_{21})$

$=a_{11} [ a_{11}(a_{22}a_{33}-a_{32}a_{23})-a_{12}(a_{21}a_{33}-a_{31}a_{23})+a_{13}(-a_{22}a_{31}+a_{32}a_{21}) ]$

$=a_{11}(a_{11} |M_{11}|-a_{12}|M_{12}|+a_{13}|M_{13}|)$

여기서 $\det(A)=a_{11} |M_{11}|-a_{12}|M_{12}|+a_{13}|M_{13}|$로 놓기로 하자. 한편

$-a_{31}|M_{33}|+a_{21}|M_{23}|$

$=-a_{31}(a_{11}a_{22}-a_{12}a_{21})+a_{21}(a_{11}a_{32}-a_{12}a_{31})$

$=a_{11}|M_{13}|$이다.

$$ \sim\left[ \begin{array}{rrr|rrr} a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & |M_{33}| & |M_{32}| & -a_{21} & a_{11} & 0\\ 0 & 0 & a_{11}\det(A)& a_{11}|M_{13}| & -a_{11}|M_{23}| & a_{11}|M_{33}| \end{array} \right]$$

$$\sim \left[ \begin{array}{rrr|rrr} a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & |M_{33}| & |M_{32}| & -a_{21} & a_{11} & 0\\ 0 & 0 & 1 & \frac{|M_{13}|}{\det(A)} & -\frac{|M_{23}|}{\det(A)} & \frac{|M_{33}|}{\det(A)} \end{array} \right]$$  

$$ \sim \left[ \begin{array}{rrr|rrr} a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & |M_{33}| & 0 & -a_{21}-\frac{|M_{32}||M_{13}|}{\det(A)}  & a_{11} +\frac{|M_{32}||M_{23}|}{\det(A)} & -\frac{|M_{32}||M_{33}|}{\det(A)} \\ 0 & 0 & 1 & \frac{|M_{13}|}{\det(A)} & -\frac{|M_{23}|}{\det(A)} & \frac{|M_{33}|}{\det(A)} \end{array} \right]$$  

위에서

$|M_{33}||M_{22}|-|M_{23}||M_{32}|=a_{11} \det(A)$

임을 활용하면 마무리 할 수 있다.

대각선(trace) 위 쪽 성분을 모두 $0$으로 만들어 보자. 지저분하지만 마무리하면 아래와 같이 역행렬을 구할 수 있다.

$$\mathbf{A}^{-1} = \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix}^{-1} = \frac{1}{\det(\mathbf{A})} \begin{pmatrix} \, A_{11} & \, A_{12}  & \,A_{13}  \\ \, A_{21} & \, A_{22}  & \,A_{23}   \\ \, A_{31} & \, A_{32}  & \,A_{33}   \\ \end{pmatrix}^T = \frac{1}{\det(\mathbf{A})} \begin{pmatrix} \, A_{11} & \, A_{21}  & \,A_{31}  \\ \, A_{12} & \, A_{22}  & \,A_{32}   \\ \, A_{13} & \, A_{23}  & \,A_{33}   \\ \end{pmatrix}$$

성분은 아래와 같은 행렬을 나머지 인자(cofactor) 행렬이라고 하고 이 행렬을 행과 열을 바꾼 전치(Transpose) 행렬을 수반(Adjugate or Adjoint) 행렬로 부른다.

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

$$cofactor\;\; matrix \;\;of \;\;A =\begin{pmatrix} \, A_{11} & \, A_{12}  & \,A_{13}  \\ \, A_{21} & \, A_{22}  & \,A_{23}   \\ \, A_{31} & \, A_{32}  & \,A_{33}   \\ \end{pmatrix}$$

$$adj(A) =\begin{pmatrix} \, A_{11} & \, A_{21}  & \,A_{31}  \\ \, A_{12} & \, A_{22}  & \,A_{32}   \\ \, A_{13} & \, A_{23}  & \,A_{33}   \\ \end{pmatrix}$$

다시 적으면 $$\mathbf{A}^{-1} = \frac {1} {\det(\mathbf{A})} \, \mathrm{adj}(\mathbf{A}) $$

더 깔끔한 방법이 있으나 설명하자면 너무 길어서 생략. 궁금하면 선형대수를 공부하기를....

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

위 행렬식은 묶는 방법을 달리하면 아래와 같이 여러 가지로 적을 수 있다. 행렬식을 쉽게 기억하기 위한 Rule of Sarrus이 있다.

$$\begin{align}\det(A)&=&a_{11}|M_{11}|-a_{12}|M_{12}|+a_{13}|M_{13}|\\&=&a_{11}|M_{11}|-a_{21}|M_{21}|+a_{31}|M_{31}|\\&=&\vdots\\&=&a_{31}|M_{31}|-a_{32}|M_{32}|+a_{33}|M_{33}|\end{align}$$ 

행렬식을 다시 정리하면 $a_{11}a_{22}a_{33}+a_{12}a_{23}a_{31}+a_{13}a_{21}a_{32}-a_{13}a_{22}a_{31}-a_{11}a_{23}a_{32}-a_{12}a_{21}a_{33}$인데 아래 그림에서 실선은 $+$ 점선은 $-$로 기억하면 된다.

 

$n$차 행렬에서 행렬식을 더욱 엄밀하게 정의한다면 아래와 같다.

$$\det(A) = \sum_{\sigma \in S_n} sgn (\sigma) \prod_{i=1}^n a_{i\sigma_i}$$

$sgn(\sigma)=(-1)^{N(\sigma)}$이다. 여기서 $\sigma$는 $\{1,2,3,\cdots,n\}$으로 이루어진 순열(permutation)이고 $N(\sigma)$는 $\sigma$에 따라 차례가 바뀌는 $i<j$ 일 때, $\sigma(i) > \sigma(j)$인 순서쌍 $(i,j)$의 개수다.  

연립방정식의 해를 쉽게 계산할 수 있는 크래머 공식(Cramer's rule)을 기억해 두자.

\begin{alignat}{7} x &\; + &\; 3y &\; - &\; 2z &\; = &\; 5 \\ 3x &\; + &\; 5y &\; + &\; 6z &\; = &\; 7 \\ 2x &\; + &\; 4y &\; + &\; 3z &\; = &\; 8 \end{alignat}

$$x=\frac {\,\left| \begin{matrix}5&3&-2\\7&5&6\\8&4&3\end{matrix} \right|\,} {\,\left| \begin{matrix}1&3&-2\\3&5&6\\2&4&3\end{matrix} \right|\,} ,\;\;\;\;y=\frac {\,\left| \begin{matrix}1&5&-2\\3&7&6\\2&8&3\end{matrix} \right|\,} {\,\left| \begin{matrix}1&3&-2\\3&5&6\\2&4&3\end{matrix} \right|\,} ,\;\;\;\;z=\frac {\,\left| \begin{matrix}1&3&5\\3&5&7\\2&4&8\end{matrix} \right|\,} {\,\left| \begin{matrix}1&3&-2\\3&5&6\\2&4&3\end{matrix} \right|\,}$$

Applications_of_linear_algebra.pdf

다운로드

Applied_Linear_Algebra_And_Matrix_Analysis_-_Thomas_S._Shor.pdf

다운로드