가우스 소거법

선형대수학에서 **가우스 소거법**(Gauß消去法, Gaussian elimination)이란, 연립일차방정식을 풀이하는 알고리즘이다. 풀이 과정에서, 일부 미지수가 차츰 소거되어 결국 남은 미지수에 대한 선형 결합으로 표현되면서 풀이가 완성된다. 가우스 소거법은 보통 행렬을 사용하며, 첨가 행렬을 그와 풀이가 같은 더 간단한 행렬로 변환하여 풀이를 완성한다. 가우스 소거법은 행렬식과 역행렬의 계산에도 응용된다.
# 정의
체 K에 대하여, n개의 미지수에 대한 m개의 방정식으로 구성된 연립일차방정식 :Mx=0 이 주어졌다고 하자. 여기서 :M=\begin{pmatrix} M_{11}&M;_{12}&\cdots&M;_{1,n+1}\\\M_{21}&M;_{22}&\cdots&M;_{2,n+1}\\\ \vdots&\vdots&\ddots&\vdots\\\M_{m1}&M;_{m2}&\cdots&M;_{m,n+1}\end{pmatrix} 은 주어진 m\times(n+1) 행렬이고, :x=\begin{pmatrix}x_1\\\x_2\\\\\vdots\\\x_n\\\1\end{pmatrix} 은 n개의 미지수를 포함하는 열벡터이다. 즉, 이는 풀어서 쓰면 다음과 같다. :M_{11}x_1+M_{12}x_2+\cdots+M_{1,n}x_n+M_{1,n+1}=0 :M_{21}x_1+M_{22}x_2+\cdots+M_{2,n}x_n+M_{2,n+1}=0 ::::::::\vdots :M_{m1}x_1+M_{m2}x_2+\cdots+M_{m,n}x_n+M_{m,n+1}=0
## 기본 행 연산
기본 행렬 이 경우, 이 연립방정식에 다음과 같은 세 가지 연산을 가할 수 있다. 이들을 **기본 행 연산**(基本行演算, elementary row operation)이라고 한다. * (행의 치환) M의 i번째 행과 j번째 행을 서로 바꾼다. ::\begin{pmatrix} M_{11}&M;_{12}&\cdots&M;_{1,n+1}\\\\\vdots&\vdots&&\vdots\\\ M_{i1}&M;_{i2}&\cdots&M;_{i,n+1}\\\\\vdots&\vdots&&\vdots\\\ M_{j1}&M;_{j2}&\cdots&M;_{j,n+1}\\\\\vdots&\vdots&&\vdots\\\ M_{m1}&M;_{m2}&\cdots&M;_{m,n+1}\end{pmatrix}x=0 \implies\begin{pmatrix} M_{11}&M;_{12}&\cdots&M;_{1,n+1}\\\\\vdots&\vdots&&\vdots\\\ M_{j1}&M;_{j2}&\cdots&M;_{j,n+1}\\\\\vdots&\vdots&&\vdots\\\ M_{i1}&M;_{i2}&\cdots&M;_{i,n+1}\\\\\vdots&\vdots&&\vdots\\\ M_{m1}&M;_{m2}&\cdots&M;_{m,n+1}\end{pmatrix}x=0 * (행의 상수곱) i번째 행을 0이 아닌 임의의 상수 a\in K\setminus\\{0\\}으로 곱한다. ::\begin{pmatrix} M_{11}&M;_{12}&\cdots&M;_{1,n+1}\\\\\vdots&\vdots&&\vdots\\\ M_{i1}&M;_{i2}&\cdots&M;_{i,n+1}\\\\\vdots&\vdots&&\vdots\\\ M_{m1}&M;_{m2}&\cdots&M;_{m,n+1}\end{pmatrix}x=0 \implies\begin{pmatrix} M_{11}&M;_{12}&\cdots&M;_{1,n+1}\\\\\vdots&\vdots&&\vdots\\\ aM_{i1}&aM;_{i2}&\cdots&aM;_{i,n+1}\\\\\vdots&\vdots&&\vdots\\\ M_{m1}&M;_{m2}&\cdots&M;_{m,n+1}\end{pmatrix}x=0 * (행의 합) 임의의 상수 a\in K에 대하여, i번째 행의 a배를 j번째 행에 더한다. ::\begin{pmatrix} M_{11}&M;_{12}&\cdots&M;_{1,n+1}\\\\\vdots&\vdots&&\vdots\\\ M_{i1}&M;_{i2}&\cdots&M;_{i,n+1}\\\\\vdots&\vdots&&\vdots\\\ M_{j1}&M;_{j2}&\cdots&M;_{j,n+1}\\\\\vdots&\vdots&&\vdots\\\ M_{m1}&M;_{m2}&\cdots&M;_{m,n+1}\end{pmatrix}x=0 \implies\begin{pmatrix} M_{11}&M;_{12}&\cdots&M;_{1,n+1}\\\\\vdots&\vdots&&\vdots\\\ M_{i1}&M;_{i2}&\cdots&M;_{i,n+1}\\\\\vdots&\vdots&&\vdots\\\ aM_{i1}+M_{j1}&aM;_{i2}+M_{j2}&\cdots&aM;_{i,n+1}+M_{j,n+1}\\\\\vdots&\vdots&&\vdots\\\ M_{m1}&M;_{m2}&\cdots&M;_{m,n+1}\end{pmatrix}x=0
## 행사다리꼴행렬
행사다리꼴행렬 m\times(n+1) 행렬 M에 대하여, j_0(i)=\min\\{j\le n\colon M_{ij}\ne0\\}이라고 하면, M_{i,j_0(i)}를 i번째 행의 **선행 계수**(先行係數, leading coefficient)라고 한다. 선행 계수는 존재하지 않을 수 있다. m\times(n+1) 행렬 M이 다음 조건을 만족시키면, M을 **행사다리꼴행렬**(사다리꼴行列, échelon matrix)이라고 한다. * 만약 0=M_{i1}=\cdots=M_{in}이라면, 모든 i\le i'에 대하여 0=M_{i'1}=\cdots=M_{i'n}이다. * 만약 i이며 j_0(i)와 j_0(i')가 존재한다면, j_0(i)이다. m\times(n+1) 행렬 M이 다음 조건을 만족시키면, M을 **기약행사다리꼴행렬**(旣約行사다리꼴行列, reduced-row échelon matrix)이라고 한다. * M은 행사다리꼴행렬이다. * j_0(i)가 존재한다면, M_{i,j_0(i)}=1이며, 모든 i'\ne i에 대하여 M_{i',j_0(i)}=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을 기본행연산을 가하여 행사다리꼴행렬로 만드는 알고리즘이며, 다음과 같다. 먼저 첫번째 행을 다음과 같이 처리한다. # 선행 계수가 위치하는 가장 작은 열수 j_1\le n을 찾는다. # M_{1j_1}=0이라면, 첫번째 행을 M_{i_1j_1}\ne0인 어떤 i_1>1번째 행과 치환한다. # 모든 i>1번째 행에 첫번째 행의 -M_{ij_1}/M_{1j_1}배를 더해, M_{1j_1} 밑의 항들을 0으로 만든다. 그 뒤, 두번째 행을 다음과 같이 처리한다. # 어떤 i\ge2번째 행의 선행 계수가 위치하는 가장 작은 열수 j_2\le n을 찾는다. # M_{2j_2}=0이라면, 두번째 행을 M_{i_2j_2}\ne0인 어떤 i_2>2번째 행과 치환한다. # 모든 i>2번째 행에 두번째 행의 -M_{ij_2}/M_{2j_2}배를 더해, M_{2j_2} 밑의 항들을 0으로 만든다. 뒤에 오는 다른 행에 대하여, 순차적으로 위와 같이 처리한다. 일반적으로, k번째 행은 다음과 같이 처리한다. # 어떤 i\ge k번째 행의 선행 계수가 위치하는 가장 작은 열수 j_k\le n을 찾는다. # M_{kj_k}=0이라면, k번째 행을 M_{i_kj_k}\ne0인 어떤 i_k>k번째 행과 치환한다. # 모든 i>k번째 행에 k번째 행의 -M_{ij_k}/M_{kj_k}배를 더해, M_{kj_k} 밑의 항들을 0으로 만든다.2013 만약 어떤 j_{r+1}\le n가 존재하지 않는다면, r번째 행에서 멈춘다. 만약 항상 j_k\le n를 찾을 수 있다면, 모든 k=1,2,\ldots,m번째 행에 대하여 순차적으로 위와 같이 처리하며, r=n으로 둔다. 기약행사다리꼴행렬을 원한다면, 찾았던 모든 j_k=j_r,j_{r-2},\ldots,j_1에 대하여 순차적으로 다음과 같은 단계를 추가로 거친다. # k번째 행에 1/M_{kj_k}를 곱해, M_{kj_k}를 1로 만든다. # 모든 i번째 행에 k번째 행의 -M_{ij_k}배를 더해, M_{kj_k} 위의 항들을 0으로 만든다. 여기서 r\le m이며 r\le n인 데 주의하자. 사실, 이는 행렬의 계수이다. *기약행사다리꼴행렬의 과정을 특히 조단이 제시한 "가우스 조단 소거법"으로 부른다.
# 성질

## 기본행연산
세 가지 기본행연산은 모두 가역 연산이다. * 행의 치환의 역연산은, 자기 자신이다. * 행의 상수곱의 역연산은, 그 행에 그 상수 대신 역수를 곱하는 것이다. * 어떤 행에 다른 행의 배수를 더하는 것의 역연산은, 더하는 대신 빼는 것이다. 두 연립일차방정식의 첨가 행렬이 하나에 기본행연산을 가하여 다른 하나를 얻을 수 있다면, 행동치라고 한다. 첨가 행렬이 행동치라면, 연립방정식의 풀이는 서로 같다. 기본 행렬은 단위 행렬에 기본행연산을 한 번 가하여 얻는 행렬이다. 이에 따라, 세 가지 기본행연산은 기본 행렬 곱셈과 같다.
## 행사다리꼴행렬
가우스 소거법 알고리즘에서 알 수 있듯, 모든 연립일차방정식의 첨가 행렬은 그와 같은 해를 갖는 행사다리꼴행렬 및 기약행사다리꼴행렬로 변환할 수 있다. 따라서, 연립일차방정식의 풀이는 행사다리꼴행렬 및 기약행사다리꼴에 대한 풀이로 귀결된다. m\times(n+1) 행사다리꼴행렬 R에 대한 연립일차방정식 Rx=0에 대하여, 다음 두 조건이 서로 동치이다. * 해가 존재한다. * 상수항이 0이 아닌 행이 존재하지 않는다. (상수항은 n+1번째 열의 항, 0행은 선행 계수가 없는 행을 뜻한다.) 해가 존재하는 Rx=0의 경우, 다음 두 조건이 서로 동치이다. * 해가 유일하다. * r=n. 즉, 0행이 아닌 행의 개수는 미지수의 개수와 같다. 즉, 선행 계수가 없는 열이 계수 행렬에 존재하지 않는다. 달리 말해, 해가 존재하는 Rx=0의 경우, 다음 두 조건이 서로 동치이다. * 해가 유일하지 않다. (체의 표수가 0이라면, 이는 해가 무한히 많은 것과 동치이다.) * r. 즉, 0행이 아닌 행의 개수는 미지수의 개수보다 적다. 즉, 선행 계수가 없는 열이 계수 행렬에 존재한다.
## 행렬식의 계산
가우스 소거법을 사용하여 정사각행렬의 행렬식을 계산할 수 있다. 이는 정사각행렬에 대하여 다음 사실들이 성립하기 때문이다. * 기본행연산을 가하면, 행렬식은 "상수배" 변화하며, 주어진 기본행연산이 행렬식을 변화시키는 배수는 자명하다. 즉, ** 행을 치환하면, 행렬식은 -1배가 된다. ** 행에 상수곱을 하면, 행렬식은 그 상수의 역수배가 된다. ** 어떤 행에 다른 어떤 행의 상수배를 더하면, 행렬식은 변하지 않는다. * 가우스 소거법을 통해 행렬을 행사다리꼴행렬로 변환할 수 있다. 특히 정사각행렬이므로, 이는 0행(즉 모든 항이 0인 행)을 갖거나, 상삼각행렬이다. * 0행을 갖는 정사각행렬의 행렬식은 0이다. * 상삼각행렬의 행렬식은 모든 대각항의 곱이다.
## 역행렬의 계산
가우스 소거법을 사용하여 정사각행렬의 역행렬을 계산할 수 있다. n\times n 행렬 M의 역행렬은 다음과 같이 계산한다. M에 n\times n 단위행렬을 추가하여 n\times 2n 행렬로 만든다. :\begin{pmatrix}M_{1,1}&\cdots&M;_{1,n}&1&\cdots&0\\\ \vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\\ 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}
## 계수 계산
가우스 소거법을 사용하여 행렬의 계수를 계산할 수 있다. m\times n 행렬 M의 계수는 가우스 소거법을 가하여 얻는 행사다리꼴행렬에서 0이 아닌 행의 계수(즉, 선행 계수의 개수) r이다.
# 예
:\left[\begin{array}{rrr|r} 1 & 3 & 1 & 9 \\\ 1 & 1 & -1 & 1 \\\ 3 & 11 & 5 & 35 \end{array}\right]\to \left[\begin{array}{rrr|r} 1 & 3 & 1 & 9 \\\ 0 & -2 & -2 & -8 \\\ 0 & 2 & 2 & 8 \end{array}\right]\to \left[\begin{array}{rrr|r} 1 & 3 & 1 & 9 \\\ 0 & -2 & -2 & -8 \\\ 0 & 0 & 0 & 0 \end{array}\right]\to \left[\begin{array}{rrr|r} 1 & 0 & -2 & -3 \\\ 0 & 1 & 1 & 4 \\\ 0 & 0 & 0 & 0 \end{array}\right]
## 해가 유일한 연립 선형 방정식
다음과 같은 선형 방정식이 주어졌다고 하자. :\begin{matrix} 2u &+& v &+& w &=& 5 \\\ 4u &-& 6v && &=& -2 \\\ -2u &+& 7v &+& 2w &=& 9 \end{matrix} 첫 번째 열을 사다리꼴로 놓기 위해, 다음과 같은 기본행연산을 가한다. # 첫째 식의 -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} 이제 행렬이 사다리꼴이 되었다. 그렇다면, 이제 미지수들을 가장 밑의 행으로부터 순서대로 대입하여 계산할 수 있다. 이것을 **후방대입**(back substitution)이라 한다.2013 :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}