가우스 소거법

선형대수학에서 가우스 소거법(Gauß消去法, 영어: Gaussian elimination)이란, 연립일차방정식을 풀이하는 알고리즘이다. 풀이 과정에서, 일부 미지수가 차츰 소거되어 결국 남은 미지수에 대한 선형 결합으로 표현되면서 풀이가 완성된다. 가우스 소거법은 보통 행렬을 사용하며, 첨가 행렬을 그와 풀이가 같은 더 간단한 행렬로 변환하여 풀이를 완성한다. 가우스 소거법은 행렬식과 역행렬의 계산에도 응용된다.

체 ${\displaystyle K}$에 대하여, ${\displaystyle n}$개의 미지수에 대한 ${\displaystyle m}$개의 방정식으로 구성된 연립일차방정식

${\displaystyle Mx=0}$

이 주어졌다고 하자. 여기서

${\displaystyle 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}}}$

은 주어진 ${\displaystyle m\times (n+1)}$ 행렬이고,

${\displaystyle x={\begin{pmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\\1\end{pmatrix}}}$

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

${\displaystyle M_{11}x_{1}+M_{12}x_{2}+\cdots +M_{1,n}x_{n}+M_{1,n+1}=0}$

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

${\displaystyle \vdots }$

${\displaystyle M_{m1}x_{1}+M_{m2}x_{2}+\cdots +M_{m,n}x_{n}+M_{m,n+1}=0}$

 이 부분의 본문은 기본 행렬입니다.

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

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

${\displaystyle {\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}$

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

${\displaystyle {\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}$

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

${\displaystyle {\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}$

일반적으로 사다리꼴행렬(Echelon matrix,에쉴론 메트릭스, 또는 행사다리꼴행렬)은,

${\displaystyle m\times (n+1)}$ 행렬 ${\displaystyle M}$에 대하여, ${\displaystyle j_{0}(i)=\min\{j\leq n\colon M_{ij}\neq 0\}}$이라고 하면, ${\displaystyle M_{i,j_{0}(i)}}$를 ${\displaystyle i}$번째 행의 선행 계수(先行係數, 영어: leading coefficient)라고 한다. 선행 계수는 존재하지 않을 수 있다.

${\displaystyle m\times (n+1)}$ 행렬 ${\displaystyle M}$이 다음 조건을 만족시키면, ${\displaystyle M}$을 행사다리꼴행렬(사다리꼴行列, 영어: échelon matrix)이라고 한다.

• 만약 ${\displaystyle 0=M_{i1}=\cdots =M_{in}}$이라면, 모든 ${\displaystyle i\leq i'}$에 대하여 ${\displaystyle 0=M_{i'1}=\cdots =M_{i'n}}$이다.
• 만약 ${\displaystyle i<i'}$이며 ${\displaystyle j_{0}(i)}$와 ${\displaystyle j_{0}(i')}$가 존재한다면, ${\displaystyle j_{0}(i)<j_{0}(i')}$이다.

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

• ${\displaystyle M}$은 행사다리꼴행렬이다.
• ${\displaystyle j_{0}(i)}$가 존재한다면, ${\displaystyle M_{i,j_{0}(i)}=1}$이며, 모든 ${\displaystyle i'\neq i}$에 대하여 ${\displaystyle M_{i',j_{0}(i)}=0}$이다.

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

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

${\displaystyle {\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}}}$

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

${\displaystyle {\begin{pmatrix}1&0&a_{1}&0&a_{2}\\0&1&a_{3}&0&a_{4}\\0&0&0&1&a_{5}\end{pmatrix}}}$

가우스 소거법은 ${\displaystyle m\times n}$ 행렬 ${\displaystyle M}$을 기본행연산을 가하여 행사다리꼴행렬로 만드는 알고리즘이며, 다음과 같다. 먼저 첫번째 행을 다음과 같이 처리한다.

1. 선행 계수가 위치하는 가장 작은 열수 ${\displaystyle j_{1}\leq n}$을 찾는다.
2. ${\displaystyle M_{1j_{1}}=0}$이라면, 첫번째 행을 ${\displaystyle M_{i_{1}j_{1}}\neq 0}$인 어떤 ${\displaystyle i_{1}>1}$번째 행과 치환한다.
3. 모든 ${\displaystyle i>1}$번째 행에 첫번째 행의 ${\displaystyle -M_{ij_{1}}/M_{1j_{1}}}$배를 더해, ${\displaystyle M_{1j_{1}}}$ 밑의 항들을 0으로 만든다.

그 뒤, 두번째 행을 다음과 같이 처리한다.

1. 어떤 ${\displaystyle i\geq 2}$번째 행의 선행 계수가 위치하는 가장 작은 열수 ${\displaystyle j_{2}\leq n}$을 찾는다.
2. ${\displaystyle M_{2j_{2}}=0}$이라면, 두번째 행을 ${\displaystyle M_{i_{2}j_{2}}\neq 0}$인 어떤 ${\displaystyle i_{2}>2}$번째 행과 치환한다.
3. 모든 ${\displaystyle i>2}$번째 행에 두번째 행의 ${\displaystyle -M_{ij_{2}}/M_{2j_{2}}}$배를 더해, ${\displaystyle M_{2j_{2}}}$ 밑의 항들을 0으로 만든다.

뒤에 오는 다른 행에 대하여, 순차적으로 위와 같이 처리한다. 일반적으로, ${\displaystyle k}$번째 행은 다음과 같이 처리한다.

1. 어떤 ${\displaystyle i\geq k}$번째 행의 선행 계수가 위치하는 가장 작은 열수 ${\displaystyle j_{k}\leq n}$을 찾는다.
2. ${\displaystyle M_{kj_{k}}=0}$이라면, ${\displaystyle k}$번째 행을 ${\displaystyle M_{i_{k}j_{k}}\neq 0}$인 어떤 ${\displaystyle i_{k}>k}$번째 행과 치환한다.
3. 모든 ${\displaystyle i>k}$번째 행에 ${\displaystyle k}$번째 행의 ${\displaystyle -M_{ij_{k}}/M_{kj_{k}}}$배를 더해, ${\displaystyle M_{kj_{k}}}$ 밑의 항들을 0으로 만든다.^[1]

만약 어떤 ${\displaystyle j_{r+1}\leq n}$가 존재하지 않는다면, ${\displaystyle r}$번째 행에서 멈춘다. 만약 항상 ${\displaystyle j_{k}\leq n}$를 찾을 수 있다면, 모든 ${\displaystyle k=1,2,\ldots ,m}$번째 행에 대하여 순차적으로 위와 같이 처리하며, ${\displaystyle r=n}$으로 둔다. 기약행사다리꼴행렬을 원한다면, 찾았던 모든 ${\displaystyle j_{k}=j_{r},j_{r-2},\ldots ,j_{1}}$에 대하여 순차적으로 다음과 같은 단계를 추가로 거친다.

1. ${\displaystyle k}$번째 행에 ${\displaystyle 1/M_{kj_{k}}}$를 곱해, ${\displaystyle M_{kj_{k}}}$를 1로 만든다.
2. 모든 ${\displaystyle i<k}$번째 행에 ${\displaystyle k}$번째 행의 ${\displaystyle -M_{ij_{k}}}$배를 더해, ${\displaystyle M_{kj_{k}}}$ 위의 항들을 0으로 만든다.

여기서 ${\displaystyle r\leq m}$이며 ${\displaystyle r\leq n}$인 데 주의하자. 사실, 이는 행렬의 계수이다.

• 기약행사다리꼴행렬의 과정을 특히 조단이 제시한 "가우스 조단 소거법"으로 부른다.

세 가지 기본행연산은 모두 가역 연산이다.

• 행의 치환의 역연산은, 자기 자신이다.
• 행의 상수곱의 역연산은, 그 행에 그 상수 대신 역수를 곱하는 것이다.
• 어떤 행에 다른 행의 배수를 더하는 것의 역연산은, 더하는 대신 빼는 것이다.

두 연립일차방정식의 첨가 행렬이 하나에 기본행연산을 가하여 다른 하나를 얻을 수 있다면, 행동치라고 한다. 첨가 행렬이 행동치라면, 연립방정식의 풀이는 서로 같다.

기본 행렬은 단위 행렬에 기본행연산을 한 번 가하여 얻는 행렬이다. 이에 따라, 세 가지 기본행연산은 기본 행렬 곱셈과 같다.

가우스 소거법 알고리즘에서 알 수 있듯, 모든 연립일차방정식의 첨가 행렬은 그와 같은 해를 갖는 행사다리꼴행렬 및 기약행사다리꼴행렬로 변환할 수 있다. 따라서, 연립일차방정식의 풀이는 행사다리꼴행렬 및 기약행사다리꼴에 대한 풀이로 귀결된다.

${\displaystyle m\times (n+1)}$ 행사다리꼴행렬 ${\displaystyle R}$에 대한 연립일차방정식 ${\displaystyle Rx=0}$에 대하여, 다음 두 조건이 서로 동치이다.

• 해가 존재한다.
• 상수항이 0이 아닌 행이 존재하지 않는다. (상수항은 ${\displaystyle n+1}$번째 열의 항, 0행은 선행 계수가 없는 행을 뜻한다.)

해가 존재하는 ${\displaystyle Rx=0}$의 경우, 다음 두 조건이 서로 동치이다.

• 해가 유일하다.
• ${\displaystyle r=n}$. 즉, 0행이 아닌 행의 개수는 미지수의 개수와 같다. 즉, 선행 계수가 없는 열이 계수 행렬에 존재하지 않는다.

달리 말해, 해가 존재하는 ${\displaystyle Rx=0}$의 경우, 다음 두 조건이 서로 동치이다.

• 해가 유일하지 않다. (체의 표수가 0이라면, 이는 해가 무한히 많은 것과 동치이다.)
• ${\displaystyle r<n}$. 즉, 0행이 아닌 행의 개수는 미지수의 개수보다 적다. 즉, 선행 계수가 없는 열이 계수 행렬에 존재한다.

가우스 소거법을 사용하여 정사각행렬의 행렬식을 계산할 수 있다. 이는 정사각행렬에 대하여 다음 사실들이 성립하기 때문이다.

• 기본행연산을 가하면, 행렬식은 "상수배" 변화하며, 주어진 기본행연산이 행렬식을 변화시키는 배수는 자명하다. 즉,
  • 행을 치환하면, 행렬식은 -1배가 된다.
  • 행에 상수곱을 하면, 행렬식은 그 상수의 역수배가 된다.
  • 어떤 행에 다른 어떤 행의 상수배를 더하면, 행렬식은 변하지 않는다.
• 가우스 소거법을 통해 행렬을 행사다리꼴행렬로 변환할 수 있다. 특히 정사각행렬이므로, 이는 0행(즉 모든 항이 0인 행)을 갖거나, 상삼각행렬이다.
• 0행을 갖는 정사각행렬의 행렬식은 0이다.
• 상삼각행렬의 행렬식은 모든 대각항의 곱이다.

가우스 소거법을 사용하여 정사각행렬의 역행렬을 계산할 수 있다. ${\displaystyle n\times n}$ 행렬 ${\displaystyle M}$의 역행렬은 다음과 같이 계산한다. ${\displaystyle M}$에 ${\displaystyle n\times n}$ 단위행렬을 추가하여 ${\displaystyle n\times 2n}$ 행렬로 만든다.

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

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

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

가우스 소거법을 사용하여 행렬의 계수를 계산할 수 있다. ${\displaystyle m\times n}$ 행렬 ${\displaystyle M}$의 계수는 가우스 소거법을 가하여 얻는 행사다리꼴행렬에서 0이 아닌 행의 계수(즉, 선행 계수의 개수) ${\displaystyle r}$이다.

${\displaystyle \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]}$

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

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

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

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

그렇다면 다음과 같다.

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

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