굉장히 길고 중요한 챕터.
Eigenvalue에 대해 알아보고, 그 응용에 대해서 알아본다.
- Introduction to Eigenvalues
- Diagonalizing a Matrix
- Systems of Differential Equations
Introduction to Eigenvalues
임의의 Square matrix에 대한 특별한 숫자가 eigenvalue이고 특별한 벡터가 eigenvector이다.
이들을 파악하는 것은 A라는 시스템을 파악하는 데 있어 굉장히 중요하다.
Eigenvalue and Eigenvector
What is the eigenvalue and eigenvector
어떤 벡터 x는 Ax를 통해 다른 방향으로 변환이 되는데, Ax의 결과가 원래의 x와 평행한 벡터들을, eigenvector라고 한다.
A에 의해 변환 전과 변환 후가 평행한 벡터들을 고유벡터(eigenvector)라고 한다.
이 변환은 물론 Linear Transformation이며, 나중에 다루게 됨.
평행하다는 것을 통해 정의를 해보면 다음의 방정식으로 정의할 수 있다.
\(Ax=\lambda x\)
변환 후 크기는 다를 수 있지만, 방향은 같아야 한다.
Linear system A에 의해 변하지 않는 성분을 eigenvalues와 eigenvectors로 표현한 것이다.
일반적으로 n by n의 행렬은 n개의 고유벡터를 갖는다.
그러나 같은 고유값에 여러개의 고유벡터가 정의될 수 있다.
고유벡터의 크기는 주로 정규화를 해준다.
Eigenspace
고유값은 유일한데, 고유벡터는 무수히 많다.
\(Ax=(c\lambda)x\) wrong!
\(A(cx)=\lambda (cx)\) correct!
고유값이 유일하지 않음을 가정하고 eigenvector를 놔두고 eigenvalue에 상수배를 해주면 틀린 식이 된다.
하지만 eigenvector가 유일하지 않음을 가정하고 상수배를 해주고 eigenvalue가 유일함을 가정하면 맞는 식이 된다.
여기서 무수히 많은 eigenvector가 존재함을 알 수 있으며, 이 무수히 많은 eigenvector들이 형성하는 subspace를 바로 eigenspace라고 한다.
eigenvalues and eigenvectors in null space
eigenvalue들은 사실 양수, 음수, 0, 심지어 복소수가 될 수도 있다.
eigenvalue인 람다가 0인 경우는 무엇일까?
Ax=0이라는 뜻이고, 이 때의 eigenvector는 null space에 존재하는 것이다.
다시 말해 A가 singular matrix라는 뜻이다.
free variable이 존재하려면 full rank가 아닌 singular matrix이고, 일부 영벡터가 아닌 벡터들을 영벡터로 보낼 수 있다.
여기서 ‘일부’라는 벡터가 바로 고유벡터가 되는 것이다.
If A is singular and \(\lambda =0\)
\(Ax=\lambda x\):
\(Ax=0x\)
\(Ax=0\)
A가 singular matrix면 람다가 0일 때 eigenvector는 null space 그자체가 된다.
_이러한 경우에선 ‘고유’라는 것이 큰 의미를 못가지는것 같다. _
null space가 존재하는 행렬의 고유값과 고유벡터의 예를 들어보자.
Link
어떤 투영행렬에 대해서는, column space전체가 람다 1에 해당하는 eigenspace가 되는 것이다.
그리고 람다 0에 해당하는 eigenspace는 null space와 같다.
Eigenvalue and Eigenvector의 계산
How to get eigenvalues/eigenvectors?
eigenvector는 변환 전/후의 벡터가 동일한 subspace에 존재하는 벡터를 의미한다.
\[Ax=\lambda x\]이를 이용해 계산해보자.
\(Ax-\lambda x=0\)
\((A-\lambda I)x=0\)
A의 대각선 성분에 x를 하나씩 빼주면 되는 것인데, 이는 A 대각 원소들을 lambda만큼 shift한 행렬이 된다.
그 결과에 벡터 x를 곱하여 영벡터가 되는 것을 찾는것이다.
이렇게 보면 Ax=0의 꼴이며, null space에 대한 해를 찾는 과정이 된다.(물론 이 때 x가 영벡터인 것을 제외하고 생각해야 한다)
그리고 이는 Ax=0를 만족시키는 해를 찾는다는 것이고, 이 때 행렬 A의 null space를 찾는다는 것이다. null space가 존재하려면 singular matrix가 되어야 하고, 쉬프트시킨 행렬이 특이행렬이 되어야 한다는 것이다. 특이 행렬이 아니면 x가 영벡터일때만 이 식이 성립하기 때문이다.
그러면 singular matrix의 determinant가 0이라는 것을 이용할 수 있다.
\(det(A-\lambda I)=0\)
이를 이용하면 eigenvalue를 먼저 찾을 수 있게 된다.
eigenvalue를 찾고 나면 eigenvector를 찾는 것은 어렵지 않게 된다. 그동안 해왔던 null space를 찾는 과정과 같다. 가우스 소거를 이용하면 된다.
eigenvalues/eigenvectors calculation method
실제 계산은 링크로
Link
eigenvalue는 유일하지만 eigenvector는 무수히 많은 수가 존재할 수 있기 때문에 eigenspace라는 공간이 존재한다.
이는 고유벡터를 계산할 때 free variable에 어떤 값을 넣고 푸는지에 따라 달라진다.
n by n도 마찬가지로 풀 수 있다.
여러가지 행렬의 고유값과 고유 벡터
permutation matrix
이는 축을 기준으로 대칭적으로 변환하므로 고유값이 1 혹은 -1이 된다.
고유값이 1인 경우 y=x선상에 존재하고, -1인 경우 y=x에 직교하는 eigenvector를 가진다. 내적하면 0임을 확인할 수 있다.
some rules of eigenvalues
permutation matrix 고유값들의 합은 0이 되는데, 일반저적으로 고유값들의 합은 대각 원소들의 합, 즉 trace와 같아진다.
Sum of \(\lambda\)s = trace of A
Product of \(\lambda\)s = determinant of A
symmetric matrix
2차원에서의 고유값 방정식의 특이한 점.
Link
2차원에서 eigenspace는,
y=x,
y=-x
두개다.
이것이 scaling될 뿐
Relationship between diagonal components of a matrix and eigenvalues
Symmetric Matrix의 고유벡터는 permutation matrix의 고유 벡터와 같음을 알 수 있다.
두 행렬의 관계는, 대칭행렬은 기존의 치환행렬에 cI를 더한 것과 같다는 것이다.
cI를 더하는 것은 고유벡터에는 어떠한 영향도 주지 않는다. 그러나 고유값에는 바로 이 더한만큼의 차이가 난다.
그러므로 다음으로 정리된다.
if \(Ax=\lambda x\)
\(Ax+3x = \lambda x+3x\)
\((A+3I)x = (\lambda + 3)x\)
어떤 행렬의 대각원소에 어떤 값을 더하거나 뺴주면 고유값에만 영향을 미친다.
고유벡터는 영향받지 않는다.
Caution in eigenvalues/eigenvectors
행렬끼리의 덧셈, 곱셈은 선형성을 만족하지 않는다.
Rotation matrix
회전행렬은 orthogonal matrix의 대표적인 예이다.
다음을 예로 들어보자.
\[\begin{bmatrix} 0 & -1 \\ 1 & 0 \\ \end{bmatrix}\]여기에 고유값에 대한 규칙을 적용해보자.
trace Q: 0+0 = \(\lambda_1+\lambda_2 = 0\)
det Q: 0+1 = \(\lambda_1 \lambda_2 = 1\)
뭔가 앞뒤가 맞지 않는다.
합이 0인데 곱이 1인 식?
정답은 복소수 i와 -i이다.
회전행렬의 고유값은 켤레 복소수(complex conjugate number)이다.
치환행렬이 symmetric한것과는 달리, Q는 비대칭행렬이다.
대칭행렬에 가까우면 실수인 eigenvalue가 나온다.
비대칭행렬에 가까우면 복소수인 eigenvalue 나온다.
결국 고유값을 이용해 행렬이 대칭이냐 비대칭이냐를 판가를 수도 있다.
대칭행렬은
\(A^T=A\)
비대칭행렬은
\(A^T=-A\)
Rotation matrix(180 deg)
180도 회전행렬은 대칭행렬이다.
0도와 180도 회전행렬은 모든 벡터가 고유벡터가 된다.
Triangular matrix
삼각행렬은 계산상의 이점이 많았다. 여기도 마찬가지다.
고유값을 구하기가 매우 쉽다.
대각원소들 각각이 고유값 그자체다.
det(A-\(\lambda\)I)=0 구하면 나머지는 다 0이 되고 대각원소만 남는다.
Diagonalization and powers
Eigenvalue와 Eigenvector를 활용할 수 있는 하나의 방법이며, Eigendecomposition이라고도 불린다.
이는 어떤 반복적인 선형방정식을 풀 때 굉장히 유용하다.
Diagonalization
Diagonalizaing a matrix
n x n 크기의 행렬은 n개의 고유값과 고유벡터를 갖는다.
(복소수까지 고려를 하면?)
어떤 행렬 A의 n개의 고유값과 고유벡터를 찾은 뒤엔 아래의 식에 따라 대각화를 수행하면 된다.
\[S^{-1}AS=\Lambda\]A는 원래의 행렬을 의미하고, S는 A의 고유벡터들을 column vector형태로 차례로 끼워넣은 n x n크기의 고유벡터 행렬이다.
그리고 람다행렬(\(\Lambda\))은 대각행렬(diagonal matrix)이고, 각각의 대각 원소들은 고유값들로 차례로 채워져있다.
여기서 전제조건이 있는데, S가 역행렬을 가질 수 있어야 하고, 이는 S가 특이행렬(singular matrix)가 아니어야 함을 의미한다. 결국 A의 고유벡터들이 n개의 독립(independent) 벡터를 가져야 한다는 것이다.
먼저 A가 n개의 독립인 고유벡터를 가진다고 가정하자.
이 고유벡터들을 column vector형태로 차례로 붙여 S를 만들었다고 해보자.
이 때 A와 S를 곱하면 어떻게 될까?
S의 좌측에서 A를 곱한것과,
S의 우측에서 A의 고유값의 대각행렬을 곱한것은 같다.
결론은 다음과 같다.
\[AS=S\Lambda\]역행렬이 존재한다고 가정하였으니,
\(S^{-1}AS=\Lambda\)
이것이 임의의 정방행렬 A를 대각화하는 과정이다.
A는 역행렬을 가지며, n개의 독립인 고유벡터를 가져야 한다
이렇게 대각화된 행렬을 eigenvalue matrix라고 한다.
Factorization of a matrix
반대로 S를 우변으로 넘기면, A를 고유값과 고유벡터들의 행렬의 조합으로 인수분해(factorizaiton)할 수 있다.
\(AS=S\Lambda\)
\(A=S\Lambda S^{-1}\)
Useful attribute
\[Ax=\lambda x\] \[A^2x=\lambda Ax\] \[A^2x={\lambda}^2 x\]행렬식도 살펴보면
\[A=S\Lambda S^{-1}\] \[A^2=S{\Lambda}^2 S^{-1}\]결과적으로 A의 k번 거듭제곱은,
\[A^{k}=S{\Lambda}^k S^{-1}\]제곱에 대해서는 LU분해나 QR분해와는 달리 계산상의 어마어마한 효율을 보유하고있다.
또한 대각화하였을 때 각 고유값이 1보다 작다면, 이것을 계속 제곱하였을 때 수렴하게 되는 안정 행렬(stable matrix)이 된다.
Diagonalizable matrices
Which matrices are diagonalizable
대각화 가능한 행렬은?
대각화 가능한 행렬은 n개의 독립인 고유값과 고유벡터를 가지고 있어야 한다.
어떤 행렬A의 고유값이 전부 다른 값을 가진다면, A는 반드시 n개의 독립인 고유벡터를 가지며 대각화가 가능하다.
When A has repeated eigenvalues
그렇다고 반복되는 고유값을 가지면 무조건 n개의 독립벡터를 가질수 없는걸까?
반드시 그런것은 아니다.
A가 반복되는 고유값을 가진다면, A는 n개의 독립인 고유벡터를 가질 수도, 가지지 않을 수도 있다.
단위행렬은 반복되는 고유값을 가지지만, 2개의 독립인 고유벡터를 가진다.(사실은 Linear Comb를 통해 수 많은)
When A has repeated eigenvalues (negative case)
삼각행렬을 예로 들면 반복되는 고유값을 가지지만, n개의 독립인 고유벡터가 존재하지 않는다.
최대 n-1개의 고유벡터만 존재한다.
A가 어떤 반복되는 고유값을 가지는 경우엔 독립인 고유벡터를 가질 수도 있지만 그렇지 않을 수도 있다.
Systems of Differential Equations
Diagonalization and Difference Equation
Difference Equation
앞에서 배운 대각화를 이용하면 방정식(equation)을 손쉽게 풀 수 있다.
선형연립방정식이 아니라, 차분방정식, 혹은 계차방정식(Difference Equation)을 의미하는 것이다.
계차방정식은 시간이 지남에 따라 상태가 변하는 문제를 방정식으로 만들어 놓은 것이다. 그러나 시간을 연속적으로 보는 것이 아니라 이산적으로 끊어서 보는 것이다. 미분방정식(Differential Equation)은 시간을 끊지 않고 연속해서 보는 개념이다.
Difference Equation
\[a_{n+1}-a_n=a_{n-1}\]Differential Equation
\[\frac{dy}{dx}=y\]현실세계의 문제는 사실 미분방정식이다.
그러나 관찰하기 좋고 컴퓨터가 계산하기 좋은 것은 계차방정식이다.
하지만 계차방정식도 n과 n+1의 간격이 매우 짧으면 미분방정식에 가까워진다.
계차방정식을 선형대수로 푸는 것은 다음을 푸는 것과 같다.
Difference Equation
\[u_{k+1}=A u_k \text{ with initial value } u_0\]시간의 개념이 있다고 하면 초기값이 있는 것도 당연한 것이다.
만약 \(u_0\)로부터 시작해서 \(A\)를 100번 곱하면 어떻게 될까?
\[u_1=Au_0, u_2=A^2u_0,...\] \[u_k=A^k u_0\]위와 같이 될것이다.
이는 first order system이다.
한번에 한 계차씩만 올라가고(k와 k+1로), 미지수는 단일 숫자가 아닌 벡터로 이루어져 있기 때문이다.
Real solution of difference equation
그러나, 실제로 \(u_{100}\)을 정말로 찾으려면 어떻게 되나?
100번 연산을 하기는 힘들다. 그렇기 때문에 대각화를 이용하여 푸는 것이다.
여기서 정말로 푼다는 것은 k가 커질수록 미지수의 값이 얼마만큼 증가하고 감소하는지 그 증가폭을 알 수 있다는 것이다. 그냥 하나의 답이 아닌, 계차방정식이 갖는 Dynamics를 아는 것이 우리가 구하고자 하는 진정한 해답이고, 이를 대각화를 통해 구하는 것이다. 단순히 A만 거듭해서는 이러한 Dynamics를 알 수 없다.
이를 풀기 위해 먼저 초기값인 \(u_0\) 벡터를 eigenvector \(x\)들의 combination으로 표현한다.
\[u_0=c_1 x_1 + c_2 x_2 + \cdots + c_n x_n = Sc\]여기에 A를 곱하면 어떻게 되나?
\[A u_0 = c_1 {\lambda}_1 x_1 + c_2 {\lambda}_2 x_2 + \cdots + c_n {\lambda}_n x_n\]이를 100번 반복하면 어떻게 되나?
\[A^{100} u_0 = c_1 {\lambda}_1^{100} x_1 + c_2 {\lambda}_2^{100} x_2 + \cdots + c_n {\lambda}_n^{100} x_n \\\\ = \Lambda^{100} S c\]S는 \(x_k\) 벡터를 column vector로 넣은 행렬이다.
물론 이를 행하기 전에 A가 n개의 독립인 고유벡터를 가지고 있다는 전제가 있어야 한다. n개의 독립인 고유벡터는 n차원 공간인 \(R^n\)의 기저를 형성하기 때문이다.
Fibonacci number
계차방정식을 푸는 법을 배웠으니 이를 다른 예제에 활용해보자.
피보나치 수열은 다음과 같이 정리할 수 있다.
\[F_{k+2}=F_{k+1}+F_k\]이를 선형계차방정식으로 만들어보자.
그러나 문제가 있다.
어떤 시스템이 되기 위해선 식이 두 개 이상 존재해야 하고, 해도 벡터로써 존재해야 한다.
그리고 이 식은 1차가 아닌 2차미분방정식과 같다.
이를 풀기 위해선 트릭이 필요한데, 먼저 시스템의 이력값이 \(u_k\)벡터를 만들어야 한다.
1차 시스템이 되기 위해선 \(A\)에 \(u_k\)를 곱했을 때 \(u_{k+1}\)이 나오면 된다.
즉 \(u_{k+1}\)은 \(u_k\)의 원소들이 \(F_{k+1}\)과 \(F_k\)가 각각 한 단계씩 더 나아간 상태, 즉 \(F_{k+2}\)와 \(F_{k+1}\)이 될 것이다.
미지수(Unknown)
\[u_k=\begin{bmatrix} F_{k+1} \\ F_k \end{bmatrix}, u_{k+1}=\begin{bmatrix} F_{k+2} \\ F_{k+1} \end{bmatrix}\]시스템 방정식(System equation)
\[F_{k+2}=F_{k+1}+F_k\] \[F_{k+1}=F_{k+1}\] \[u_k = A u_k\] \[A=\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\]이 A에 대해 두 고유값을 구할 수 있을 것이고, 이를 통해 eigenvector를 찾을 수 있다. A는 symmetric matrix이다.
\[u_0=A^0 u_0=c_1 \lambda_1^0 x_1 + c_2 \lambda_2^0 x_2 \\\\ c_1 x_1 + c_2x_2 \\\\ S c = u_0 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}\]\(u_0\)을 eigenvector로 표현하고 c_1과 c_2를 구할 수 있다.
Differential Equation
What is differential equation?
미분방정식(differential equation)이란 방정식에 도함수, 즉 미분(derivative)이 포함된 것이다.