필립 클라인의 저서 코딩 더 매트릭스 7장 차원

여부분공간을 이해합니다.
선형함수의 가역조건을 차원 원리에 적용해 봅니다.
Kernel-Image 정리와 rank-nullity 정리를 이해합니다.
가역함수의 조건을 바탕으로 행렬의 가역조건을 이해합니다.
소멸자의 정의를 알고 $V^0 = Null\text{ }A$ , $(V^0)^0 = V$ 임을 이해합니다.
차원 관련 프로시저를 작성해 봅니다.

여부분공간 Complementary subspace

벡터공간 $W$ 와 부분공간 $U$ , $V$ 에 대해 $U \oplus V = W$ 이면 $U$ 와 $V$ 를 여부분공간이라 합니다. 예를 들어 다음 직선과 평면들은 $\Bbb{R}^3$ 의 여부분공간입니다.

두 그림은 같은 평면에 대해 여부분공간인 직선이 여러개임을 보여주기도 합니다.

임의의 벡터공간 $W$ 와 $W$ 의 임의의 부분공간 $U$ 에 대해 $W = U \oplus V$ 를 만족하는 $W$ 의 부분공간 $V$ 가 존재합니다. $\{u_1, ..., u_n\}$ 를 $U$ 의 기저라 하겠습니다. Superset basis에 의하면 $U$ 의 기저를 포함하는 $W$ 의 기저가 존재하므로 $W$ 의 기저를 $\{u_1, ..., u_n, v_1, ..., v_m\}$ 과 같이 쓸 수 있습니다. 이 때 $V = Span\text{ }\{v_1, ..., v_m\}$ 이라 하겠습니다. $W$ 내 임의의 벡터 $w$ 는 다음과 같이 나타낼 수 있습니다.

w = \underbrace{\alpha_1 u_1 + ... + \alpha_n u_n}_{\in U} + \underbrace{\beta_1 v_1 + ... + \beta_m v_m}_{\in V}

$U$ 와 $V$ 의 직합을 정의할 수 있다면 $w$ 는 $U \oplus V$ 의 임의의 벡터이고 이는 $W = U \oplus V$ 를 만족하는 $W$ 의 부분공간 $V$ 가 있음을 보여줍니다. 어떤 벡터 $v$ 가 $U$ 와 $V$ 에 모두 속한다고 할 때 $v$ 를 다음과 같이 쓸 수 있습니다.

v = \alpha_1 u_1 + ... + \alpha_n u_n = \beta_1 v_1 + ... + \beta_m v_m

위 식을 변형하면 다음이 성립합니다.

\alpha_1 u_1 + ... + \alpha_n u_n - (\beta_1 v_1 + ... + \beta_m v_m) = 0

$\{u_1, ..., u_n, v_1, ..., v_m\}$ 는 $W$ 의 기저이므로 일차독립입니다. 위 식은 자명한 선형결합에 대해서만 성립하므로 $v$ 는 영벡터이고 이는 $U$ 와 $V$ 가 영벡터만 공유함을 의미합니다. 따라서 $U \oplus V$ 를 정의할 수 있고 $U \oplus V = W$ 를 만족하는 부분공간 $V$ 가 존재합니다.

차원과 선형함수

선형함수 $f: V \to W$ 가 가역이기 위한 필요충분조건은 $f$ 가 전단사함수여야 한다는 것이었습니다. 단사함수이기 위한 필요충분조건은 $Ker\text{ }f$ 가 자명한 경우입니다. (참고) 전사함수일 필요충분조건은 $Im\text{ }f = W$ 인 경우입니다. 차원 원리를 식 $Im\text{ }f = W$ 에 적용하면 $dim\text{ }Im\text{ }f = dim\text{ }W$ 입니다. 따라서 $f$ 가 전사함수일 필요충분조건은 $dim\text{ }Im\text{ }f = dim\text{ }W$ 인 경우라 할 수 있습니다.

Kernel-Image 정리

이번 섹션에서는 아래 식을 도출하기 위해 긴 증명과정을 따라가 보겠습니다.

dim\text{ }V = dim\text{ }Im\text{ }f + dim\text{ }Ker\text{ }f

반드시 가역적이지는 않은 함수 $f: V \to W$ 가 있습니다.

함수 $f$ 를 바탕으로 가역적인 서브함수 $f^* : V^* \to W^*$ 를 정의해 보겠습니다. $f^*$ 가 전사함수가 되도록 $W^*$ 를 선택합니다. 선택한 원소들 $w_1, ..., w_r$ 은 $W^*$ 의 기저라 하겠습니다.

다음에 $v_1, ..., v_r$ 은 $w_1, ..., w_r$ 의 원상이라 하고 $f(v_1) = w_1, ..., f(v_r) = w_r$ 을 만족하는 $V$ 내의 임의의 벡터들 $v_1, ..., v_r$ 을 선택하겠습니다. 이제 $V^* = Span\text{ }\{v_1, ..., v_r\}$ 이라 하겠습니다.

함수 $f^* : V^* \to W^*$ 는 $f^*(x) = f(x)$ 라고 정의합니다. 선택한 서브함수 $f^*$ 는 전단사함수입니다. 따라서 $Im\text{ }f^* = W^*$ , $Ker\text{ }f^* = \{0\}$ 입니다.

함수 $f$ 에서 가역 서브함수 $f^*$ 를 구성하는 것은 서브함수의 정의역을 원래 선형함수 $f$ 의 커널에 연관시켜 다음 식을 이끌어 냅니다.

V = Ker\text{ }f \oplus V^*

위 식이 성립하기 위해서는 $Ker\text{ }f \oplus V^*$ 이 정의되어야 하고 $V$ 내의 모든 벡터가 $Ker\text{ }f \oplus V^* = \{u + v^*: u \in Ker\text{ }f, v^* \in V^* \}$ 의 원소 $u + v^*$ 로 표현될 수 있어야 합니다.

$V^*$ 의 원소 중 $f^*(x) = 0$ 을 만족하는 원소는 영벡터뿐이므로 $Ker\text{ }f$ 와 $V^*$ 는 영벡터만을 공유합니다. 따라서 $Ker\text{ }f \oplus V^*$ 를 정의할 수 있습니다. $V$ 내의 임의의 벡터 $v$ 에 대해 $f(v) = w$ 라 하면 $f^*$ 는 전사함수이므로 $f(v^*) = w$ 를 만족하는 $v^*$ 가 존재합니다. $f(v) = f(v^*)$ 이고 $f(v - v^*) = 0$ 으로 다시 쓸 수 있습니다. $u = v - v^*$ 라 하면 $f(u) = 0$ 이므로 $u \in Ker\text{ }f$ 입니다. $v = u + v^*$ 이므로 임의의 벡터 $v \in V$ 를 $Ker\text{ }f \oplus V^* = \{u + v^*: u \in Ker\text{ }f, v^* \in V^* \}$ 의 원소로서 표현할 수 있습니다. 따라서 $V = Ker\text{ }f \oplus V^*$ 가 성립합니다.

$V = Ker\text{ }f \oplus V^*$ 에서 $Ker\text{ }f$ 의 기저와 $V^*$ 의 기저의 합집합은 $Ker\text{ }f \oplus V^*$ 의 기저이므로 $dim\text{ }Ker\text{ }f + dim\text{ }V^* = dim\text{ }V$ 식이 성립합니다. 여기서 $dim\text{ }V^*$ 의 $V^*$ 는 $f^*(v^*) = w^*$ 의 원상이고 $f^*$ 는 전단사함수이므로 $dim\text{ }V^* = dim\text{ }W^* = dim\text{ }Im\text{ }f$ 입니다. 따라서 $dim\text{ }V = dim\text{ }Im\text{ }f + dim\text{ }Ker\text{ }f$ 라 할 수 있습니다. 이를 Kernel-Image 정리라 합니다.

Kernel-Image 정리를 도출하는 동안 이용했던 서브함수 $f^*$ 를 통해 가역적인 함수의 성질을 다시 한번 정리할 수 있습니다. 선형함수가 가역적이려면 $Ker\text{ }f = \{0\}$ , $dim\text{ }W = dim\text{ }Im\text{ }f$ 이어야 합니다. 가역함수 $f^*$ 는 $dim\text{ }Im\text{ }f = dim\text{ }W^* = dim\text{ }V^*$ 이었습니다. 따라서 선형함수 $f: V \to W$ 가 가역적이려면 $dim\text{ }W = dim\text{ }V$ 이고 $Ker\text{ }f = \{0\}$ 이어야 합니다.

rank-nullity 정리

선형함수는 행렬곱셈으로 표현할 수 있었습니다. 예를 들어 $R \times C$ 행렬 $A$ 에 대해 $f: F^C \to F^R$ 을 $f(x) = Ax$ 라 하면 $dim\text{ }F^C = dim\text{ }Ker\text{ }f + dim\text{ }Im\text{ }f$ 이므로 다음과 같이 바꿔 쓸 수 있습니다.

dim\text{ }F^C = dim\text{ }Null\text{ }A + dim\text{ }Col\text{ }A

위 식에서 $Ax$ 는 $A$ 의 열공간에 대한 선형결합이므로 $dim\text{ }Im\text{ }f = dim\text{ }Col\text{ }A$ 입니다. 행렬 $A$ 의 영공간의 차원 $dim\text{ }Null\text{ }A$ 를 $nullity\text{ }A$ 라 합니다. $A$ 의 열의 개수를 $n$ 이라 하면 다음을 얻습니다.

n = nullity\text{ }A + rank\text{ }A

행렬의 가역성

함수가 가역함수일 조건들을 행렬의 가역성에 대응할 수 있습니다. $f: F^C \to F^R$ , $R \times C$ 행렬 $A$ 에 대해 $f(x) = Ax$ 라 할 때,

단사함수일 조건 $Ker\text{ }f = \{0\} \to dim\text{ }Null\text{ }A = nullity\text{ }A = 0$
전사함수일 조건 $dim\text{ }F^C = dim\text{ }F^R \to |C| = |R|$

첫번째 조건 $dim\text{ }Null\text{ }A = 0$ 은 행렬의 열벡터들에 의한 선형결합이 0이 되는 경우는 자명한 선형결합 뿐임을 뜻하고 이는 열벡터들이 일차독립이어야 함을 뜻합니다.

가역행렬의 전치행렬은 가역행렬입니다. 가역행렬 $A$ 가 있다고 할 때 $A$ 는 정방행렬이고 열벡터들은 일차독립입니다. $A^T$ 의 열벡터들의 랭크는 $A$ 의 행랭크입니다. 행렬의 행랭크와 열랭크는 같고 $A$ 는 정방행렬이므로 $A$ 의 행들은 일차독립입니다. 따라서 $A^T$ 가 정방행렬이고 열벡터들이 일차독립이므로 가역행렬의 전치행렬은 가역적이라고 할 수 있습니다.

소멸자 Annihilator

벡터공간을 어떤 벡터들의 생성으로서 또는 동차선형시스템의 해집합으로서 표현할 수 있습니다. 예를 들어 평면 $\{[x,y,z]\in \Bbb{R}^3: [4,-1,1] \cdot [x,y,z] = 0\}$ 은 $Span\text{ }\{[1,2,-2], [0,1,1]\}$ 으로 표현할 수 있습니다. 아핀공간 역시 아핀hull 로서 또는 선형시스템의 해집합으로서 표현할 수 있습니다. 벡터공간 또는 아핀공간을 해집합 또는 생성으로서 표현하는 것은 이번 섹션인 소멸자와 연관됩니다.

$F^n$ 의 부분공간 $V$ 에 대해 $V$ 의 소멸자는 $V^0$ 로 표현되고 다음과 같습니다.

V^0 = \{u \in F^n : u \cdot v = 0, v \in V\}

평면을 해집합으로 표현한 $\{[x,y,z]\in \Bbb{R}^3: [4,-1,1] \cdot [x,y,z] = 0\}$ 의 해는 소멸자 $\{u \in \Bbb{R}^3 : u \cdot [4,-1,1] = 0\}$ 를 찾는 것과 같습니다.

한편 소멸자를 찾는 것은 영공간의 생성자를 찾는 것과 같습니다. $a_1, ..., a_m$ 은 $V$ 에 대한 생성자들이라 하고 행렬 $A$ 가 다음과 같다고 하겠습니다.

A = \begin{bmatrix} & a_1 & \\ \hline & ... & \\ \hline & a_m & \end{bmatrix}

$F^n$ 의 벡터 $v$ 가 $Null\text{ }A$ 에 있을 필요충분조건은 모든 벡터 $a \in Span\text{ }\{a_1, ..., a_m\}$ 에 대해 $a \cdot v = 0$ 인 경우입니다. $V$ 의 소멸자 $V^0$ 가 $\{v \in F^n: v \cdot a = 0, a \in Span\text{ }\{a_1, ..., a_m\}\}$ 이므로 $V^0 = Null\text{ }A$ 입니다.

Annihilator Dimension 정리

$V$ , $V^0$ 가 $F^n$ 의 부분공간일때 $dim\text{ }V + dim\text{ }V^0 = n$ 가 성립하고 이를 Annihilator Dimension 정리라 합니다. $A$ 가 행렬이고 행공간을 $V$ 라 하면 rank-nullity 정리에 의해 $rank\text{ }A + nullity\text{ }A = n$ 이 성립하고 $rank\text{ }A = dim\text{ }Row\text{ }A = dim\text{ }V$ , $nullity\text{ }A = dim\text{ }Null\text{ }A = dim\text{ }V^0$ 이므로 $dim\text{ }V + dim\text{ }V^0 = n$ 는 참입니다.

Annihilator 정리

어떤 알고리즘 X가 있습니다. X의 입력값으로 $V$ 의 생성자들이 주어지면 $V^0$ 의 생성자들이 출력됩니다. X에 $V^0$ 의 생성자들이 입력되면 $(V^0)^0$ 의 생성자들이 출력될 것입니다. 그렇다면 $(V^0)^0$ 는 무엇일까요?

$V$ 의 기저를 $a_1, ..., a_n$ , $V^0$ 의 기저를 $b_1, ..., b_m$ 이라 하겠습니다. $b_1 \cdot a_1 = 0, ..., b_m \cdot a_1 = 0$ 이 성립하고 $a_2, ..., a_n$ 에 대해 모두 식이 성립합니다. 따라서 $a_1, ..., a_n$ 은 $(V^0)^0$ 의 부분공간입니다. 한편 Annihilator Dimension 정리에 의해 $dim\text{ }V + dim\text{ }V^0 = n$ 이고 $dim\text{ }V^0 + dim\text{ }(V^0)^0 = n$ 입니다. 두 식을 연립하면 $dim\text{ }V = dim\text{ }(V^0)^0$ 를 얻습니다. 차원정리에 의해 $V = (V^0)^0$ 가 성립합니다.

차원 관련 프로시저

morphing 정리를 직접 구현한 프로시저 morph. solve 모듈은 소스파일에서 다운로드 받을 수 있습니다.

from solver import solve
from matutil import coldict2mat
from vecutil import list2vec

def is_superfluous(L, i):
    if len(L) == 1:
        return False
    M = coldict2mat(L[0:i] + L[i + 1:])
    u = solve(M, L[i])
    return (L[i] - M * u).is_almost_zero()

def is_independent(L):
    for i in range(len(L)):
        if is_superfluous(L, i):
            return False
    return True

def exchange(S, A, z):
    for i in range(len(S)):
        if not is_independent(A + [S[i]]):
            continue
        M = S[0:i] + [z] + S[i+1:]
        for v in S:
            if not is_superfluous([v] + M, 0):
                break
        else:
            return S[i]

def morph(S, B):
    res = []
    A = []
    for z in B:
        w = exchange(S, A, z)
        A.append(z)
        S.append(z)
        S = [ s for s in S if s != w ]
        res.append((z, w))
    return res

S = [ list2vec(v) for v in [ [2,4,0], [1,0,3], [0,4,4], [1,1,1] ] ]
B = [ list2vec(v) for v in [ [1,0,0], [0,1,0], [0,0,1] ] ]
for (z,w) in morph(S, B):
    print("injecting", z)
    print("ejecting", w)

>>>
injecting
 0 1 2
------
 1 0 0
ejecting
 0 1 2
------
 2 4 0

injecting
 0 1 2
------
 0 1 0
ejecting
 0 1 2
------
 1 0 3

injecting
 0 1 2
------
 0 0 1
ejecting
 0 1 2
------
 0 4 4

Morphing 정리는 교환정리를 기반으로 증명되므로 프로시저 exchange를 사용합니다.

랭크를 찾는 프로시저 my_rank

def subset_basis(T):
    subset = []
    for v in T:
        if not is_superfluous([v] + subset, 0):
            subset = [v] + subset
    return subset

def my_rank(L):
    return len(subset_basis(L))

assert my_rank([ list2vec(v) for v in [ [1,2,3], [4,5,6], [1.1,1.1,1.1] ] ]) == 2
assert my_rank([ list2vec(v) for v in [ [1,3,0,0], [2,0,5,1], [0,0,1,0], [0,0,7,-1] ] ]) == 4
assert my_rank([ list2vec(v) for v in [ [one,0,one,0], [0,one,0,0], [one,one,one,one], [0,0,0,one] ] ]) == 3

랭크는 기저의 크기이므로 프로시저 subset_basis로 기저벡터들을 찾은 뒤 갯수만 반환합니다.

프로시저 direct_sum_decompose. 입력 벡터 $w$ 를 두 벡터공간의 기저들의 선형결합으로 표현합니다. 이 때 $w = u + v, u \in U, v \in V$ 입니다.

def direct_sum_decompose(U_basis, V_basis, w):
    U_len = len(U_basis)
    V_len = len(V_basis)
    M = coldict2mat({ i: (U_basis + V_basis)[i] for i in range(U_len + V_len) })
    x = solve(M, w)
    u = sum([ x[i] * U_basis[i] for i in range(U_len)])
    v = sum([ x[j] * V_basis[i] for i, j in zip(range(V_len), range(U_len, U_len + V_len))])
    return (u, v)

U_basis = [ list2vec(v) for v in [ [2,1,0,0,6,0], [11,5,0,0,1,0], [3,1.5,0,0,7.5,0] ] ]
V_basis = [ list2vec(v) for v in [ [0,0,7,0,0,1], [0,0,15,0,0,2] ] ]

w = list2vec([ 2,5,0,0,1,0 ])
(u,v) = direct_sum_decompose(U_basis, V_basis, w)
print(u,v)

w = list2vec([ 0,0,3,0,0,-4 ])
(u,v) = direct_sum_decompose(U_basis, V_basis, w)
print(u,v)

w = list2vec([ 1,2,0,0,2,1 ])
(u,v) = direct_sum_decompose(U_basis, V_basis, w)
print(u,v)

w = list2vec([ -6,2,4,0,4,5 ])
(u,v) = direct_sum_decompose(U_basis, V_basis, w)
print(u,v)

>>>

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

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

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

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

행렬의 가역성을 이용한 프로시저 is_invertible

from matutil import mat2coldict, listlist2mat
from GF2 import one

def is_invertible(M):
    L = [ v for k, v in mat2coldict(M).items() ]
    if len(M.D[0]) != len(M.D[1]):
        return False
    return is_independent(L)

assert is_invertible(listlist2mat([ [1,2,3], [3,1,1] ])) == False
assert is_invertible(listlist2mat([ [1,0,1,0], [0,2,1,0], [0,0,3,1], [0,0,0,4] ])) == True
assert is_invertible(listlist2mat([ [1,0], [0,1], [2,1] ])) == False
assert is_invertible(listlist2mat([ [one,0,one], [0,one,one], [one,one,0] ])) == False
assert is_invertible(listlist2mat([ [one,one], [0,one] ])) == True

행렬의 가역성 조건에 맞춰 행렬이 정방행렬인지, 열벡터들이 일차독립인지 확인합니다.

GF(2) 상에서 역행렬을 찾는 프로시저 find_matrix_inverse

from GF2 import one
from solver import solve
from matutil import coldict2mat
from vec import Vec

def find_matrix_inverse(A):
    coldict = {}
    for r in A.D[0]:
        coldict[r] = solve(A, Vec(A.D[0], { r: one }))
    return coldict2mat(coldict)

A = listlist2mat([ [one,one,one,one], [one,one,one,0], [0,one,0,one], [0,0,one,0] ])
print(find_matrix_inverse(A) * A)

>>>
       0 1 2 3
     ---------
 0  |  1 0 0 0
 1  |  0 1 0 0
 2  |  0 0 1 0
 3  |  0 0 0 1

행렬-벡터 곱셈에 따라 $Ax_1 = [1,0,0,...,0]$ , $Ax_2 = [0,1,0,...,0]$ , ..., $Ax_n = [0,0,0,...,1]$ 를 만족하는 벡터 $x_1, ..., x_n$ 을 찾은 뒤 $x_1, ..., x_n$ 을 열벡터로 갖는 행렬을 반환합니다.

상삼각행렬의 역행렬을 찾는 프로시저 find_triangular_matrix_inverse

from vec import Vec
from vecutil import zero_vec
from matutil import mat2rowdict, coldict2mat, listlist2mat

def triangular_solve(rowlist, v):
    D = rowlist[0].D
    label_list = sorted(list(D))
    u = zero_vec(D)
    for i in reversed(range(len(rowlist))):
        c = label_list[i]
        row = rowlist[i]
        u[c] = (v[i] - row * u) / row[c]
    return u

def find_triangular_matrix_inverse(A):
    rowdict = mat2rowdict(A)
    rowlist = [ rowdict[k] for k in sorted(list(rowdict.keys())) ]
    inverse_coldict = {}
    for r in A.D[0]:
        inverse_coldict[r] = triangular_solve(rowlist, Vec(A.D[0], { r: 1 }))
    return coldict2mat(inverse_coldict)

A = listlist2mat([ [1,.5, .2, 4], [0, 1, .3, .9], [0, 0, 1, .1], [0, 0, 0, 1] ])
print(find_triangular_matrix_inverse(A))
print(find_triangular_matrix_inverse(A) * A)

>>>
       0    1     2     3
     --------------------
 0  |  1 -0.5 -0.05 -3.54
 1  |  0    1  -0.3 -0.87
 2  |  0    0     1  -0.1
 3  |  0    0     0     1


       0 1 2 3
     ---------
 0  |  1 0 0 0
 1  |  0 1 0 0
 2  |  0 0 1 0
 3  |  0 0 0 1

입력된 행렬이 상삼각행렬이라면 solve 모듈없이 역행렬을 찾을 수 있습니다. 후진대입법을 이용해 행렬-벡터 곱셈의 해를 찾고 그것들을 열벡터로 갖는 행렬을 반환합니다.

코딩 더 매트릭스 - 7장 차원 (2)

여부분공간, Kernel-Image 정리와 rank-nullity 정리

2018년 12월 27일