연결 강의: MIT 18.06 Linear Algebra - Lecture 22: Diagonalization and Powers of A

1. 이번 강의의 위치

지난 강의에서는 eigenvalue와 eigenvector의 기본 방정식을 배웠다.

$$Ax=\lambda x$$

여기서 $x$는 eigenvector이고, $\lambda$는 eigenvalue이다.

이번 강의의 목표는 한 단계 더 나아가는 것이다.

eigenvalues와 eigenvectors를 찾은 뒤, 그것을 어떻게 사용하는지를 본다.

핵심은 행렬 $A$를 diagonal matrix와 연결하는 것이다.

이 과정을 diagonalization, 즉 대각화라고 한다.

---

2. Eigenvector들을 행렬로 모으기

행렬 $A$가 $n$개의 linearly independent eigenvectors를 가진다고 하자.

이 eigenvectors를 다음처럼 두자.

$$x_1, x_2, \dots, x_n$$

각 eigenvector는 자기 eigenvalue를 가진다.

$$Ax_1=\lambda_1x_1$$ $$Ax_2=\lambda_2x_2$$

계속해서,

$$Ax_n=\lambda_nx_n$$

이제 이 eigenvectors를 column으로 모아 행렬 $S$를 만든다.

$$S = \begin{bmatrix} | & | & & | \\ x_1 & x_2 & \cdots & x_n \\ | & | & & | \end{bmatrix}$$

이 행렬 $S$를 eigenvector matrix라고 부를 수 있다.

중요한 조건은 $x_1,\dots,x_n$이 linearly independent여야 한다는 점이다.

그래야 $S$가 invertible matrix가 된다.

---

3. $AS$를 계산하면 무슨 일이 생기는가

$S$의 column들은 모두 eigenvectors이다.

따라서 $A$를 $S$에 곱하면, 각 column에 $A$가 따로 작용한다.

$$AS = A \begin{bmatrix} | & | & & | \\ x_1 & x_2 & \cdots & x_n \\ | & | & & | \end{bmatrix}$$

행렬곱을 column 단위로 보면 다음과 같다.

$$AS = \begin{bmatrix} | & | & & | \\ Ax_1 & Ax_2 & \cdots & Ax_n \\ | & | & & | \end{bmatrix}$$

그런데 각 $x_i$는 eigenvector이므로,

$$Ax_i=\lambda_i x_i$$

이다.

따라서,

$$AS = \begin{bmatrix} | & | & & | \\ \lambda_1x_1 & \lambda_2x_2 & \cdots & \lambda_nx_n \\ | & | & & | \end{bmatrix}$$

이제 eigenvalues만 따로 diagonal matrix로 빼낼 수 있다.

$$\Lambda = \begin{bmatrix} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_n \end{bmatrix}$$

그러면 다음이 성립한다.

$$AS=S\Lambda$$

이 식이 대각화의 출발점이다.

---

4. Diagonalization 공식

방금 얻은 식은 다음이다.

$$AS=S\Lambda$$

$S$가 invertible이면 양변 왼쪽에 $S^{-1}$을 곱할 수 있다.

$$S^{-1}AS = \Lambda$$

이 식은 행렬 $A$를 eigenvector basis에서 보면 diagonal matrix $\Lambda$가 된다는 뜻이다.

또 같은 식을 $A$에 대해 정리하면 다음과 같다.

$$A=S\Lambda S^{-1}$$

이것이 diagonalization 공식이다.

$$\boxed{ A=S\Lambda S^{-1} }$$

여기서 각 행렬의 의미는 다음과 같다.

1. $S$: eigenvectors를 column으로 모은 행렬이다.
2. $\Lambda$: eigenvalues를 diagonal에 둔 행렬이다.
3. $S^{-1}$: 기존 좌표를 eigenvector 좌표로 바꾸는 역할을 한다.

이 분해는 이전에 배운 $A=LU$, $A=QR$과 비슷하게 행렬을 이해하기 좋은 형태로 바꾸는 새로운 factorization이다.

---

5. 왜 $S$가 invertible이어야 하는가

대각화를 하려면 반드시 $S^{-1}$이 존재해야 한다.

즉, eigenvector matrix $S$의 column들이 linearly independent여야 한다.

$$S = \begin{bmatrix} | & | & & | \\ x_1 & x_2 & \cdots & x_n \\ | & | & & | \end{bmatrix}$$

$x_1,\dots,x_n$이 independent이면 $S$는 invertible이다.

반대로 eigenvectors가 부족하면 $S$를 invertible하게 만들 수 없다.

따라서 diagonalization은 모든 행렬에 항상 가능한 것은 아니다.

행렬 $A$가 $n$개의 linearly independent eigenvectors를 가질 때만 가능하다.

---

6. $A^2$의 eigenvalues와 eigenvectors

대각화가 왜 유용한지 보려면 행렬의 거듭제곱을 보면 된다.

먼저 eigenvalue equation에서 시작하자.

$$Ax=\lambda x$$

양변에 다시 $A$를 곱하면,

$$A^2x=A(\lambda x)$$

$\lambda$는 scalar이므로 밖으로 뺄 수 있다.

$$A^2x=\lambda Ax$$

그런데 $Ax=\lambda x$이므로,

$$A^2x=\lambda(\lambda x)$$

따라서,

$$A^2x=\lambda^2x$$

즉, $A^2$의 eigenvector는 $A$와 같고, eigenvalue는 제곱된다.

$$\text{eigenvalue of } A^2 = \lambda^2$$

---

7. 대각화로 $A^2$ 보기

같은 사실을 diagonalization으로도 볼 수 있다.

$$A=S\Lambda S^{-1}$$

그러면,

$$A^2=(S\Lambda S^{-1})(S\Lambda S^{-1})$$

가운데의 $S^{-1}S$는 identity matrix이다.

$$S^{-1}S=I$$

따라서,

$$A^2=S\Lambda I \Lambda S^{-1}$$

즉,

$$A^2=S\Lambda^2S^{-1}$$

이다.

$\Lambda$는 diagonal matrix이므로 $\Lambda^2$도 diagonal matrix이고, 그 diagonal entries는 eigenvalues의 제곱이다.

$$\Lambda^2 = \begin{bmatrix} \lambda_1^2 & 0 & \cdots & 0 \\ 0 & \lambda_2^2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_n^2 \end{bmatrix}$$

---

8. $A^k$ 공식

같은 방식으로 $A$를 $k$번 곱하면 중간의 $S^{-1}S$가 계속 사라진다.

$$A^k = (S\Lambda S^{-1})(S\Lambda S^{-1})\cdots(S\Lambda S^{-1})$$

중간 항들이 모두 identity가 되므로,

$$A^k=S\Lambda^kS^{-1}$$

이다.

$$\boxed{ A^k=S\Lambda^kS^{-1} }$$

이 식은 diagonalization이 강력한 가장 큰 이유 중 하나이다.

행렬 $A$를 직접 $100$번 곱하는 것은 어렵다.

하지만 diagonal matrix $\Lambda$의 $100$제곱은 쉽다.

$$\Lambda^{100} = \begin{bmatrix} \lambda_1^{100} & 0 & \cdots & 0 \\ 0 & \lambda_2^{100} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_n^{100} \end{bmatrix}$$

즉, 행렬의 거듭제곱 문제를 eigenvalue의 거듭제곱 문제로 바꾼다.

---

9. 안정성: 언제 $A^k \to 0$인가

diagonalization을 사용하면 $A^k$가 커지는지, 작아지는지, 0으로 가는지 쉽게 볼 수 있다.

$$A^k=S\Lambda^kS^{-1}$$

여기서 $S$와 $S^{-1}$은 고정되어 있다.

$k$가 커질 때 변하는 것은 $\Lambda^k$이다.

따라서 $A^k$가 0으로 가려면 모든 eigenvalue의 거듭제곱이 0으로 가야 한다.

즉,

$$|\lambda_i|<1 \quad \text{for all } i$$

이면,

$$A^k \to 0 \quad (k\to\infty)$$

이다.

여기서 절댓값을 쓰는 이유는 eigenvalues가 음수이거나 complex number일 수 있기 때문이다.

정리하면 다음과 같다.

$$A^k \to 0 \quad \Longleftrightarrow \quad |\lambda_i|<1 \text{ for all eigenvalues}$$

단, 이 설명은 $A$가 diagonalizable하다는 가정 아래에서 보는 것이 가장 깔끔하다.

---

10. 어떤 행렬이 diagonalizable한가

대각화가 가능하려면 $n$개의 linearly independent eigenvectors가 필요하다.

가장 좋은 경우는 eigenvalues가 모두 서로 다른 경우이다.

즉, $n \times n$ 행렬 $A$가 $n$개의 distinct eigenvalues를 가지면, $A$는 $n$개의 independent eigenvectors를 가진다.

따라서 $A$는 diagonalizable하다.

$$\lambda_1,\lambda_2,\dots,\lambda_n \text{ all distinct} \quad \Longrightarrow \quad A \text{ is diagonalizable}$$

이것은 매우 중요한 사실이다.

랜덤하게 고른 대부분의 행렬은 eigenvalues가 서로 다르기 때문에 보통 diagonalizable하다.

문제가 생기는 경우는 repeated eigenvalue가 있을 때이다.

---

11. Repeated eigenvalue는 항상 나쁜가

repeated eigenvalue가 있다고 해서 항상 diagonalization이 불가능한 것은 아니다.

대표적인 예시는 identity matrix이다.

$$I = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix}$$

identity matrix의 eigenvalue는 전부 1이다.

즉, eigenvalue 1이 $n$번 반복된다.

하지만 모든 벡터가 eigenvector이다.

$$Ix=x$$

따라서 eigenvectors는 부족하지 않다.

원하는 대로 $n$개의 independent eigenvectors를 고를 수 있다.

즉, repeated eigenvalue가 있다고 해서 무조건 diagonalizable하지 않은 것은 아니다.

다만 repeated eigenvalue가 있으면 eigenvectors가 충분한지 반드시 확인해야 한다.

---

12. Diagonalization이 실패하는 예시

다음 행렬을 보자.

$$A = \begin{bmatrix} 2 & 1 \\ 0 & 2 \end{bmatrix}$$

이 행렬은 triangular matrix이다.

triangular matrix의 eigenvalues는 diagonal entries에서 바로 읽을 수 있다.

따라서 eigenvalues는 다음과 같다.

$$\lambda_1=2, \quad \lambda_2=2$$

즉, eigenvalue 2가 두 번 반복된다.

직접 characteristic equation을 보면 다음과 같다.

$$A-\lambda I = \begin{bmatrix} 2-\lambda & 1 \\ 0 & 2-\lambda \end{bmatrix}$$

determinant는 대각성분의 곱이다.

$$\det(A-\lambda I)=(2-\lambda)^2$$

따라서 $\lambda=2$가 double root이다.

---

13. Algebraic multiplicity와 geometric multiplicity

위 예시에서 eigenvalue 2는 characteristic polynomial에서 두 번 반복된다.

이 반복 횟수를 algebraic multiplicity라고 한다.

$$\det(A-\lambda I)=(2-\lambda)^2$$

따라서 $\lambda=2$의 algebraic multiplicity는 2이다.

하지만 eigenvectors가 몇 방향 나오는지는 따로 봐야 한다.

이를 위해 $A-2I$의 nullspace를 구한다.

$$A-2I = \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}$$

eigenvector는 다음 식을 만족해야 한다.

$$(A-2I)x=0$$

즉,

$$\begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$$

이 식은 $x_2=0$을 의미한다.

$x_1$만 자유변수이므로 nullspace는 다음 한 방향뿐이다.

$$\operatorname{null}(A-2I) = \operatorname{span} \left\{ \begin{bmatrix} 1 \\ 0 \end{bmatrix} \right\}$$

따라서 independent eigenvector는 하나뿐이다.

이 eigenvector 방향의 개수를 geometric multiplicity라고 한다.

이 예시에서는 다음과 같다.

$$\text{algebraic multiplicity}=2$$

하지만,

$$\text{geometric multiplicity}=1$$

이다.

따라서 $2 \times 2$ 행렬인데 independent eigenvector가 하나밖에 없고, 이 행렬은 diagonalizable하지 않다.

---

14. Difference equation

대각화가 가장 잘 쓰이는 곳 중 하나는 행렬의 반복 적용이다.

다음 recurrence를 생각하자.

$$u_{k+1}=Au_k$$

여기서 $u_k$는 벡터이고, $A$는 고정된 행렬이다.

초기값 $u_0$가 주어지면,

$$u_1=Au_0$$ $$u_2=Au_1=A^2u_0$$

계속해서,

$$u_k=A^ku_0$$

이다.

이 식 자체는 간단하지만, 실제로 $A^k$를 계산하는 것은 쉽지 않다.

여기서 diagonalization이 필요하다.

$$A^k=S\Lambda^kS^{-1}$$

따라서,

$$u_k=S\Lambda^kS^{-1}u_0$$

이다.

---

15. 초기벡터를 eigenvector들의 조합으로 쓰기

대각화의 의미를 더 직관적으로 보자.

초기벡터 $u_0$를 eigenvectors의 linear combination으로 쓴다고 하자.

$$u_0=c_1x_1+c_2x_2+\cdots+c_nx_n$$

이제 $A$를 한 번 곱하면,

$$Au_0 = c_1Ax_1+c_2Ax_2+\cdots+c_nAx_n$$

각 $x_i$는 eigenvector이므로,

$$Au_0 = c_1\lambda_1x_1 +c_2\lambda_2x_2 +\cdots +c_n\lambda_nx_n$$

$A$를 $k$번 곱하면 다음이 된다.

$$A^ku_0 = c_1\lambda_1^kx_1 +c_2\lambda_2^kx_2 +\cdots +c_n\lambda_n^kx_n$$

즉, 각 eigenvector 방향은 자기 eigenvalue만큼 독립적으로 커지거나 작아진다.

이것이 eigenvector basis가 강력한 이유이다.

일반 좌표에서는 서로 섞여 보이는 동역학이, eigenvector 좌표에서는 각각 따로 움직인다.

---

16. Fibonacci 수열 예시

Fibonacci 수열을 eigenvalue 관점에서 보자.

초기값을 다음처럼 둔다.

$$F_0=0, \quad F_1=1$$

그리고 점화식은 다음이다.

$$F_{k+2}=F_{k+1}+F_k$$

따라서 수열은 다음처럼 시작한다.

$$0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ \dots$$

질문은 다음이다.

$$F_{100} \text{은 얼마나 큰가?}$$

또는 더 일반적으로, Fibonacci 수열은 얼마나 빠르게 증가하는가?

이 질문의 답은 eigenvalue에 들어 있다.

---

17. Fibonacci를 first-order system으로 바꾸기

Fibonacci 점화식은 scalar equation이지만, 두 단계 전 값까지 필요하다.

$$F_{k+2}=F_{k+1}+F_k$$

즉, second-order recurrence이다.

이를 first-order system으로 바꾸기 위해 벡터를 정의한다.

$$u_k = \begin{bmatrix} F_{k+1} \\ F_k \end{bmatrix}$$

그러면 다음 단계는

$$u_{k+1} = \begin{bmatrix} F_{k+2} \\ F_{k+1} \end{bmatrix}$$

이다.

점화식 $F_{k+2}=F_{k+1}+F_k$를 사용하면,

$$\begin{bmatrix} F_{k+2} \\ F_{k+1} \end{bmatrix} = \begin{bmatrix} F_{k+1}+F_k \\ F_{k+1} \end{bmatrix}$$

이것은 다음 행렬곱으로 쓸 수 있다.

$$u_{k+1} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} u_k$$

따라서 Fibonacci recurrence는 다음 matrix difference equation이 된다.

$$u_{k+1}=Au_k$$

여기서,

$$A= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$$

이다.

---

18. Fibonacci matrix의 eigenvalues

이제 행렬

$$A= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$$

의 eigenvalues를 구하자.

먼저 $A-\lambda I$는 다음이다.

$$A-\lambda I = \begin{bmatrix} 1-\lambda & 1 \\ 1 & -\lambda \end{bmatrix}$$

determinant는 다음과 같다.

$$\det(A-\lambda I) = (1-\lambda)(-\lambda)-1$$

정리하면,

$$\det(A-\lambda I) = \lambda^2-\lambda-1$$

따라서 characteristic equation은 다음이다.

$$\lambda^2-\lambda-1=0$$

이 식의 해는 quadratic formula로 구한다.

$$\lambda = \frac{1\pm\sqrt{5}}{2}$$

따라서 eigenvalues는 다음과 같다.

$$\lambda_1=\frac{1+\sqrt{5}}{2}$$ $$\lambda_2=\frac{1-\sqrt{5}}{2}$$

$\lambda_1$은 약 $1.618$이고, $\lambda_2$는 약 $-0.618$이다.

$$\lambda_1 \approx 1.618, \quad \lambda_2 \approx -0.618$$

이 두 eigenvalue는 trace와 determinant 성질도 만족한다.

trace는 다음이다.

$$\operatorname{tr}(A)=1+0=1$$

따라서,

$$\lambda_1+\lambda_2=1$$

determinant는 다음이다.

$$\det(A)=1\cdot 0-1\cdot 1=-1$$

따라서,

$$\lambda_1\lambda_2=-1$$

이다.

---

19. Fibonacci matrix의 eigenvectors

각 eigenvalue에 대해 eigenvector를 찾자.

$$A-\lambda I = \begin{bmatrix} 1-\lambda & 1 \\ 1 & -\lambda \end{bmatrix}$$

이 행렬은 eigenvalue $\lambda$에 대해 singular이다.

다음 벡터를 생각하자.

$$x = \begin{bmatrix} \lambda \\ 1 \end{bmatrix}$$

확인해보면,

$$(A-\lambda I) \begin{bmatrix} \lambda \\ 1 \end{bmatrix} =0$$

첫 번째 성분은 다음이다.

$$(1-\lambda)\lambda+1 = \lambda-\lambda^2+1$$

그런데 $\lambda$는 characteristic equation을 만족한다.

$$\lambda^2-\lambda-1=0$$

즉,

$$\lambda^2=\lambda+1$$

따라서 첫 번째 성분은 0이다.

두 번째 성분은 다음이다.

$$\lambda-\lambda=0$$

따라서 eigenvector는 다음처럼 잡을 수 있다.

$$x_1= \begin{bmatrix} \lambda_1 \\ 1 \end{bmatrix}, \quad x_2= \begin{bmatrix} \lambda_2 \\ 1 \end{bmatrix}$$

eigenvalues가 서로 다르므로 이 두 eigenvector는 independent이다.

따라서 Fibonacci matrix는 diagonalizable하다.

---

20. Fibonacci 수열의 성장률

초기벡터는 다음이다.

$$u_0 = \begin{bmatrix} F_1 \\ F_0 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$$

이 벡터를 eigenvectors의 조합으로 쓴다.

$$u_0=c_1x_1+c_2x_2$$

즉,

$$\begin{bmatrix} 1 \\ 0 \end{bmatrix} = c_1 \begin{bmatrix} \lambda_1 \\ 1 \end{bmatrix} + c_2 \begin{bmatrix} \lambda_2 \\ 1 \end{bmatrix}$$

두 번째 성분을 보면,

$$c_1+c_2=0$$

따라서 $c_2=-c_1$이다.

첫 번째 성분은 다음이다.

$$c_1\lambda_1+c_2\lambda_2=1$$

$c_2=-c_1$을 대입하면,

$$c_1(\lambda_1-\lambda_2)=1$$

그런데,

$$\lambda_1-\lambda_2=\sqrt{5}$$

이므로,

$$c_1=\frac{1}{\sqrt{5}}, \quad c_2=-\frac{1}{\sqrt{5}}$$

이제 $u_k=A^ku_0$를 계산하면,

$$u_k = c_1\lambda_1^kx_1 +c_2\lambda_2^kx_2$$

따라서 두 번째 성분인 $F_k$는 다음이다.

$$F_k = \frac{1}{\sqrt{5}}\lambda_1^k - \frac{1}{\sqrt{5}}\lambda_2^k$$

즉,

$$\boxed{ F_k= \frac{\lambda_1^k-\lambda_2^k}{\sqrt{5}} }$$

여기서,

$$\lambda_1=\frac{1+\sqrt{5}}{2}, \quad \lambda_2=\frac{1-\sqrt{5}}{2}$$

이다.

이 공식은 Fibonacci 수열의 closed form이다.

---

21. 왜 큰 eigenvalue가 지배하는가

$\lambda_1$은 약 $1.618$이다.

$$\lambda_1 \approx 1.618$$

반면 $\lambda_2$는 약 $-0.618$이다.

$$\lambda_2 \approx -0.618$$

$k$가 커질수록 $\lambda_1^k$는 빠르게 커진다.

하지만 $\lambda_2^k$는 절댓값이 1보다 작기 때문에 0에 가까워진다.

$$|\lambda_2|<1 \quad \Longrightarrow \quad \lambda_2^k \to 0$$

따라서 큰 $k$에 대해서는 Fibonacci 수열이 거의 다음처럼 행동한다.

$$F_k \approx \frac{1}{\sqrt{5}}\lambda_1^k$$

즉, Fibonacci 수열의 성장률은 dominant eigenvalue인 $\lambda_1$이 결정한다.

이 값은 golden ratio이다.

$$\phi=\frac{1+\sqrt{5}}{2}$$

따라서 Fibonacci 수열은 대략 매 단계마다 $\phi \approx 1.618$배씩 증가한다고 볼 수 있다.

---

22. 핵심 정리

이번 강의의 핵심은 eigenvectors를 이용해 행렬을 diagonal matrix로 바꾸는 것이다.

eigenvectors를 column으로 모은 행렬을 $S$라 하고, eigenvalues를 diagonal에 둔 행렬을 $\Lambda$라 하면 다음이 성립한다.

$$AS=S\Lambda$$

$S$가 invertible이면,

$$S^{-1}AS=\Lambda$$

이고,

$$A=S\Lambda S^{-1}$$

이다.

이것이 diagonalization이다.

대각화를 하면 행렬의 거듭제곱을 쉽게 계산할 수 있다.

$$A^k=S\Lambda^kS^{-1}$$

따라서 $A^k$의 행동은 eigenvalues의 거듭제곱이 결정한다.

특히 모든 eigenvalue가 절댓값 1보다 작으면,

$$A^k\to 0$$

이다.

대각화 가능성은 eigenvectors가 충분한지에 달려 있다.

1. eigenvalues가 모두 distinct이면 diagonalizable하다.
2. repeated eigenvalue가 있어도 diagonalizable할 수 있다.
3. repeated eigenvalue가 있을 때 eigenvectors가 부족하면 diagonalizable하지 않다.

Fibonacci 예시는 대각화의 의미를 잘 보여준다.

recurrence를 matrix system으로 바꾸면,

$$u_{k+1}=Au_k$$

이고, 그 해는 eigenvalues와 eigenvectors로 표현된다.

결국 Fibonacci 수열의 성장률은 가장 큰 eigenvalue가 결정한다.

$$\lambda_1=\frac{1+\sqrt{5}}{2}$$

이처럼 diagonalization은 행렬이 반복해서 작용할 때, 그 안에서 실제로 어떤 방향이 커지고 어떤 방향이 사라지는지를 보여주는 도구이다.