[선형대수] Row Reduction과 Echelon Forms

728x90

nonzero와 leading entry

Echelon form은 linear system을 편리하게 해결하는 Row Reduction 알고리즘을 수행하기 위해 알아야하는 구조입니다. Echelon form을 알기 위해서는 nonzero와 leading entry에 대하여 알아야합니다.

nonzero는 말 그대로 0이 아닌 것을 의미합니다. 즉 nonzero row는 0으로만 이루어지지 않은 행을 의미합니다. 즉 행의 원소중 하나이상은 0이 아닌 값을 지니고 있어야합니다. nonzero column은 열의 원소중 하나 이상은 0이 아닌 값을 지니고 있는 것을 의미합니다.

leading entry는 nonzero row에서 0이 아닌 수 중에서 가장 왼쪽에 있는 값을 의미합니다.

$$
\begin{bmatrix}
0 & 1 & 0 \\
0 & 0 & 2 \\
3 & 1 & 0 \end{bmatrix}
$$
즉 위와 같은 행렬에서 leading entry를 구한다면 1행에서는 1, 2행에서는 2, 3행에서는 3이 각각의 leading entry가 됩니다.

Echelon form

Echelon form은 특정한 규칙을 따르는 행렬을 의미합니다. Echelon form을 만족하기 위해서는 두가지 규칙을 만족하면 됩니다.

nonzero row가 항상 모두 0인 행렬의 위에 있어야합니다.
leading entry의 위치가 위에 행의 leading entry보다 오른쪽에 있어야합니다.

이 두 규칙을 읽었을 때 의미가 이해가 되지 않을 수 있습니다. Echelon form이 무엇인지 직접 살펴보며 이해하도록 하겠습니다.

$$
\begin{bmatrix}
1 & 0 & 0 & 5 \\
0 & 0 & 2 & 0\\
0 & 0 & 0 & 3 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
\end{bmatrix}
$$

이 예시의 행렬은 Echelon form입니다. 먼저 1행부터 3행까지는 nonzero row이며 4행과 5행은 nonzero row가 아닙니다. 따라서 첫번째 조건인 항상 모두 0인 행렬의 위에 있어야함을 만족합니다.
다음으로 1행의 leading entry는 1열에 2행의 leading entry는 3열에 그리고 3행의 leading entry는 4열에 존재합니다. 즉 따라서 두번째 제약조건인 leading entry의 위치가 위에 있는 행의 오른쪽에 위치하게 됩니다.
따라서 위 두 조건을 만족하기 때문에 Echelon form이라고 할 수 있습니다.

Reduced echelon form

Reduced echelon form은 echelon form에서 2가지 조건을 추가적으로 만족하는 행렬을 의미합니다.

leading entry값이 항상 1입니다.
leading entry를 포함한 열은 leading entry를 제외하면 모두 0이어야 합니다.

이 두가지 조건을 만족하는 행렬을 확인해보겠습니다.
$$
\begin{bmatrix}
1 & 5 & 0 & 0 \\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
\end{bmatrix}
$$

위 행렬의 leading entry의 값들을 보면 모두 1임을 확인할 수 있습니다.
그리고 leading entry를 가진 열을 확인하였을 때 leading entry를 제외하고 모두 값이 0임을 알 수 있습니다.

이 Reduced echelon form에서 Uniqueness of the Reduced Echelon Form라는 정리가 나오게 됩니다. 이 정리의 의미는 행렬은 Reduced echelon form이 유일하게 하나밖에 나올 수 없음을 의미합니다. 너무나 당연한 이야기라고 생각합니다. 위에서 예시로든 Reduced echelon form을 제외하고 동일한 다른 것을 찾는 것은 불가능합니다.

Row reduction 알고리즘

이제 linear system의 해를 구하는 방법인 Row reduction 알고리즘을 알아보겠습니다. 이를 이해하기 위해서는 pivot의 개념을 이해해야 합니다 pivot은 pivot column에서 가장 위에 있는 값을 의미합니다.

step1. 가장 왼쪽에 nonzero한 column을 찾기

$$
\begin{bmatrix}
0 & 5 & 2 & 4 \\
2 & 3 & 1 & 5\\
1 & 1 & 3 & 1 \\
\end{bmatrix}
$$
이렇게 주어진 경우 가장 왼쪽의 nonzero column을 찾아줍니다.
이 경우에는 1열이 가장 왼쪽의 nonzero column입니다.

step2. pivot이 nonzero가 되도록 interchange

$$
\begin{bmatrix}
0 & 5 & 2 & 4 \\
2 & 3 & 1 & 5\\
1 & 1 & 3 & 1 \\
\end{bmatrix}
\rightarrow
\begin{bmatrix}
1 & 1 & 3 & 1 \\
2 & 3 & 1 & 5\\
0 & 5 & 2 & 4 \\
\end{bmatrix}
$$
step1에서 구한 열의 pivot값이 nonzero가 되도록 수행해주어야 합니다.
1행의 값이 0이기 때문에 이를 3행과 변경하여 줍니다.

step3. row replacement를 수행

$$
\begin{bmatrix}
1 & 1 & 3 & 1 \\
2 & 3 & 1 & 5\\
0 & 5 & 2 & 4 \\
\end{bmatrix}
\rightarrow
\begin{bmatrix}
1 & 1 & 3 & 1 \\
0 & 1 & -5 & 3\\
0 & 5 & 2 & 4 \\
\end{bmatrix}
$$
맨 위에 있는 행렬을 활용하여 replacement를 수행합니다.
이 경우 1열에 있는 값을 2곱하여 2열에 빼주면 됩니다. 3열은 원래 0이기 때문에 그대로 두면 됩니다.

step4. pivot을 포함한 행을 제외하고 step1-3을 반복

$$
\begin{bmatrix}
1 & 1 & 3 & 1 \\
0 & 1 & -5 & 3\\
0 & 5 & 2 & 4 \\
\end{bmatrix}

\rightarrow

\begin{bmatrix}
1 & 1 & 3 & 1 \\
0 & 1 & -5 & 3\\
0 & 0 & 27 & -11 \\
\end{bmatrix}
$$
현재 pivot을 포함한 행은 1행이었으므로 이를 제외하고 2와 3열로 계산을 동일하게 계산을 수행합니다. step 1에 따라 2열이 가장 왼쪽에 nonzero column으로 선택됩니다. 그리고 pivot이 nonzero에 대한 조건을 만족하기 때문에 step2는 생략할 수 있습니다. step3를 해결하기 위해 2열에 5를 곱하여 3열을 빼주면 step4를 마무리할 수 있습니다.

최종 step1-4를 수행하여 얻은 행렬을 자세히 보면 Echelon form을 만족하는 것을 알 수 있습니다. 이렇게 Echelon form을 구하는 step1-4과정을 forward phase라고 부릅니다.

step5. Reduced echelon form 만들기

이제 step1-4로 구한 echelon form을 Reduced echelon form으로 변경하겠습니다. step1-4를 보면 항상 제일 왼쪽에서부터 시작하는 것을 알 수있습니다. 하지만 이 과정은 반대로 맨 오른쪽에서부터 시작합니다.
연산을 조금 쉽게 해결하기 위해 그동안 제작한 echelon form 대신 새로운 행렬을 생성하겠습니다.
$$
\begin{bmatrix}
1 & 1 & 4 & 4 & 4 \\
0 & 1 & 2 & 4 & 4\\
0 & 0 & 0 & 2  & 4\\
\end{bmatrix}
$$
우선 Reduce echelon form을 만들기 위해서는 leading entry의 열에는 leading entry이외 값은 모두 0으로 변경되어야 합니다. step5는 오른쪽에서 부터 진행되기 때문에 가장 오른쪽에 있는 leading entry값이 있는 곳부터 왼쪽으로 가며 조건을 만족시켜주면 됩니다.
$$
\begin{bmatrix}
1 & 1 & 4 & 4 & 4 \\
0 & 1 & 2 & 4 & 4\\
0 & 0 & 0 & 2  & 4\\
\end{bmatrix}

\rightarrow

\begin{bmatrix}
1 & 1 & 4 & 0 & -4\\
0 & 1 & 2 & 0 & -4\\
0 & 0 & 0 & 2  & 4\\
\end{bmatrix}

\rightarrow

\begin{bmatrix}
1 & 0 & 2 & 0 & 0\\
0 & 1 & 2 & 0 & -4\\
0 & 0 & 0 & 2  & 4\\
\end{bmatrix}
$$
가장 오른쪽에 있는 leading entry값이 3행의 2이므로 1열과 2열에 값을 0으로 바꾸어주기 위해서는 2를 곱하여 빼주어야 합니다. 그리고 다음 왼쪽에 있는 leading entry는 2열의 1이므로 1열에 그대로 빼주어 조건을 만족시켜 주었습니다.

이제 마지막으로 reduced echelon form을 만들기 위하여 각 leading entry가 1이 될 수 있도록 scaling해주면 됩니다.
$$
\begin{bmatrix}
1 & 0 & 2 & 0 & 0\\
0 & 1 & 2 & 0 & -4\\
0 & 0 & 0 & 2  & 4\\
\end{bmatrix}

\rightarrow

\begin{bmatrix}
1 & 0 & 2 & 0 & 0\\
0 & 1 & 2 & 0 & -4\\
0 & 0 & 0 & 1  & 2\\
\end{bmatrix}
$$
3행을 2로 나누어주면 최종적인 결과로 reduced echelon form을 생성할 수 있게 됩니다.

이렇게 step5에서 reduced echelon form을 생성하는 과정을 backward phase라고 부릅니다.

마지막 linear System 풀이

위 5가지 step을 통해 최종적으로 Reduced echelon form을 만들어주었다면 이제 최종 목적인 linear System을 해결해보겠습니다.
$$
\begin{bmatrix}
1 & 0 & 2 & 0 & 0\\
0 & 1 & 2 & 0 & -4\\
0 & 0 & 0 & 1 & 2\\
\end{bmatrix}
$$
위 Reduced echelon form을 수식으로 표현하면 아래와 같이 나타낼 수 있습니다.

$$
x_1 + 2x_3 = 0
$$
$$
x_2 + 2x_3 = -4
$$
$$
x_4 = 2
$$
이 값들은 $x_1,x_2,x_3$의 값에 따라 해가 달라질 수 있게 됩니다. 즉 $x_1$이 2인 경우에는 $x_3$는 -1이 되고 $x_2$는 -2가 됩니다. 이렇게 위 3개의 변수값이 달라질 때마다 다른 값을 가질 수 있으므로 이 linear System은 무수히 많은 해를 가진다고 할 수 있습니다.

이를 식으로 표현할 때 가장 큰 문제점은 $x_1,x_2,x_3$ 세개의 변수에 따라 다른 식으로 표현될 수 있다는 것입니다. 따라서 동일한 결과의 식이어도 사람마다 표현하는 방법이 다르게 되는 문제가 있습니다. 이러한 문제를 해결하기 위해 한가지 약속을 하였습니다.

일반해를 구할 때 free variable은 항상 leading entry가 아닌 값의 위치로 지정하는 것 입니다. 위 예에서는 $x_1,x_2$가 leading entry이므로 $x_3$만을 free variable로 지정하여 일반해로 표현하게 됩니다.

$$x_1 = -2x_3$$
$$x_2 = -4 - 2x_3$$
$$x_3 = free$$
$$x_4 = 2$$
이렇게 일반해를 표현하게 됩니다. 이와 같은 결과를 통해 우리는 Reduced echelon form에서 leading entry를 가지고 있지 않은 변수는 free variable이 되는 것을 알게 되었습니다.

Existence and Uniqueness Theorem

이 정리는 Row Reduction 알고리즘을 활용하여 만든 Reduced echelon form을 활용하여 단일해가 존재하는 경우에 대한 정리입니다.

모든 행의 pivot column값의 위치가 맨 오른쪽 bias의 값이 아니라면 해는 존재합니다.
free variable이 없을 때 해가 존재합니다.(모든 변수가 leading entry값을 가질 때)

위 정리를 통해 linear system이 어떤 해를 가지고 있는지 Row Reduction으로 구해진 Reduced echelon form의 값들로 유추할 수 있습니다.