Lecture 2. 행렬의 소거법 (Elimination with matrices)

다음은 Gilbert Strang의 선형대수학 MIT 강의를 듣고 정리한 글이다. 강의 링크

소거법 (Elimination)

소거법이란 연립 방정식을 풀 때, 행렬을 이용한 풀이 방법이다. 소거법의 단계는 다음과 같다.

$$
\begin{cases}
x + 2y + z = 2 \\
3x + 8y + z = 12 \\
4y +z = 2
\end{cases} \Leftrightarrow
\begin{bmatrix} 1 & 2 & 1 \\
3 & 8 & 1
\\ 0 & 4 & 1 \end{bmatrix}
\begin{bmatrix} x \\ y \\ z \end{bmatrix} =
\begin{bmatrix} 2 \\ 12 \\ 2 \end{bmatrix} \\
$$
이 때, 첫 행의 첫 값을 사용하여 다른 행의 x를 제거하게 되는데, 이를 피봇(Pivot) 이라고 한다. 피봇은 0이 되지 않아야 한다는 조건이 있다. (0이면 활용하여 변수를 제거할 수 없다.)

$$
\left[
\begin{array}{ccc|c}
1 & 2 & 1 & 2\\
3 & 8 & 1 & 12\\
0 & 4 & 1 & 2
\end{array}
\right] =
\left[
\begin{array}{ccc|c}
1 & 2 & 1 & 2\\
3 & 8 & 1 & 12\\
0 & 4 & 1 & 2
\end{array}
\right] (R_2 - R_1 * 3 \rightarrow R_2)
$$
위와 같이 벡터 b까지 덧붙인 행렬을 확장행렬(Augmented Matrix)라고 한다.
같은 방식으로 마지막 행 까지 진행하다보면,
$$
\left[
\begin{array}{ccc|c}
1 & 2 & 1 & 2\\
3 & 8 & 1 & 12\\
0 & 4 & 1 & 2
\end{array}
\right] ,\text{Pivot is }A_{11}(=1) =
\left[
\begin{array}{ccc|c}
1 & 2 & 1 & 2\\
0 & 2 & -2 & 6\\
0 & 4 & 1 & 2
\end{array}
\right] (R_2 - R_1 * 3 \rightarrow R_2) \\
\left[
\begin{array}{ccc|c}
1 & 2 & 1 & 2\\
0 & 2 & -2 & 6\\
0 & 4 & 1 & 2
\end{array}
\right],\text{Pivot is }A_{22}(=2) =
\left[
\begin{array}{ccc|c}
1 & 2 & 1 & 2\\
0 & 2 & -2 & 6\\
0 & 0 & 5 & -10
\end{array}
\right] (R_3 - R_1 * 2 \rightarrow R_3) \\
$$

이런 방법을 전진 소거법(Straightforward Elimination) 이라고 하고, 위와 같이 주대각성분 아래의 값이 0인 행렬을 상삼각행렬(Upper Triangular Matrix) 이라고 한다. 전진 소거법의 목적은 상삼각행렬 (이하 U로 표기)을 얻기 위함이라고 할 수 있다. 그런데 전진 소거법을 사용하면 실패를 겪는 경우가 생긴다. 실패는 크게 일시적인 실패와 완전히 실패하는 경우가 있을 수 있는데, 일시적인 실패는 피봇이 0이어서 해당 행을 활용해 변수를 제거할 수 없는 상황이다. 이때는 다른 0이 아닌 피봇을 가지는 행과 위치를 교환하여 간단하게 해결할 수 있다. 그러나 같은 방법을 반복해 (가능한) 마지막 까지 도달 했는데 완료되지 못하고 심지어 교환할 행까지 남아있지 않다면 이는 완전한 실패에 해당한다.

이제는 후진 대입법(Backward Substitution) 을 사용하여 변수의 값을 구할 수 있다.
$$
\left[
\begin{array}{ccc|c}
1 & 2 & 1 & 2\\
0 & 2 & -2 & 6\\
0 & 0 & 5 & -10
\end{array}
\right]=
\left[
\begin{array}{ccc|c}
1 & 2 & 1 & 2\\
0 & 2 & -2 & 6\\
0 & 0 & 1 & -2
\end{array}
\right]\\=
\left[
\begin{array}{ccc|c}
1 & 2 & 1 & 2\\
0 & 2 & 0 & 2\\
0 & 0 & 1 & -2
\end{array}
\right] =
\left[
\begin{array}{ccc|c}
1 & 2 & 1 & 2\\
0 & 1 & 0 & 1\\
0 & 0 & 1 & -2
\end{array}
\right]\\=
\left[
\begin{array}{ccc|c}
1 & 0 & 0 & 2\\
0 & 1 & 0 & 1\\
0 & 0 & 1 & -2
\end{array}
\right]\\
$$

이제 이 연산들을 행렬로 표현할 것이다. 그러기 위해서는 저번 강의에서 행렬과 벡터의 곱을 어떻게 바라보았는지 상기시킬 필요가 있다. 행렬과 벡터의 곱은 행렬을 열 벡터(Column Vector)로 나눈 것들의 선형결합과 같다고 하였다. (Matrix * Column = Column)
$$\begin{bmatrix}
a & b & c \\
d & e & f \\
g & h & i \end{bmatrix}
\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix} =
1*
\begin{bmatrix}
a \\ d \\ g
\end{bmatrix}
+2*
\begin{bmatrix}
b \\ e \\ h
\end{bmatrix}
+3*
\begin{bmatrix}
c \\ f \\ i
\end{bmatrix}$$
이 규칙은 행 벡터(Row Vector)에도 적용이 가능하고, 이는 즉 행들에 대한 선형 결합이라고 볼 수 있다. (Row * Matrix = Row)
$$
\begin{bmatrix} 1 & 2 & 3 \end{bmatrix}
\begin{bmatrix} a & b & c \\
d & e & f
\\ g & h & i \end{bmatrix} =
1\begin{bmatrix} a & b & c\end{bmatrix} + 2\begin{bmatrix} d &e & f \end{bmatrix} + 3\begin{bmatrix} g & h & i\end{bmatrix}
$$
위 아이디어를 사용하여 전진 소거법을 행렬로 표현해 볼 것이다.

먼저, 첫 번째 행은 변할 필요가 없다. 따라서 1번 행 한 개를 사용하고, 나머지는 사용하지 않는다.
$$
\begin{bmatrix} 1 & 0 & 0\\
? & ? & ?\\
? & ? & ? \end{bmatrix}
\begin{bmatrix} 1 & 2 & 1\\
3 & 8 & 1\\
0 & 4 & 1 \end{bmatrix} =
\begin{bmatrix} 1 & 2 & 1\\
0 & 2 & -2\\
0 & 4 & 1
\end{bmatrix}
$$

마찬가지로, 3번 행은 이미 3행 1열에 0이 들어가 있으므로, 1번 행을 사용하여 추가적인 연산을 할 필요가 없다. 따라서 그대로 유지하기 위해 3번 행 한 개와 나머지 0개를 조합한다.
$$
\begin{bmatrix} 1 & 0 & 0\\
? & ? & ?\\
0 & 0 & 1 \end{bmatrix}
\begin{bmatrix} 1 & 2 & 1\\
3 & 8 & 1\\
0 & 4 & 1 \end{bmatrix} =
\begin{bmatrix} 1 & 2 & 1\\
0 & 2 & -2\\
0 & 4 & 1
\end{bmatrix}
$$
2번 행은 변경을 해야만 하므로, 1번 행에 -3을 곱하고 2번행에 더해야만 한다.
$$
\begin{bmatrix} 1 & 0 & 0\\
-3 & 1 & 0\\
0 & 0 & 1 \end{bmatrix}
\begin{bmatrix} 1 & 2 & 1\\
3 & 8 & 1\\
0 & 4 & 1 \end{bmatrix} =
\begin{bmatrix} 1 & 2 & 1\\
0 & 2 & -2\\
0 & 4 & 1
\end{bmatrix}
$$
이런 식으로, 전진 소거법을 행렬의 곱으로 나타낼 수 있다. 좌측의 행렬을 소거행렬(Elimination Matrices) 또는 기본행렬(Elementary Matrices) 이라는 뜻으로 앞으로 E로 표기할 것이고, 2번 행 1번 열의 값을 고친다는 의미에서 E_21로 표기할 것이다.
마찬가지로, 2행을 사용해 3행을 소거하는 과정도 행렬로 나타낼 수 있다.
$$
\begin{bmatrix} 1 & 0 & 0\\
0 & 1 & 0\\
0 & -2 & 1 \end{bmatrix}
\begin{bmatrix} 1 & 2 & 1\\
0 & 2 & -2\\
0 & 4 & 1
\end{bmatrix} =
\begin{bmatrix} 1 & 2 & 1\\
0 & 2 & -2\\
0 & 0 & 5
\end{bmatrix} \\
E_{21} = \begin{bmatrix} 1 & 0 & 0\\
-3 & 1 & 0\\
0 & 0 & 1 \end{bmatrix} , E_{32} = \begin{bmatrix} 1 & 0 & 0\\
0 & 1 & 0\\
0 & -2 & 1 \end{bmatrix}
$$
전진 소거법을 행렬로 표현하니, 행렬 A에서 행렬 U로 가는 과정을 한 줄로 표현할 수 있다.

$$
E_{32}(E_{21}A) = U \\
\rightarrow (E_{32}E_{21})A = U \text{ (Associative Law)}
$$

추가적으로, 위 아이디어를 적용해 치환행렬(Permutation Matrix)과 역행렬(Inverse Matrix)도 쉽게 만들어 낼 수 있다.

치환행렬

$$
\begin{bmatrix} 0 & 1 \\
1 & 0
\end{bmatrix}
\begin{bmatrix} a & b \\
c & d
\end{bmatrix} =
\begin{bmatrix} c & d \\
a & b
\end{bmatrix} \\
\begin{bmatrix} a & b \\
c & d
\end{bmatrix}
\begin{bmatrix} 0 & 1 \\
1 & 0
\end{bmatrix} =
\begin{bmatrix} b & a \\
d & c
\end{bmatrix}
$$

역행렬

$$
E^{-1}E = I \\
\begin{bmatrix} ? & ? & ?\\
? & ? & ?\\
? & ? & ? \end{bmatrix}
\begin{bmatrix} 1 & 0 & 0\\
-3 & 1 & 0\\
0 & 0 & 1 \end{bmatrix} =
\begin{bmatrix} 1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1
\end{bmatrix} \\
\rightarrow
\begin{bmatrix} 1 & 0 & 0\\
? & ? & ?\\
0 & 0 & 1 \end{bmatrix}
\begin{bmatrix} 1 & 0 & 0\\
-3 & 1 & 0\\
0 & 0 & 1 \end{bmatrix} =
\begin{bmatrix} 1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1
\end{bmatrix} \\
\rightarrow
\begin{bmatrix} 1 & 0 & 0\\
3 & 1 & 0\\
0 & 0 & 1 \end{bmatrix}
\begin{bmatrix} 1 & 0 & 0\\
-3 & 1 & 0\\
0 & 0 & 1 \end{bmatrix} =
\begin{bmatrix} 1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1
\end{bmatrix} \\
$$