1. Gauss-Jordan Elimination(가우스조던 소거법)

Linear System과 Matrix로 표현

 중학교 때 연립방정식을 처음으로 배웠다. 가감법, 대입법 등등의 추억의 방식으로 x,y,z 등의 미지수들을 알아냈다. 사실 우리는 눈치채지 못했지만 우리는 Linear System을 배운 것이다.

 Linear System이란 Linear Equation(선형방정식)의 모임이다. Linear equation이란 일차방정식이라고 생각하면 쉽다. \(x_1+2x_2+4x_3+2x_4=2\) 이런게 Linear equation이다. 그러면 Linear system은 1차 연립방정식이라고 생각할 수 있다. 이러한 1차 연립방정식을 Matrix형태로 변경할 수 있다.

$$\begin{matrix} a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n=b_1 \\ a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n=b_2 \\ \vdots \\ a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n=b_m \\ \end{matrix}$$

$$\Updownarrow$$

$$\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1j} & \cdots & a_{1n}\\ a_{21} & \ddots & & \vdots & & \vdots \\ \vdots & & \ddots & \vdots & & \vdots \\ a_{i1} & \cdots & \cdots & a_{ij} & \cdots & a_{in} \\ \vdots & & & \vdots & \ddots & \vdots \\ a_{m1} & \cdots & \cdots & a_{mj} & \cdots & a_{mn} \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_j \\ \vdots \\ x_n \end{bmatrix} = \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_i \\ \vdots \\ b_m \end{bmatrix}$$

$$\Updownarrow$$

$$A\boldsymbol{x}=\boldsymbol{b}$$

 앞으로 이러한 표현을 사용하여 Linear system을 풀어볼 것이다.

---

Linear System의 Solution

 3가지의 Solution이 있다. '하나의 해가 존재한다', '해가 없다', '무수히 많은 해가 존재한다'

2차원에서는 3가지 경우가 있다. 

해가 있는 경우

해가 없는 경우

해가 무수히 많은 경우

 3차원에서는 8가지 경우가 있다.

 일반적으로 미지수가 n개 있을 경우도 마찬가지이다.

 

 어렸을 때 미지수가 n개이고 식이 n개이면 해를 구할 수가 있고, 때에 따라서 해가 없을 수도, 또 무수히 많을 수도 있다. 하지만 우리가 중고등학교 때는 미지수가 n개 식이 n개인 문제를 많이 다뤘었다.

미지수와 식이 같은 경우

 행렬식으로 표현하게 되면 이런모양이 된다. 구하고자 하는 벡터 \(\boldsymbol{x}\)와 그 결과에 해당하는 벡터 \(\boldsymbol{b}\)의 column의 개수가 같고 그에 따른 행렬 \(A\)의 모양이 정사각행렬이 된다.

 하지만 미지수와 식의 개수가 다를경우도 많이 있다. 우선 미지수가 더 많은 경우는 이런 모양이 된다.

미지수가 식보다 많은 경우

 반대로 식이 더 많은 경우는 이런 모양이 된다.

식이 미지수보다 많은 경우

 우선은 모양만 이렇구나 라고 이해만 하자.

---

Reduced Row Echelon Form(RREF)

 가우스 조던 소거법의 핵심은 행렬 \(A\)를 Reduced Row Echelon Form(RREF)으로 만드는 것이다. RREF을 만들기 전에 Row Echelon Form(REF)를 알아야한다.

 Row Echelon Form(REF)의 정의

- 전체가 0인 행은 최하단에 위치한다.

- 각 행의 첫 번째 0이 아닌 숫자의 위치는 아랫 행의 숫자가 윗 행의 숫자보다 우측에 위치한다.

 정의만 봐서는 도대체 무슨 뜻인지 전혀 감이 안온다. REF가 어떤 행렬모양을 가지고 있는지 그림으로 살펴보면 쉽게 이해할 수 있을 것이다.

$$\begin{bmatrix} 1 & * & * & * \\ 0 & 1 & * & * \\ 0 & 0 & 1 & * \\ 0 & 0 & 0 & 1\end{bmatrix},\begin{bmatrix} 1 & * & * & * \\ 0 & 1 & * & * \\ 0 & 0 & 1 & * \\ 0 & 0 & 0 & 0\end{bmatrix},\begin{bmatrix} 1 & * & * & * \\ 0 & 1 & * & * \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0\end{bmatrix},\begin{bmatrix} 0 & 1 & * & * & * & * & * & * & * \\ 0 & 0 & 0 & 1 & * & * & * & * & * \\ 0 & 0 & 0 & 0 & 1 & * & * & * & * \\ 0 & 0 & 0 & 0 & 0 & 1 & * & * & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & * \end{bmatrix}$$

 요소에서 1이 대각선에 위치하고 있다. *는 아무숫자나 와도 괜찮다는 뜻이다. 1이 위치하는 곳을 pivot이라고 부르고 1을 중심으로 왼쪽과 아래쪽의 모든 요소들이 0이다. 아직은 잘은 모르지만 \(A\)행렬을 가우스 조던 소거법으로 REF의 모양으로 만든 뒤 RREF모양으로 만들어야한다.

 Reduced Row Echelon Form(RREF)의 정의

- 각 행의 첫번째 0이 아닌 숫자가 존재하는 열에서 그 숫자를 제외하고는 모두 0이다.

- 각 행의 첫번째 0이 아닌 성분의 값은 1이다.

 여전히 정의만 봐서는 잘 모르겠다. RREF도 행렬모양을 보고 직관적으로 이해를 하자.

$$\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix},\begin{bmatrix} 1 & 0 & 0 & * \\ 0 & 1 & 0 & * \\ 0 & 0 & 1 & * \\ 0 & 0 & 0 & 0\end{bmatrix},\begin{bmatrix} 1 & 0 & * & * \\ 0 & 1 & * & * \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0\end{bmatrix},\begin{bmatrix} 0 & 1 & * & 0 & 0 & 0 & * & 0 & * \\ 0 & 0 & 0 & 1 & 0 & 0 & * & 0 & * \\ 0 & 0 & 0 & 0 & 1 & 0 & * & 0 & * \\ 0 & 0 & 0 & 0 & 0 & 1 & * & 0 & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & * \end{bmatrix}$$

 pivot을 중심으로 이제는 왼쪽, 아래, 위의 모든 요소들이 0이다. 이제 행렬\(A\)이 가우스 조던 소거법으로 RREF모양이 되었다면, 해를 한번에 구할 수가 있다.

 그 이유는 밑의 예시를 보면서 이해해보자.

---

Elementary Row Operation(ERO)

 예시를 보기전에 우선 Elementary Row Operation(ERO)을 알아야 한다. 행렬의 행간 연산을 의미한다. 연산은 총 3가지가 있다.

이러한 Matrix가 주어진다.

$$A=[a_{ij}]_{m\times n}=\begin{bmatrix} R_1 \\ R_2 \\ \vdots \\ R_m \end{bmatrix}$$

그러면 우리는 ERO를 이렇게 정의한다.

- \(aR_i \rightarrow R_i\) : i번째 행에 a만큼 상수배를 한다.

- \(R_i \leftrightarrow R_j\) : i번째 행과 j번째 행을 바꾼다.

- \(aR_i+R_j \rightarrow R_j\) : i번째 행에 a만큼 상수배한 것을 j번째 행이랑 더해서 j번째 행에 대입한다.

 이 3가지 연산을 바탕으로 가우스 조던 소거법으로 행렬 \(A\)를 RREF로 만들자.

---

Gauss-Jordan Elimination으로 Reduced Row Echelon Form 만들기