선형대수학 입문/선형 연립방정식

선형 연립방정식의 행렬꼴

우리는 선형 연립방정식을 행렬꼴로 나타내기 전에 그것이 뭔지 정의할 필요가 있습니다.

정의 2.1. 선형 연립방정식

자연수 $n$개의(우리 논의에서 0은 자연수가 아니다.) 미지수 $x_{1},x_{2},\ldots ,x_{n}$의 선형 연립방정식은 다음 형태의 방정식 묶음으로 나타낸다. $${\begin{cases}a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}=b_{1},\\a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}=b_{2},\\\quad \qquad \qquad \qquad \vdots \\a_{m1}x_{1}+a_{m2}x_{2}+\cdots +a_{mn}x_{n}=b_{m},\end{cases}}$$ 여기서 $a_{ij}$와 $b_{k}$는 어떤 상수다.

참고

• 몇몇 다른 정의에서는 하나의 선형 방정식(계수가 1인 방정식) 역시도 선형 연립방정식으로 취급하는 경우가 있지만, 하나의 선형 방정식은 풀기 쉽고, 이런 경우는 우리의 관심에서 멀기 때문에, 우리는 이걸 고려하지 않을 것이다.

앞으로 선형 연립방정식을 기술할 때 '일관적'(consistent), 그리고 '모순적'(혹은 비일관적, inconsistent)이라는 단어를 사용할 것입니다.

두 미지수가 있고, 세 개의 선형 방정식(선)이 있는 이 그림은 세 선이 동시에 지나는 점이 없으므로 일관적이지 않다.

정의 2.2. (선형 연립방정식의 일관성)

선형 연립방정식은 적어도 하나의 해가 있으면 일관적이다. 그렇지 않으면 모순적이다.(따라서 해가 하나도 없으면 모순적이다.)

참고

• 우리가 나중에 볼 것이지만, 선형 연립방정식은 해가 전혀 없거나, 하나만 있거나, 무수히 많다. 따라서 선형 연립방정식이 일관적이면 해가 유일하거나 무수히 많은 것은 동치다.

예시 (일관적인 선형 연립방정식)

다음 선형 연립방정식을 고려하자. $${\begin{cases}x+2y=3&\quad (1)\\3x+6y=9&\quad (2)\end{cases}}.$$ 여기서 $$(2)\iff 3x+6y=9\iff (3/3)x+(6/3)y\iff (9/3)\iff x+2y=3\iff (1)$$ 이므로, 이 선형 연립방정식의 해는 $x+2y=3$를 만족하는 $(x,y)$이다. 따라서 이 선형 연립방정식의 해는 무수하게 많고, 그러므로 일관적이다.

예시 (모순적인 선형 연립방정식)

다음 선형 연립방정식을 고려하자. $${\begin{cases}x+2y=3&\quad (1)\\x+2y=4&\quad (2)\end{cases}}.$$ $(2)$에 $(1)$을 대입하면, $$3=4$$ 이고, 말이 안되는 소리이므로 두 방정식을 만족하는 $(x,y)$는 존재하지 않는다. 이는 선형 연립방정식의 해가 없다는 것이고, 따라서 이 선형 연립방정식은 모순적이다.

예시 (선형 연립방정식의 응용)

10병의 오렌지 주스가 닭, 오리, 거위에게 배당한다고 하자. 닭과 오리에게 똑같은 개수의 병이 주어지고, 거위는 닭과 오리에 비해 한 병 더 많다고 하면 각각의 동물에게 얼마의 병이 배당되었는가?

답:

닭, 오리, 거위에게 할당된 오렌지 주스 병의 개수를 각각 $c,d,g$라고 하자. 그러면 주어진 상황과 조건에 따라 우리는 다음과 같은 선형 연립방정식을 세울 수 있다. $${\begin{cases}c+d+g=10&\quad (1)\\c=d&\quad (2)\\g=c+1&\quad (3)\end{cases}}$$ 여기서 $c,d,g$는 모두 음이 아닌 정수다.

$(2)$와 $(3)$을 $(1)$에 대입하면 $$c+c+c+1=10\implies c=3.$$ 따라서 $d=c=3$이고 $g=c+1=4$이다.

즉, 닭과 오리는 각각 3개의 오렌지 주스 병이 배당되었고, 거위는 4개의 오렌지 주스 병이 배당되었다.

선형 연립방정식을 정의했으므로, 우리는 이것을 다양한 방법의 행렬 꼴로 표현할 수 있다. 그리고 그것을 다음과 같이 정의한다.

정의 2.3 (계수행렬과 첨가행렬)

$${\begin{cases}a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}=b_{1},\\a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}=b_{2},\\\quad \qquad \qquad \qquad \vdots \\a_{m1}x_{1}+a_{m2}x_{2}+\cdots +a_{mn}x_{n}=b_{m}\end{cases}}$$ 를 미지수 $x_{1},x_{2},\ldots ,x_{n}$가 주어지고, $a_{ij}$와 $b_{k}$는 어떤 상수인 선형 연립방정식을 생각하자.

행렬 ${\color {green}(a_{ij})_{m\times n}}$은 연립방정식의 계수 행렬이라 하고, 행렬 $$\left({\begin{array}{cccc|c}a_{11}&a_{12}&\cdots &a_{1n}&b_{1}\\a_{21}&a_{22}&\cdots &a_{2n}&b_{2}\\\vdots &\vdots &\ddots &\vdots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}&b_{n}\end{array}}\right)$$ 은 연립방정식의 첨가행렬이라고 한다.

참고

• 첨가행렬에서 수직선은 선택적인 것으로, 상수를 '$=$'의 왼쪽과 오른쪽으로 나누기 위해 선형 연립방정식에서 사용한다.
• 이 연립방정식은 다음과 똑같다.

$$\underbrace {\begin{pmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}\end{pmatrix}} _{{\text{계수}}\;A{\text{표현}}}\underbrace {\begin{pmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{pmatrix}} _{{\text{미지수}}\;\mathbf {x} {\text{표현}}}=\underbrace {\begin{pmatrix}b_{1}\\b_{2}\\\vdots \\b_{n}\end{pmatrix}} _{{\text{상수}}\;\mathbf {b} {\text{표현}}},$$

이는 $A\mathbf {x} =\mathbf {b}$로 다시 쓸 수 있다.

• 미지수가 어떤 상수인지 특정할 수 없기 때문에 미지수만 표현하는 것은 중요하지 않다. 따라서 첨가행렬은 연립방정식을 푸는데 필수적인 정보를 준다.

예시(계수행렬과 첨가행렬)

선형 연립방정식 $${\begin{cases}w+x+y=1\\w+z=3\\x+z=8\end{cases}}$$ 을 고려하자. 이것을 달리 표현하면 다음과 같다. $${\begin{cases}w+x+y+0z=1\\w+0x+0y+z=3\\0w+x+0y+z=8\end{cases}}$$

선형 연립방정식의 계수행렬은 $${\begin{pmatrix}1&1&1&0\\1&0&0&1\\0&1&0&1\end{pmatrix}}$$ 이고, 선형 연립방정식의 첨가행렬은 $$\left({\begin{array}{cccc|c}1&1&1&0&1\\1&0&0&1&3\\0&1&0&1&8\end{array}}\right)$$ 이다. 우리는 이 선형 연립방정식을 또 $${\begin{pmatrix}1&1&1&0\\1&0&0&1\\0&1&0&1\end{pmatrix}}{\begin{pmatrix}w\\x\\y\\z\end{pmatrix}}={\begin{pmatrix}1\\3\\8\end{pmatrix}}$$ 로 표현할 수 있고 또 $A\mathbf {x} =\mathbf {b}$로 사용할 수 있다.

가우스-요르단 소거법

정의 2.4. (기본 행 연산) 행렬에서 적용할 수 있는 기본 행 연산에는 세 가지가 있다:

• 두 행의 치환
• 행에 0이 아닌 스칼라의 곱셈
• 한 행에 다른 행의 스칼라배 더하기

참고

기본 행 연산에서 다음과 같은 표기를 따를 것이다:

• $\mathbf {r} _{1},\mathbf {r} _{2},\ldots ,\mathbf {r} _{m}$: $m\times n$ 행렬의 행 (행은 원래 벡터이므로 볼드체를 쓴다.)
• $\mathbf {r} _{\color {blue}i}{\color {green}\leftrightarrow }\mathbf {r} _{\color {red}j}$: $\color {blue}i$번째 행과 $\color {red}j$번째 행을 치환
• ${\color {green}k}\mathbf {r} _{i}\to \mathbf {r} _{i}$: $i$번째 행에 0이 아닌 스칼라 $\color {green}k$를 곱하기
• ${\color {purple}k}\mathbf {r} _{\color {red}j}{\color {green}+}\mathbf {r} _{\color {blue}i}\to \mathbf {r} _{\color {blue}i}$: $\color {blue}i$번째 행에 $\color {purple}k$배를 한 $\color {red}j$번째 행 더하기

정의 2.5. (행 동치, Row equivalence) 같은 크기의 두 행렬에 대하여 한 행렬에다가 어떤 기본 행연산을 실행해서 다른 행렬을 만들어낼 수 있으면 서로 행 동치다.

참고

• 기본 행연산은 (성질에 의해)가역적이라서 행렬 $B$를 기본 행연산으로 행렬 $A$로 바꿀 수 있으면 $A$도 기본 행연산을 통해 $B$로 만들어낼 수 있다.(각각의 연산의 역을 찾고 순서에 맞게 잘 정리해서 얻어낼 수 있다.)

• 따라서 행 동치를 증명하기 위해서 어떤 한 쪽의 행렬이 다른 쪽의 행렬로 기본 행연산을 하면 같아진다는 것만 증명하면 된다.(물론 두 행렬의 크기는 같아야한다.) 이에 대한 증명은 아래에서 할 것이다.

예시 (Demonstration of three types of EROs)

행렬 $$A={\begin{pmatrix}{\color {red}1}&{\color {red}2}&{\color {red}3}\\{\color {blue}4}&{\color {blue}5}&{\color {blue}6}\\{\color {green}7}&{\color {green}8}&{\color {green}9}\end{pmatrix}}$$ 을 생각하자. 그러면 기본 행연산은 다음을 같이 연산한다: $${\begin{aligned}{\begin{pmatrix}{\color {red}1}&{\color {red}2}&{\color {red}3}\\{\color {blue}4}&{\color {blue}5}&{\color {blue}6}\\{\color {green}7}&{\color {green}8}&{\color {green}9}\end{pmatrix}}&{\overset {\mathbf {r} _{1}\leftrightarrow \mathbf {r} _{3}}{\to }}{\begin{pmatrix}{\color {green}7}&{\color {green}8}&{\color {green}9}\\{\color {blue}4}&{\color {blue}5}&{\color {blue}6}\\{\color {red}1}&{\color {red}2}&{\color {red}3}\end{pmatrix}}\\&{\overset {\pi \mathbf {r} _{1}\to \mathbf {r} _{1}}{\to }}{\begin{pmatrix}{\color {green}7}\pi &{\color {green}8}\pi &{\color {green}9}\pi \\{\color {blue}4}&{\color {blue}5}&{\color {blue}6}\\{\color {red}1}&{\color {red}2}&{\color {red}3}\end{pmatrix}}\\&{\overset {2\mathbf {r} _{2}+\mathbf {r} _{3}\to \mathbf {r} _{3}}{\to }}{\begin{pmatrix}{\color {green}7}\pi &{\color {green}8}\pi &{\color {green}9}\pi \\{\color {blue}4}&{\color {blue}5}&{\color {blue}6}\\2({\color {blue}4})+{\color {red}1}&2({\color {blue}5})+{\color {red}2}&2({\color {blue}6})+{\color {red}3}\\\end{pmatrix}}\\&{\overset {-2\mathbf {r} _{2}+\mathbf {r} _{3}\to \mathbf {r} _{3}}{\to }}{\begin{pmatrix}{\color {green}7}\pi &{\color {green}8}\pi &{\color {green}9}\pi \\{\color {blue}4}&{\color {blue}5}&{\color {blue}6}\\{\color {red}1}&{\color {red}2}&{\color {red}3}\\\end{pmatrix}}\\&{\overset {(1/\pi )\mathbf {r} _{1}\rightarrow \mathbf {r} _{1}}{\to }}{\begin{pmatrix}{\color {green}7}&{\color {green}8}&{\color {green}9}\\{\color {blue}4}&{\color {blue}5}&{\color {blue}6}\\{\color {red}1}&{\color {red}2}&{\color {red}3}\\\end{pmatrix}}\\&{\overset {\mathbf {r} _{1}\rightarrow \mathbf {r} _{3}}{\to }}{\begin{pmatrix}{\color {red}1}&{\color {red}2}&{\color {red}3}\\{\color {blue}4}&{\color {blue}5}&{\color {blue}6}\\{\color {green}7}&{\color {green}8}&{\color {green}9}\\\end{pmatrix}}=A.\end{aligned}}$$ 여기에 보여진 각각의 행렬은 각자 $A$로 가는 기본 행연산이 주어져있기 때문에 $A$와 행 동치를 이루고, $A$와 같은 크기를 가진다.(그리고 기본 행연산에 대한 이전으로 돌아가는 역산도 보여준다.)

성질 (기본 행연산의 가역성)

행렬$B$에 적절한 기본 행연산으로 행렬 $A$를 만들 수 있다면, $A$ 역시도 적절한 기본 행연산으로 $B$로 바꿀 수 있다.(역과정에서 사용한 기본 행연산은 조금 다를 수 있다.)

증명:

설명: 각자의 기본 행연산에는 역과정이 있고(다시 말해 모든 기본 행연산은 그 역과정과 같이 존재하고, 이것은 행렬에 영향을 미치지 못한다.), 이의 역과정은 다음과 같다:

• 치환 기본 행연산 $\mathbf {r} _{i}\leftrightarrow \mathbf {r} _{j}$의 역과정 역시 $\mathbf {r} _{i}\leftrightarrow \mathbf {r} _{j}$이다.
• 스칼라곱 기본 행연산 $k\mathbf {r} _{i}\to \mathbf {r} _{i}$의 역과정은 스칼라곱 기본행연산 ${\frac {1}{k}}\mathbf {r} _{i}\to \mathbf {r} _{i}$ ($k=0$일 때의 이 연산 자체가 정의되어 있지 않다. 이것이 $k$가 반드시 0이 아니어야 하는 이유고, 따라서 역과정이 존재한다.)
• 덧셈 기본 행연산 $k\mathbf {r} _{j}+\mathbf {r} _{i}\to \mathbf {r} _{i}$의 역과정은 덧셈 기본 행연산 $-k\mathbf {r} _{j}+\mathbf {r} _{i}\to \mathbf {r} _{i}$이다.

예시 (각각의 기본 행연산의 역과정들)

• 치환:

$${\begin{pmatrix}{\color {red}1}&{\color {red}2}\\{\color {blue}3}&{\color {blue}4}\\\end{pmatrix}}{\overset {\mathbf {r} _{1}\leftrightarrow \mathbf {r} _{2}}{\to }}{\begin{pmatrix}{\color {blue}3}&{\color {blue}4}\\{\color {red}1}&{\color {red}2}\\\end{pmatrix}}{\overset {\mathbf {r} _{1}\leftrightarrow \mathbf {r} _{2}}{\to }}{\begin{pmatrix}{\color {red}1}&{\color {red}2}\\{\color {blue}3}&{\color {blue}4}\\\end{pmatrix}}$$

• 스칼라곱:

$${\begin{pmatrix}{\color {red}1}&{\color {red}2}\\{\color {blue}3}&{\color {blue}4}\\\end{pmatrix}}{\overset {{\color {green}k}\mathbf {r} _{1}\to \mathbf {r} _{1}}{\to }}{\begin{pmatrix}{\color {red}1}{\color {green}k}&{\color {red}2}{\color {green}k}\\{\color {blue}3}&{\color {blue}4}\\\end{pmatrix}}{\overset {{\color {green}{\frac {1}{k}}}\mathbf {r} _{1}\to \mathbf {r} _{1}}{\to }}{\begin{pmatrix}{\color {red}1}{\color {green}{\cancel {k}}}\cdot {\color {green}{\frac {1}{\cancel {k}}}}&{\color {red}2}{\color {green}{\cancel {k}}}\cdot {\color {green}{\frac {1}{\cancel {k}}}}\\{\color {blue}3}&{\color {blue}4}\\\end{pmatrix}}={\begin{pmatrix}{\color {red}1}&{\color {red}2}\\{\color {blue}3}&{\color {blue}4}\\\end{pmatrix}}\quad (k\neq 0)$$

• 덧셈:

$${\begin{pmatrix}{\color {red}1}&{\color {red}2}\\{\color {blue}3}&{\color {blue}4}\\\end{pmatrix}}{\overset {{\color {green}k}\mathbf {r} _{2}+\mathbf {r} _{1}\to \mathbf {r} _{1}}{\to }}{\begin{pmatrix}{\color {red}1}+{\color {blue}3}{\color {green}k}&{\color {red}2}+{\color {blue}4}{\color {green}k}\\{\color {blue}3}&{\color {blue}4}\\\end{pmatrix}}{\overset {{\color {green}-k}\mathbf {r} _{2}+\mathbf {r} _{1}\to \mathbf {r} _{1}}{\to }}{\begin{pmatrix}{\color {red}1}{\cancel {+{\color {blue}3}{\color {green}k}-{\color {blue}3}{\color {green}k}}}&{\color {red}2}{\cancel {+{\color {blue}4}{\color {green}k}-{\color {blue}4}{\color {green}k}}}\\{\color {blue}3}&{\color {blue}4}\\\end{pmatrix}}={\begin{pmatrix}{\color {red}1}&{\color {red}2}\\{\color {blue}3}&{\color {blue}4}\\\end{pmatrix}}$$

성질 (행 동치와 해)

$A\mathbf {x} =\mathbf {b}$와 $C\mathbf {y} =\mathbf {d}$인 방정식 개수와 변수의 개수가 같은 두 개의 선형 연립방정식을 생각해보자. 첨가행렬 $(A|\mathbf {b} )$와 $(C|\mathbf {d} )$가 행 동치이면, 두 개의 연립방정식은 같은 해들을 갖는다.

증명

설명: 하나의 기본 행연산으로 해들이 바뀌지 않음을 보이기만 하면 충분하다. 예를 들어

• 치환:

$${\begin{cases}x+2y=3\\4x+5y=6\\\end{cases}}{\text{ and }}{\begin{cases}4x+5y=6\\x+2y=3\\\end{cases}}{\text{비 교}}\;$$

• 스칼라 곱셈:

$${\begin{cases}x+2y=3\\4x+5y=6\\\end{cases}}{\text{ and }}{\begin{cases}kx+2ky=3k\\4x+5y=6\\\end{cases}}\Leftrightarrow {\begin{cases}x+2y=3\\4x+5y=6\\\end{cases}}\quad (k\neq 0){\text{비 교}}\;$$

• 덧셈:

$${\begin{cases}x+2y=3\\4x+5y=6\\\end{cases}}{\text{ and }}{\begin{cases}x+2y=3&\quad (1)\\(4+k)x+(5+2k)y=6+3k&\quad (2)\\\end{cases}}{\text{비 교}}\;$$ $(1)-k(2):$ $$(4+k-k)x+(5+2k-2k)y=6+3k-3k\iff 4x+5y=6$$

정의 2.6. (선행성분)

행렬의 행의 선행성분은 0이 아닌 가장 왼쪽에 있는 성분이다.

예시

아래 행렬의 첫번째, 두번째 세번째 행의 선행성분은 $${\begin{pmatrix}0&{\color {blue}2}&3\\0&0&{\color {blue}3}\\{\color {blue}8}&6&2\\\end{pmatrix}}$$ 각각 $2,3,8$이다.

정의 2.7. (사다리꼴행렬)

다음 조건을 만족하는 행렬은 행사다리꼴행렬(혹은 사다리꼴행렬, 약자 REF)이다.

1. 모든 성분이 $0$인 행은 (존재한다면)행렬의 가장 밑자리에 놓여있다.
2. $0$이 아닌 성분이 하나라도 포함된 행의 선행성분은 반드시 항상 위 행렬의 선행성분의 오른쪽에 있다.

정의 2.8. (기약행사다리꼴행렬)

다음 조건을 만족하는 행렬을 기약행사다리꼴행렬(Reduced-Row Echelon Form matrix, RREF)이라 한다.

1. 사다리꼴 행렬이다.
2. $0$이 아닌 성분이 하나라도 포함된 행의 선행성분이 ${\color {green}1}$이다.(이를 선행 1(leading one)이라고 부른다.)
3. 각각의 선행 1에 대해서 같은 열의 다른 모든 성분은 0이다.

예시(REF와 RREF)

• RREF가 아닌 REF:

$${\begin{pmatrix}{\color {blue}3}&2&1&1\\0&{\color {blue}2}&9&4\\0&0&0&{\color {blue}7}\\0&0&0&0\\0&0&0&0\\\end{pmatrix}},{\begin{pmatrix}{\color {blue}3}&2&1&1\\0&{\color {blue}2}&9&4\\0&0&0&{\color {blue}7}\\0&0&0&0\\0&0&0&0\\\end{pmatrix}},{\begin{pmatrix}0&0&{\color {blue}3}&2&1&0\\0&0&0&0&0&{\color {blue}2}\\0&0&0&0&0&0\\\end{pmatrix}}$$

• RREF 행렬들(그리고 당연하게 REF이기도 하다.):

$${\begin{pmatrix}{\color {blue}1}&{\color {green}0}&7&{\color {green}0}&1\\{\color {green}0}&{\color {blue}1}&9&{\color {green}0}&2\\{\color {green}0}&{\color {green}0}&0&{\color {blue}1}&9\\{\color {green}0}&{\color {green}0}&0&{\color {green}0}&0\\\end{pmatrix}},{\begin{pmatrix}{\color {blue}1}&{\color {green}0}&7&{\color {green}0}&1\\{\color {green}0}&{\color {blue}1}&9&{\color {green}0}&2\\{\color {green}0}&{\color {green}0}&0&{\color {blue}1}&9\\\end{pmatrix}},{\begin{pmatrix}{\color {blue}1}&{\color {green}0}&7&{\color {green}0}\\{\color {green}0}&{\color {blue}1}&9&{\color {green}0}\\{\color {green}0}&{\color {green}0}&0&{\color {blue}1}\\\end{pmatrix}},{\begin{pmatrix}0&{\color {blue}1}&{\color {green}0}&{\color {green}0}\\0&{\color {green}0}&{\color {blue}1}&{\color {green}0}\\0&{\color {green}0}&{\color {green}0}&{\color {blue}1}\\\end{pmatrix}},I,O$$

• REF가 아닌 행렬들(마찬가지로 RREF도 아니다.):

$${\begin{pmatrix}1&2&1&1\\{\color {red}0}&{\color {red}0}&{\color {red}0}&{\color {red}0}\\0&1&9&4\\0&0&0&1\\0&0&0&0\\\end{pmatrix}},{\begin{pmatrix}0&0&0&0&0&{\color {red}1}\\0&0&{\color {red}1}&2&1&0\\0&0&0&0&0&0\\\end{pmatrix}},{\begin{pmatrix}{\color {red}1}&2&3\\{\color {red}4}&5&6\\{\color {red}7}&8&9\\\end{pmatrix}},{\begin{pmatrix}0&0&{\color {red}1}\\0&{\color {red}1}&0\\{\color {red}1}&0&0\\\end{pmatrix}},{\begin{pmatrix}{\color {red}1}&0&0\\0&{\color {red}1}&0\\0&{\color {red}1}&0\\\end{pmatrix}}$$

정의 2.9. (가우스-요르단 소거법)

가우스-요르단 소거법은 행렬에 기본 행연산을 적용하여 RREF(기약행사다리꼴행렬) 행렬로 바꾸는 방법이다. 가우스-요르단 소거법은 다음의 과정을 따른다:

1. 가장 왼쪽에 있는 $0$이 아닌 성분이 하나라도 포함된 열에 대해서 $i$열이라고 하자. (필요하다면) $i$열의 첫번째 성분 $a$가 $0$이 아니게 되도록 행을 바꾼다.
2. 첫번째 행에 $a^{-1}$을 곱해 $i$열의 첫번째 성분이 $1$이 되게 한다.
3. $i$열의 $0$이 아닌 성분 $b$가 있는 각각의 행에 첫번째 행에 $-b$를 곱한 것을 더하여 그 성분을 $0$으로 만든다.
4. 첫번째 행을 제외한 모든 행의 모든 성분이 $0$이면 과정은 끝났다. 아니라면, 첫번째 행을 제외하고, 다른 행 중에서 선행성분이 가장 왼쪽에 있는 행을 (필요하다면)두번째 행과 바꾼다. 이 때의 열을 $j$열이라고 하고, 선행성분을 $c$라고 하자.
5. 두번째 행에 $c^{-1}$를 곱해서 $j$열의 두번째 행을 $1$로 만든다.
6. $j$열의 각각의 $0$이 아닌 성분 $d$가 있는 행에 add 두번째 행에 $-d$를 곱한 것을 더해서그 성분을 $0$으로 만든다.
7. 위 과정을 반복하여 모든 열과 행에 대해 적용하거나, 나머지 행을 0으로 만들어버린다. 그러면 이 결과로 나온 행렬은 RREF 행렬이다.

참고

• 행렬 $A$의 RREF 행렬에 대해 기본 행연산을 잘 수행하면 $A$를 얻을 수 있다.

• 모든 행렬에 가우스-요르단 소거법을 사용할 수 있으므로, 모든 행렬은 RREF 행렬이 존재한다.

• 행렬의 RREF 행렬은 유일하다. (증명은 복잡하니 생략한다.)
• 가우스-요르단 소거법의 몇몇 다른 정의에서는 과정이 다를 수 있지만, 그래도 여전히 행렬을 그것의 RREF로 바꿀 수 있다.
• 인터넷을 뒤져보면 쉽게 가우스-요르단 소거법이나 여타 기본 행연산에 관련된 계산을 하는 이런 사이트를 찾아볼 수 있을 것이다.

예시 (가우스-요르단 소거법)

$${\begin{aligned}{\begin{pmatrix}0&0&1\\3&3&2\\8&2&6\\\end{pmatrix}}&{\overset {\mathbf {r} _{1}\leftrightarrow \mathbf {r} _{2}}{\to }}{\begin{pmatrix}3&3&2\\0&0&1\\8&2&6\\\end{pmatrix}}&{\text{과 정 1}}\\&{\overset {{\frac {1}{3}}\mathbf {r} _{1}\to \mathbf {r} _{1}}{\to }}{\begin{pmatrix}1&1&2/3\\0&0&1\\8&2&6\\\end{pmatrix}}&{\text{과 정 2}}\\&{\overset {-8\mathbf {r} _{1}+\mathbf {r} _{3}\to \mathbf {r} _{3}}{\to }}{\begin{pmatrix}1&1&2/3\\0&0&1\\0&-6&2/3\\\end{pmatrix}}&{\text{과 정 3}}\\&{\overset {\mathbf {r} _{2}\leftrightarrow \mathbf {r} _{3}}{\to }}{\begin{pmatrix}1&1&2/3\\0&-6&2/3\\0&0&1\\\end{pmatrix}}&{\text{과 정 4}}\\&{\overset {-{\frac {1}{6}}\mathbf {r} _{2}\to \mathbf {r} _{2}}{\to }}{\begin{pmatrix}1&1&2/3\\0&1&-1/9\\0&0&1\\\end{pmatrix}}&{\text{과 정 5}}\\&{\overset {-\mathbf {r} _{2}+\mathbf {r} _{1}\to \mathbf {r} _{1}}{\to }}{\begin{pmatrix}1&0&7/9\\0&1&-1/9\\0&0&1\\\end{pmatrix}}&{\text{과 정 6}}\\&{\overset {{\frac {1}{9}}\mathbf {r} _{3}+\mathbf {r} _{2}\to \mathbf {r} _{2}}{\overset {-{\frac {7}{9}}\mathbf {r} _{3}+\mathbf {r} _{1}\to \mathbf {r} _{1}}{\to }}}{\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\\\end{pmatrix}}&{\text{과 정 7}}\end{aligned}}$$

성질 (선형 연립방정식의 해의 개수 결정)

$A\mathbf {x} =\mathbf {b}$를 $m$개의 선형 방정식과 $n$개의 미지수로 구성된 선형 연립방정식이라 하자. 그리고 $R$을 크기가 $m\times (n+1)$인 첨가행렬 $(A|\mathbf {b} )$의 RREF라고 하자. 그러면 다음을 따른다.

• $R$이 ${\color {green}(n+1)}$열에서 선행성분($=1$)을 가지고 있으면, 이 연립방정식은 모순적이다.
• $R$이 ${\color {green}(n+1)}$을 제외한 각각의 열에서 선행성분을 가지고 있으면, 이 연립방정식의 해는 유일하다.
• $R$이 ${\color {green}(n+1)}$열에서 선행성분을 가지고 있지 않고, 이 열을 제외한 각각의 열에 선행성분을 모두 가지고 있는 것이 아니라면, 이 연립방정식의 해는 무수히 많다.

참고

$R$은 위 세가지 중 반드시 하나만을 만족해야 하므로, 선형 연립방정식의 해는 반드시 0개이거나(존재하지 않거나), 1개 이거나(유일하거나) 무수히 많다.

예시

$3\times 4$의 RREF 첨가행렬로 표현된 선형 연립방정식 $${\begin{pmatrix}1&2&0&0\\0&0&1&0\\{\color {green}0}&{\color {green}0}&{\color {green}0}&{\color {green}1}\\\end{pmatrix}}$$ 는 4열에 선행성분을 가지고 있으므로 모순적이다.

$4\times 4$의 RREF 첨가행렬로 표현된 선형 연립방정식 $${\begin{pmatrix}{\color {green}1}&0&0&2\\0&{\color {green}1}&0&3\\0&0&{\color {green}1}&3\\0&0&0&0\\\end{pmatrix}}$$ 는 앞의 3개의 열은 선행성분을 갖지만, 4열은 그렇지 않으므로 유일한 해를 갖는다.

$3\times 4$의 RREF 첨가행렬로 표현된 선형 연립방정식 $${\begin{pmatrix}{\color {green}1}&3&0&2\\0&0&{\color {green}1}&3\\0&0&0&0\\\end{pmatrix}}$$ 는 앞의 3개의 열 중 선행성분이 존재하지 않은 열(2열)이 있고, 동시에 4열에도 선행성분이 존재하지 않으므로 무수히 많은 해를 가진다. 이 행렬을 선형 연립방정식으로 표현하면 $${\begin{cases}x+3y=2\\z=3\\\end{cases}}$$ 이다. $y$를 독립 미지수 $t$로 두어 $y=t$로 표현하면 $x=2-3t$이고 $z=3$이므로, $x$ 역시도 하나의 해로 결정할 수 없다.

참고

• 독립 미지수(혹은 자유변수)들은 선행성분이 없는 열에 대응되는 미지수들이다.
• 종속 미지수(혹은 기본변수)들은 선행성분이 있는 열에 대응되는 미지수들이다.

정의 2.10. (homogeneous한 선형 연립방정식)

선형 연립방정식의 꼴이 $A\mathbf {x} =\mathbf {0}$이면 homogeneous하다. Homogeneous한 연립방정식은 모든 방정식의 꼴이 미지수항$=0$이라 해를 가지기 때문에, 자명한 해의 정의에 의해 항상 일관적일 수 밖에 없다. 만약에 다른해가 존재한다면 그 해를 자명하지 않은 해라고 부른다.

참고

Homogeneous한 선형 연립방정식은 선형 연립방정식의 해의 개수의 결정에 대한 성질과 homogeneous한 선형 연립방정식들은 일관적이어야만 한다는 사실에 기반하여 homogeneous한 선형 연립방정식들은 해를 갖지 않는다는 가능성 자체를 배제할 수 있기에 단 하나의 유일한 해를 갖거나, 무수히 많은 해들을 가진다.

예시(homogeneous한 선형 연립방정식)

선형 연립방정식 $${\begin{cases}x+y+z&=0\\2x+8y+3z&=0\\2x+4y+6z&=0\\\end{cases}}$$ 은 homogeneous하고, 따라서 일관적이다.

게다가, 이 선형 연립방정식의 RREF 첨가행렬은 $${\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\\end{pmatrix}}$$ 이고, 우리는 이 선형 연립방정식의 유일한 해인 $(x,y,z)=(0,0,0)$를 볼 수 있고, 이것은 자명한 해다.

선형 연립방정식 $${\begin{cases}x+4y+5z&=0\\2x+3y+5z&=0\\x+2y+3z&=0\\\end{cases}}$$ 은 homogeneous하고, 따라서 일관적이다.

덧붙여, 이 선형 연립방정식의 RREF 첨가행렬은 $${\begin{pmatrix}1&0&1&0\\0&1&1&0\\0&0&0&0\\\end{pmatrix}}$$ 이고, 따라서 이 선형 연립방정식은 3열과 4열의 선행성분이 빠졌기 때문에 수 많은 해를 가진다. 우리는 $z$를 아무렇게나 둘 수 있다.

성질 (homogeneous한 선형 연립방정식이 비자명한 해를 가지는 충분조건)

$m$개의 선형 방정식과 $n$개의 미지수를 가지고 있는 homogeneous한 연립 방정식은 ${\color {green}m<n}$이면 반드시 비자명한 해를 가진다.

증명

$m$개의 선형 방정식과 $n$개의 미지수를 가지고 있는 homogeneous한 연립 방정식의 첨가행렬을 $A\mathbf {x} =\mathbf {0}$, $(A|\mathbf {0} )$이라 하고, 따라서 이 행렬의 RREF는 $(R|\mathbf {0} )$이라 하자.(여기서 $R$의 크기는 $m$개의 선형 방정식과 $n$개의 미지수를 가지고 있으므로 $m\times n$이다.)

$R$이 각각의 $n$개의 열에 대해서 선행성분을 가지고 있으면 $R$은 적어도 $n$행을 가지고 있을 것이다. 그러나 $R$은 $m<n$인 $m$개의 행만을 가지므로 모순이다. 따라서, homogeneous한 선형 연립방정식은 유일한 해를 가지지 않는다.

선형 연립방정식은 해가 없거나(homogeneous한 경우 불가능) 유일한 해가 있거나(이 경우에는 불가능) 무수히 많은 해가 있으므로, 이 homogeneous한 선형 연립방정식은 반드시 무수한 해를 가져야 한다. 즉, 비자명한 해를 가진다.

참고

• 이 성질은 homogeneous한 선형 연립방정식이 비자명한 해를 가진다면 선형 방정식 수가 미지수의 개수보다 딸린다는 주장을 하는 것이 아니다.(성질의 역(逆))

• 위의 예시(homogeneous한 선형 연립방정식)의 두번째에서 미지수의 개수와 선형 방정식의 개수가 같지만 선형 연립방정식은 여전히 비자명한 해를 갖는다.

예시

homogeneous한 선형 연립방정식 $${\begin{cases}x+y+z=0\\2x+5y+z=0\end{cases}}$$ 은 반드시 비자명한 해를 가진다.

더불어, 이 선형 연립방정식의 첨가행렬의 RREF는 $${\begin{pmatrix}1&0&{\frac {4}{3}}&0\\0&1&-{\frac {1}{3}}&0\end{pmatrix}}$$ 이다. 이제 $z$를 독립 미지수 $z=t$로 두면, 우리는 $x=-{\frac {4}{3}}t,y={\frac {1}{3}}t$를 얻는다.