행렬을 이용한 선형연립방정식의 풀이 : 가우스 소거법

이전 글에서 선형연립방정식의 간단한 풀이법과 연립방정식의 해의 종류에 대해 알아보았습니다. 이번 글에서는 선형연립방정식의 본격적인 풀이법에 대해 알아보겠습니다. 행렬을 이용한 선형연립방정식의 풀이에는 행렬의 역행렬이나 행렬식같은 선행 개념을 필요로 하는 방법이 많기 때문에 이 글에서는 가장 간단한 가우스 소거법을 소개합니다.

 

행렬이란 선형연립방정식의 계수들만을 모아 행과 열로써 표기하는 표현방법입니다. 이러한 표기법은 선형연립방정식의 계수에 따라 해의 존재여부가 결정되는 것에서 착안해, 계수들만을 모은 행렬을 이용해서 선형연립방정식을 풀이하는 방법이 많이 연구되어졌습니다. 행렬은 또한, 이후 견고하게 정립된 원론적 개념 덕분에 선형연립방정식의 풀이를 위한 방법을 넘어 고도의 수학 개념을 표기하기 위한 강력한 도구가 되었습니다.

 

이제 행렬의 생김새를 한번 보도록 합시다. 아래는 일차연립방정식의 일반화된 표현을 계수만을 이용해 행렬로 표현한 것입니다.

 

$\begin{cases}a_{11}x_1 + a_{12}x_2 + a_{13}x_3 + \cdots + a_{1n}x_n = b_1\\a_{21}x_1 + a_{22}x_2 + a_{23}x_3 + \cdots + a_{2n}x_n = b_2\\\qquad\qquad\qquad\qquad\vdots\\a_{m1}x_1 + a_{m2}x_2 + a_{m3}x_3 + \cdots + a_{mn}x_n = b_m\end{cases}$$\Rightarrow \begin{bmatrix} a_{11} & a_{12} & a_{13} & \cdots & a_{1n} \\ a_{21} & a_{22} & a_{23} & \cdots & a_{2n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & a_{m3} & \cdots & a_{mn} \end{bmatrix}$

 

행렬을 이루는 계수 $a_{ij}$ 는 $i$행 $j$열 성분이라 칭하며 계수들의 가로줄을 행, 세로줄을 열이라고 합니다. 또한 이렇게 계수들만을 선택해 만든 행렬을 계수행렬이라고 하는데, 아래와 같이 계수행렬의 오른쪽에 $b_i = \{b_1, b_2, \cdots, b_m\}$ 를 붙이면 첨가행렬이라고 하는 새로운 행렬을 만들 수 있습니다.

 

$$\left[\begin{array}{ccccc|c} a_{11} & a_{12} & a_{13} & \cdots & a_{1n} & b_1 \\ a_{21} & a_{22} & a_{23} & \cdots & a_{2n} & b_2 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{m1} & a_{m2} & a_{m3} & \cdots & a_{mn} & b_m \end{array}\right]$$

 

본질이 선형연립방정식이기 때문에 행렬의 행과 행을 서로 바꿀 수 있고 연립방정식에서 변수를 없애는 소거법에서 했듯이 한 행 전체에 상수배를 하고 다른 행에 더할 수 있습니다. 이런 연산들은 3가지 기본행연산으로 불리웁니다.

 

E1. 두 행을 교환하는 연산

E2. 한 행에 $0$이 아닌 상수를 곱하는 연산

E3. 한 행의 상수배를 다른 행에 더하는 연산

 

이번 글에서 우리는 이 첨가행렬과 기본행연산들을 이용해서 선형연립방정식의 풀이를 해볼 것입니다.

 

가우스 소거법

가우스 소거법은 사실 단순히 선형연립방정식을 행렬의 형태로 바꿔서 풀이하는 방법에 불과합니다. 이 풀이법에 대해 설명하기 전에 먼저 예시로 사용할 선형연립방정식을 첨가행렬으로 표현해보겠습니다.

 

$\begin{cases}\ \ x_1 + 3x_2 + 2x_3 + \ \ x_4 = 3\\2x_1 + 3x_2 + \ \ x_3 - \ \ x_4 = 0\\3x_1 + \ \ x_2 + 2x_3  - \ \ x_4 = 1\\4x_1 + \ \ x_2 + 3x_3  + \ \ x_4 = 2\end{cases}\quad$$\Rightarrow \left[\begin{array}{cccc|c} 1 & 3 & 2 & 1 & 3 \\ 2 & 3 & 1 & -1 & 0 \\ 3 & 1 & 2 & -1 & 1 \\ 4 & 1 & 3 & 1 & 2 \end{array}\right]$

 

가우스 소거법의 과정은 이러합니다.

 

$1$행의 계수들에 $0$이 아닌 상수 $k$를 곱해서 나머지 행 즉, $2$행 또는 $3$행 또는 $4$행에 더해줍니다. 여기서 $k$는 곱해지는 행의 첫번째 성분이 $k$배한 $1$행과 더해졌을 때 $0$이 되게되는 수를 잡아야 합니다.

 

$\left[\begin{array}{cccc|c}a & b & c & d & e \\2 & 3 & 1 & -1 & 0 \\\vdots & \vdots & \vdots & \vdots & \vdots \\\vdots & \vdots & \vdots & \vdots & \vdots\end{array}\right]$$\sim \left[\begin{array}{cccc|c}a & b & c & d & e \\ 2+ak & 3 + bk & 1 + ck & -1 + dk & 0 + ek \\\vdots & \vdots & \vdots & \vdots & \vdots \\\vdots & \vdots & \vdots & \vdots & \vdots\end{array}\right]$

 

위의 경우 첫번째 행의 성분에 $k$배를 한 것을 두번째 행에 더했는데 이 때 두번째 행의 첫 성분 $2+ak$가 $0$이 되게하는 상수 $k=\frac{-2}{a}$ 입니다. 이렇게 구한 $k$로 두번째 행을 연산하면 됩니다.

 

$\left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\2 & 3 & 1 & -1 & 0 \\3 & 1 & 2 & -1 & 1 \\4 & 1 & 3 & 1 & 2\end{array}\right]$$\sim \left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\ 2+k & 3 + 3k & 1 + 2k & -1 + k & 0 + 3k \\3 & 1 & 2 & -1 & 1 \\4 & 1 & 3 & 1 & 2\end{array}\right]$

 

위의 경우에 상수 $k$는 $-2$가 되겠네요.

 

$\left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\2 & 3 & 1 & -1 & 0 \\3 & 1 & 2 & -1 & 1 \\4 & 1 & 3 & 1 & 2\end{array}\right]$$\sim \left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\ 2+k & 3 + 3k & 1 + 2k & -1 + k & 0 + 3k \\3 & 1 & 2 & -1 & 1 \\4 & 1 & 3 & 1 & 2\end{array}\right]$$\sim \left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\ 0 & -3 & -3 & -3 & -6 \\3 & 1 & 2 & -1 & 1 \\4 & 1 & 3 & 1 & 2\end{array}\right]$

 

이제 $2$행의 첫 성분이 $0$이 되었으니 세번째, 네번째 행에도 그 행의 첫 성분을 $0$으로 만드는 어떤 상수가 곱해진 $1$행을 더해서 행연산을 해줍니다.

 

$\left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\2 & 3 & 1 & -1 & 0 \\3 & 1 & 2 & -1 & 1 \\4 & 1 & 3 & 1 & 2\end{array}\right]$$\sim \left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\0 & -3 & -3 & -3 & -6 \\3 & 1 & 2 & -1 & 1 \\4 & 1 & 3 & 1 & 2\end{array}\right]$$\sim \left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\0 & -3 & -3 & -3 & -6 \\0 & -8 & -4 & -4 & -8 \\4 & 1 & 3 & 1 & 2\end{array}\right]$$\sim\left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\0 & -3 & -3 & -3 & -6 \\0 & 0 & 4 & 4 & 8 \\0 & -11 & -5 & -3 & -10\end{array}\right]$

 

위와 같이 이제 $1$행을 제외한 모든 행들의 첫 성분이 $0$이 되었습니다. 이렇게 됐을 때 우리는 $1$행 $1$열의 성분 $1$을 피봇(pivot)으로 설정했다고 말할 수 있습니다.

 

피봇은 보통 가장 위 왼쪽의 첫 성분을 시작점으로 잡고 피봇의 아래 열 성분을 모두 행연산을 통해 $0$으로 만든 다음, 현재피봇 바로 아래 행의 왼쪽에서부터 $0$이 아닌 수를 갖는 첫 성분을 피봇으로 잡게됩니다. 이렇게 잡은 피봇으로 역시 그 피봇 바로 아래 열 성분을 모두 $0$으로 만드는 행연산을 수행하게 됩니다. 이 연산을 행렬의 끝까지, 즉 피봇이 행렬의 가장 밑에 왔을 때까지 반복하면, 그 행렬은 아래로 갈수록 왼쪽에서부터 $0$이 많아지는 행사다리꼴 형태가 됩니다.

 

$\left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\2 & 3 & 1 & -1 & 0 \\3 & 1 & 2 & -1 & 1 \\4 & 1 & 3 & 1 & 2\end{array}\right]$$\sim \left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\0 & -3 & -3 & -3 & -6 \\3 & 1 & 2 & -1 & 1 \\4 & 1 & 3 & 1 & 2\end{array}\right]$$\sim \left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\0 & -3 & -3 & -3 & -6 \\0 & -8 & -4 & -4 & -8 \\4 & 1 & 3 & 1 & 2\end{array}\right]$$\sim\left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\0 & -3 & -3 & -3 & -6 \\0 & 0 & 4 & 4 & 8 \\0 & -11 & -5 & -3 & -10\end{array}\right]$$\sim \left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\0 & -3 & -3 & -3 & -6 \\0 & 0 & 4 & 4 & 8 \\0 & 0 & 6 & 8 & 12\end{array}\right]$$\sim \left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\0 & -3 & -3 & -3 & -6 \\0 & 0 & 4 & 4 & 8 \\0 & 0 & 0 & 2 & 0\end{array}\right]$

 

$$\left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\0 & -3 & -3 & -3 & -6 \\0 & 0 & 4 & 4 & 8 \\0 & 0 & 0 & 2 & 0\end{array}\right]$$

 

위와같은 행사다리꼴의 형태는 이 행렬을 다시 원래의 선형연립방정식으로 바꿨을 때 가우스 소거법을 사용한 이유를 이해할 수 있게 해줍니다.

 

$$\begin{cases} x_1 & +3x_2 & +2x_3 & +x_4 & = & \ 3 \\\ & -3x_2 & -3x_3 & -3x_4 & = & -6 \\\ & \ & +4x_3 & +4x_4 & = & 8 \\\ & \ & \ & +2x_4 & = & 0\end{cases}$$

 

우리는 맨 아래의 식을 통해 $x_4$의 값을 알 수 있고 알게된 $x_4$의 값과 세번째 식을 통해 $x_3$의 값을 알 수 있고 이런식으로 방정식들을 거슬러올라가 최종적으로 이 선형연립방정식의 해 $(x_1, x_2, x_3, x_4)$를 알 수 있게 됩니다. 이렇게 거슬러 올라가서 대입하는 연산을 역대입법이라고 합니다.

 

최종적인 역대입법 연산을 통해 우리는 이 선형연립방정식의 해를 $(x_1 = -1, x_2 = 0, x_3 = 2, x_4 = 0)$라고 구할 수 있으며 연립방정식의 해 $$X=\left[\begin{array}\ -1\\0\\2\\0\end{array}\right]$$ 라고 표현합니다.

 

가우스-조르단 소거법

가우스-조르단 소거법은 기존의 가우스 소거법으로 행사다리꼴을 만드는 과정에서 잡은 피봇을 전부 $1$로 만들고 피봇과 첨가행렬 부분을 제외한 나머지 성분을 전부 행연산을 통해 $0$으로 만드는 과정이 추가된 방식입니다. 위에서 사용했던 예제를 사용해보겠습니다.

 

$$\left[\begin{matrix}1 & 3 & 2 & 1 & 3 \\0 & -3 & -3 & -3 & -6 \\0 & -8 & -4 & -4 & -8 \\0 & -11 & -5 & -3 & -10\end{matrix}\right]$$

 

첫번째 피봇은 처음부터 $1$이였기 때문에 바로 다음 피봇을 정해봅시다. 두번째 행의 왼쪽으로부터 $0$이 아닌 첫번째 성분 $-3$이 바로 다음 피봇이 되겠네요. 피봇을 $1$로 만들기 위해 $2$행의 모든 성분에 $-\frac{1}{3}$을 곱해줍니다.

 

$$\left[\begin{matrix}1 & 3 & 2 & 1 & 3 \\0 & 1 & 1 & 1 & -2 \\0 & -8 & -4 & -4 & -8 \\0 & -11 & -5 & -3 & -10\end{matrix}\right]$$

 

행연산을 통해 새롭게 정한 피봇 아래를 모두 $0$으로 만드는 과정을 반복해 행사다리꼴을 만들어봅시다.

 

$\left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\0 & 1 & 1 & 1 & 2 \\0 & -8 & -4 & -4 & -8 \\0 & -11 & -5 & -3 & -10\end{array}\right]$$\sim \left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\0 & 1 & 1 & 1 & 2 \\0 & 0 & 4 & 4 & 8 \\0 & -11 & -5 & -3 & -10\end{array}\right]$$\sim \left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\0 & 1 & 1 & 1 & 2 \\0 & 0 & 4 & 4 & 8 \\0 & 0 & 6 & 8 & 12\end{array}\right]$$\sim \left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\0 & 1 & 1 & 1 & 2 \\0 & 0 & 1 & 1 & 2 \\0 & 0 & 6 & 8 & 12\end{array}\right]$$\sim \left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\0 & 1 & 1 & 1 & 2 \\0 & 0 & 1 & 1 & 2 \\0 & 0 & 0 & 2 & 0\end{array}\right]$$\sim \left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\0 & 1 & 1 & 1 & 2 \\0 & 0 & 1 & 1 & 2 \\0 & 0 & 0 & 1 & 0\end{array}\right]$

 

이렇게 피봇까지 $1$로 만든 행사다리꼴 형태에서 맨 마지막 행에 피봇을 잡고 그 피봇에 $-1$배 해서 나머지 행들에 행연산을 해줌으로써 이번에는 피봇 위의 성분들을 $0$으로 만들어줍니다.

 

$\left[\begin{array}{cccc|c}1 & 3 & 2 & 1 & 3 \\0 & 1 & 1 & 1 & 2 \\0 & 0 & 1 & 1 & 2 \\0 & 0 & 0 & 1 & 0\end{array}\right]$$\sim \left[\begin{array}{cccc|c}1 & 3 & 2 & 0 & 3 \\0 & 1 & 1 & 0 & 2 \\0 & 0 & 1 & 0 & 2 \\0 & 0 & 0 & 1 & 0\end{array}\right]$$\sim \left[\begin{array}{cccc|c}1 & 3 & 0 & 0 & -1 \\0 & 1 & 0 & 0 & 0 \\0 & 0 & 1 & 0 & 2 \\0 & 0 & 0 & 1 & 0\end{array}\right]$$\sim \left[\begin{array}{cccc|c}1 & 0 & 0 & 0 & -1 \\0 & 1 & 0 & 0 & 0 \\0 & 0 & 1 & 0 & 2 \\0 & 0 & 0 & 1 & 0\end{array}\right]$

 

이렇게 만들어진 피봇과 첨가행렬 부분을 제외한 모든 성분이 $0$인 꼴을 기약행사다리꼴이라고 합니다. 이 경우 첨가행렬 부분이 바로 이 선형연립방정식의 해가 됩니다. 역대입법이 필요없이 바로 해가 나오게 됩니다.

 

$$\left[\begin{array}{cccc|c}1 & 0 & 0 & 0 & -1 \\0 & 1 & 0 & 0 & 0 \\0 & 0 & 1 & 0 & 2 \\0 & 0 & 0 & 1 & 0\end{array}\right] \Rightarrow \begin{cases}x_1 &  &  &  & = & -1 \\& x_2 &  &  & = & 0 \\& & x_3 &  & = & 2 \\& & & x_4 & = & 0 \end{cases}$$

 

해가 무수히 많은 경우에 대한 풀이법

지금까지 가우스 소거법을 이용해서 해가 깔끔하게 하나로 떨어지는 예를 살펴보았습니다. 해가 없는 경우는 말 그대로 해가 없으니 마지막으로 무수히 많은 해를 갖는 예를 한번 들어봅시다.

 

$$\begin{cases}2x+y+z=3\\x+2y-z=3\end{cases} \Rightarrow \left[\begin{array}{ccc|c}2 & 1 & 1 & 3 \\1 & 2 & -1 & 3\end{array}\right]$$

 

이 선형연립방정식은 방정식의 개수가 미지수의 개수보다 적기 때문에 무수히 많은 해를 갖게 됨을 알 수 있습니다.

 

$\left[\begin{array}{ccc|c}2 & 1 & 1 & 3 \\1 & 2 & -1 & 3\end{array}\right]$$\sim \left[\begin{array}{ccc|c}1 & \frac{1}{2} & \frac{1}{2} & \frac{3}{2} \\1 & 2 & -1 & 3\end{array}\right]$$\sim \left[\begin{array}{ccc|c}1 & \frac{1}{2} & \frac{1}{2} & \frac{3}{2} \\0 & \frac{3}{2} & \frac{-3}{2} & \frac{3}{2}\end{array}\right]$$\sim \left[\begin{array}{ccc|c}1 & \frac{1}{2} & \frac{1}{2} & \frac{3}{2} \\0 & 1 & -1 & 1\end{array}\right]$$\sim \left[\begin{array}{ccc|c}1 & 0 & 1 & 1 \\0 & 1 & -1 & 1\end{array}\right]$

 

$$\begin{cases}x_1 &  & +x_3 & = & 1 \\& x_2 & -x_3 & = & 1\end{cases}$$

 

이런 경우에 미지수 $x_{3}$을 $t$로 치환해서 일반해를 표현하게 됩니다.

 

$$X=\left[\begin{array}\ 1 - t\\1 + t \\t\end{array}\right]$$