[Linear Algebra] Part13. 가우스-조던 소거법(Gauss-Jordan Elimination)

가우스 조던 소거법(이하 가우스 소거법)은 이미 우리가 알고 있는 연립방정식 풀이법과 동일하다.

단지, 선형대수에서는 방정식의 수가 매우 많은 경우를 다루기 때문에 수식을 행렬로 변형하여 다룬다.

이 때 사용되는 선형연립방정식의 행렬 버전이 가우스 소거법이라고 할 수 있다.

 

---

1. 확장행렬

가우스 소거법을 하기 위해서는 확장행렬이라는 개념이 필요하다.

아래 수식을 보자.

 

$$ \left\{\begin{matrix} x+2y=4 \\2x+5y=9 \end{matrix}\right.\Rightarrow \begin{bmatrix} 1 & 2 \\ 2 & 5 \\ \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix}=\begin{bmatrix} 4 \\ 9 \end{bmatrix}\Rightarrow \begin{bmatrix} 1 & 2 &| 4 \\ 2 & 5 &| 9 \\ \end{bmatrix} $$

 

위의 수식처럼 연립방정식을 행렬로 표현하면 가운데처럼 x, y가 그대로 있게 된다. 이를 생략한다고 했을때, 계수와 값만을 두고 보면 오른쪽 행렬과 같이 $2\times 3$ 행렬로 표현할 수 있는데, 이를 확장(확대)행렬( Augmented coefficient matrix )이라고 한다.

 

 

2. 가우스 소거법

가우스 소거법에는 몇가지 규칙이 있다.

1. 양 변에 0이 아닌 상수(k)배를 해준다
2. 상수배한 행을 다른 행에 더하거나 뺀다.
3. 행끼리 자리를 바꿔준다.

이러한 규칙은 이미 연립방정식의 소거법에서 알고있는 부분일 것이다.

 

가우스 소거법을 적용한 예시를 보자.

 

$$ \begin{bmatrix} 1 & 2 & |4 \\ 2 & 5 & |9 \\ \end{bmatrix}= \begin{bmatrix} 1 & 2 & |4 \\ 0 & 1 & |1 \\ \end{bmatrix}= \begin{bmatrix} 1 & 0 & |2 \\ 0 & 1 & |1 \\ \end{bmatrix} $$

 

첫번째 행에 2를 곱하여 두번째 행에서 빼주면 두번째 행은 [1 0 1]이 된다. 이를 방정식으로 표현하면

$2x+5y+9-2(x+2y+4) = (0x)+1y+1$이 된다. 마찬가지로 두번째 행에서 2를 곱하여 첫번째 행에서 빼주면 첫번째 행은 [1 0 2]가 되어 최종적으로 위의 수식에서 오른쪽 행렬이 된다.

 

여기서 중요한 점은 위와 같은 연산을 확장행렬의 계수부분(1열~m-1열)이 항등행렬이 될때까지 반복해주는 것이다.

계수부분이 항등행렬이 되었을때 나머지 부분(m열)이 선형연립방정식의 해가 된다.

위의 경우는 $x=2$, $y=1$이 된다.

 

 

이렇게 계수부분을 항등행렬로 만들어서 해를 찾아내는 방법을 가우스 조던 소거법이라고 한다.

 

---

위의 예시는 행렬과 벡터의 연산에서 값을 찾는 방법이었는데, 행렬과 행렬 연산에서 가우스 소거법은 적용될 수 있을까??

여기서 역행렬 개념이 나온다.

이는 다음 포스팅에서 계속 정리해보도록 하자.