코딩 더 매트릭스 - 8장 가우스 소거법

필립 클라인의 저서 코딩 더 매트릭스 8장 가우스 소거법

1. 사다리꼴 행렬의 특징을 파악하고 기본행덧셈연산을 알아봅니다.
2. 기본행덧셈연산을 이용한 가우스 소거법을 알아봅니다.
3. 가우스 소거법을 이용한 문제 해결법을 알아봅니다.

사다리꼴 Echelon form

임의의 사다리꼴 행렬의 행에 대해 만약 그 행의 첫 번째 영이 아닌 엔트리가 위치 $k$에 있으면 그 행 이전의 모든 행의 첫 번째 영이 아닌 엔트리는 $k$보다 작은 어떤 위치에 있습니다. 직관적으로 다음과 같은 행렬을 사다리꼴 행렬이라 할 수 있습니다.

사다리꼴 행렬의 0이 아닌 행들은 행공간의 기저입니다. 행들이 행공간을 생성하므로 일차독립임을 증명하면 기저임을 증명할 수 있습니다. 증명을 위해 Grow 알고리즘을 이용합니다.

def Grow(V):
	S = 0 # 영공간
	repeat while possible:
		find a vector v in V that is not in Span S, and put it in S

사다리꼴 행렬의 행들을 역순으로 Grow 알고리즘의 반복문에 대입하면 행공간 $S$는 $v$를 포함하지 않습니다. 예를 들어 $S = Span \{[0,0,0,0,9]\}$ 는 $[0,0,0,0,1,2]$ 를 포함하지 않습니다. 모든 행들에 대해 성립하므로 사다리꼴 행렬의 행들은 일차독립입니다. 따라서 기저입니다.

무작위로 섞여 있는 행들을 사다리꼴 행렬의 행들의 순서에 맞게 재정렬하는 코드를 작성해 보겠습니다.

from vecutil import list2vec

rowlist = [
    list2vec([0,2,3,4,5]),
    list2vec([0,0,0,3,2]),
    list2vec([1,2,3,4,5]),
    list2vec([0,0,0,6,7]),
    list2vec([0,0,0,9,9])
]
new_rowlist = []
rows_left = set(range(len(rowlist)))
col_label_list = sorted(rowlist[0].D, key=hash)

for c in col_label_list:
    rows_with_non_zero = [ r for r in rows_left if rowlist[r][c] != 0 ]
    if rows_with_non_zero != []:
        pivot = rows_with_non_zero[0]
        new_rowlist.append(rowlist[pivot])
        rows_left.remove(pivot)

for r in new_rowlist:
    print(r)

>>>
 0 1 2 3 4
----------
 1 2 3 4 5

 0 1 2 3 4
----------
 0 2 3 4 5

 0 1 2 3 4
----------
 0 0 0 3 2

 0 1 2 3 4
----------
 0 0 0 6 7

하지만 재정렬된 행들은 세번째와 네번째 행이 같은 엔트리에서 0이 아닌 값을 가지므로 사다리꼴 행렬의 행들에 부합하지 않습니다.

기본행덧셈연산

위의 예가 사다리꼴 행렬에 부합하기 위해서는 네번째 행의 0이 아닌 가장 앞 엔트리가 0이 되어야 합니다. 이는 세번째 행에 -2배를 한 뒤 네번째 행을 더한 값을 네번째 행으로 바꾸면 가능합니다.

위와 같은 기본행 덧셈 연산을 코드에 반영해 보겠습니다.

for c in col_label_list:
    rows_with_non_zero = [ r for r in rows_left if rowlist[r][c] != 0 ]
    if rows_with_non_zero != []:
        pivot = rows_with_non_zero[0]
        new_rowlist.append(rowlist[pivot])
        rows_left.remove(pivot)

		for r in rows_with_non_zero[1:]:
			multiplier = rowlist[r][c] / rowlist[pivot][c]
			rowlist[r] -= multiplier * rowlist[pivot]

기본행덧셈연산은 기본행덧셈 행렬의 곱으로 나타내기도 합니다. 예를 들면 다음과 같습니다.

기본행덧셈 행렬 $\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & -2 & 1 \end{bmatrix}$ 은 세번째 행에 -2배한 값을 네번째 행에 더한다는 것을 의미합니다.

행공간을 유지하는 행덧셈연산

행렬 $A$와 $N$이 있을 때 $Row\text{ }NA \subset Row\text{ }A$입니다. 벡터-행렬 곱셈을 이용해 이를 증명할 수 있습니다. $v$가 행공간 $Row\text{ }NA$의 임의의 벡터라 할 때 다음과 같이 벡터 $u$를 이용해 벡터-행렬 곱셈의 선형결합으로서 표현할 수 있습니다.

즉 $v$는 $A$의 행들의 선형결합으로 표현될 수 있음을 보여줍니다.

행렬 $N$을 가역적인 행렬 $M$으로 바꾸어 보겠습니다. 이 때 $Row\text{ }MA = Row\text{ }A$ 가 성립합니다. 우선 이전에 행렬 $NA$에 대해 $Row\text{ }NA \subset Row\text{ }A$ 임을 보았습니다. 따라서 $Row\text{ }MA \subset Row\text{ }A$ 입니다. $B = MA$ 라 할 때 $M$의 역행렬 $M^{-1}$이 존재하므로 $Row\text{ }M^{-1}B \subset Row\text{ }B$ 가 성립합니다. $B = MA$ 이므로 $Row\text{ }M^{-1}B \subset Row\text{ }B$ 은 $Row\text{ }M^{-1}MA \subset Row\text{ }B$ 와 같습니다. 따라서 $Row\text{ }A \subset Row\text{ }MA$ 이고 $Row\text{ }MA = Row\text{ }A$ 입니다.

행덧셈 행렬에 위의 성질들을 적용해 보겠습니다.

위 식은 $Row\text{ }MA \subset Row\text{ }A$ 임을 보여줍니다.

행덧셈 행렬인 $M$ 은 역행렬이 존재하므로 다음 식도 쓸 수 있습니다.

위 식은 $Row\text{ }M^{-1}MA \subset Row\text{ }MA$ 임을 보여줍니다. 임의의 벡터 $v$ 는 $Row\text{ }A$와 $Row\text{ }MA$ 에 모두 속합니다. 따라서 행덧셈 연산은 행공간을 유지합니다.

가역행렬 M과 사다리꼴 행렬 MA

가우스 소거법으로 문제를 해결하는데 사용하는 핵심은 입력 행렬을 사다리꼴 행렬로 만드는데 사용되는 기본행 덧셈 연산을 추적하는 것입니다. 기본행 덧셈 연산은 행렬에 적용될 수 있는데 이것은 기본행 덧셈 행렬 $M$을 그 행렬과 곱함으로써 이루어 집니다. 예를 들어 행렬 $A$에 한번의 기본행 덧셈 행렬을 곱하면 $M_1A$, 두번째 기본행 덧셈 행렬을 곱하면 $M_2M_1A$가 됩니다. 기본행 덧셈 행렬의 곱의 총 개수를 $k$라 하면 다음과 같이 쓸 수 있습니다.

$M_k M_{k-1} ... M_2 M_1 = \bar{M}$ 라 하면 물론 $\bar{M}A$는 올바른 순서로 되어 있지 않아 사다리꼴이 아닙니다. $\bar{M}$을 다시 정렬했을 때 $MA$ 는 사다리꼴이 되는 그런 $M$을 얻을 수 있습니다. 여기서 알 수 있는 사실은 기본행 덧셈 행렬 $M_k$가 모두 가역적이므로 $\bar{M}$과 $\bar{M}$을 재정렬한 $M$도 모두 가역적이라는 것입니다.

예를 통해 행렬 $A$를 $MA$로 만드는 과정을 살펴 보겠습니다.

우선 단위행렬의 곱으로 $M$을 초기화 합니다.

두번째 행을 -2배 한 후 4번째 행과 더하는 기본행덧셈을 반영하면 다음과 같습니다.

같은 엔트리에 오직 하나의 0이 아닌 값을 가지도록 기본행 덧셈 행렬을 연속해 곱하보겠습니다.

이제 행렬 $M$을 찾는 과정을 코드에 추가해 보겠습니다.

from vec import Vec

rowlist = [
    list2vec([0,2,3,4,5]),
    list2vec([0,0,0,3,2]),
    list2vec([1,2,3,4,5]),
    list2vec([0,0,0,6,7]),
    list2vec([0,0,0,9,8])
]
new_rowlist = []
rows_left = set(range(len(rowlist)))
col_label_list = sorted(rowlist[0].D, key=hash)
row_labels = set(range(len(rowlist)))
M_rowlist = [ Vec(row_labels, { r: 1 }) for r in range(len(row_labels)) ]

for c in col_label_list:
    rows_with_non_zero = [ r for r in rows_left if rowlist[r][c] != 0 ]
    if rows_with_non_zero != []:
        pivot = rows_with_non_zero[0]
        new_rowlist.append(rowlist[pivot])
        rows_left.remove(pivot)

        for r in rows_with_non_zero[1:]:
            multiplier = rowlist[r][c] / rowlist[pivot][c]
            rowlist[r] -= multiplier * rowlist[pivot]
            M_rowlist[r] -= multiplier * M_rowlist[pivot]

위 코드의 M_rowlist는 아직 행들의 정렬을 고려하지 않습니다. $MA$가 사다리꼴 행렬이 되도록 변수 new_M_rowlist를 추가하고 다시 코드를 작성해 보겠습니다. new_rowlist가 rowlist 의 피봇인 행을 추가하는 타이밍에 new_M_rowlist는 같은 피봇 인덱스의 M_rowlist 행을 추가합니다.

new_M_rowlist = []

for c in col_label_list:
    rows_with_non_zero = [ r for r in rows_left if rowlist[r][c] != 0 ]
    if rows_with_non_zero != []:
        pivot = rows_with_non_zero[0]
        new_rowlist.append(rowlist[pivot])
        new_M_rowlist.append(M_rowlist[pivot])
        rows_left.remove(pivot)

        for r in rows_with_non_zero[1:]:
            multiplier = rowlist[r][c] / rowlist[pivot][c]
            rowlist[r] -= multiplier * rowlist[pivot]
            M_rowlist[r] -= multiplier * M_rowlist[pivot]

for r in rows_left:
    new_M_rowlist.append(M_rowlist[r])

가우스 소거법을 이용해 행렬-벡터 방정식 풀기

행렬 방정식 $Ax = b$가 있을 때 $x$를 가우스 소거법을 이용해 구할 수 있습니다. 만약 좌변을 사다리꼴 행렬과 $x$의 곱으로 변형시키면 후진대입법을 이용해 $x$를 구할 수 있을 것입니다. $A$를 사다리꼴 행렬로 만드는 행렬 $M$을 찾고 양변에 $M$을 곱해 보겠습니다.

$U$는 사다리꼴 행렬이므로 후진대입법을 이용해 $x$를 구할 수 있습니다. 이 때 $U$는 상삼각행렬이 아닌 사다리꼴이므로 다음에 주의해야 합니다.

• 엔트리가 모두 0인 행들에 대한 처리
• 관련없는 열들에 대한 처리

먼저 엔트리가 모두 0인 행을 $a_i$라 할 때 $a_ix = b_i$ 가 $b_i = 0$ 또는 $b_i \neq 0$인 경우로 나누어 해석할 수 있습니다. $a_ix = 0$인 경우 $x$값에 관계없이 항상 성립하므로 무시하면 됩니다. $a_ix \neq 0$인 경우 $x$값에 관계없이 항상 성립하지 않으므로 무시하면 됩니다.

관련없는 열들이란 다음과 같은 행렬에서 세번째와 마지막 열을 가리킵니다.

세번째와 마지막 열은 각 행의 첫번째 0인 아닌 엔트리가 아닙니다. 예시로 하나의 행렬 방정식을 보겠습니다.

세번째와 마지막 열을 제외해 다음과 같이 다시 쓸 수 있습니다.

위 식은 상삼각행렬과 벡터의 곱이므로 후진대입법을 이용해 $x_1$, $x_2$, $x_4$를 구할 수 있습니다. 세번째와 마지막 열에 대응하는 $x_3$, $x_5$는 0으로 둡니다.

가우스 소거법을 이용해 영공간에 대한 기저 찾기

행렬 $A$에 대해 벡터공간 $\{v : v * A = 0\}$의 기저를 찾는 과정을 살펴보겠습니다. 이 벡터공간은 $A^T$의 영공간이라 할 수 있습니다. 예를 들어 GF2 상의 행렬 $A$가 다음과 같습니다.

$A$를 상삼각행렬로 만드는 행렬 $M$은 다음과 같습니다.

$M$의 네번째와 마지막행은 $v * A = 0$을 만족합니다. $M$은 가역행렬이므로 두 행은 일차독립이고 $\{v: v * A = 0\}$ 이라는 벡터공간을 생성합니다. 따라서 $M$의 네번째와 마지막행은 $A$의 영공간의 기저입니다.

한편 행렬 방정식의 우변에서 0이 아닌 행들은 $Row\text{ }A$에 대한 기저입니다. $A$의 영공간에 대한 기저의 개수는 행렬 방정식의 우변의 엔트리가 모두 0인 행의 개수이고 $nullity\text{ }A^T$라 할 수 있습니다. 따라서 다음이 성립합니다.

$m$을 $A$의 행의 개수라 하면

가우스 소거법 관련 프로시저

• 사다리꼴 행렬인지 판별하는 프로시저 is_echelon

from vecutil import list2vec

def is_echelon(A):
    col_label_list = sorted(A[0].D)
    entry = col_label_list[0]
    for c in col_label_list:
        if A[0][c] != 0:
            entry = c
            break
    for row in A[1:]:
        for c in col_label_list:
            if row[c] != 0:
                if entry >= c:
                    return False
                entry = c
                break
    return True

A1 = [
    list2vec([2,1,0]),
    list2vec([0,-4,0]),
    list2vec([0,0,1]),
]
A2 = [
    list2vec([2,1,0]),
    list2vec([-4,0,0]),
    list2vec([0,0,1]),
]
A3 = [
    list2vec([2,1,0]),
    list2vec([0,3,0]),
    list2vec([1,0,1]),
]
A4 = [
    list2vec([1,1,1,1,1]),
    list2vec([0,2,0,1,3]),
    list2vec([0,0,0,5,3]),
]

assert is_echelon(A1) == True
assert is_echelon(A2) == False
assert is_echelon(A3) == False
assert is_echelon(A4) == True

is_echelon은 가장 처음 0이 아닌 값을 가지는 엔트리를 변수 entry에 담고 이후 행에서 entry보다 작은 엔트리에 0이 아닌 값이 나타나면 False를 반환합니다.

• 사다리꼴 행렬 $A$ 에 대한 식 $Ax = b$를 푸는 프로시저 echelon_solve

from vecutil import zero_vec, list2vec
from GF2 import one

def echelon_solve(rowlist, label_list, b):
    x = zero_vec(set(label_list))
    for i in reversed(range(len(rowlist))):
        not_zero = [ c for c in label_list if rowlist[i][c] != 0 ]
        if not_zero != []:
            entry = not_zero[0]
            x[entry] = (b[i] - rowlist[i] * x) / rowlist[i][entry]
    return x

rowlist = [
    list2vec([ one, one, 0, one, 0 ]),
    list2vec([ 0, one,0, one, one ]),
    list2vec([ 0, 0, one, 0, one ]),
    list2vec([ 0, 0, 0, 0, 0 ]),
]
b = list2vec([ one, 0, one, 0 ])
x = echelon_solve(rowlist, rowlist[0].D, b)
print(x)

>>>
 0 1 2 3 4
----------
 1 0 1 0 0

상삼각행렬 $A$가 있을 때 $Ax = b$를 만족하는 벡터 $x$를 후진대입법을 이용해 찾을 수 있었습니다. $A$가 사다리꼴 행렬인 경우 한가지 트릭만 적용하면 행렬 방정식을 풀 수 있습니다. 사다리꼴 행렬 $A$의 행 중 0이 아니지만 행의 가장 선행하지 않는 엔트리는 무시해도 됩니다. 따라서 행의 0이 아닌 가장 선행하는 엔트리만 찾아 후진대입법을 적용합니다. 이 과정은 다음 구문에서 구현됩니다.

...
entry = not_zero[0]
x[entry] = (b[i] - rowlist[i] * x) / rowlist[i][entry]
...