[MIT 18.065] 1.6. Eigenvalues and Eigenvectors
카테고리: MIT 18.065
태그: Linear Algebra
💡 이 글은 MIT의 선형대수학 강의 MIT 18.065 Spring 2018 및 Gilbert Strang 교수님의 책 『Linear Algebra and Learning from Data』을 따라 정리했습니다. 강의 내용과 일부 연습문제 풀이를 포함합니다.
1. Introduction
1.2절에서, 1장 전체를 통해 5가지 중요한 분해(factorization)를 다룬다고 하였다.
- $A=LU$: Elimination
- $A=QR$: Orthogonalization (Gram-Schmidt)
- $S = Q \Lambda Q^T$: Eigenvalue, Eigenvector (Spectral Theorem)
- $A=X \Lambda X^{-1}$: Diagonalization
- $A=U \Sigma V^T$: Singular Value Decomposition (SVD)
여기서는 4번째 분해인 $A=X \Lambda X^{-1}$에 대해 다룬다.
2. Eigenvalues and Eigenvectors
Eigenvector $x$의 의미를 해석해보면 $A$를 곱해도 그 방향이 변하지 않는 벡터라고 할 수 있다. 단지 그 크기가 $\lambda$만큼 변할 뿐이다. 따라서 다음과 같이 생각할 수 있다. (단, 마지막 식은 $A$가 invertible한 경우에만 성립한다.)
\[Ax = \lambda x \quad A^k x = \lambda^k x \quad A^{-1} x = \frac{1}{\lambda} x\]대부분의 $n \times n$ 행렬 $A$에 대해, $n$개의 independent eigenvectors $x_1, x_2, \cdots, x_n$가 존재한다. 이들은 $n$개의 서로 다른 eigenvalues $\lambda_1, \lambda_2, \cdots, \lambda_n$에 대응된다. 그렇다면 모든 $v \in \mathbb{R}^n$에 대해 다음과 같이 쓸 수 있다.
\[\begin{aligned} v &= c_1 x_1 + c_2 x_2 + \cdots + c_n x_n \\ Av &= c_1 \lambda_1 x_1 + c_2 \lambda_2 x_2 + \cdots + c_n \lambda_n x_n \\ A^k v &= c_1 \lambda_1^k x_1 + c_2 \lambda_2^k x_2 + \cdots + c_n \lambda_n^k x_n \end{aligned}\]따라서 만약 $\vert \lambda_i \vert > 1$이면 $A^k v$는 $x_i$ 방향으로는 발산하고, $\vert \lambda_i \vert < 1$이면 수렴한다. 각 이는 eigenvector에 대해 독립적이다. 저자는 이를 “They look into the heart of a matrix”라고 표현한다.
Eigenvalues와 eigenvectors에 대해 주의해야 할 점이 몇 가지 있다. 아래의 마지막 문장은 1.5절의 Problem 6을 통해 어느 정도 알아보았다.
$A+B$의 eigenvalues는 $A$와 $B$의 eigenvalues의 합이 아니다.
$AB$의 eigenvalues는 $A$와 $B$의 eigenvalues의 곱이 아니다.
$\lambda_1 = \lambda_2$라면 각각의 eigenvector는 독립일 수도 있고, 그렇지 않을 수도 있다.
Real matrix $A$의 eigenvector가 서로 orthogonal한 것과 $A^T A = A A^T$는 동치이다.
한편 이러한 eigenvalues와 eigenvectors는 선형미분방정식(linear differential equations) $d \mathbf{u} / dt = A \mathbf{u}$를 풀 때 중요한 역할을 한다. 선형미분방정식의 해는 다음과 같다.
이때 $\text{Re } \lambda$에 따라 각 항이 수렴(decay)하거나 발산(grow)하고, $\text{Im } \lambda$에 따라 각 항이 진동(oscillate)한다.
3. Similar Matrices
Invertible matrix $B$를 이용해 $BAB^{-1}$을 만들 수 있고, 이 $BAB^{-1}$를 우리는 A와 similar하다고 한다. 즉, $BAB^{-1}$ 꼴로 나타낼 수 있는 모든 행렬은 A와 similar하다고 할 수 있다. 왜 “similar”라고 하는가? 여러 특성이 비슷하기 때문이다.
- Determinant: $\det(BAB^{-1}) = \det(A)$
- Invertibility: $BAB^{-1}$가 invertible하면 $A$도 invertible하다. 역도 성립한다.
- Rank: $\text{rank}(BAB^{-1}) = \text{rank}(A)$
- Nullity: $\text{nullity}(BAB^{-1}) = \text{nullity}(A)$
- Trace: $\text{tr}(BAB^{-1}) = \text{tr}(A)$
- Characteristic polynomial: $\det(A - \lambda I) = \det(BAB^{-1} - \lambda I)$
- Eigenvalues: $Ax = \lambda x \Leftrightarrow BAB^{-1}(Bx) = \lambda (Bx)$
- Eigenspace dimension: $\dim(\mathbf{N} (A - \lambda I)) = \dim(\mathbf{N} (BAB^{-1} - \lambda I))$
여기서 얻어야 할 아이디어는 eigenvalue를 계산하기 어려운 큰 matrix $A$로부터 조금씩 $BAB^{-1}$ 연산을 통해 eigenvalue를 계산하기 쉬운 triangular matrix로 변환하는 것이다. Triangular matrix의 eigenvalue는 diagonal element와 같기 때문이다. 예를 들어 아래 matrix의 eigenvalue $\lambda_1 = a$, $\lambda_2 = d$이다.
\[\begin{bmatrix} a & b \\ 0 & d \end{bmatrix}\]4. Diagonalization
4.1. $A = X \Lambda X^{-1}$ Factorization
$A$가 $n$개의 independent eigenvectors $x_1, x_2, \cdots, x_n$를 가지고 있다고 가정하자. 이때 다음과 같이 $AX = X \Lambda$로 나타낼 수 있다.
$X$는 independent eigenvectors로 이루어져 있으므로 invertible하고, 따라서 $A = X \Lambda X^{-1}$로 나타낼 수 있다. 이때 $\Lambda$는 diagonal eigenvalue matrix이다. 이러한 과정을 diagonalization이라고 한다. 따라서 다음도 성립한다.
\[A^k = (X \Lambda X^{-1})(X \Lambda X^{-1}) \cdots (X \Lambda X^{-1}) = X \Lambda^k X^{-1}\]4.2. Nondiagonalizable Matrices
그러나 모든 $A$에 대해 $A = X \Lambda X^{-1}$로 나타낼 수 있는 것은 아니다. 이러한 $A$를 non-diagonalizable하다고 한다. 여기서 GM(Geometric Multiplicity)와 AM(Algebraic Multiplicity)를 정의하자.
GM = $\dim(\mathbf{N} (A - \lambda I))$ = eigenvalue $\lambda$에 대한 independent eigenvectors의 개수
AM = $\det(A - \lambda I)$에서의 근 $\lambda$의 개수 = eigenvalue $\lambda$의 반복수
항상 $GM \leq AM$이다. 만약 모든 $\lambda$에 대하여 $GM = AM$이면 $A$는 diagonalizable하다. 그러나 적어도 하나의 $\lambda$에 대해 $GM < AM$이면 $A$는 non-diagonalizable하다. 따라서, $n \times n$ matrix $A$에 대하여 모든 eigenvalue가 다르다면 각각의 $\lambda$에 대해 $AM = 1$이다. 예를 들어 다음 행렬들은 모두 repeated eigenvalue $\lambda = 5$를 가지고 있고, $AM = 2$, $GM = 1$이다. 따라서 non-diagonalizable하다.
\[\begin{bmatrix} 5 & 1 \\ 0 & 5 \end{bmatrix}, \quad \begin{bmatrix} 6 & -1 \\ 1 & 4 \end{bmatrix}, \quad \begin{bmatrix} 7 & 2 \\ -2 & 3 \end{bmatrix}\]5. Selected Solutions to Problems
Problem 4.
Q. $B$가 invertible할 때 $AB$의 eigenvalues와 $BA$의 eigenvalues가 같음을 보여라.
$AB$와 $BA$가 similar하다는 것을 보이면 된다. 이때 $B$가 invertible하므로 다음과 같이 나타낼 수 있다.
\[B (AB) B^{-1} = BA\]따라서 $AB$와 $BA$는 similar하다. 따라서 $AB$와 $BA$의 eigenvalues는 같다.
Problem 6.
Q. Markov matrix $A$에 대하여 $A^\infty$를 구하라.
\[A = \begin{bmatrix} 0.6 & 0.2 \\ 0.4 & 0.8 \end{bmatrix}\]Markov matrix는 stochastic matrix로, 각 column의 합이 1인 matrix이다. $A$에 대하여 eigenvalue를 구하면 다음과 같다.
\[\begin{aligned} \det (A - \lambda I) &= 0 \\ \det \left( \begin{bmatrix} 0.6 - \lambda & 0.2 \\ 0.4 & 0.8 - \lambda \end{bmatrix} \right) &= 0 \\ (0.6 - \lambda)(0.8 - \lambda) - 0.08 &= 0 \\ \therefore \lambda_1 &= 1, \quad \lambda_2 = 0.4 \end{aligned}\]이를 대입하여 eigenvector를 구하면 다음과 같다.
\[x_1 = \begin{bmatrix} 1 \\ 2 \end{bmatrix}, \quad x_2 = \begin{bmatrix} 1 \\ -1 \end{bmatrix}\]따라서 $A = X \Lambda X^{-1}$로 나타내면 다음과 같이 된다.
\[\begin{aligned} A &= \begin{bmatrix} 1 & 1 \\ 2 & -1 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 0.4 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 2 & -1 \end{bmatrix}^{-1} \\ &= \frac{1}{3} \begin{bmatrix} 1 & 1 \\ 2 & -1 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 0.4 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 2 & -1 \end{bmatrix} \end{aligned}\]따라서 $A^\infty = X \Lambda^\infty X^{-1}$로 나타낼 수 있다.
\[\begin{aligned} A^\infty &= \frac{1}{3} \begin{bmatrix} 1 & 1 \\ 2 & -1 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 2 & -1 \end{bmatrix} \\ &= \begin{bmatrix} 1/3 & 1/3 \\ 2/3 & 2/3 \end{bmatrix} \end{aligned}\]Problem 7.
Q. $\det(A) = \lambda_1 \lambda_2 \cdots \lambda_n$임을 보여라.
Characteristic polynomial $f(\lambda)$를 다음과 같이 쓸 수 있다.
\[f(\lambda) = \det(A - \lambda I) = (-1)^n (\lambda - \lambda_1)(\lambda - \lambda_2) \cdots (\lambda - \lambda_n)\]여기에 $\lambda = 0$을 대입하면 결과를 얻을 수 있다.
\[f(0) = \det(A) = \lambda_1 \lambda_2 \cdots \lambda_n\]Problem 8.
Q. $2 \times 2$ matrix $A$에서 $\text{tr} (A) = \lambda_1 + \lambda_2$임을 보여라.
일반적인 $2 \times 2$ matrix $A$는 다음과 같이 나타낼 수 있다.
\[A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}\]이때 characteristic polynomial은 다음과 같다.
\[\det(A - \lambda I) = \lambda^2 - (a+d) \lambda + (ad - bc) = 0\]따라서 근과 계수의 관계에 의해 다음이 성립한다.
\[\lambda_1 + \lambda_2 = a + d = \text{tr} (A)\]이를 확장하여 다음과 같이 나타낼 수 있다.
Problem 17.
Q. $A$의 eigenvector로 이루어진 $X$의 column이 모두 linearly independent하다면, 다음이 참인지 거짓인지 판단하라.
(1) $A$는 invertible하다.
(2) $A$는 diagonalizable하다.
(3) $X$는 invertible하다.
(4) $X$는 diagonalizable하다.
(2), (3)은 참이다. 즉, 모두 동일한 문장이다. 하지만 (1)과 (4)는 거짓이다. 각각의 예시는 다음과 같다.
\[A = \begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix}, \quad X = \begin{bmatrix} 5 & 1 \\ 0 & 5 \end{bmatrix}\]위 예시의 $A$는 invertible하지 않지만 diagonalizable하다. 반면 $X$는 invertible하지만 diagonalizable하지 않다. 따라서 다음과 같이 정리할 수 있다.
Problem 19.
Q. $A$의 eigenvalue가 2, 2, 5일 때, 다음이 참인지 거짓인지 판단하라.
(1) $A$는 invertible하다.
(2) $A$는 diagonalizable하다.
(3) $A$는 non-diagonalizable하다.
(1)은 참이다. $A$의 eigenvalue가 모두 0이 아니므로 invertible하다. $\det (A) = \lambda_1 \lambda_2 \lambda_3$으로도 보일 수 있다.
(2), (3)은 거짓이다. $\lambda = 2$에 대하여 $GM = AM$이면 diagonalizable하고, 그렇지 않으면 non-diagonalizable하다.
Problem 20.
Q. $A$의 eigenvector가 (1, 4) 뿐일 때, 다음이 참인지 거짓인지 판단하라.
(1) $A$는 invertible하지 않다.
(2) $A$는 repeated eigenvalue를 가진다.
(3) $A$는 non-diagonalizable하다.
(1)은 거짓이다. $A$의 eigenvector가 (1, 4) 뿐이더라도 $\lambda \neq 0$이면 invertible할 수 있다.
(2)는 참이다. $A$의 eigenvector가 (1, 4) 뿐이므로 $Ax = \lambda x$가 성립하는 $x$가 하나뿐이라는 것이고, 따라서 $\lambda$도 하나뿐이므로 repeated eigenvalue를 가진다. 그러나 반대로 repeated eigenvalue를 가지고 있다고 해서 eigenvector가 하나뿐이라는 것은 아니다.
(3)은 참이다. $A$의 eigenvector가 (1, 4) 뿐이므로 non-diagonalizable하다.
Problem 23.
Q. 다음 $A$의 eigenvalue는 1, 9이고, $B$의 eigenvalue는 -1, 9이다. 이때 일종의 $\sqrt{A}$인 $R = X \sqrt{\Lambda} X^{-1}$를 구하라. 그리고 $\sqrt{B}$는 왜 real matrix가 아닌지 설명하라.
\[A = \begin{bmatrix} 5 & 4 \\ 4 & 5 \end{bmatrix}, \quad B = \begin{bmatrix} 4 & 5 \\ 5 & 4 \end{bmatrix}\]먼저 $A$의 eigenvalue와 eigenvector를 구하면 다음과 같다.
\[\lambda_1 = 9, \quad \lambda_2 = 1 \\ x_1 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix}, \quad x_2 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ -1 \end{bmatrix}\]따라서 $A = X \Lambda X^{-1}$로 다음과 같이 나타낼 수 있다.
\[A = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} 9 & 0 \\ 0 & 1 \end{bmatrix} \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}\]따라서 $\sqrt{A}$는 다음과 같이 나타낼 수 있다.
\[\sqrt{A} = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} 3 & 0 \\ 0 & 1 \end{bmatrix} \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}\]실제로 $\sqrt{A}^ 2 = A$임을 확인할 수 있다.
\[\sqrt{A}^ 2 = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix} \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix} = \begin{bmatrix} 5 & 4 \\ 4 & 5 \end{bmatrix} = A\]반면 $B$의 경우 다음과 같이 나타낼 수 있다.
\[B = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} 9 & 0 \\ 0 & -1 \end{bmatrix} \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}\]따라서 eigenvalue가 음수인 것이 있으므로, $\sqrt{B}$는 real matrix가 될 수 없다.
\[\sqrt{B} = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} 3 & 0 \\ 0 & i \end{bmatrix} \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} = \frac{1}{2} \begin{bmatrix} 3 + i & 3 - i \\ 3 - i & 3 + i \end{bmatrix}\]이 경우에도 실제로 $\sqrt{B}^ 2 = B$임을 확인할 수 있다.
\[\sqrt{B}^ 2 = \frac{1}{4} \begin{bmatrix} 3 + i & 3 - i \\ 3 - i & 3 + i \end{bmatrix} \begin{bmatrix} 3 + i & 3 - i \\ 3 - i & 3 + i \end{bmatrix} = \begin{bmatrix} 4 & 5 \\ 5 & 4 \end{bmatrix} = B\]이 문제를 통해 $A^k$를 실수 단위로 확장할 수 있음을 알 수 있다.
Problem 25.
Q. $A$의 left eigenvector는 $y^T A = \lambda y^T$를 만족하는 $y$이다. $A$의 eigenvalue $\lambda$, eigenvector $x$, left eigenvector $y$를 이용하여 $A = X \Lambda X^{-1}$를 rank one matrices의 합으로 나타내라.
$A = X \Lambda X^{-1}$로부터 $A^T = (X \Lambda X^{-1})^T = (X^{-1})^ T \Lambda X^T$이고, left eigenvector를 구하는 식을 다음과 같이 쓸 수 있다.
\[y^T A = \lambda y^T \Leftrightarrow A^T y = \lambda y\]따라서 $y$는 $A^T$의 eigenvector이므로, 결국 $Y = (X^{-1})^ T$로 나타낼 수 있다. 여기서 $Y$는 $A^T = Y \Lambda Y^{-1}$로 나타낼 수 있는 eigenvector matrix이다. 따라서 $A= X \Lambda X^{-1}$를 다음과 같이 나타낼 수 있다.
댓글 남기기