Linear Equation
연립일차방정식의 풀이법을 알아보기 전에, Linear algebra에서 주로 다루게 되는 Linear equation에 대해서 간단히 소개하고자 한다. Linear equation이란
$$ a_1x_1 + a_2x_2 + a_3x_3 + \cdots + a_nx_n = b $$
형태의 방정식을 말하며 아래의 세 가지 조건을 만족한다.
- $a_1$, $a_2$, $a_3$, $\cdots$, $a_n$, $b$ : const.
- $a_1$, $a_2$, $a_3$, $\cdots$, $a_n$ is not all zero
- $x_1$, $x_2$, $x_3$, $\cdots$, $x_n$ : variables
직관적으로 보았을 때 변수들이 서로 상수곱과 덧셈으로 결합되어 있는 관계식, 즉 선형적인 결합으로 이루어져 있는 방정식이 바로 Linear equation인 것으로 생각할 수 있다.
몇 가지 중요한 성질들
Linear equation의 성질들을 다루는 이유는 이들이 Gaussian elimination을 통해 연립방정식의 해를 얻을 수 있는 기저로 작용하기 때문이다. 반드시 상기할 필요는 없으나, 아래의 성질들을 이해한다면 Gaussian elimination이 성립하는 이유를 쉽게 알 수 있기에 한 번쯤 읽어보는 것을 추천한다.
- If $ \begin{cases} x=s \\ y=t \\ z=r \end{cases} $ is a solution, then $ \begin{cases} x=ks \\ y=kt \\ z=kr \end{cases} $ is also a solution (k is const.)
- If $ \begin{cases} a_1x_1 + a_2x_2 + a_3x_3 + \cdots + a_nx_n = b_1 \\ a_1y_1 + a_2y_2 + a_3y_3 + \cdots + a_ny_n = b_2 \end{cases} $,
then $ a_1\left( x_1 + y_1\right) + a_2\left( x_2 + y_2\right) + a_3\left( x_3 + y_3\right) + \cdots + a_n\left( x_n + y_n\right) = b_1 + b_2 $ - If $ \begin{cases} c_1, c_2, c_3, \cdots , c_n \\ h_1, h_2, h_3, \cdots , h_n \end{cases} $ is a solution to $ \begin{cases} a_1x_1 + a_2x_2 + a_3x_3 + \cdots + a_nx_n = C \\ a_1x_1 + a_2x_2 + a_3x_3 + \cdots + a_nx_n = 0 \end{cases} $,
then $ c_1 + h_1, c_2 + h_2, c_3 + h_3, \cdots , c_n + h_n $ is a solution to $ a_1x_1 + a_2x_2 + a_3x_3 + \cdots + a_nx_n = C $ - If $ \begin{cases} c_1, c_2, c_3, \cdots , c_n \\ d_1, d_2, d_3, \cdots , d_n \end{cases} $ is a solution to $ a_1x_1 + a_2x_2 + a_3x_3 + \cdots + a_nx_n = C $,
then $ c_1 - d_1, c_2 - d_2, c_3 - d_3, \cdots , c_n - d_n $ is a solution to $ a_1x_1 + a_2x_2 + a_3x_3 + \cdots + a_nx_n = 0 $
위 성질들을 해석해보면, Linear equation의 해는 그 또한 선형성을 가진다는 것을 알 수 있다.
가우스 소거법 (Gaussian Elimination)
기약 행사다리꼴 (Reduced Row Echelon Form)
Gaussian elimination의 최종적인 목표는 주어진 연립방정식을 RREF 꼴로 표현하는 것이다. 먼저 Row Echelon Form(REF)과 Reduced Row Echelon Form(RREF)이 무엇인지 알아보자.
REF는 행사다리꼴이라는 용어로 표현하기도 한다. 이름으로부터 뭔가 사다리꼴 모양이 행렬에서 나타날 것을 유추할 수 있을 것이다. 엄밀하게는 아래의 조건들을 만족하는 행렬을 REF라고 한다.
- 각 행의 0이 아닌 첫 번째 성분은 1이다.
- $i$번째 행의 첫 번째 1은 $i+1$번째 행의 첫 번째 1의 왼쪽에 위치한다.
- 모든 성분이 0인 행은 행렬의 맨 아래에 위치한다.
아래 행렬들은 모두 REF의 예시이다.
$$ \begin{bmatrix} 1 & 4 & -3 & 7 \\ 0 & 1 & 6 & 2 \\ 0 & 0 & 1 & 5 \end{bmatrix}, \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix}, \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} $$
RREF는 기약 행사다리꼴이라고도 한다. RREF는 REF 중에서도 아래의 조건을 추가적으로 만족하는 행렬이다.
- 각 행의 0이 아닌 첫 번째 성분 1은 그 행의 유일한 non-zero 성분이다.
아래 행렬들은 모두 RREF의 예시이다.
$$ \begin{bmatrix} 1 & 0 & 0 & 4 \\ 0 & 1 & 0 & 7 \\ 0 & 0 & 1 & -1\end{bmatrix}, \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \begin{bmatrix} 0 & 1 & -2 & 0 & 1 \\ 0 & 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} $$
기본행연산 (Elementary Row Operation)
아래의 연립일차방정식을 풀이하는 상황에서, 연립방정식의 다음 행렬과 같이 표현할 수 있다.
$$ \begin{cases} a_{11}x + a_{12}y + a_{13}z = b_1 \\ a_{21}x + a_{22}y + a_{23}z = b_2 \\ a_{31}x + a_{32}y + a_{33}z = b_3 \end{cases} \quad \Rightarrow \quad \begin{bmatrix} a_{11} & a_{12} & a_{13} & b_1 \\ a_{21} & a_{22} & a_{23} & b_2 \\ a_{31} & a_{32} & a_{33} & b_3 \end{bmatrix} $$
그런데 앞서 살펴보았던 Linear equation의 성질에 의해 연립방정식의 해는 보존하면서 행렬의 형태를 바꾸는 방법이 존재한다. 그것이 바로 기본행연산이다.
기본행연산은 아래 3가지 방법으로 행렬을 변형시키는 것이다.
- 두 행의 순서를 바꾼다.
- 한 행에 0이 아닌 상수를 곱한다.
- 한 행에 상수를 곱한 결과를 다른 행에 더한다.
따라서, Gaussian elimination이란 결국 연립일차방정식을 행렬의 형태로 나타내고, 그 행렬을 기본행연산을 통해 RREF 꼴로 바꾸어 그 해를 구하는 방법이라고 할 수 있다.
왜 RREF 형태로의 변환이 필요한지 생각해보자. 만일 아래와 같이 주어진 연립일차방정식을 기본행연산을 통해 RREF 형태로 변환한 상황을 가정해보자.
$$ \begin{cases} x-4y-2z=2 \\ -x+6y+3z=-1 \\ 2x-8y-2z=18 \end{cases} \quad\Rightarrow\quad \begin{bmatrix} 1 & -4 & -2 & 2 \\ -1 & 6 & 3 & -1 \\ 2 & -8 & -2 & 18 \end{bmatrix} \quad\Rightarrow\quad \begin{bmatrix} 1&0&0&4 \\ 0&1&0&-3 \\ 0&0&1&7 \end{bmatrix}$$
이 상황은 다시 아래와 같은 연립방정식으로 나타낼 수 있다.
$$ \begin{cases} 1x+0y+0z=x=4 \\ 0x+1y+0z=y=-3 \\ 0x+0y+1z=z=7 \end{cases} $$
즉 RREF 형태로 변환한 행렬의 맨 마지막 열이 바로 연립방정식의 해가 되기 때문에 Gaussian elimination에서는 기본행연산을 통해 RREF 꼴을 구하는 것이 최종적인 목표가 되는 것이다.
예제
아래 연립일차방정식을 Gaussian elimination을 사용해 풀이함으로써 Gaussian elimination을 완벽히 이해하며 글을 마치고자 한다.
$$ \begin{cases} x-4y-2z=2 \\ -x+6y+3z=-1 \\ 2x-8y-2z=18 \end{cases} $$
행렬을 통해 연립방정식을 표현하면 다음과 같다.
$$ \begin{bmatrix} 1 & -4 & -2 & 2 \\ -1 & 6 & 3 & -1 \\ 2 & -8 & -2 & 18 \end{bmatrix} $$
이제 기본행연산을 통해 주어진 행렬을 RREF 꼴로 변환할 차례이다. 1행에 -2를 곱하여 3행에 더하면,
$$ \begin{bmatrix} 1 & -4 & -2 & 2 \\ -1 & 6 & 3 & -1 \\ 0 & 0 & 2 & 14 \end{bmatrix} $$
3행에 $\frac{1}{2}$를 곱하면,
$$ \begin{bmatrix} 1 & -4 & -2 & 2 \\ -1 & 6 & 3 & -1 \\ 0 & 0 & 1 & 7 \end{bmatrix} $$
2행에 1행을 더하면,
$$ \begin{bmatrix} 1 & -4 & -2 & 2 \\ 0 & 2 & 1 & 1 \\ 0 & 0 & 1 & 7 \end{bmatrix} $$
3행에 -1을 곱하여 2행에 더하면,
$$ \begin{bmatrix} 1 & -4 & -2 & 2 \\ 0 & 2 & 0 & -6 \\ 0 & 0 & 1 & 7 \end{bmatrix} $$
2행에 $\frac{1}{2}$를 곱하면,
$$ \begin{bmatrix} 1 & -4 & -2 & 2 \\ 0 & 1 & 0 & -3 \\ 0 & 0 & 1 & 7 \end{bmatrix} $$
3행에 2를 곱하여 1행에 더하면,
$$ \begin{bmatrix} 1 & -4 & 0 & 16 \\ 0 & 1 & 0 & -3 \\ 0 & 0 & 1 & 7 \end{bmatrix} $$
2행에 4를 곱하여 1행에 더하면,
$$ \begin{bmatrix} 1 & 0 & 0 & 4 \\ 0 & 1 & 0 & -3 \\ 0 & 0 & 1 & 7 \end{bmatrix} $$
따라서 연립방정식의 해는 $x=4$, $y=-3$, $z=7$ 이다.