코딩 더 매트릭스 - 5장 행렬 (1)

필립 클라인의 저서 코딩 더 매트릭스 5장 행렬

1. 행렬 인스턴스 Mat을 만들어 봅니다.
2. 행렬-벡터, 벡터-행렬의 곱셈을 선형결합의 관점에서 이해합니다.
3. 행렬-벡터 곱셈의 산술적 성질을 증명하고 영공간에 대해 알아봅니다.
4. 선형함수를 이해하고 선형결합과 행렬방정식을 선형함수로 표현합니다.

matutil 작성

class Mat:
    def __init__(self, labels, function):
        self.D = labels
        self.f = function

    def __getitem__(self, k):
        return self.f[k] if k in self.f else 0

    def __repr__(self):
        return 'Mat((%s,%s), %s)' % (self.D[0], self.D[1], self.f)

    def __str__(self):
        pad = 2
        row_labels = sorted(self.D[0])
        col_labels = sorted(self.D[1])
        max_len = max({ len(str(c)) for c in col_labels } | { len(str(self[k])) for k in self.f.keys() }) + pad
        max_row_label_len = max({ len(str(r)) for r in row_labels }) + pad
        col_line = ''.join([' ' * (max_row_label_len + 1)] + [ str(c).rjust(max_len) for c in col_labels ])
        dash_line = ''.join([' ' * (max_row_label_len + 1)] + [ '-' * max_len for i in range(len(col_labels)) ])
        value_lines = '\n'.join([
            ''.join([ str(r).ljust(max_row_label_len), '|' ] + [ str(self[r, c]).rjust(max_len) for c in col_labels ])
            for r in row_labels
        ])
        return '%s\n%s\n%s' % (col_line, dash_line, value_lines)

행렬 인스턴스를 만들기 위해 첫번째 인수 labels로서 두 개의 집합을 받습니다. labels[0]은 행 라벨, labels[1]은 열라벨 입니다. 두번째 인수 function은 행라벨과 열라벨의 조합을 값에 매핑하는 dict입니다. 3개의 행과 2개의 열을 갖는 행렬은 다음과 같이 만들 수 있습니다.

M = Mat(
	({1,2,3}, {1,2}),
	{ (1,1): 1, (1,2): 2, (2,1): 3, (2,2): 4, (3,1): 5, (3,2): 6 }
)
print(M)

      1  2
    ------
1  |  1  2
2  |  3  4
3  |  5  6

행렬 클래스를 뼈대 삼아 앞으로 필요한 연산이 있을 때마다 하나씩 추가해 보겠습니다.

열공간과 행공간

• 열공간: 열벡터들로 만들어지는 공간 $e.g. Span\{[1,3,5], [2,4,6]\}$
• 행공간: 행벡터들로 만들어지는 공간 $e.g. Span\{[1,2], [3,4], [5,6]\}$

행렬-벡터, 벡터-행렬 곱셈

행렬 $M$, $N$이 있고 곱셈이 가능하다고 할때 $MN$, 즉 그들의 곱셈을 구하는 가장 흔한 방법은 $MN$의 $(i, j)$값을 $M$의 행과 $N$의 열의 도트곱으로 나타내는 것입니다. 하지만 행렬과 행렬의 곱셈은 선형결합으로 표현할 수도 있습니다. 예를 들어 다음과 같은 행렬-벡터의 곱셈이 있습니다.

각각의 행렬의 열은 벡터의 엔트리들과 스칼라곱해 더해집니다. 위와 같은 선형결합을 간단하게 $\sum_{c\in C}v[c]$로 쓸 수 있습니다. 여기서 $C$는 행렬의 열들의 집합, $v$는 벡터입니다. 이제 class Mat에 행렬-벡터 곱셈을 추가해 보겠습니다.

class Mat:

	...

	def __mul__(self, other):
		if isinstance(other, Vec):
			return self.vec_mul(other)

	def vec_mul(self, vec):
        if self.D[1] != vec.D:
            raise Exception('Invalid multiplication')
        res = zero_vec(self.D[0])
        for (r, c) in self.f:
            res[r] += self.f[r, c] * vec[c]
        return res

행렬-벡터 곱셈을 정의하는 vec_mul프로시저는 행렬의 sparsity를 고려해 만들어집니다. sparsity를 고려하지 않고 모든 정의역에 대해 반복한다면 반복횟수가 늘어날 뿐만 아니라 결과 벡터인 res도 sparse해 집니다.

한편 벡터-행렬 곱셈은 행렬의 행과 벡터의 엔트리들의 선형결합입니다. 이전의 과자공장 예시를 살펴보겠습니다.

각각의 과자의 생산량과 과자 하나를 생산하는데 필요한 원료량을 선형결합하면 필요한 총 원료량을 알 수 있었습니다. 이것을 벡터-행렬 곱셈으로 표현하면 아래와 같습니다.

계산을 위해 벡터-행렬 곱셈을 코드로 옮겨보겠습니다.

class Mat:

	...

	def __rmul__(self, other):
		if isinstance(other, Vec):
			return self.vec_rmul(other)

	def vec_rmul(self, vec):
        if self.D[0] != vec.D:
            raise Exception('Invalid multiplication')
        res = zero_vec(self.D[1])
        for (r, c) in self.f:
            res[c] += self.f[r, c] * vec[r]
        return res

벡터-행렬 곱셈의 경우 이전에 만들었던 class Vec에 약간의 코드 수정이 필요합니다. Python은 두 객체의 곱셈연산인 *에 대해 연산자의 왼편에 있는 객체에 __mul__ 프로시저가 정의되어 있지 않은 경우 오른편에 있는 객체의 __rmul__프로시저를 실행합니다. class Vec의 경우 __mul__ 프로시저가 정의되어 있으므로 Python은 class Mat의 __rmul__ 프로시저 대신 class Vec의 __mul__을 실행합니다. 따라서 아래와 같은 코드 수정이 필요합니다.

class Vec:

	...

	def __mul__(self, other):
		from matutil import Mat

		if isinstance(other, Vec):
			return sum([ self[d] * other[d] for d in self.D ])

		# 곱셈 연사자 "*" 에 대해 오른편이 Mat 인스턴스라면 Mat의 __rmul__ 실행
		elif isinstance(other, Mat):
			return other.__rmul__(self)
		else:
			return Vec(self.D, { d: self[d] * other for d in self.D })

이제 벡터-행렬의 곱셈을 이용해 원료의 총 필요한 양을 구해 보겠습니다.

from matutil import Mat

def rowdict2mat(rowdict):
    row_labels = set(rowdict.keys())
    col_labels = rowdict[next(iter(row_labels))].D
    return Mat(
        (row_labels, col_labels),
        { (r, c): rowdict[r][c] for r, v in rowdict.items() for c in v.f }
    )

D = { '소금', '밀가루', '물', '식용유', '설탕' }
# 새우깽 생산 하나 당 필요 원료
v_s = Vec(D, {'밀가루': 1.3, '물': .2, '식용유': .8, '설탕': .4 })
# 바나나슛 생산 하나 당 필요 원료
v_b = Vec(D, {'물': 1.5, '식용유': .4, '설탕': .3 })
# 홈런밥 생산 하나 당 필요 원료
v_h = Vec(D, { '소금': .25, '식용유': .2, '설탕': .7 })
# 멋동산 생산 하나 당 필요 원료
v_m = Vec(D, {'물': .3, '식용유': .7, '설탕': .5 })
# 포커칩 생산 하나 당 필요 원료
v_p = Vec(D, { '소금': .15, '물': .5, '식용유': .4, '설탕': .8 })

M = rowdict2mat({
	'새우깽': v_s,
	'바나나슛' : v_b,
	'홈런밥' : v_h,
	'멋동산': v_m,
	'포커칩': v_p
})
amount = Vec(
	{'새우깽', '바나나슛', '홈런밥', '멋동산', '포커칩'},
	{
		'새우깽': 240,
		'바나나슛': 55,
		'홈런밥': 150,
		'멋동산': 133,
		'포커칩': 90
	}
)
print(amount * M)

    물    밀가루     설탕     소금    식용유
---------------------------------
215.4  312.0  356.0   51.0  373.1

행렬-벡터, 벡터-행렬 곱셈의 식은 $A * x = b$ 또는 $x * A = b$ 와 같이 씁니다. 선형대수학에서는 주어진 식의 해인 $x$를 찾는 것에 많은 관심을 가집니다. 과자 공장의 예시의 경우 과자 하나당 원료량을 나타내는 표를 행렬 $A$, 총 필요한 원료량의 벡터를 $b$, 과자의 생산량 벡터를 $x$로 나타낼 수 있습니다. $x$를 구하는 알고리즘은 차차 배우게 될 것입니다. 간단히 행렬 벡터 곱에 대한 해를 구할 수 있도록 numpy를 이용해 보겠습니다.

import numpy as np

M = np.matrix([
    [0, 1.3, .2, .8, .4],
    [0, 0, 1.5, .4, .3],
    [.25, 0, 0, .2, .7],
    [0, 0, .3, .7, .5],
    [.15, 0, .5, .4, .8]
])
u = np.array([51, 312, 215, 373, 356])
x = np.linalg.solve(M.T, u)
print(x)
[240. 54.60880196 149.74327628 132.90953545  90.42787286]

부동소수점 오차를 감안했을때 이전 코드에서 선언했던 변수 amount와 맞아 떨어집니다. 위 코드에서 한가지 눈여겨볼 것은 행렬 $M$을 전치시킨 M.T입니다. 구하고자 하는 해 $x$는 식 $x * A = b$의 해인데 이 식의 행과 열 개수를 표시하면

와 같습니다. numpy.linalg.solve 프로시저는 $A * x = b$와 같은 식의 형태에서 해를 구합니다. 따라서 $x$와 $A$의 위치를 바꿔줄 때 행렬 $A$를 전치시켜 다음과 같은 식으로 만들어 줍니다.

선형시스템을 행렬-벡터 방정식으로 구성

선형시스템을 다음과 같이 쓸 수 있었습니다.

행렬 $A$를 행들이 $a_1, a_2, ..., a_n$인 행렬이라 하고 벡터 $b$를 $[\beta_1, \beta_2, ..., \beta_n]$이라 하면 위의 선형시스템을 $A * x = b$로 바꿔 쓸 수 있습니다. 따라서 선형시스템의 해를 구하는 것은 행렬방정식의 해를 구하는 것과 같습니다.

행렬 벡터 곱셈의 산술적 성질

행렬 $A$와 벡터 $v$에 대해 다음의 성질을 만족합니다.

• $A * (\alpha v) = \alpha (A * v)$
• $A * (u + v) = A * u + A * v$

첫번째 성질을 증명해 보겠습니다. $A$의 행 각각을 행벡터 $a_1, a_2, ..., a_m$이라 하면 $A * (\alpha v)$는

따라서 $A * (\alpha v) = \alpha (A * v)$입니다.

두번째 성질은 벡터 도트곱의 분배성에 의해 참입니다. $A$의 한 행벡터 $a_1$에 대해 $a_1 \cdot (u + v) = a_1 \cdot u + a_1 \cdot v$를 만족하므로 모든 행벡터 $a_i$에 대해 만족합니다. 따라서 $A * (u + v) = A * u + A * v$입니다.

영공간 (Null space)

선형시스템 중 선형방정식의 우변이 모두 0인 경우를 동차 선형시스템이라 했습니다. 선형시스템을 행렬방정식 $A * x = b$으로 표현할 수 있으므로 동차 선형시스템은 행렬방정식 $A * x = 0$으로 표현할 수 있습니다. 여기서 행렬방정식을 만족하는 $x$의 집합 $\{x : A * x = 0\}$을 영공간이라 하고 Null A로 나타냅니다. Null A는 동차 선형시스템의 해집합이므로 벡터공간입니다.

벡터 $u_1$이 행렬-벡터 방정식 $A * x = b$의 해라고 할때 $u_2$ 또한 해가 될 필요충분조건은 $A(u_1 - u_2) = 0$, 즉 $u_1 - u_2$가 $A$의 영공간에 속할 때 입니다. 만약 $u_1 - u_2$가 자명한 해, 영벡터라면 $u_1 = u_2$이므로 행렬-벡터 방정식 $A * x = b$는 유일한 해를 갖습니다. 이는 선형시스템에서 유일한 해를 가질 필요충분조건이 대응하는 동차 선형시스템의 해가 자명한 해여야 한다는 것과 같습니다.

선형함수

필드 $F$상에 벡터 공간 $U$와 $V$가 있습니다. 함수 $f: U \to V$는 다음 두 성질을 만족할 때 선형함수라 합니다.

• $f$의 정의역 내 임의의 벡터 $u$와 $F$내 임의의 스칼라 $\alpha$에 대해

• $f$의 정의역 내 임의의 두 벡터 $u$와 $v$에 대해

선형함수의 위 두 성질은 행렬-벡터 곱셈의 산술적 성질과 같습니다. 따라서 임의의 행렬 $M$에 대해 함수 $x \to M * x$는 선형함수입니다. 몇가지 예를 통해 선형함수인 경우와 그렇지 않은 경우를 살펴보겠습니다.

1. 임의의 필드 $F$에 대해 $F^2$에서 $F$로의 함수 $f: (x,y) \to x + y$ (선형함수 O)
2. $f(\alpha x,\alpha y) = \alpha x + \alpha y = \alpha(x + y) = \alpha f(x, y)$
3. $x, y$ 쌍 $(x_1, y_1)$, $(x_2, y_2)$에 대해

2. 임의의 필드 $F$에 대해 $F^2$에서 $F$로의 함수 $f: (x,y) \to xy$ (선형함수 X)
3. $f(\alpha x,\alpha y) = \alpha^2 xy \neq \alpha xy = \alpha f(x,y)$
4. $x, y$ 쌍 $(x_1, y_1)$, $(x_2, y_2)$에 대해

3. 어떤 점을 1유닛 오른쪽으로, 2유닛 위쪽으로 평행이동하는 $\Bbb{R}^2$에서 $\Bbb{R}^2$로의 함수 $f: (x,y) \to (x + 1, y + 2)$ (선형함수 X)
4. $f(\alpha x,\alpha y) = (\alpha x + 1, \alpha y + 2) \neq (\alpha(x + 1), \alpha(y + 2)) = \alpha f(x,y)$
5. $x, y$ 쌍 $(x_1, y_1)$, $(x_2, y_2)$에 대해

행렬의 영공간과 마찬가지로 선형함수 $f$에 대해 $\{x: f(x) = 0\}$을 만족하는 집합을 $f$의 커널이라고 하고 $Ker\text{ }f$로 씁니다.

선형함수와 영벡터

선형함수 $f: U \to V$에 대해 $f$는 $U$의 영벡터를 $V$의 영벡터에 매핑합니다. 선형함수의 성질을 이용하면 간단히 증명할 수 있습니다.

입니다. 양변에서 $f(0)$을 빼면 $f(0) = 0$입니다.

선형결합과 선형함수

선형결합의 예로서 아핀결합은 다음과 같았습니다.

위 집합을 정의역으로 갖는 선형함수 $f$의 상은 아래와 같습니다.

아핀결합은 두 점 $u$, $v$를 지나는 직선이므로 선형함수 $f$의 상은 $f(u)$, $f(v)$를 지나는 직선입니다. 이것을 일반화하면, 선형결합을 선형함수에 의해 매핑한 상은 또 다른 선형결합입니다. 따라서 다음과 같이 쓸 수 있습니다.

또한 선형결합으로 만들어지는 기하 객체 flat의 선형함수에 대한 상 역시 또 다른 flat입니다.

단사함수인 선형함수

선형함수 $f$의 커널, $Ker\text{ }f$가 자명한 벡터공간이라면 $f$는 단사함수입니다. $f(u_1) = f(u_2)$을 만족하는 $u_1$, $u_2$가 있다면 $f$가 단사함수일때 $u_1 = u_2$여야 합니다. 커널을 이용해서 간단히 증명해 보겠습니다.

$f(u_1) = f(u_2)$라고 할때 선형함수의 성질을 이용해 다음과 같이 고쳐쓸 수 있습니다.

함수 $f$의 커널 $Ker\text{ }f$가 자명한 벡터공간이므로 $u_1 - u_2 = 0$, 따라서 $u_1 = u_2$입니다. 거꾸로 $f$가 단사함수일때 선형함수 $f$의 커널은 자명한 벡터공간입니다. $f(x) = 0$을 만족하는 벡터공간 $x$에 영벡터가 포함됩니다.($\because f(0) = 0$) 만약 $f(x) = 0$을 만족하는 다른 해가 있다면 단사함수가 아니게 됩니다. 따라서 $Ker\text{ }f = \{0\}$입니다.

행렬에 의해 표현될 수 있는 선형함수

앞서 임의의 행렬 $M$에 대해 함수 $f: x \to M * x$는 선형함수임을 봤습니다. 여기서 행렬 $M$의 엔트리들을 어떻게 알 수 있을까요? $M$의 열벡터가 $a_1, a_2, ..., a_n$일때 행렬-벡터곱을 이용해 열벡터 $a_i$를 구할 수 있습니다. 벡터 $v = [v_1, v_2, ..., v_n]$이 있을때 행렬-벡터곱은 선형결합 $v_1a_1 + v_2a_2 + ... + v_na_n$입니다. 여기서 벡터 $v$를 생성자 $[1,0,...,0]$이라 하면 $M * v = a_1$이고 이것은 행렬 $M$의 첫번째 열벡터입니다. 이것은 생성자 $e$와 함수 $f(x) = M * x$에 대해 $f(e_i) = a_i$임을 보여줍니다.

$f(x) = M * x$ 식을 만족하는 행렬 $M$이 존재하는지 어떻게 알 수 있을까요? $R \times C$ 행렬 $M$과 벡터 $x \in F^c$가 있습니다. 각 $c \in C$에 대해 $\alpha_c$는 $x$의 엔트리들이라 하면 $x = \sum_{c \in C}\alpha_c e_c$로 쓸 수 있습니다.(생성자들의 선형결합) $x$에 대한 함수 $f$의 상은 $f(x) = \sum_{c \in C}\alpha_c f(e_c)$입니다. $M * x$는 계수가 $x$의 엔트리들인 $M$의 열벡터들의 선형결합입니다. $M$의 한 열벡터는 $f(e_i)$이므로 $M * x$는 $\sum_{c \in C}\alpha_c f(e_c)$로 쓸 수 있습니다. 따라서 $f(x) = M * x$를 만족하는 행렬 $M$이 존재합니다.

대각행렬

위와 같이 정방행렬 $A$의 엔트리, $\{a_{ij} = 0 : i \neq j\}$이고 나머지 엔트리가 실수인 행렬을 대각행렬이라 합니다. 선형함수 $f: \Bbb{R}^n \to \Bbb{R}^n$, $f([x_1,x_2,..., x_n]) = [d_1x_1, d_2x_2, ..., d_nx_n]$는 대각행렬에 대응하는 함수입니다.

코드는 다음과 같이 작성할 수 있습니다.

def diag(D, entries):
	return Mat((D, D), { (d, d): entries[d] for d in D })

인수 entries는 정의역 D를 매핑하는 딕셔너리입니다.