가우스 소거법

선형대수학에서, 가우스 소거법(Gauß消去法, 영어: Gaussian elimination, 약자 GE)은 일차연립방정식을 풀기 위한 알고리즘이다. 한 방정식을 첫 변수에 대해 푼 다음, 이 식을 나머지 방정식에 넣어 연립 선형방정식을 푸는 방식이다. 위의 결과는 방정식과 변수의 개수가 원래 연립방정식보다 하나 적은 새로운 연립방정식이 된다. 같은 과정을 2번째 변수에 적용하고, 방정식이 하나만 남을 때까지 다른 변수들에 이 과정을 되풀이한다. 하나 남은 방정식에서는 마지막 변수만 미지변수이다. 이 방정식의 해로 바로 앞에서 얻은 미지수가 2개인 방정식의 해를 구한다. 이 과정은 모든 미지수의 값을 구할 때까지 계속된다.

정의

어떤 체 $K$에 대하여, 다음과 같은 꼴의, $n-1$개의 미지수에 대한 m개의 방정식으로 구성된 일차연립방정식이 주어졌다고 하자.

$M\mathbf x=0$

여기서

$M=\begin{pmatrix} M_{11}&M_{12}&\cdots&M_{1n}\\ M_{21}&M_{22}&\cdots&M_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ M_{m1}&M_{m2}&\cdots&M_{mn} \end{pmatrix}$

은 주어진 $m\times n$ 행렬이고,

$\mathbf x=\begin{pmatrix}x_1\\x_2\\\vdots\\x_{n-1}\\1\end{pmatrix}$

은 $n-1$개의 미지수를 포함하는 열벡터이다. 즉, 이는 풀어서 쓰면 다음과 같다.

$M_{11}x_1+M_{12}x_2+\cdots+M_{1,n-1}x_{n-1}+M_{1n}=0$

$M_{21}x_1+M_{22}x_2+\cdots+M_{2,n-1}x_{n-1}+M_{2n}=0$

$\vdots$

$M_{m1}x_1+M_{m2}x_2+\cdots+M_{m,n-1}x_{n-1}+M_{mn}=0$

보통, 유일한 해를 가진 일차 연립 방정식의 경우 방정식의 수는 미지수의 수와 같으며, 즉 $m=n-1$이다. 그러나 해가 유일하지 못한 경우나, 해가 없는 경우, 방정식이 중복되는 경우 등에서는 $m\ne n-1$일 수 있다.

기본 행 연산

이 경우, 이 연립 방정식에 다음과 같은 세 가지 연산을 가할 수 있다. 이들을 기본 행 연산(基本行演算, 영어: elementary row operation)이라고 한다.

• (행의 치환) $M$의 $i$번째 행과 $j$번째 행을 서로 바꾼다.

$\begin{pmatrix} M_{11}&M_{12}&\cdots&M_{1n}\\ \vdots&\vdots&&\vdots\\ M_{i1}&M_{i2}&\cdots&M_{in}\\ \vdots&\vdots&&\vdots\\ M_{j1}&M_{j2}&\cdots&M_{jn}\\ \vdots&\vdots&&\vdots\\ M_{m1}&M_{m2}&\cdots&M_{mn} \end{pmatrix}\mathbf x=0 \implies\begin{pmatrix} M_{11}&M_{12}&\cdots&M_{1n}\\ \vdots&\vdots&&\vdots\\ M_{j1}&M_{j2}&\cdots&M_{jn}\\ \vdots&\vdots&&\vdots\\ M_{i1}&M_{i2}&\cdots&M_{in}\\ \vdots&\vdots&&\vdots\\ M_{m1}&M_{m2}&\cdots&M_{mn} \end{pmatrix}\mathbf x=0$

• (행의 상수곱) $i$번째 행을 0이 아닌 임의의 상수 $a\in K\setminus\{0\}$으로 곱한다.

$\begin{pmatrix} M_{11}&M_{12}&\cdots&M_{1n}\\ \vdots&\vdots&&\vdots\\ M_{i1}&M_{i2}&\cdots&M_{in}\\ \vdots&\vdots&&\vdots\\ M_{m1}&M_{m2}&\cdots&M_{mn} \end{pmatrix}\mathbf x=0 \implies\begin{pmatrix} M_{11}&M_{12}&\cdots&M_{1n}\\ \vdots&\vdots&&\vdots\\ aM_{i1}&aM_{i2}&\cdots&aM_{in}\\ \vdots&\vdots&&\vdots\\ M_{m1}&M_{m2}&\cdots&M_{mn} \end{pmatrix}\mathbf x=0$

• (행의 합) 임의의 상수 $a\in K$에 대하여, $i$번째 행의 $a$배를 $j$번째 행에 더한다.

$\begin{pmatrix} M_{11}&M_{12}&\cdots&M_{1n}\\ \vdots&\vdots&&\vdots\\ M_{i1}&M_{i2}&\cdots&M_{in}\\ \vdots&\vdots&&\vdots\\ M_{j1}&M_{j2}&\cdots&M_{jn}\\ \vdots&\vdots&&\vdots\\ M_{m1}&M_{m2}&\cdots&M_{mn} \end{pmatrix}\mathbf x=0 \implies\begin{pmatrix} M_{11}&M_{12}&\cdots&M_{1n}\\ \vdots&\vdots&&\vdots\\ M_{i1}&M_{i2}&\cdots&M_{in}\\ \vdots&\vdots&&\vdots\\ aM_{i1}+M_{j1}&aM_{i2}+M_{j2}&\cdots&aM_{in}+M_{jn}\\ \vdots&\vdots&&\vdots\\ M_{m1}&M_{m2}&\cdots&M_{mn} \end{pmatrix}\mathbf x=0$

사다리꼴 행렬

가우스 소거법의 기본적인 목표는 행렬을 기본 행 연산을 적용하여 사다리꼴 행렬(사다리꼴行列, 영어: échelon matrix)로 만드는 것이다. $m\times n$ 행렬 $M$이 다음 조건을 만족시키면, $M$을 사다리꼴 행렬이라고 한다.

• 만약 $M_{ij}=0$이라면, 모든 $i\le i'$에 대하여 $M_{i'j}=0$이다.
• $j_0(i)=\min\{j\colon M_{ij}\ne0\}$이라고 하면, $M_{i,j_0(i)}$를 $i$번째 행의 선행계수(영어: leading coefficient)라고 한다. 만약 $i<i'$라면, $j_0(i)<j_0(i')$이다.

$m\times n$ 행렬 $M$이 다음 조건을 만족시키면, $M$을 기약행 사다리꼴 행렬(旣約行사다리꼴行列, 영어: reduced-row échelon matrix)이라고 한다.

• $M$은 사다리꼴이다.
• $M_{i,j_0(i)}$가 $i$번째 행의 선행계수라고 하자. 그렇다면 $M_{i,j_0(i)}=1$이며, 모든 $j\ne j_0(i)$에 대하여 $M_{ij}=0$이다.

즉, 사다리꼴 행렬은 행렬의 원소들이 대략 위에는 사다리꼴, 밑에는 0인 형태의 행렬이다. 기약행 사다리꼴 조건은 사다리꼴 조건보다 더 강한 조건이다.

예를 들어, 다음과 같은 행렬은 사다리꼴 행렬이다.

$\begin{pmatrix} 1 & a_0 & a_1 & a_2 & a_3 \\ 0 & 0 & 2 & a_4 & a_5 \\ 0 & 0 & 0 & 1 & a_6 \end{pmatrix}$

다음과 같은 행렬은 기약행 사다리꼴 행렬이다.

$\begin{pmatrix} 1 & 0 & a_1 & 0 & a_2 \\ 0 & 1 & a_3 & 0 & a_4 \\ 0 & 0 & 0 & 1 & a_5 \end{pmatrix}$

가우스 소거법 알고리즘

가우스 소거법은 $m\times n$ 행렬 $M$을 기본 행 연산을 가하여 사다리꼴로 만드는 알고리즘이며, 대략 다음과 같다. 각 행에 대하여, 첫 번째 행부터 각각 사다리꼴로 놓을 수 있다. 즉, $i$번째 행을 처리한다고 하자.

1. 우선 선행계수가 $j$번째 열에 위치해 있지만 $M_{ij}=0$이라면, 선행계수가 0이지 않게 하기 위해 그 밑에 있는 다른 열과 치환한다.
2. 그 뒤, $i$번째 행의 밑에 있는 다른 모든 행의 원소들을 $i$번째 행의 배수를 더해 0으로 만든다.
3. 만약 기약행 사다리꼴을 원한다면, 다음과 같은 두 단계를 추가로 거친다.
   1. $i$번째 행 자체를, $M_{ij}=1$로 놓기 위해 상수로 곱한다.
   2. 또한, $i$번째 행 위에 있는 다른 행들 또한 $i$번째 행의 배수를 더해 0으로 만든다.

이는 의사코드로는 다음과 같다. $M$의 각 열벡터들을 $M_1,\dots,M_m$이라고 쓰자.

for $i_0=1,\dots,m$:

$j_0\leftarrow\min\{j|\exists i_0'\ge i_0\colon M_{i_0'j}\ne0\}$ ($j_0$은 $i_0$번째 행의 선행계수의 위치. 만약 이러한 $j_0$이 없다면, 알고리즘을 종료시킨다.)

$i_0'\in\{i_0'<i_0|M_{i_0'j}\ne0\}$ ($i_0'$가 $i_0'>i_0$이며 $M_{i_0'j}\ne0$인 임의의 행이라고 하자)

$(M_{i_0},M_{i_0'})\leftarrow(M_{i_0'},M_{i_0})$ ($i_0$번째 행과 $i_0'$번째 행을 치환)

(*) $M_{i_0}\leftarrow M_{i_0}/M_{i_0j_0}$

for $i=i_0+1,\dots,m$:

$M_i\leftarrow M_i-M_{i_0}(M_{ij_0}/M_{i_0j_0})$ ($i$번째 행에 $i_0$번째 행의 $-M_{ij_0}/M_{j_0j_0}$배를 더한다)

(*) for $i=1,\dots,i_0-1$:

$M_i\leftarrow M_i-M_{i_0}(M_{ij_0}/M_{i_0j_0})$ ($i$번째 행에 $i_0$번째 행의 $-M_{ij_0}/M_{j_0j_0}$배를 더한다)

이 의사코드는 행렬을 기약행 사다리꼴로 만든다. 만약 기약행 사다리꼴 대신 그냥 사다리꼴로 족하다면, 앞에 (*)이 붙은 단계들은 생략할 수 있다.

역행렬의 계산

가우스 소거법을 사용하여 정사각행렬의 역행렬을 계산할 수 있다. $n\times n$ 행렬 $M$의 역행렬을 계산하려면, $<math>M$에 $n\times n$ 단위행렬을 추가하여, $n\times 2n$ 행렬로 만든다.

$\begin{pmatrix}M_{1,1}&\cdots&M_{1,n}&1&\cdots&0\\ \vdots&\ddots&\vdots&\vdots&\ddots\\ M_{n,1}&\cdots&M_{n,n}&0&\cdots&1 \end{pmatrix}$

이 행렬에 기본 행 연산을 가하여

$\begin{pmatrix}1&\cdots&0&\tilde M_{11}&\cdots&\tilde M_{1,n}\\ \vdots&\ddots&\vdots&\ddots&\vdots&\ddots\\ 0&\cdots&1&\tilde M_{n,1}&\cdots&\tilde M_{n,n} \end{pmatrix}$

로 만든다면, 행렬 $\tilde M$은 $M^{-1}$과 같다.

$\tilde M=M^{-1}$

예

해가 유일한 연립 선형 방정식

다음과 같은 선형 방정식이 주어졌다고 하자.

$\begin{matrix} 2u &+& v &+& w &=& 5 \\ 4u &-& 6v && &=& -2 \\ -2u &+& 7v &+& 2w &=& 9 \end{matrix}$

첫 번째 열을 사다리꼴로 놓기 위해, 다음과 같은 기본 행 연산을 가한다.

1. 첫째 식의 -2배를 둘째 식에 더한다
2. 첫째 식의 1배를 셋째 식에 더한다.

그렇다면 다음과 같다.

$\begin{matrix} 2u &+& v &+& w &=& 5 \\ &-& 8v &-& 2w &=& -12 \\ && 8v &+& 3w &=& 14 \end{matrix}$

두 번째 열을 사다리꼴로 놓기 위해, 다음과 같은 기본 행 연산을 가한다.

• 둘째 식의 1배를 셋째 식에 더한다. 그러면 다음과 같다.

$\begin{matrix} 2u &+& v &+& w &=& 5 \\ &-& 8v &-& 2w &=& -12 \\ && && w &=& 2 \end{matrix}$

이제 행렬이 사다리꼴이 되었다. 그렇다면, 이제 미지수들을 가장 밑의 행으로부터 순서대로 대입하여 계산할 수 있다.

$w=2$

$-8v-2w=-12\implies v=1$

$2u+v+w=5\implies u=1$

해가 유일하지 않거나 없는 연립 선형 방정식

정칙(Nonsingular) 행렬일 경우의 예

(식 2와 3을 바꾸어 해결한다)

• $\begin{cases} 10u + 2v + -1w & = \ 27 \\ -3u + -6v + 2w & = \ -61.5 \\ u + v + 5w & = \ -21.5 \end{cases}$

비정칙(Singular) 행렬일 경우의 예

(해가 없는 경우도 있다.)

• $\begin{cases} u + v + w & = \ ? \\ 2u + 2v + 5w & = \ ? \\ 4u + 4v + 8w & = \ ? \\ \end{cases}$

• $\begin{cases} u + v + w & = \ ? \\ 3w & = \ ? \\ 4w & = \ ? \end{cases}$

역행렬의 계산

다음과 같은 행렬 $M$의 역행렬을 계산한다고 하자.

$M = \begin{pmatrix} -1 & 1 & 2 \\ 3 & -1 & 1 \\ -1 & 3 & 4 \end{pmatrix}$

기본 행 연산을 가하면, 다음과 같다.

$\begin{align} \begin{pmatrix} \ A &\vert& I \end{pmatrix} &\to \left( \left. \begin{matrix} -1 & 1 & 2 \\ 3 & -1 & 1 \\ -1 & 3 & 4 \\ \end{matrix} \ \ \right| \ \ \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{matrix} \right)\\ &\to\left(\left. \begin{matrix} -1 & 1 & 2 \\ 0 & 2 & 7 \\ 0 & 2 & 2 \\ \end{matrix} \right| \begin{matrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ -1 & 0 & 1 \\ \end{matrix} \right)\\ &\to\left(\left. \begin{matrix} -1 & 1 & 2 \\ 0 & 2 & 7 \\ 0 & 0 & -5 \\ \end{matrix} \right| \begin{matrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ -4 & -1 & 1 \\ \end{matrix}\right)\\ &\to\left( \left. \begin{matrix} 1 & -1 & -2 \\ 0 & 1 & 3.5 \\ 0 & 0 & 1 \\ \end{matrix} \right| \begin{matrix} -1 & 0 & 0 \\ 1.5 & 0.5 & 0 \\ 0.8 & 0.2 & -0.2 \\ \end{matrix} \right)\\ &\to\left( \left. \begin{matrix} 1 & -1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{matrix} \ \ \right| \ \ \begin{matrix} 0.6 & 0.4 & -0.4 \\ -1.3 & -0.2 & 0.7 \\ 0.8 & 0.2 & -0.2 \\ \end{matrix} \right) \\ & \to \left( \left. \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{matrix} \ \ \right| \ \ \begin{matrix} -0.7 & 0.2 & 0.3 \\ -1.3 & -0.2 & 0.7 \\ 0.8 & 0.2 & -0.2 \\ \end{matrix} \right) \end{align}$

따라서 $M^{-1}$은 다음과 같다.

$M^{-1}=\begin{pmatrix} -0.7 & 0.2 & 0.3 \\ -1.3 & -0.2 & 0.7 \\ 0.8 & 0.2 & -0.2 \end{pmatrix}$

바깥 고리

• “Gauss method” (영어). 《Encyclopedia of Mathematics》. Springer. 2001. ISBN 978-1-55608-010-4. 
• Eric Wolfgang Weisstein. “Gaussian elimination” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• Eric Wolfgang Weisstein. “Gauss-JordanElimination” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• Eric Wolfgang Weisstein. “Echelon form” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• Eric Wolfgang Weisstein. “Elementary row and column operations” (영어). 《Wolfram MathWorld》. Wolfram Research.