가우스 소거법

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

정의

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

[math]\displaystyle{ Mx=0 }[/math]

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

[math]\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} }[/math]

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

[math]\displaystyle{ x=\begin{pmatrix}x_1\\x_2\\\vdots\\x_n\\1\end{pmatrix} }[/math]

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

[math]\displaystyle{ M_{11}x_1+M_{12}x_2+\cdots+M_{1,n}x_n+M_{1,n+1}=0 }[/math]

[math]\displaystyle{ M_{21}x_1+M_{22}x_2+\cdots+M_{2,n}x_n+M_{2,n+1}=0 }[/math]

[math]\displaystyle{ \vdots }[/math]

[math]\displaystyle{ M_{m1}x_1+M_{m2}x_2+\cdots+M_{m,n}x_n+M_{m,n+1}=0 }[/math]

기본 행 연산

이 경우, 이 연립방정식에 다음과 같은 세 가지 연산을 가할 수 있다. 이들을 기본 행 연산이라고 한다.

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

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

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

행사다리꼴행렬

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

[math]\displaystyle{ m\times(n+1) }[/math] 행렬 [math]\displaystyle{ M }[/math]에 대하여, [math]\displaystyle{ j_0(i)=\min\{j\le n\colon M_{ij}\ne0\} }[/math]이라고 하면, [math]\displaystyle{ M_{i,j_0(i)} }[/math]를 [math]\displaystyle{ i }[/math]번째 행의 선행 계수(先行係數, 틀:Llang)라고 한다. 선행 계수는 존재하지 않을 수 있다.

[math]\displaystyle{ m\times(n+1) }[/math] 행렬 [math]\displaystyle{ M }[/math]이 다음 조건을 만족시키면, [math]\displaystyle{ M }[/math]을 행사다리꼴행렬(사다리꼴行列, 틀:Llang)이라고 한다.

• 만약 [math]\displaystyle{ 0=M_{i1}=\cdots=M_{in} }[/math]이라면, 모든 [math]\displaystyle{ i\le i' }[/math]에 대하여 [math]\displaystyle{ 0=M_{i'1}=\cdots=M_{i'n} }[/math]이다.
• 만약 [math]\displaystyle{ i\lt i' }[/math]이며 [math]\displaystyle{ j_0(i) }[/math]와 [math]\displaystyle{ j_0(i') }[/math]가 존재한다면, [math]\displaystyle{ j_0(i)\lt j_0(i') }[/math]이다.

[math]\displaystyle{ m\times(n+1) }[/math] 행렬 [math]\displaystyle{ M }[/math]이 다음 조건을 만족시키면, [math]\displaystyle{ M }[/math]을 기약행사다리꼴행렬(旣約行사다리꼴行列, 틀:Llang)이라고 한다.

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

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

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

[math]\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} }[/math]

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

[math]\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} }[/math]

가우스 소거법

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

1. 선행 계수가 위치하는 가장 작은 열수 [math]\displaystyle{ j_1\le n }[/math]을 찾는다.
2. [math]\displaystyle{ M_{1j_1}=0 }[/math]이라면, 첫번째 행을 [math]\displaystyle{ M_{i_1j_1}\ne0 }[/math]인 어떤 [math]\displaystyle{ i_1\gt 1 }[/math]번째 행과 치환한다.
3. 모든 [math]\displaystyle{ i\gt 1 }[/math]번째 행에 첫번째 행의 [math]\displaystyle{ -M_{ij_1}/M_{1j_1} }[/math]배를 더해, [math]\displaystyle{ M_{1j_1} }[/math] 밑의 항들을 0으로 만든다.

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

1. 어떤 [math]\displaystyle{ i\ge2 }[/math]번째 행의 선행 계수가 위치하는 가장 작은 열수 [math]\displaystyle{ j_2\le n }[/math]을 찾는다.
2. [math]\displaystyle{ M_{2j_2}=0 }[/math]이라면, 두번째 행을 [math]\displaystyle{ M_{i_2j_2}\ne0 }[/math]인 어떤 [math]\displaystyle{ i_2\gt 2 }[/math]번째 행과 치환한다.
3. 모든 [math]\displaystyle{ i\gt 2 }[/math]번째 행에 두번째 행의 [math]\displaystyle{ -M_{ij_2}/M_{2j_2} }[/math]배를 더해, [math]\displaystyle{ M_{2j_2} }[/math] 밑의 항들을 0으로 만든다.

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

1. 어떤 [math]\displaystyle{ i\ge k }[/math]번째 행의 선행 계수가 위치하는 가장 작은 열수 [math]\displaystyle{ j_k\le n }[/math]을 찾는다.
2. [math]\displaystyle{ M_{kj_k}=0 }[/math]이라면, [math]\displaystyle{ k }[/math]번째 행을 [math]\displaystyle{ M_{i_kj_k}\ne0 }[/math]인 어떤 [math]\displaystyle{ i_k\gt k }[/math]번째 행과 치환한다.
3. 모든 [math]\displaystyle{ i\gt k }[/math]번째 행에 [math]\displaystyle{ k }[/math]번째 행의 [math]\displaystyle{ -M_{ij_k}/M_{kj_k} }[/math]배를 더해, [math]\displaystyle{ M_{kj_k} }[/math] 밑의 항들을 0으로 만든다.틀:Sfn

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

1. [math]\displaystyle{ k }[/math]번째 행에 [math]\displaystyle{ 1/M_{kj_k} }[/math]를 곱해, [math]\displaystyle{ M_{kj_k} }[/math]를 1로 만든다.
2. 모든 [math]\displaystyle{ i\lt k }[/math]번째 행에 [math]\displaystyle{ k }[/math]번째 행의 [math]\displaystyle{ -M_{ij_k} }[/math]배를 더해, [math]\displaystyle{ M_{kj_k} }[/math] 위의 항들을 0으로 만든다.

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

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

성질

기본행연산

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

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

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

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

행사다리꼴행렬

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

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

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

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

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

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

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

행렬식의 계산

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

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

역행렬의 계산

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

[math]\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} }[/math]

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

[math]\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} }[/math]

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

[math]\displaystyle{ \tilde M=M^{-1} }[/math]

계수 계산

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

예

[math]\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] }[/math]

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

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

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

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

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

그렇다면 다음과 같다.

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

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

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

[math]\displaystyle{ \begin{matrix} 2u &+& v &+& w &=& 5 \\ &-& 8v &-& 2w &=& -12 \\ && && w &=& 2 \end{matrix} }[/math]

이제 행렬이 사다리꼴이 되었다.

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

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

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

• [math]\displaystyle{ \begin{cases} 10u + 2v + -1w & = \ 27 \\ -3u + -6v + 2w & = \ -61.5 \\ u + v + 5w & = \ -21.5 \end{cases} }[/math]

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

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

• [math]\displaystyle{ \begin{cases} u + v + w & = \ ? \\ 2u + 2v + 5w & = \ ? \\ 4u + 4v + 8w & = \ ? \\ \end{cases} }[/math]

• [math]\displaystyle{ \begin{cases} u + v + w & = \ ? \\ 3w & = \ ? \\ 4w & = \ ? \end{cases} }[/math]

역행렬의 계산

다음과 같은 행렬 [math]\displaystyle{ M }[/math]의 역행렬을 계산한다고 하자.

[math]\displaystyle{ M = \begin{pmatrix} -1 & 1 & 2 \\ 3 & -1 & 1 \\ -1 & 3 & 4 \end{pmatrix} }[/math]

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

[math]\displaystyle{ \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} }[/math]

따라서 [math]\displaystyle{ M^{-1} }[/math]은 다음과 같다.

[math]\displaystyle{ M^{-1}=\begin{pmatrix} -0.7 & 0.2 & 0.3 \\ -1.3 & -0.2 & 0.7 \\ 0.8 & 0.2 & -0.2 \end{pmatrix} }[/math]