(행렬) 가우스-조던 소거법

기약 행 사다리꼴 행렬 (Row-Reduced Echelon Form : RREF)

• 행렬로 표현된 아래의 연립방정식에 대해서,

$$\left(\begin{array}{ccc}2& 1& 1\\ 4& -6& 0\\ 1& 0& 2\end{array}\right)\left(\begin{array}{c}x\\ y\\ z\end{array}\right)=\left(\begin{array}{c}1\\ 2\\ -1\end{array}\right)$$

• 계수 행렬을 다음과 같은 형태로 만들면, 간단하게 x, y, z 를 구할 수 있게 되며, 이러한 행렬의 형태를 기약 행 사다리꼴 행렬이라 한다.

$$\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right)\left(\begin{array}{c}x\\ y\\ z\end{array}\right)=\left(\begin{array}{c}?\\ ?\\ ?\end{array}\right)$$

• 행렬 A가 다음 조건을 만족할 때, A를 RREF 행렬 이라고 부른다.
  1. 어떤 행의 모든 성분이 0일 경우, 그 행은 가장 아래에 위치 한다.
  2. 어떤 행의 성분 중 0이 아닌 것이 있을 경우, 그 성분등 중 가장 왼쪽의 성분은 1이다.
  3. (2)에서 논하는 가장 왼쪽의 1을 포함한 열에 대해, 이 1을 제외한 모든 성분은 0이다.
  4. (2)에서 논하는 가장 왼쪽의 1은 계단형태로 위치한다.
• 즉, i번째 행과 j번째 행이 가장 왼쪽의 1을 갖고 있다면, i<j 일 때 i번째 행의 1이 j번째 행의 1보다 왼쪽에 위치한다.

$$\left(\begin{array}{ccccccccc}1& 0& ?& 0& ?& ?& 0& \cdots & ?\\ 0& 1& ?& 0& ?& ?& 0& \cdots & ?\\ 0& 0& 0& 1& ?& ?& 0& \cdots & ?\\ 0& 0& 0& 0& 0& 0& 1& \cdots & ?\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& 0& 0& 0& 0& \cdots & 0\end{array}\right)$$

---

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

• 가우스 소거법 (Gaussian Elimination) 은 행렬을 행 사다리꼴(Row Echelon Form, REF)**로 만드는 것이다.
• 가우스-조던 소거법 은 행렬을 기약 행 사다리꼴 행렬 (RREF) 로 바꾸는 과정
• 기본 행 연산을 통해 행렬 A를 RREF로 바꾸면 다음과 같다.

$$\left(\begin{array}{ccccc}0& -3& -6& 4& 9\\ -1& -2& -1& 3& 1\\ -2& -3& 0& 3& -1\\ 1& 4& 5& -9& -7\end{array}\right)$$ $$\left(\begin{array}{ccccc}1& 0& 3& 0& 5\\ 0& 1& 2& 0& -3\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0\end{array}\right)$$

• 이 때, ${\sim }_r$ 이란 두 행렬이 기본 행 연산을 통해 행 동등(Row Equivalent) 하다는 뜻 ($A{\sim }_{r}B$)

• 임의의 행렬 A를 아래 과정을 통해 유일한 RREF 형태로 바꿀 수 있다.

• 가장 첫 번째 행부터 관찰하여 다음과 같은 과정을 시행한다.

  1. 선도 성분이 0이 되지 않도록 행 들의 위치를 서로 맞바꾼다.
  2. 선도 성분이 1이 될 수 있도록 해당하는 행에 상수배를 한다.
  3. 선도 1을 포함하는 열의 나머지 성분이 0이 될 수 있도록 해당 행의 상수배를 다른 행에 더한다.
  4. 다음 행으로 넘어간다.

• 이 때, 3번 과정을 제외한 시행을 가우스 소거법이라 하고, 3번 과정을 포함한 모든 과정을 가우스-조던 소거법이라고 한다.

특징	가우스 소거법 (Gaussian Elimination)	가우스-조던 소거법 (Gauss-Jordan Elimination)
최종 형태	행 사다리꼴 (REF)	기약 행 사다리꼴 (RREF)
선도 1 주변	선도 1 아래만 0	선도 1 위아래 모두 0
해 도출 방식	후방 대입법(Back-substitution) 필요	해를 직접 읽을 수 있음 (추가 계산 불필요)
계산량	일반적으로 적음 (해만 구할 경우)	일반적으로 많음 (역행렬 계산에 유용)
주요 용도	연립방정식 해, 행렬 랭크	연립방정식 해, 역행렬 계산, 행렬 랭크

가우스-조던 소거법을 이용한 연립방정식 풀이

• 아래의 연립방정식을 가우스-조던 소거법을 이용해 풀어 보자.

$$\{\begin{array}{l}3x-7y+7z=-8\\ x-3y+4z=-4\\ -4x+6y-z=7\end{array}$$

• 방정식을 행렬 곱으로 나타내면 다음과 같다.

$$A=\left(\begin{array}{ccc}3& -7& 7\\ 1& -3& 4\\ -4& 6& -1\end{array}\right),X=\left(\begin{array}{c}x\\ y\\ z\end{array}\right),B=\left(\begin{array}{c}-8\\ -4\\ 7\end{array}\right)$$ $$\Rightarrow AX=B$$

• 이 때, AX=B의 첨가행렬은 다음과 같다.

$$(A,B)=\left(\begin{array}{cccc}3& -7& 7& -8\\ 1& -3& 4& -4\\ -4& 6& -1& 7\end{array}\right)$$

• 다음 과정을 통해 첨가행렬 (A, B)를 RREF 형태로 만들 수 있다.

1. 선도 성분이 0이 되지 않도록 행 들의 위치를 서로 맞바꾼다.
   • 현재 첫 번째 행의 선도 성분은 3이며, 계산을 용이하게 하기 위해 선도 성분을 1로 만드는 것이 좋다. 두 번째 행의 선도 성분이 1이므로, 두 번째 행과 첫 번째 행을 맞바꾼다.
   $$\left(\begin{array}{cccc}1& -3& 4& -4\\ 3& -7& 7& -8\\ -4& 6& -1& 7\end{array}\right)$$
2. 선도 성분이 1이 될 수 있도록 해당하는 행에 상수배를 한다.
   • 첫 번째 행의 선도 성분이 이미 1이므로, 그대로 둔다.
3. 선도 1을 포함하는 열의 나머지 성분이 0이 될 수 있도록 해당 행의 상수배를 다른 행에 더한다.
   • 첫 번째 열의 선도 1 아래의 성분들을 0으로 만든다.
   $$\left(\begin{array}{cccc}1& -3& 4& -4\\ 3& -7& 7& -8\\ -4& 6& -1& 7\end{array}\right)+\left(\begin{array}{cccc}\ast & \ast & \ast & \ast \\ -3\cdot 1& -3\cdot -3& -3\cdot 4& -3\cdot -4\\ 4\cdot 1& 4\cdot -3& 4\cdot 4& 4\cdot -4\end{array}\right)$$ $$\left(\begin{array}{cccc}1& -3& 4& -4\\ 0& 2& -5& 4\\ 0& -6& 15& -9\end{array}\right)$$
4. 다음 행에서 2번부터 과정을 반복한다.
   • 두 번째 행의 선도 성분을 1로 만든다.
   $$\left(\begin{array}{cccc}1& -3& 4& -4\\ 0& 2/2& -5/2& 4/2\\ 0& -6& 15& -9\end{array}\right)=\left(\begin{array}{cccc}1& -3& 4& -4\\ 0& 1& -\frac{2}{5}& 2\\ 0& -6& 15& -9\end{array}\right)$$
   • 두 번째 열의 선도 1 위아래 성분들을 0으로 만든다.
   $$⟹\left(\begin{array}{cccc}1& 0& -\frac{7}{2}& 2\\ 0& 1& -\frac{5}{2}& 2\\ 0& 0& 0& 3\end{array}\right)$$
   • 세 번째 행에서도 선도 성분을 1로 만들고, 위아래 성분들을 0으로 만들면 최종 아래의 행렬이 나온다.

$$\left(\begin{array}{cccc}1& -3& 4& -4\\ 3& -7& 7& -8\\ -4& 6& -1& 7\end{array}\right){\sim }_r\left(\begin{array}{cccc}1& 0& -\frac{7}{2}& 0\\ 0& 1& -\frac{5}{2}& 0\\ 0& 0& 0& 1\end{array}\right)=(A^{\prime },B^{\prime })$$

• 이것을 다시 연립방정식 꼴로 고쳐보면 다음과 같다.

$$A^{\prime }X=B^{\prime }$$ $$\Rightarrow \{\begin{array}{l}1\cdot x+0\cdot y-\frac{7}{2}\cdot z=0\\ 0\cdot x+1\cdot y-\frac{5}{2}\cdot z=0\\ 0\cdot x+0\cdot y+0\cdot z=1\end{array}$$

• 이 때, 3번째 식이 $0=1$ 이라는 모순이 나왔다 $\Rightarrow$ 이 연립방정식은 해가 없다

• 만약 어떤 첨가행렬의 RREF가 다음과 같다면

$$\left(\begin{array}{cccc}1& 0& 0& 3\\ 0& 1& 0& 2\\ 0& 0& 1& 1\end{array}\right)=(A^{\prime },B^{\prime })$$

• 연립방정식의 해는 다음과 같다.

$$x=3,y=2,z=1$$

• 만약 어떤 첨가행렬의 RREF가 다음과 같다면

$$(A^{\prime },B^{\prime })=\left(\begin{array}{ccccc}1& 1& 0& 0& 1\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 2\end{array}\right)$$
$$A^{\prime }X=B^{\prime }$$ $$\Rightarrow \{\begin{array}{l}{x}_1+x_2=1\\ x_3=0\\ x_4=2\end{array}$$

• 식은 3개, 미지수는 4개인 연립방정식인데, 첫 번째 식의 경우 유일한 해를 구할 수 없다.

---

역행렬 구하기

2차 정방행렬의 역행렬을 구하는 방법

가역행렬(Invertible Matrix)

n차 정방행렬 $A$에 대해,

$AB=I_n=BA$ 를 만족하는 n차 정방행렬 $B$가 존재할 때,

A를 가역행렬이라 한다. 이 때, B를 A의 역행렬이라고 부르고 다음과 같이 표기한다.

$B=A^{-1},A=B^{-1}$

• 행렬의 곱셈은 일반적으로 교환법칙이 성립하지 않기 때문에, 가역행렬인지 확인하기 위해 AB, BA 모두 확인 해봐야 하지만, ==무조건 AB=I 이면, BA=I 이다.==

• ==A가 가역행렬 일 때, A의 역행렬은 하나로 유일하다.==

• A가 가역행렬 일 때, A의 역행렬 또한 자명하게 가역행렬이다.

2차 정방행렬 $A$에 대해, 다음 조건을 만족하면 $A$는 가역이다.

$$A=\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)\iff ad-bc\ne 0$$

이 때, A의 역행렬은

$${\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)}^{-1}=\frac{1}{ad-bc}\left(\begin{array}{cc}d& -b\\ -c& a\end{array}\right)$$

2차 정방 행렬에 대해서는 위와 같은 식이 나오며, (행렬) 가우스-조던 소거법 을 이용해 역행렬을 구할 수 있다.

원본 링크

3차 이상의 역행렬 구하는 방법

• A의 역행렬이 존재한다면 (A가 가역행렬 이라면) 다음을 만족한다.

$AX=I$ $A^{-1}(AX)=A^{-1}I$ $(A^{-1}A)X=A^{-1}$ $IX=A^{-1}$

$\therefore X=A^{-1}$

• 다음 행렬 A의 역행렬을 구해보자

$$\left(\begin{array}{ccc}1& -1& 2\\ 2& 0& 4\\ -1& 2& 0\end{array}\right)$$

• 이 때, $I$는 항등 행렬이므로 첨가행렬 $(A,I)$ 은

$$\left(\begin{array}{cccccc}1& -1& 2& 1& 0& 0\\ 2& 0& 4& 0& 1& 0\\ -1& 2& 0& 0& 0& 1\end{array}\right)$$

• 가우스-조던 소거법을 이용해 RREF 형태로 고쳐보면,

$$\left(\begin{array}{cccccc}1& 0& 0& -2& 1& -1\\ 0& 1& 0& -1& \frac{1}{2}& 0\\ 0& 0& 1& 1& -\frac{1}{4}& \frac{1}{2}\end{array}\right)$$

• 위 행렬은 $(I,B)$ 라 표현 할 수 있고, 다시 방정식으로 표현해보면, $(IX=B)\Rightarrow (X=B)$가 된다.
• 따라서, $A$ 의 역행렬 $X$ 는 다음과 같다.

$$\therefore X=\left(\begin{array}{ccc}-2& 1& -1\\ -1& \frac{1}{2}& 0\\ 1& -\frac{1}{4}& \frac{1}{2}\end{array}\right)=A^{-1}$$

역행렬 과정 정리

• n차 정방행렬 A의 역행렬이 존재할 때, A의 역행렬은 다음과 같이 구할 수 있다.

  1. 항등행렬 $I$를 오른쪽에 붙인 $(n\times 2n)$ 크기의 첨가행렬 $(A,I_n)$을 만든다.
  2. 1에서 만든 첨가행렬을 가우스 소거법을 통해 RREF 꼴로 고친다
  3. 2과정을 거친 RREF 행렬은 $(I_n,A^{-1})$가 된다.

• 즉, RREF 행렬의 오른쪽 $(n\times n)$ 행렬이 A의 역행렬이 된다.

---

참고

• [선형대수학] I. 행렬 - 2. 가우스 소거법(가우스-요르단) feat.역행렬 구하는 방법 (Gauss-Jordan Elimination) : 네이버 블로그

---

Prev: (행렬) 연립방정식과 행렬

Next: (행렬) 초등행렬

---

가우스소거법선형대수수학행렬