The Function

Function Invertibility Theorem: A function f is invertible if and only if it is one-to-one and onto

The Field

In [6]: 1+3j + (10+20j)  
Out[6]: (11+23j)

In [7]: x = 1+3j

In [8]: (x-1)**2  
Out[8]: (-9+0j)

In [9]: x.real  
Out[9]: 1.0

In [10]: x.imag  
Out[10]: 3.0

In [11]: type(1+2j)  
Out[11]: complex  

Such a collection of "numbers" with +, -, *, / is called a field. Different fields are like different classes obeying the same interface

field C 는 complex numbers 다. 이걸 공부해야 하는 이유는

• C is similar enough to R to be familiar but different enough to illustrate the idea of a filed
• Complex numbers are intellectual ancestors of vectors
• In more advanced parts of linear algebra, complex numbers play an important role

Playing with C

complex numbers C 상에서는 한 축이 real number, 다른 축이 imagenary number (python 에선 j 로 표시) 다.

이 때 translation f = z + z0 를 arrow 처럼 볼 수 있다. z0 에서 시작해서 z + z0 를 향하는 화살표로

따라서 f1(z) = z + z1, f2(z) = z + z2 가 있을때 function composition (f1 * f2)(z) 는, adding arrow 처럼 생각할 수 있다.

http://resources.codingthematrix.com/ 여기서 준비물을 구하고 아래 코드를 실행해 보자.

In [1]: from plotting import plot

In [2]: L = [2+2j, 3+2j, 1.75+1j, 2+1j, 2.25+1j, 2.5+1j, 2.75+1j, 3+1j, 3.25+1j]

In [3]: plot(L)

In [4]: plot({z/2 for z in L})  

벡터와 비슷하게 스케일링은 양수를 곱하면 된다. arrow 를 뒤집고 싶으면 -1 을 곱하면 되고,

반시계방향으로 90도 rotation 을 원하면 f(z) = iz translation 을 사용하면 된다. x+yi 가 -y+xi 가 된다.

complex number 에서는 z 와 1 + 0i 의 각도를 argument 라 부르는데, 이를 구하기 위한 공식을 오일러가 만들어 두었다.

어느 real number θ 에 대해서, e^(θi) 가 단위 원 위의 argument θ 를 가진 점 z 가 된다.

따라서 θ = π 일때, e^(πi) = -1 이다.

In [1]: from plotting import plot  
In [2]: from math import e, pi  
In [3]: plot([e**(t*2*pi*1j/20) for t in range(20)])  

따라서 기존 z 값에 원하는 라디안 값 k 만큼 e^(ki) 를 곱해주면 exponentiation law 에 의해서, 그만큼 회전한다.

In [11]: plot([e**(pi*1j/4) * z for z in L])  

Playing with GF(2)

Galois Field 2 has just two elements 0 and 1

GF(2) 에서는 특이하게도 addition 이 XOR 과 같다. multiplication 나 usual algebraic laws (e.g multiplication distribution) 는 기존과 동일하다.

In [1]: from GF2 import one

In [2]: def encrypt(p, k): return p+k

In [3]: k = one

In [4]: p = one

In [5]: c = en  
%env       encrypt    enumerate

In [5]: c = encrypt(p, k)

In [6]: c  
Out[6]: 0  

더 자세히는, p 를 어떻게 선택하는지는 c 의 probability distribution 에 영향을 주지 않기때문에 Eve 가 c 를 관찰한다 할지라도 p 에 대해 정보를 얻을 수 없다.

왜 이 cryptosystem 이 perfect secrecy 를 만드는걸까?

p = 0 에 대해 k 를 받아 c 를 돌려주는 함수를 f0 이라 하면, f0 은 one-to-one, onto function 이다. 따라서 k 를 선택하는 확률이 균일하다면 c 의 확률도 uniformly distribution 이다. f1 도 마찬가지다.

이 아이디어가 one-time pad 라는 cryptosystem 의 근간이다.

If each bit is encrypted with its own one-bit key, the cryptosystem is unbreakable

GF(2) 를 network coding 에도 사용할 수 있다. 커스터머 c, d 에게 동시에 video streaming 을 하면 중간지점에서 병목이 발생할 수 있는데 b1 + b2 를 더해 나중에 c 와 d 에서 substraction 을 이용해 원래 비트를 구하면 된다.

Vector

quaternions (4원수) 에 관한 이야기부터 시작한다.

해밀턴은 복소수가 2차원 평면상의 점으로 표현될 수 있다는 사실로부터, 3차원 공간에서 점을 표현하는 같은 방법을 찾으려 하였다. 3차원 공간에서의 정점은 3개의 수로 이루어지며, 해밀턴은 그 3개의 수들을 어떻게 더하고 곱할 수 있는지에 관해 생각해왔다. 그러나 그는 두개의 정점간의 나누기를 어떻게 정의할지 알지 못했고, 난관에 부딪히고 말았다.

1843년 10월 16일, 해밀턴은 그의 아내와 더블린의 로열 운하(영어: Royal Canal, 아일랜드어: An Chanáil Ríoga)을 걷고 있었다. 브로엄 다리(Brougham Bridge, 현재는 브룸 다리 Broom Bridge)를 걷고 있을 때, 나누기에 관한 해답이 그의 뇌리를 스쳤다. 그는 3개의 요소(Triples)를 나누지는 못하지만, 4개의 요소(quadruples)를 나눌 수 있다는 걸 생각했다. 4개의 요소 중, 3요소를 이용해 3차원 공간의 정점을 표현 할 수 있다. 해밀턴은 3차원 공간상의 정점에 대한 그의 새로운 수체계를 표현할 수 있었다. 그는 이 수체계의 기본 규칙을 다리에 새겨놓았다.

i^2 = j^2 = k^2 = ijk = -1

해밀턴은 위의 기본적인 규칙을 적용한 4개의 요소를 "사원수"라고 명명했다. 그 후 그는 사원수를 연구하고 알리는데 그의 남은 여생을 바쳤다. 그는 "사원수론자"(Quaternionists)라는 학파를 창시하고, 몇권의 책을 출판하여 사원수를 전파시켰다. 그의 마지막 책 《사원수 원론》(Elements of Quaternions)는 800여 쪽으로 구성되어 있고, 해밀턴 사망 직후에 출판되었다.

해밀턴의 죽음 이후, 그의 제자인 피터 거스리 테이트는 사원수의 연구를 계속하였다. 당시 더블린에서는 사원수가 의무적인 시험의 하나였다. 현재는 공간 운동학, 맥스월 방정식 등의 벡터를 이용하여 설명하는 물리와 기하학의 논제들은 그 당시에는 모두 사원수를 이용하여 설명되었다. 또한 사원수에 관한 전문적인 연구학회인 사원수 학회(영어: The Quaternion Society)도 존재하였다.

1880년대 중반부터 조사이어 윌러드 기브스와 올리버 헤비사이드가 제안한 벡터 해석학이 사원수 표현을 대신하기 시작했다. 벡터는 사원수와 같은 현상을 설명하였기 때문에, 고전 사원수 연구에서 많은 아이디어와 용어 등을 빌려왔다. 그러나 벡터 해석이 보다 간결한 개념과 표기법을 가지고 있었기에 사원수는 수학과 물리에서 비주류가 되었다. 이는 해밀턴의 사원수가 이해하기 난해하고, 표기가 친숙하지 않았으며, 그의 저작물에 길고 불분명한 표현이 많았기 때문이다.

그러나 사원수는 20세기 말에 공간상에서의 회전에 관한 사원수의 유용성에 의해서 다시 주목받기 시작했다. 사원수를 이용한 회전의 표현은 행렬을 사용하는 표현에 비해 더욱 간결했고 계산이 빨랐다. 이런 이유로, 사원수는 컴퓨터 그래픽, 제어이론, 신호처리, 자세제어(attitue control), 물리학, 생물정보학, 분자동역학, 컴퓨터 시뮬레이션, 궤도역학(orbital mechanics)등에 사용되고 있다.

vector 를 정의역(domain) 에서 치역(image) 로 대응되는 일종의 function 이라 볼 수 있다. python 에서는 dictionary 로 쉽게 나타낼 수 있다.

vector 에서 0 이 많으면 sparse vector 라 부르고, k 개 만큼만 0 이 아닌 원소가 있으면 k-sparse 라 부른다. vector 의 몇번째 원소가 0이 아닌지를 나타내야되기 때문에 k-sparse vector 는 k proportional space 가 필요하다.

physical sensors 로 얻어지는 signal 은 대부분 sparse vector 가 아니기 때문에 공간을 아끼기 위해, signal 을 lossy compression 으로 압축해서 보내는 법을 강의 후반부에서 배울 것이다.

Addition, Multiplication

In [1]: from plotting import plot  
In [2]: v = [3, 2]  
In [3]: def scalar_vector_mult(alpha, v): return [alpha * x for x in v]  
In [4]: plot([scalar_vector_mult(i/10, v) for i in range(11)])  

arbitrary line segment 를 addition, multiplication 을 이용해 a[3, 2] + [0.5, 1] 처럼 표현할 수 있는데, 여기서 식을 좀 더 변형해 convex combination 을 만들 수 있다. 이걸 이용하면 u, v 의 비중이 얼마냐에 따라 output 이 어떻게 달라지는지를 쉽게 표현할 수 있다.

[0.5, 1] 부터 [3.5, 3] 까지 infinite line 을 표현하기 위해 affine combination 을 이용할 수 있다. 더 자세한 내용은 Wiki: line combination 을 참고하자

Dictionary-based Representation

앞서 언급했듯이 vector 는 domain D 로 부터 어떤 field 로 mapping 하는 function 이다. 파이썬에서는 이런 function 을 dictionary 로 표현할 수 있다.

class Vec:  
    def __init__(self, domain, function):
        self.D = domain
        self.f = function


def zero_vec(D):  
    return Vec(D, {d: 0 for d in D})


def setItem(v, d, val):  
    v.f[d] = val


def getItem(v, d):  
    return v.f[d] if d in v.f else 0


def list2vec(L):  
    return Vec(set(range(len(L))), {k:v for k, v in enumerate(L)})

# vec test
v = Vec({'A', 'B', 'C'}, {'A': 1})  
for d in v.D:  
    if d in v.f:
        print(v.F[d])

# zero_vec test
D = {'A', 'B', 'C'}  
v = zero_vec(D)  
for d in v.D:  
    print v.f[d]

# list2vec test
L = [1, 2, 3, 4]  
V = list2vec(L)

for d in V.D:  
    print(d)
    print(V.f[d])

Vectors over GF(2)

두명에게 나누어 v 를 전송하기 위해 uniform distribution 으로 vA 를 얻어 vB = v - vA 를 만든 뒤 각 한명씩에게 vA, vB 를 전송하는 것이다.

vA 는 랜덤 n-vector 고 vB 는 f(x) = v - x 의 output 인데, 이 함수의 input 이 랜덤하게 골라졌으므로 이것만으로는 어떤것도 얻을 수 없다.

RSA 가 이 테크닉을 사용한다고 한다.

• Split each password into two parts
• Store the two parts on two separate servers

Dot-Product

inner product (내적) 이라 부른다. scalar 값을 돌려주고 두 벡터가 이루는 각을 알 수 있다. 외적과 내적에 관한 자세한 내용은 프로그래밍에 미치다 - 외적, 내적 분해 를 참고하자.

내적은 linear equation 에 사용할 수 있다.

D = {"radio", "sensor", "CPU", "memory"}  
duration = {"radio": 0.1, "sensor": 0.5, "CPU": 1, "memory": 0.5} # second  
rate = {"radio": 500, "sensor": 20, "CPU": 1000, "memory": 200} # mA

duration * rate  

linear equation 과 관련해서 중요한 질문들을 던져보자.

• Is there an algorithm for solving a system of linear equations?
• How can we know whether there is only one solution
• What if our data are slightly inaccurate

이후의 강의들에서 위에서 던진 질문들을 해결할 것이다.

두 음성이 비슷한지 dot-product 로 비교할 수 있다. 매 부분마다 음성이 비슷한지 비교해야 하므로 연산이 느릴 수 있지만 Fast Fourier Transform 을 이용하면 계산을 빠르게 수행할 수 있다.

Dot-Product over GF(2)

몇번의 질문을 컴퓨터가 던지는것과 비슷하게 n-vector password x 에 대해 컴퓨터가 random n-vector a 를 보내고, 사람이 dot-product 값 a * x = b 를 보낸다.

eavesdropper 가 a1, ..., an b1, ..., bn 값을 도청한다면 패스워드를 알기 위해선 다음의 질문을 반드시 해결해야 한다

• How many solutions for that linear equation?
• How to compute them?

만약 Eve 가 01011 과 11110 을 관찰했다면 01011 + 11110 에 대해서는 그림에서 보듯이 해킹이 가능하다. 따라서 추가적으로 던져야 할 질문은

• If a vector satisfies the equations, then what other equations does the vector satisfy?

Triangular System

• If rowlist[i][i] is zero procedure will raise ZeroDivisionError
• If this never happens, solution found is the only solution to the system

위의 코드는 D = {0, 1, ..., n-1} domain 에 대해서만 작동하기 때문에 다른 도메인에서 돌아갈 수 있도록 코드를 수정하면

def trianuglar_solve(rowlist, domain, b):  
    x = zero_vec(set(label_list))

    for r in reversed(range(len(rowlist))):
        c = label_list[r]
        x[c] = (b[r] - x * rowlist[r]) / rowlist[r][c]

    return x

Refs

(1) Title image
(2) Coding the Matrix by Philip Klein
(3) Wiki: 4원수
(4) Math Wiki: 4원수
(5) Wiki: line combination
(6) 프로그래밍에 미치다 - 외적, 내적 분해