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

기약 행 사다리꼴 행렬과 가우스 소거법

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

$$\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)$$

만약 계수 행렬을 다음과 같은 형태로 만들면,

$$\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)$$

간단하게 x, y, z 를 구할 수 있게 된다.

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

행렬 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)$$

가우스 소거법 (Gaussian Elimination)

임의 행렬을 기약 행 사다리꼴 행렬 (Row-Reduced Echelon Form RREF)로 바꾸는 과정

임의 행렬 A를 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$)

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

임의의 행렬 A를 기본 행 연상을 통해 유일한 RREF 형태로 바꿀 수 있다. 가장 첫 번째 행부터 관찰하여 다음과 같은 과정을 시행한다.

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

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

일반적으로 가우스-조던 소거법을 가우스 소거법이라 한다.

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

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

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

방정식을 행렬 곱으로 나타내면,

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

이 때, AX=B의 첨가행렬은

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

첨가행렬 (A, B)를 RREF 형태로 고쳐보면,

$$\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: (행렬) 초등행렬

---

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