[더플러스수학] 가우스 소거법 - 기본 행 연산, 기본 행렬

연립방정식을 풀 때, 문자를 소거하느라 단순 계산 과정이 엄청 많다는 것을 경험한 적이 있을 것이다. 특히 연립방정식 중에서 미지수의 개수가 식의 개수보다 많은 연립방정식이면 역행렬이 존재하지 않아서 해를 구하기가 힘들다. 또, 역행렬이 존재한다 하더라도 행렬의 크기가 커 역행렬 구하기가 힘들 때, 우리는 가우스 소거법을 많이 쓴다.

또, 컴퓨터 프로그램으로 짜기도 쉬어 가우스 소거법을 이용하여 해를 구하는 과정이 쉬워진다. 

가우스 소거법에 대하여 알아보자. 

다음과 같은 \(\displaystyle 3\)개의 미지수를 가진 연립일차방정식을 생각해보자.

\(\displaystyle \begin{cases} a_{11}x +a_{12}y+a_{13}z=b_{1} \\a_{21}x +a_{22}y+a_{23}z=b_{2} \\a_{11}x +a_{12}y+a_{13}z=b_{2}\\a_{31}x +a_{32}y+a_{33}z=b_{3}\end{cases}\)      (1)

이것을 행렬로 나타내면

\(\displaystyle \begin{pmatrix} a_{11}&a_{12}&a_{13} \\a_{21}&a_{22}&a_{23} \\a_{31}&a_{32}&a_{33}\end{pmatrix}\begin{pmatrix}x_1\\x_2\\x_3 \end{pmatrix}=\begin{pmatrix}b_1\\b_2\\b_3 \end{pmatrix} \) 

이 때, \(\displaystyle \begin{pmatrix} a_{11}&a_{12}&a_{13} \\a_{21}&a_{22}&a_{23} \\a_{31}&a_{32}&a_{33}\end{pmatrix}\)를 주어진 방정식의 계수행렬(coefficient matrix)이라고 한다.

또, 이 때의 미지수 \(\displaystyle x_1 ,~x_2 ,~x_3  \)를 이 순서대로 고정시키면 연립방정식 (1)에 대해 \(\displaystyle b_1,~b_2 ,~b_3\) 를 계수행렬에 덧붙여 다음과 같은 행렬을 만들 수 있다.

\(\displaystyle \left( \begin{matrix} a_{11}&a_{12}&a_{13} \\a_{21}&a_{22}&a_{23} \\a_{31}&a_{32}&a_{33}\end{matrix}\right. \begin{matrix} \vert\\ \vert\\\vert \end{matrix} \left.\begin{matrix}b_1\\b_2\\b_3 \end{matrix} \right)\) 

이 행렬을 행렬 \(\displaystyle A\)에 덧붙인 행렬(Augmented matrix)라고 한다. 또, 일반적으로 두 연립방정식의 해가 같을 때, 이 두 연립방정식은 서로 동치라고 말한다.

우리가 연립방정식을 풀 때, 한 문자를 소거하기 위해 하는 행위를 통해 만들어지는 모든 연립방정식들은 원래의 연립방정시과 모두 동치이다. 그 행위를 정리하면 아래와 같다. 

(i) 서로 다른 두 방정식을 바꾸어 놓는다.

(ii) 한 방정식에 영이 아닌 수 \(\displaystyle a\)를 곱한다.

(iii) 한 방정식의 \(\displaystyle a\)배를 하여 다른 방정식에 더한다.

 

이 연산을 덧붙인 행렬(augmented matrix)에 시행하는 것을 기본행연산이라고 한다. 즉,

(i) 두 행을 바꾸어 놓는다.

(ii) 한 행에 영이 아닌 수 \(\displaystyle a\)를 곱한다.

(iii) 한 행에 \(\displaystyle a\)배를 하여 다른 행에 더한다.

 

정의1. \(\displaystyle n\)차 단위행렬 \(\displaystyle I_{n \times n}\)에 기본행 연산을 오직 한번만 수행하여 얻어지는 행렬을 기본행렬(elementary matrix)라고 한다.

예를 들어 \(\displaystyle 3\)차 단위행렬 \(\displaystyle I_{3 \times 3}\)에서

(1) \(\displaystyle 1\)행과 \(\displaystyle 2\)행를 바꾸는 기본행렬은 마치 일차변환에서 \(\displaystyle y=x\)에 대칭변환하듯이 단위행렬 \(\displaystyle I_{3 \times 3}\)에서 \(\displaystyle 1\)행과 \(\displaystyle 2\)행을 바꾸면 된다. 즉,

\(\displaystyle \begin{pmatrix} 0&\textcolor{red}{1}&0 \\\textcolor{red}{1}&0&0 \\0&0&1\end{pmatrix}\) 

(2) \(\displaystyle 3\)행에 \(\displaystyle 5\)배 하는 연산은 \(\displaystyle I_{3 \times 3}\)의 \(\displaystyle (3,~3)\)성분에 \(\displaystyle 5\)를 넣으면 된다. 

\(\displaystyle \begin{pmatrix} 1&0&0 \\0&1&0 \\0&0&\textcolor{red}{5}\end{pmatrix}\) 

(3) \(\displaystyle 3\)행에 \(\displaystyle 4\)배하여 \(\displaystyle 1\)행에 더하는 기본행렬은 단위행렬 \(\displaystyle I_{3 \times 3}\)에서 \(\displaystyle (1,~3)\)의 성분에 \(\displaystyle 4\)를 넣으면 된다.즉,

\(\displaystyle \begin{pmatrix} \textcolor{red}{1}&0&\textcolor{red}{4} \\0&1&0 \\0&0&1\end{pmatrix}\) 

 

이제 위의 기본행연산과 그것을 행렬로 표현한 기본행렬을 이용하여 가우스 소거법을 시행해 보자.

\(\displaystyle \begin{cases} 3x -7y+2z=4 \\2x -4y+z=1\end{cases}\) \(\displaystyle \Longleftrightarrow \)     \(\displaystyle \left( \begin{matrix} 3&-7&2\\2&-4&1\end{matrix}\right. \begin{matrix} \vert\\ \vert\end{matrix} \left.\begin{matrix}4\\1\end{matrix} \right)\) 

\(\displaystyle 2\)행에 \(\displaystyle (-1)\)배하여 \(\displaystyle 1\)행에 더한다. (행연산 iii)

\(\displaystyle \begin{cases} x -3y+z=3 \\2x -4y+z=1\end{cases}\) \(\displaystyle \Longleftrightarrow \)     \(\displaystyle \left( \begin{matrix} 1&-3&1\\2&-4&1\end{matrix}\right. \begin{matrix} \vert\\ \vert\end{matrix} \left.\begin{matrix}3\\1\end{matrix} \right)\) 

 이것을 기본행렬로 만들면 \(\displaystyle \begin{pmatrix} 1& \textcolor{red}{-1}\\0&1\end{pmatrix}\) 이고 이것을 위의 행렬의 왼쪽에 곱하면 똑같은 결과가 나온다. 즉, 

\(\displaystyle \begin{pmatrix} 1& \textcolor{red}{-1}\\0&1\end{pmatrix}\left( \begin{matrix} 3&-7&2\\2&-4&1\end{matrix}\right. \begin{matrix} \vert\\ \vert\end{matrix} \left.\begin{matrix}4\\1\end{matrix} \right)=\left( \begin{matrix} 1&-3&1\\2&-4&1\end{matrix}\right. \begin{matrix} \vert\\ \vert\end{matrix} \left.\begin{matrix}3\\1\end{matrix} \right)\) 

다음 \(\displaystyle 1\)행에 \(\displaystyle (-2)\)배하여 \(\displaystyle 2\)행에 더한다. (행연산 iii)

\(\displaystyle \begin{cases} x -3y+z=3 \\0x +2y-z=-1\end{cases}\) \(\displaystyle \Longleftrightarrow \)     \(\displaystyle \left( \begin{matrix} 1&-3&1\\0&2&-1\end{matrix}\right. \begin{matrix} \vert\\ \vert\end{matrix} \left.\begin{matrix}3\\-5\end{matrix} \right)\)

 이것을 기본행렬로 만들면 \(\displaystyle \begin{pmatrix} 1& 0\\\textcolor{red}{-2}&1\end{pmatrix}\) 이고 이것을 위의 행렬의 왼쪽에 곱하면 똑같은 결과가 나온다. 즉, 

\(\displaystyle \begin{pmatrix} 1& 0\\\textcolor{red}{-2}&1\end{pmatrix} \left( \begin{matrix} 1&-3&1\\2&-4&1\end{matrix}\right. \begin{matrix} \vert\\ \vert\end{matrix} \left.\begin{matrix}3\\1\end{matrix} \right)=\left( \begin{matrix} 1&-3&1\\0&2&-1\end{matrix}\right. \begin{matrix} \vert\\ \vert\end{matrix} \left.\begin{matrix}3\\-5\end{matrix} \right) \) 

이제 \(\displaystyle 2\)행에 \(\displaystyle \frac{1}{2}\)배하자. (행연산 ii)

\(\displaystyle \begin{cases} x -3y+z=3 \\0x +y- \frac{1}{2} z=- \frac{5}{2}\end{cases}\) \(\displaystyle \Longleftrightarrow \)     \(\displaystyle \left( \begin{matrix} 1&-3&1\\0&1&-\frac{1}{2}\end{matrix}\right. \begin{matrix} \vert\\ \vert\end{matrix} \left.\begin{matrix}3\\- \frac{5}{2}\end{matrix} \right)\)

 이것을 기본행렬로 만들면 \(\displaystyle \begin{pmatrix} 1& 0\\0&\textcolor{red}{\frac{1}{2}}\end{pmatrix}\) 이고 이것을 위의 행렬의 왼쪽에 곱하면 똑같은 결과가 나온다. 즉, 

\(\displaystyle \begin{pmatrix} 1& 0\\0&\textcolor{red}{\frac{1}{2}}\end{pmatrix} \left( \begin{matrix} 1&-3&1\\0&2&-1\end{matrix}\right. \begin{matrix} \vert\\ \vert\end{matrix} \left.\begin{matrix}3\\-5\end{matrix} \right)= \left( \begin{matrix} 1&-3&1\\0&1&-\frac{1}{2}\end{matrix}\right. \begin{matrix} \vert\\ \vert\end{matrix} \left.\begin{matrix}3\\- \frac{5}{2}\end{matrix} \right)\)

이제 연립방정식으로 다시 쓰면

\(\displaystyle \left( \begin{matrix} 1&-3&1\\0&1&-\frac{1}{2}\end{matrix}\right. \begin{matrix} \vert\\ \vert\end{matrix} \left.\begin{matrix}3\\- \frac{5}{2}\end{matrix} \right) \)  \(\displaystyle \Longleftrightarrow \)   \(\displaystyle \begin{cases} 1x-3y+z=3\\0x+1y-\frac{1}{2}z=- \frac{5}{2}\end{cases} \)    (2)

여기서 \(\displaystyle  z\)가 어떤 실숫값을 가지더라도 처음 주어진 두 방정식의 근 \(\displaystyle  x,~y,~z\)가 결정되므로 \(\displaystyle  z\)를 자유변수라고 한다. 또, \(\displaystyle  x,~y\)는 \(\displaystyle  z\)에 의해 결정되므로 종속변수라고 말한다.

이 때, \(\displaystyle z=t\)라 두면 \(\displaystyle y- \frac{1}{2} t = - \frac{5}{2}\)이므로 \(\displaystyle y= \frac{1}{2} t  - \frac{5}{2}\) 이다.

또, \(\displaystyle x-3y+z=3\)에 \(\displaystyle z=t\), \(\displaystyle y= \frac{1}{2} t  - \frac{5}{2}\)를 대입하여 \(\displaystyle x\)에 관하여 정리하면

\(\displaystyle \begin{align}x &= 3\left( \frac{1}{2} t  - \frac{5}{2}\right) -t+3 \\&= \frac{1}{2}t - \frac{9}{2} \end{align}\)

이다. 이를 정리하고 행렬로 표현하면

\(\displaystyle \begin{cases}x= \frac{1}{2}t - \frac{9}{2} \\  y= \frac{1}{2} t  - \frac{5}{2} \\z=t \end{cases}  \)   \(\displaystyle \Longleftrightarrow\)   \(\displaystyle \begin{pmatrix}x &y&z\end{pmatrix}= t \begin{pmatrix} \frac{1}{2} \\\frac{1}{2} \\1\end{pmatrix} + \begin{pmatrix}- \frac{9}{2} \\ -\frac{5}{2} \\ 0\end{pmatrix}  \)  (\(\displaystyle t \) 는 실수)

(2)의 왼쪽의 행렬을 보면 모양이 사다리꼴 모양이 나온다. 이 행렬을 행사다리꼴 행렬이라고 한다. 

 

정의2. 행사다리꼴, 기약행사다리꼴 행렬

다음 \(\displaystyle 4\)가지 조건을 모두 만족시키는 행렬을 기약행사다리꼴 행렬이라 한다.

(1)  \(\displaystyle 0\)만으로 이루어진 행은 그렇지 않은 행보다 뒤에 놓여 있다.

(2) 각 행에서 처음으로 \(\displaystyle0\)이 아닌 성분은 \(\displaystyle1\)이다. 이것을 선도 \(\displaystyle1\) (leading \(\displaystyle1\))이라고 한다.

(3) 조건 (2)의 \(\displaystyle1\)은 행의 번호가 커질수록 더 오른쪽에 놓여 있다.

(4) 조건 (2)의 \(\displaystyle1\)이 들어 있는 열의 나머지 성분은 모두 \(\displaystyle 0\)이다.

위의 조건 중 (1)에서 (3)까지 만족하는 행렬을 행사다리꼴 행렬이라고 한다.

 

예제 다음 행렬은 행사다리꼴 행렬이다.

\(\displaystyle \left( \begin{matrix} \textcolor{red}{1} &\textcolor {blue}{-3}&1\\0 & \textcolor{red}{1}  & -\frac{1}{2}  \end{matrix} \right. \begin{matrix} \vert \\ \vert \end{matrix} \left. \begin{matrix} 3\\- \frac{5}{2} \end{matrix} \right) \)

이 때 빨간 \(\displaystyle\textcolor{red}{1}  \)을 선도 \(\displaystyle 1\) 또는 leading \(\displaystyle1\)이라고 부른다. 그런데 푸른 색 \(\displaystyle \textcolor {blue}{-3} \)이 \(\displaystyle 0\)이 된다면 이 행렬은 기약행사다리꼴 행렬이 된다. 즉 \(\displaystyle 2\)행에 \(\displaystyle 3\)배하여 \(\displaystyle 1 \)행에 더하자. 기본행렬 \(\displaystyle \left( \begin{matrix} 1&\textcolor{red}{3}\\0&1\end{matrix} \right) \)을 곱하자.

\(\displaystyle \left( \begin{matrix} 1&\textcolor{red}{3}\\0&1 \end{matrix} \right) \left( \begin{matrix} \textcolor{red}{1} &\textcolor {blue}{-3}&1\\0 & \textcolor{red}{1}  & -\frac{1}{2}  \end{matrix} \right. \begin{matrix} \vert \\ \vert \end{matrix} \left. \begin{matrix} 3\\- \frac{5}{2} \end{matrix} \right) = \left( \begin{matrix} \textcolor{red}{1} &\textcolor {blue}{0}& -\frac{1}{2}\\0 & \textcolor{red}{1}  & -\frac{1}{2}  \end{matrix} \right. \begin{matrix} \vert \\ \vert \end{matrix} \left. \begin{matrix} -\frac{9}{2}\\- \frac{5}{2} \end{matrix} \right)  \)

그러면 \(\displaystyle \left( \begin{matrix} \textcolor{red}{1} &\textcolor {blue}{0}& -\frac{1}{2}\\0 & \textcolor{red}{1}  & -\frac{1}{2}  \end{matrix} \right. \begin{matrix} \vert \\ \vert \end{matrix} \left. \begin{matrix} -\frac{9}{2}\\- \frac{5}{2} \end{matrix} \right)  \)은 기약행사다리꼴 행렬이다. 

기약행사다리꼴 행렬을 만들면 자유변수 \(\displaystyle z\)를 \(\displaystyle z=t\)로 놓고 \(\displaystyle x,~y\)를 \(\displaystyle z\)로 표현하기가 쉽다. 그러나 기본 행 연산을 더 많이 해야 하므로 좀 귀찮다.

다른 예를 좀 더 보자.

 \(\displaystyle \begin{pmatrix} 1&\textcolor {red}{0}&4\\0&1&3\end{pmatrix}\)은 기약행사다리꼴이자 행사다리꼴이다.

\(\displaystyle \begin{pmatrix} 1&\textcolor {red}{2}&3\\0&1&1\end{pmatrix}\)은 행사다리꼴 행렬이다. 빨간 \(\displaystyle \textcolor {red}{2}\)가 \(\displaystyle 0\)이 아니기 때문이다.

\(\displaystyle \begin{pmatrix} 1&{0}&1\\0&0&\textcolor {red}{1}\\0&\textcolor {red}{1}&2\end{pmatrix}\)은 행사다리꼴 행렬도 기약행사다리꼴 행렬도 아니다. \(\displaystyle 2\)행, \(\displaystyle 3\)행이 위의 (3) 조건을 만족하지 않기 때문이다. \(\displaystyle 2\)과 \(\displaystyle3\)행을 바꾸면 행사다리꼴 행렬은 된다. 즉

\(\displaystyle \begin{pmatrix} 1&{0}&\textcolor {blue}{1}\\0&\textcolor {red}{1}&\textcolor {blue}{2}\\0&0&\textcolor {red}{1}\end{pmatrix}\)

파란 색의 수들이 \(\displaystyle 0\)이 아니어서 기약행사다리꼴 행렬은 안된다.

 

(참고) 기약행사다리꼴 행렬과 행사다리꼴 행렬의 특징

(1) 모든 행렬은 기약행사다리꼴 행렬은 유일하다. 즉, 어떠한 기본행연산을 하든 관계없이 마지막에 남는 기약행사다리꼴 행렬은 똑같다.

(2) 그렇지만 행사다리꼴 행렬은 유일하지 않다. 즉 기본행연산의 순서가 다르면 다른 행사다리꼴 행렬이 나온다.

(3) 행사다리꼴은 유일하지는 않지만 행렬 \(\displaystyle A\)의 모든 행사다리꼴은 같은 수의 '모든 원소가 \(\displaystyle0\)'인 행을 갖고, 항상 같은 위치에 선도 \(\displaystyle1\)도 같은 위치에 난다. 이곳을 행렬 \(\displaystyle A\)의 축의 위치라고 하고 축이 있는 열을 \(\displaystyle A\)의 축열이라고 한다.

행렬  \(\displaystyle A\)와 행사다리꼴, 기약행 사다리꼴에서 위의 성질을 확인할 수 있다. 또, 축의 위치, 즉 선도  \(\displaystyle1\)이 있는 위치는  \(\displaystyle (1,~1),~(2,~1)\)이고 축열은  \(\displaystyle 1\)열과  \(\displaystyle2\)열이다.

 \(\displaystyle A=\left( \begin{matrix} 3&-7&2\\2&-4&1\end{matrix}\right. \begin{matrix} \vert\\ \vert\end{matrix} \left.\begin{matrix}4\\1\end{matrix} \right)\)  \(\displaystyle \left( \begin{matrix} \textcolor{red}{1} &\textcolor {blue}{-3}&1\\0 & \textcolor{red}{1}  & -\frac{1}{2}  \end{matrix} \right. \begin{matrix} \vert \\ \vert \end{matrix} \left. \begin{matrix} 3\\- \frac{5}{2} \end{matrix} \right)\)   \(\displaystyle \left( \begin{matrix} \textcolor{red}{1} &\textcolor {blue}{0}& -\frac{1}{2}\\0 & \textcolor{red}{1}  & -\frac{1}{2}  \end{matrix} \right. \begin{matrix} \vert \\ \vert \end{matrix} \left. \begin{matrix} -\frac{9}{2}\\- \frac{5}{2} \end{matrix} \right)  \)

 

정의3 가우스 소거법

연립일차방정식의 해를 구할 때, 먼저 주어진 연립방정식을 덧붙인 행렬(augmented matrix)로 만든 후 기본행연산을 유한 번 시행하여 행사다리꼴 행렬 (또는 기약행사다리꼴 행렬)로 만든 후 연립일차방정식을 푸는 방법을 가우스 소거법이라고 한다.

 

과학고 내신대비와 대학입시를 위해서는 다음의 글을 참조하세요. 다양한 글이 있습니다.

http://mathhowtosolveit.com/%EA%B3%BC%ED%95%99%EA%B3%A0-%ED%95%99%EB%85%84%EB%B3%84-%EB%82%B4%EC%8B%A0%EB%8C%80%EB%B9%84-%EC%98%88%EC%83%81%EB%AC%B8%EC%A0%9C

더플러스수학 https://www.youtube.com/@THEPLUSMATH/channels

더플러스수학 블로그 https://plusthemath.tistory.com/

더플러스수학 네이버블로그 https://m.blog.naver.com/plusthemath