Applications of Eigenvalues and Eigenvectors

Eigenvalue/Eigenvector는 어디서나 보인다. 전자공학, 전산학은 물론, 과학, 공학, 사회, 경제 분야에서 널리 쓰인다 (참고, 구글).  

여러 버젼이 있지만 아인슈타인에게 어떤 미녀가 묻기를 "상대성이론에서 시간이 빨리 가기도 한다던데, 그게 예쁜 미녀와 얘기하면 시간이 빨리 가는 것과 비슷한 원리라고 하던데요"  아인슈타인이 말하길, "바로 그것입니다"

전공, 과학, 기술에서 어떤 것은 정말 필수 기본 교양이라 이것을 모르고 어떻게 그 분야를 한다고 할 수 있을까 하는 그런 지식이 있다.  Eigenvalue/Eigenvector가 그 중 하나다.  이의 숙달없이 인공지능을 말함은 한국말, 한글도 모르는 사람이 우리말로 시를 짓는다는 것과 같다.  그들이 얘기하는 수준은 앞의 미녀가 이해하는 상대성이론 수준이기에 그에 합당하게 대응해 주는 것이 우리의 도리.  

■ Dynamical Systems

Eigenvalues and eigenvectors provide the key to understanding evolution of a dynamical system described by an equation of the form x_k+1 = Ax_k.  The state vectors x_k's give information about the system as time (denoted by k, k=0, 1, 2, ... ) passes.  The matrix A is a linear/matrix transformation that maps/changes x_k to x_k+1. 

앞서 "행렬"섹션에서 우린 간단한 Markov Chain 예를 봄.  그 시스템의 evolution 식이 행렬방정식으로,

                    x_k+1 = Px_k

형태.  Markov Chain과 같이 이런 형태의 state transition equation을 갖는 시스템을 Discrete Linear Dynamical System이라 함.  이 때 square matrix A를 (state) transition matrix, 벡터 x_k 는 시간 k 때의  system의 state. 시스템이 discrete하다는 의미는 k=0, 1, 2, ...  이기 때문.  State는 initial state vector x₀ 에서 시작해 infinite하게 evolve할 수 있음. 집합 {x_0, x_1, x_{2, .....} 를 시스템의 trajectory라 함.}

_{■ Finding steady state of a simple Markov Chain}

_{앞에서의 Markov Chain 시스템은,}

       

Trajectory는 앞서 {[600, 400], [500, 500], [550, 450] , .... } 이었음 (벡터를 가로로 뉘임).  이 시스템의 steady state는 [400, 600] 이라 했음.  끝까지 해보지 않고 어떻게 알았나?

- 이 시스템은 2개의 state A, B를 갖는데 A의 팬, B의 팬이 어디 공기중으로 사라지지 않는 한 총 팬 수는 1000.  따라서 각 x_k (k=0,1,2, ... )의 벡터합은 1000. 

- steady state vector 값에 이르러서는 더 이상 state vector의 변화가 없음.  즉, x_k+1 = x_k.  이 때 x_k+1 = x_k = x 라 하면

x = Px  (P는 2 x 2 matrix, x는 R² 벡터)

- 위 식은 λ=1 시의 Eigenvalue/Eigenvector 식.  P가 eigenvalue 1을 실제 갖고 있나?

- transition matrix P의 charateristic equation

두개의 eigenvalue가 λ₁ = 1 ,  λ₂ = 0.5

P가 Markov Chain의 transition matrix(stochastic matrix)이면, P의 eigenvalue로 1이 존재.  P의 다른 eigenvalue λ는 |λ|<1

- λ₁ = 1 의 eigenvector:  we get  -0.3x₁ +  0.2x₂ = 0

Similarly,

a) 위의 결과를 직관적으로 적용하면,

x_k 는 A에 몇명인지, B에 몇명인지 k 시점의 분포를 나타냄.  앞에서 구한 eigenvector x 역시 같음.  팬의 수가 총 1000 이므로 두 state의 합이 1000이어야 함. 

일단 eigenvalue가 0.5일 때 eigenvector는 고려 대상 아님. B 팬의 수가 음수가 될 수 없고 어떤 방법으로도 팬의 총 수가 1000이 되게 할 수 없음.

따라서 eigenvalue=1 경우를 고려.  이 때 eigenvector는 [2  3]^T 의 multiple.  이제 이 eigenvector의 element의 합이 1000인  [2  3]^T 의 multiple만 구하면 됨.  scale 값을 200으로 하면 [400  600]^T 되어 1000이 됨.

b) General approach - Use of diagonalization

A little definition:

Define the algebraic multiplicity of an eigenvalue to be its multiplicity as a root of the characteristic equation (used this earlier).

Define the geometric multiplicity of an eigenvalue λ to be dim E_λ, the dimension of its corresponding eigenspace

Let A be an n x n matrix and let λ_1, λ_2, ....  λ_k  be distinct eigenvalues of A.  If Β_i is a basis for the eigenspace E_i, then the union of Β_i's, Β  =   Β₁ ∪ Β₂ ∪ … ∪ Β_k   (i.e., the total collection of basis vectors for all of the eigenspaces) is linearly independent.

The Diagonalization Theorem

Let A be an n x n matrix with λ_1, λ_2, ....  λ_k (where k ≤ n) distinct eigenvalues. The following statements are equivalent :

a) A is diagonalizable

b) The union Β of the bases of the eigenspaces of A (corresponding to distinct eigenvalues of A) contains n vectors.

c) algebraic multiplicity of each eigenvalue equals its geometric multiplicity

example) 

앞서 행렬 

A는 3개의 distinct eigenvalue를 갖지 않고, 2개의 eigenvalue 1, -2(algebraic multiplicity of 2) 만 갖고 있기에 곧바로 A의 diagonalizable 여부는 판단 곤란.  그러나, A의 eigenspace들 basis 들의 union이 3개의 벡터 [1, -1, 1], [-1, 1, 0], [-1, 0, 1] 이기에 위 theorem에 의해 A가 diagonal 함을 암.  또 각 eigenvalue의 algebraic multiplicity와 geometric multiplicity도 같음을 볼 수 있음

example) Markov chain에서 아래 식이 성립.

  

위 식에서 P^k 를 쉽게 구할 수 있으면 좋겠음.  (x_k를 iterative하게 구하지 않아도 되고 쉽게 steady state 짐작할 수 있음). 

Solution)

P가 두 개의 distinct eigenvalue 1과 0.5를 갖으므로 P는 diagonalizable.  (Diagonalize 를 할 때 'P' notation을 쓰기에 transition matrix P와 혼동 방지를 위해 transition matrix P를 A로 표기). 따라서 A^k 를 구하려 함.

Since A is diagonalizable there is a P such,

수많은 eigenvalue-eigenvector 쓰임새 중에 매우 작은 한 부문, 매우 초보적 Markov Chain, 하늘의 별같이 다양한 Linear Algebra 내용과 쓰임새에 대한 간략한 방문 마침.