Lecture 2. 소거법과 행렬

지난 강의에서 연립방정식을 보는 두 가지 관점, Row picture와 Column picture를 살펴보았다. 해를 구할 때는 그림에서 읽거나 값을 대입해서 확인하였다. 미지수가 두세 개일 때는 그렇게 할 수 있지만, 개수가 많아지면 쓸 수 없는 방법이다.

이번 강의에서는 연립방정식을 기계적으로 푸는 방법인 소거법(Elimination)을 다룬다. 절차 자체는 중고등학교에서 배운 것과 같다. 한 식에서 다른 식의 몇 배를 빼서 미지수를 하나씩 지워 나가는 방법이다.

새로 볼 것은 두 가지이다. 하나는 소거의 각 단계를 하나의 행렬로 쓸 수 있다는 것이고, 다른 하나는 소거가 해를 바꾸지 않는다는 것이다. 앞의 것은 다음 강의의 역행렬과 그다음 강의의 LU 분해로 이어진다.

1. 소거법 (Elimination)¶

다음 시스템을 예로 삼는다. 이번 강의에서 계속 쓸 것이다.

행렬로 적으면 다음과 같다.

소거는 왼쪽 위에서 시작한다. 첫 번째 행의 첫 성분 1 이 첫 번째 피벗(pivot)이다. 이 피벗을 이용해 같은 열의 아래쪽 성분들을 0으로 만든다.

두 번째 행의 첫 성분은 3 이다. 두 번째 행에서 첫 번째 행의 3배를 빼면 0이 된다.

성분별로 계산해 보면 다음과 같다.

여기서 뺀 배수 3 은 어디서 나왔는가. 두 번째 행의 첫 성분 $a_{21} = 3$ 을 첫 번째 피벗 $a_{11} = 1$ 로 나눈 값이다. 일반적으로 $j$ 열을 정리할 때 $i$ 행에서 빼는 배수는

이고, 이 값을 곱수(multiplier)라 한다. 이렇게 정하면 그 자리가 정확히 0이 된다.

(6)에서 피벗 $a_{jj}$ 로 나누고 있다는 점에 주목하자. 피벗이 0이면 이 나눗셈이 불가능하다. 피벗이 0이 될 수 없다고 하는 이유가 이것이며, 3절에서 다시 다룬다.

세 번째 행의 첫 성분은 이미 0이므로 곱수가 $0/1 = 0$ 이고, 아무것도 바뀌지 않는다. 첫 번째 열이 정리되었다.

이제 두 번째 열로 넘어간다. 두 번째 행의 두 번째 성분 2 가 두 번째 피벗이다. 세 번째 행의 두 번째 성분이 4 이므로, 세 번째 행에서 두 번째 행의 2배를 빼면 0이 된다.

곱수는 $m_{32} = 4/2 = 2$ 이고, 계산하면 다음과 같다.

대각선 아래가 모두 0인 행렬을 위삼각행렬(upper triangular matrix)이라 하고 $U$ 로 적는다. 소거의 목표가 바로 이 형태이다.

이 예제의 피벗은 $1, 2, 5$ 이다. 피벗은 대각선 자리에 놓이며, 소거를 진행하는 기준이 된다.

2. 후진 대입 (Back substitution)¶

지금까지는 계수행렬만 다루었다. 실제로 방정식을 풀려면 우변 $\vv{b}$ 도 같은 연산을 받아야 한다. 그래서 보통 $A$ 와 $\vv{b}$ 를 붙여 놓고 함께 처리한다. 이렇게 붙인 것을 증강행렬(augmented matrix)이라 하고 $[A \mid \vv{b}]$ 로 적는다.

우변은 $(2, 12, 2)$ 에서 $(2, 6, -10)$ 으로 바뀌었다. 이것을 $\vv{c}$ 라 하면 원래 문제 $A\vv{x} = \vv{b}$ 가 $U\vv{x} = \vv{c}$ 로 바뀐 것이다. 방정식으로 다시 쓰면 다음과 같다.

이 형태는 아래에서 위로 올라가며 풀 수 있다. 마지막 식에서 $z = -2$ 가 바로 나온다. 이것을 둘째 식에 넣으면 $2y + 4 = 6$ 이므로 $y = 1$ 이다. 다시 첫째 식에 넣으면 $x + 2 - 2 = 2$ 이므로 $x = 2$ 이다.

이렇게 마지막 식부터 거꾸로 올라가며 푸는 것을 후진 대입(back substitution)이라 한다.

일반적으로 쓰면 다음과 같다. $U\vv{x} = \vv{c}$ 의 $i$ 번째 식은 $U$ 가 위삼각행렬이므로 $j < i$ 인 항이 모두 0이고, 남는 것은 다음과 같다.

아래에서부터 올라오면 $x_{i+1}, \dots, x_n$ 은 이미 구해져 있으므로, 모르는 것은 $x_i$ 하나뿐이다. $x_i$ 에 대해 정리하면

이다. $i = n$ 일 때는 합이 비어 있으므로 $x_n = c_n / u_{nn}$ 이 되고, 여기서부터 위로 올라가며 하나씩 확정된다. 이 식에서도 피벗 $u_{ii}$ 로 나누므로 피벗이 0이면 안 된다.

소거와 후진 대입은 한 세트이다. 소거로 위삼각 형태를 만들고, 후진 대입으로 해를 읽어낸다.

3. 피벗이 0이 되는 경우¶

피벗은 0이 될 수 없다. 아래 성분을 0으로 만들려면 피벗으로 나눈 배수를 써야 하는데, 0으로는 나눌 수 없기 때문이다.

그런데 소거를 진행하다 보면 피벗 자리에 0이 나오는 일이 생긴다. 두 가지 경우로 나뉜다.

첫째, 그 아래에 0이 아닌 성분이 있는 경우이다. 두 행의 순서를 바꾸면 0이 아닌 값이 피벗 자리로 올라오므로 소거를 계속할 수 있다. 방정식의 순서를 바꾸는 것뿐이므로 해는 달라지지 않는다. 이 행 교환을 행렬로 쓰는 방법은 6절에서 다룬다.

둘째, 그 아래도 전부 0인 경우이다. 행을 어떻게 바꿔도 0이 아닌 값을 가져올 수 없으므로 소거가 더 진행되지 않는다. 이때 피벗의 개수는 행의 개수보다 적다.

두 번째 경우의 행렬을 특이행렬(singular matrix)이라 한다. 지난 강의에서 세 열이 한 평면 안에 놓여 있어 $\vv{b}$ 에 따라 해가 없거나 무수히 많았던 그 행렬이다. 소거의 언어로 말하면 피벗이 모자란 행렬이고, 열의 언어로 말하면 공간을 다 채우지 못하는 행렬이다.

즉 소거가 끝까지 진행되어 피벗이 $n$ 개 나오는가 아닌가가, 그 행렬이 가역인가 아닌가와 같은 이야기이다.

4. 소거의 한 단계를 행렬로 쓰기¶

여기서부터가 이번 강의의 핵심이다.

(3)에서 한 일을 다시 보자. "두 번째 행에서 첫 번째 행의 3배를 뺀다"는 것은 하나의 동작이다. 이 동작 자체를 행렬 하나로 나타낼 수 있는가?

지난 강의에서 $A\vv{x}$ 가 $A$ 의 열들의 선형결합이라고 하였다. 행렬끼리의 곱에서도 비슷한 이야기를 할 수 있는데, 왼쪽에서 곱할 때는 행에 대한 이야기가 된다.

즉 $EA$ 의 각 행은 $A$ 의 행들의 선형결합이며, 그 계수가 $E$ 의 해당 행이다.

이 관점으로 보면 원하는 행렬을 바로 적을 수 있다. 결과의 1행은 $A$ 의 1행 그대로이므로 계수가 $(1, 0, 0)$ 이다. 2행은 (2행) $-$ 3(1행) 이므로 계수가 $(-3, 1, 0)$ 이다. 3행은 그대로이므로 $(0, 0, 1)$ 이다. 이것을 그대로 쌓으면 된다.

단위행렬(identity matrix) $I$ 에서 $(2,1)$ 자리만 -3 으로 바꾼 것이다. 아래첨자 21 은 $(2,1)$ 자리를 0으로 만드는 행렬이라는 뜻이다.

실제로 곱해 보자. (16)에 따라 $E_{21}$ 의 각 행이 $A$ 의 행들을 섞는 계수가 된다.

두 번째 행의 계산이 (4)의 계산과 완전히 같다. 나머지 두 행은 계수가 $(1,0,0)$ 과 $(0,0,1)$ 이라 원래 행이 그대로 남는다. 정리하면 다음과 같다.

5. 소거 전체를 하나의 행렬로¶

두 번째 단계도 같은 방식으로 쓸 수 있다. (3행)에서 (2행)의 2배를 빼는 것이므로 $(3,2)$ 자리를 -2 로 둔다.

두 단계를 차례로 적용하면 위삼각행렬이 나온다.

행렬 곱셈에는 결합법칙이 성립하므로 (다음 강의에서 다룬다) 괄호를 옮겨도 된다. 그렇다면 두 소거 행렬을 먼저 곱해 두면 하나의 행렬이 나온다. 계산해 보자. 이번에는 $E_{32}$ 의 각 행이 $E_{21}$ 의 행들을 섞는다.

이 행렬 하나로 소거가 끝나는지 확인해 보자. 세 번째 행만 계산해 보면 된다.

(10)의 세 번째 행과 같다. 앞의 두 행도 마찬가지로 확인되므로

이다. 소거의 전 과정이 행렬 하나에 담겼다. 이것이 이번 강의에서 얻는 가장 중요한 결과이다.

$E$ 의 세 번째 행이 $(6, -2, 1)$ 인 것이 조금 의외로 보일 수 있다. 두 단계 모두 3행에서 3 이나 2 를 뺀 적이 없는데 6 이 나왔기 때문이다. $E_{32}$ 가 2행을 끌어다 쓰는데, 그 2행은 이미 $E_{21}$ 이 1행을 섞어 놓은 결과이기 때문에 그렇다. 두 단계가 서로 간섭한 셈이다. 다음다음 강의에서 이 간섭이 사라지는 형태를 보게 된다.

6. 치환행렬 (Permutation matrix)¶

3절에서 미뤄 둔 행 교환도 행렬로 쓸 수 있다. 방법은 4절과 같다. 결과의 각 행이 $A$ 의 어느 행인지 계수로 적으면 된다.

1행과 2행을 바꾸려면 결과의 1행이 $A$ 의 2행, 2행이 $A$ 의 1행이어야 한다.

단위행렬의 행을 원하는 순서로 바꿔 놓은 것이다. 이런 행렬을 치환행렬(permutation matrix)이라 한다.

열을 바꾸고 싶다면 오른쪽에서 곱하면 된다. 앞 절의 규칙이 그대로 적용된다.

7. 소거를 기하적으로 보면¶

소거의 각 단계에서 방정식이 바뀌면, 그 방정식이 나타내는 평면도 바뀐다. 그런데 세 평면이 만나는 점은 바뀌지 않는다.

왜 그런지 확인해 보자. 소거의 한 단계는 $i$ 행에서 $j$ 행의 $m$ 배를 빼는 것이므로, 바뀐 식은 다음과 같다. $A$ 의 $i$ 번째 행을 $\vv{a}_i$ 로 적는다.

어떤 $\vv{x}$ 가 원래의 두 식 $\vv{a}_i \cdot \vv{x} = b_i$ 와 $\vv{a}_j \cdot \vv{x} = b_j$ 를 모두 만족한다고 하자. 내적은 분배법칙이 성립하므로

가 되어 (27)의 식을 만족한다. 즉 원래 시스템의 해는 모두 새 시스템의 해이다.

반대 방향도 성립한다. 소거한 결과에서 $j$ 행의 $m$ 배를 다시 더하면 원래 행이 돌아오기 때문이다.

$j$ 행은 소거 과정에서 바뀌지 않으므로 이 되돌리기가 언제나 가능하다. 위와 같은 계산을 그대로 적용하면 새 시스템의 해도 모두 원래 시스템의 해가 된다.

양쪽이 서로를 포함하므로 두 해집합은 같다. 소거는 되돌릴 수 있는 연산이고, 그래서 해집합을 바꾸지 않는다. 정리하면 소거란 해집합은 그대로 두고 더 풀기 쉬운 형태로 바꾸는 일이다.

마치며...¶

이번 강의에서 다룬 것을 정리하면 다음과 같다.

절차 자체는 익숙한 것이었지만 두 가지를 새로 보았다. 하나는 소거의 각 단계가 행렬 곱이라는 것이다. "2행에서 1행의 3배를 뺀다"는 동작이 $E_{21}$ 하나에 담겼고, 소거 전체는 그 행렬들의 곱 $E$ 가 되어 $EA = U$ 로 정리되었다. 다른 하나는 소거가 해를 바꾸지 않는다는 것이다. 평면은 기울어졌지만 교점은 제자리였다.

여기서 질문이 하나 생긴다. 소거의 각 단계가 행렬이고 그것들의 곱도 행렬이라면, 그 곱을 되돌리는 행렬도 있는가? 소거를 거꾸로 감는 행렬 말이다.

다음 강의에서는 지금까지 별다른 설명 없이 써 온 행렬 곱셈을 네 가지 관점에서 정리하고, 이어서 역행렬(Inverse matrix)에 대해 알아보도록 하자.

이번 강의의 내용을 파이썬으로 확인해 보려면 L2 실습 노트북으로 넘어가면 된다. 소거를 직접 구현해 보고, 위의 평면 그림을 단계별로 움직여 가며 교점이 정말 고정되어 있는지 확인할 수 있다.