[Linear Algebra] 가우스-요르단(Gauss-Jordan) 소거법

---

기본 행 연산과 행동치

 

• 연립 방정식 풀이

연립 일차방정식을 풀 때 각 방정식끼리의 연산을 통해 풀기 쉬운 방정식으로 변환하여 풀이하는 것이 일반적이다. 예를 들어 아래와 같은 연립 일차방정식이 있다고 가정하자.

$$ \begin{cases} 3x +  6x_2= 15 & \cdots (1) \\ -x + 7x_2 = 4 & \cdots (2) \end{cases} $$

이 연립 방정식을 아래와 같이 풀 수 있을 것이다.

• $ (2) \times 3 $

$$ \begin{cases} 3x + 6x_2 = 15 & \cdots (1) \\ -3x + 21x_2 = 12 & \cdots (2) \end{cases} $$

• $ (1) + (2) $

$$ \begin{cases} 3x + 6x_2 = 15 & \cdots (1) \\ 0 + 27x_2 = 27 & \cdots (2) \end{cases} \\ \therefore x_2 = 1 $$

• $ (1) \div 3 $

$$ \begin{cases} x + 2x_2 = 5 & \cdots (1) \\ 0 + x_2 = 1 & \cdots (2) \end{cases} \\ \therefore x = 3 $$

이러한 방법은 연립 방정식을 확대행렬로 변환한 후에도 적용시킬 수 있다. 위 과정을 확대행렬을 통해 확인하면 아래와 같다.

$$ \begin{bmatrix} \begin{array}{cc:c} 3 & 6 & 15 \\ -1 & 7 & 4 \end{array} \end{bmatrix} $$

$$ \begin{bmatrix} \begin{array}{cc:c} 3 & 6 & 15 \\ 0 & 27 & 27 \end{array} \end{bmatrix} $$

$$ \begin{bmatrix} \begin{array}{cc:c} 1 & 2 & 5 \\ 0 & 1 & 1 \end{array} \end{bmatrix} $$

이러한 방식으로 각 행(row)에 대해 연산하는 것은 연립 방정식에서 각 방정식에 연산하는 것과 유사하다.

 

• 기본 행 연산 (Elementary Row Operation)

어떤 행렬에 대해 다음의 연산들을 기본 행 연산이라 한다.

• $ k R_i $ : 행렬의 $ i $ 행에 0 이 아닌 상수 $ k $ 를 곱한다.
• $ R_i \leftrightarrow R_j $ : 행렬의 서로 다른 두 행, $ i $ 행과 $ j $ 행을 교환한다.
• $ k R_i + R_j $ : 행렬의 $ i $ 행에 $ k $ 를 곱한 후 그 결과를 $ j $ 행에 더한다.

 

• 행동치 (Row equivalent)

행렬 $ A $ 에 기본 행 연산을 유한히 시행하여 얻은 행렬을 $ B $ 라 하면 $ A $ 와 $ B $ 를 행동치라 한다. 즉 행연산을 통해, 다른 말로는 다른 행렬 행의 선형결합을 통해 어떤 행렬을 나타낼 수 있다면 두 행렬은 행동치이다.

 

---

행 사다리꼴과 기약 행 사다리꼴

 

• 행 사다리꼴 (Row Echelon Form)

어떤 행렬이 다음 조건을 만족하면 행 사다리꼴이라 한다.

• 모든 성분이 0 인 행은 행렬의 최하단에 위치한다.
• 각 행에서 처음으로 나타내는 0 이 아닌 성분은 1 이다. 그것을 선행(leading entry) 1 이라 한다.
• $ i $ 행과 $ i + 1 $ 행에 선행 1 이 있으면 $ i + 1 $ 행의 선행 1 은 $ i $ 행의 선행 1 보다 우측에 위치힌다.

예를 들어 아래와 같은 행렬은 행 사다리꼴이다.

$$ \begin{bmatrix} 1 & 2 & 0 & 3 \\ 0 & 1 & 2 & -6 \\ 0 & 0 & 1 & 7 \\ 0 & 0 & 0 & 0 \end{bmatrix} $$

 

• 기약 행 사다리꼴 (Reduced Row Echelon Form)

어떤 행렬이 다음 조건을 만족하면 기약 행 사다리꼴이라 한다.

• 행렬이 행 사다리꼴이다.
• 선행 1 을 포함한 열의 다른 모든 성분은 0 이다.

예를 들어 아래와 같은 행렬은 기약 행 사다리꼴이다.

$$ \begin{bmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & -3 \\ 0 & 0 & 1 & 5 \\ 0 & 0 & 0 & 0 \end{bmatrix} $$

 

---

가우스 소거법과 가우스-요르단 소거법

 

• 가우스 소거법 (Gauss Elimination)

연립 일차방정식의 확대행렬을 행 사다리꼴로 변형하여 해를 구할 수 있게 하는 방법이다. 확대행렬에 유한히 기본 행 연산을 하여 행 사다리꼴로 만드는 것이다. 행 사다리꼴로 만들었다면 아래서부터 차례대로 해를 구하면 된다.

 

• 가우스-요르단 소거법 (Gauss-Jordan Elimination)

연립 일차방정식의 확대행렬을 기약 행 사다리꼴로 변형하여 해를 구할 수 있게 하는 방법이다. 가우스 소거법에서 한 발 더 나가면 된다.  기약 행 사다리꼴을 만든 시점에서 연립 일차방정식의 해가 구해진다.