Introduction
이번에 선형대수를 공부하면서 내용을 정리해보았습니다.
강의 영상 : https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/video_galleries/video-lectures/
Video Lectures | Linear Algebra | Mathematics | MIT OpenCourseWare
This section contains a complete set of video lectures on linear algebra along with transcripts and related resource files.
ocw.mit.edu
스터디 github : https://github.com/jwkweon/study-linear-algebra
GitHub - jwkweon/study-linear-algebra
Contribute to jwkweon/study-linear-algebra development by creating an account on GitHub.
github.com
참고한 블로그 :
Lecture 22: Diagonalization and powers of A
Lecture 22: Diagonalization and powers of A (6/25) - 좋아. 시작해볼까? 이번 강의는 고유값에 대한 ...
blog.naver.com
[Linear Algebra] Lecture 22 행렬의 대각화(Diagonalization)와 거듭제곱(powers)
이번 포스팅에서 다룰 내용은 바로 행렬의 대각화(Diagonalization)이다. 행렬의 대각화는 지난 시간에 배운 고유값(eigenvalue)과 고유벡터(eigenvector)를 활용하기 위한 하나의 방법이라고 할 수 있으며,
twlab.tistory.com
(제가 이해하기 쉽게 요약해서 적었으므로 좀더 자세히 공부하고싶다면 위 블로그를 참고하시면 됩니다.)
행렬의 대각화(Diagonalization)
이번 Lecture는 지난 고유값에 연장 강의라고 생각하면 된다. 이전 강의에서 배운 식을 봐보자.
$$ Ax = \lambda x $$
고유값과 고유벡터로 무엇을 할 수 있을까? 바로 행렬을 대각화 할 수 있다는 것이다.
핵심공식은 다음과 같다.
$$ S^{-1} AS = \Lambda $$
여기서 S는 고유벡터로 구성된 행렬이다.
이때, S는 역행렬이 필요하기 때문에 n개의 서로 독립인 고유벡터가 필요하다. (특이행렬이 아니어야함
$$AS$$
먼저 이 A 곱하기 S가 무엇인지 봐보자.
$$ AS = A \begin{bmatrix} | & | & | & |\\ x_1 & x_2 & \cdots & x_n \\ | & | & | & | \end{bmatrix} = \begin{bmatrix} | & | & | & |\\ \lambda_1 x_1 & \lambda_2 x_2 & \cdots & \lambda_n x_n \\ | & | & | & | \end{bmatrix}$$
S는 고유벡터로 구성된 행렬이고 A에다 각 column의 고유벡터를 구하면 오른쪽처럼 고유벡터에 람다를 곱한 형태가 될 것이다.
이제 위 식을 다시 고유벡터가있는 S행렬과 람다만 모아둔 행렬로 분해하면 다음과 같다.
$$ \begin{bmatrix} | & | & | & |\\ \lambda_1 x_1 & \lambda_2 x_2 & \cdots & \lambda_n x_n \\ | & | & | & | \end{bmatrix} = \begin{bmatrix} | & | & | & |\\ x_1 & x_2 & \cdots & x_n \\ | & | & | & | \end{bmatrix} \underset{\Lambda}{\begin{bmatrix} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_n \end{bmatrix}} = S \Lambda$$
이렇게 고유값으로 구성된 대각행렬을 $\Lambda$(람다)라고 부른다.
따라서, 우리는 다음 식을 직관적으로 얻었다.
$$ AS = S \Lambda$$
여기서 S는 n개의 서로 도립인 고유벡터로 이루어진 행렬이기 때문에 S의 역함수를 양변 왼쪽에 곱할 수 있다.
$$ S^{-1} A S = \Lambda $$
양변 오른쪽에 S의 역함수를 곱할수도 있다.
$$ A = S \Lambda S^{-1} $$
이 형태는 새로운 인수화이며 이전의 배웠던 소거를 통한 LU 분해나 QR분해에 대한 대체방법이다.
그렇다면 이러한 식을 어떻게 사용할 수 있을까?
행렬 A의 제곱을 해보자. 다음 식에서부터 시작할 것이다.
$$Ax = \lambda x $$
양변의 왼쪽에 행렬 A를 곱한다.
$$ A^2 x = \lambda A x $$
여기서 $Ax = \lambda x $가 되므로
$$ A^2 x = \lambda^2 x $$
요약하면, $A^2$의 고유값은 $\lambda^2$과 같고, $A^2$의 고유벡터는 $A$의 고유벡터와 같다.
이번에는 아래식에서부터 시작해보자.
$$A = S \Lambda S^{-1} $$
여기서 행렬 A를 제곱해보자.
$$ A^2 = S \Lambda S^{-1} S \Lambda S^{-1} $$
$S^{-1}S = I $를 이용하면
$$ A^2 = S \Lambda^2 S^{-1} $$
이는 방금전에 배운것과 동일한 내용을 알려준다.
따라서, $A^2$의 고유값행렬($\Lambda$)은 $\Lambda^2$과 같고, $A^2$의 고유벡터행렬($S$)는 $A$의 고유벡터행렬과 같다.
이런식으로 A행렬을 k번 거듭제곱하면 고유벡터행렬은 그대로 유지되고 고유값행렬이 k번 거듭제곱될 것이다.
$$ A^k = S \Lambda^k S^{-1} $$
이렇게 고유값과 고유벡터는 행렬의 거듭제곱을 이해하기 위한 훌륭한 방법을 제공한다.
예를들어 LU분해나 QR분해 등의 방법을 이용하여 행렬을 인수분해 했을 경우,
A를 100제곱하면 LU*LU*LU*...을 100번 수행한 행렬이나 QR*QR*QR*...을 100번 수행한 행렬을 가지고 A의 100제곱이 어떤 결과를 보일지 분석해야하지만 이러한 방법으로는 거의 불가능하다.
그러나 고유값행렬과 고유값벡터행렬로 분해한식은 고유값행렬의 100제곱만 분석하면되고 이마저도 고유값행렬의 100제곱을 할 필요도 없이 각 고유값들의 제곱을 계산하면 된다.
$$ \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} $$
결국 고유값은 행렬의 거듭제곱에 대해서 말해준다.
그러면 언제 행렬의 K제곱이 0이될까?
다음과 같은 행렬을 안정 행렬(Stable matrix)라고 한다.
$$ {\rm if \ \ all \ \ | \lambda_i | < 1 \ \ then} $$
$$ A^k \rightarrow 0 \ \ {\rm as} \ \ k \rightarrow \infty $$
이는 당연히 고유값들이 1보다 작으면 제곱할수록 0에 근사한값을 가지게 될 것이다.
대각화 가능한 행렬과 아닌 행렬
이 모든게 제대로 동작하기 위한 한 가지 가정이 있다.
$A=S \Lambda S^{-1}$로 대각화 된다는 것은 A는 n개의 서로 독립인 고유벡터를 가져야 한다는 것이다.
만일, n개의 독립된 고유벡터가 없다면 우리는 행렬을 대각화할 수 없다.
그리고 n개의 서로 독립인 고유벡터가 있다는 것은 모든 고유값이 서로 다르다는 것과 같은 이야기다.
즉, 모든 고유값이 서로 다르면 A는 대각화가 가능하고, 대부분의 행렬들이 이렇게 대각화가 가능하다.
그렇다면 고유값이 몇번 반복됬을 때를 생각해야한다.
만약 3번 반복되었다고 해보자. 결론은 다음과 같다.
n개의 서로 독립인 고유벡터를 가질수도 가지지 않을 수도 있다는 것이다.
먼저, 고유값이 반복되는데 n개의 독립인 고유벡터를 가지는 경우를 생각해보자.
예를들어 단위행렬, 10x10 단위행렬을 생각해보자.
단위 행렬의 고유값을 찾으면 모두 1이 될 것이고 고유값 1은 10번 반복될 것이다.
단위행렬은 사실 모든 column vector가 고유벡터이다.
행렬 A가 단위 행렬이라면 A의 모든 column이 S의 column이 되고 결국 $S^{-1} A S =I^{-1} I I = I $로 다시 단위 행렬을 얻을 것이다.
따라서, 단위행렬은 이미 대각행렬화 되있는 것이다.
요약하면, 대각행렬은 고유값 자체가 대각성분에 놓여있는거고, 각 column vector가 고유벡터가 된다.
따라서, 행렬이 이미 대각행렬이라면 고유값행렬($\Lambda$)은 원래 행렬과 동일하게 된다.
이번에는 고유값이 반복되는데 n개의 독립인 고유벡터를 가지지 않는 경우를 생각해보자.
다음과 같은 삼각행렬 A가 있다.
$$ A = \begin{bmatrix} 2 & 1 \\ 0 & 2 \end{bmatrix} $$
고유값을 구해보자.
$$ det \ \ (A- \lambda I) = \begin{vmatrix} 2- \lambda & 1 \\ 0 & 2 - \lambda \end{vmatrix} = (2- \lambda)^2 = 0 $$
$$ \therefore \quad \lambda_1 = 2 , \quad \lambda_2 = 2 $$
고유벡터를 구해보자.
$$ (A - \lambda I ) x = 0 $$
$$ \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix} $$
$$ \therefore \quad x_{\lambda_1} = \begin{bmatrix} 1 \\ 0 \end{bmatrix} , \quad x_{\lambda_2} = ? $$
이 고유벡터는 $(A- \lambda I)$의 Null space가 된다. 근데, Null space는 단지 1차원이 된다.
이는 충분한 고유벡터를 가지지 못하는 경우가 되고 결국 2개의 서로 독립인 고유벡터를 찾을 수 없고 단 1개의 고유벡터만이 있으며 이 행렬은 대각화가 될 수 없다.
여기서 $\lambda$의 근이 2, 2로 2번 중복되는데 이런걸 대수적 중복도(algebraic multiplicity)가 2가 된다고 한다.
가장 중복이 많은 경우를 세면 된다.
하지만, 기하학적 중복도(geometric multiplicity)는 고유벡터에 대해서 보는데 여기선 Null space를 의미하고 유일한 고유벡터는 (1, 0)이 된다. 따라서 기하학적 중복도는 1이 된다.
이 강의에서는 고유값이 중복되는 경우는 다루지 않는다.
이전에 배웠던 A의 거듭제곱이 0으로 가는 경우도 반복된 고유값에 대해서 처리한 것은 아니라고 한다.
이 강의에서는 항상 대각화가 되는걸 다루고 각각의 고유값에 대해서 최소한 하나의 고유벡터가 존재한다.
이런 경우 모든 고유값에 대한 대수적 중복도는 1이고, 기하학적 중복도도 1이다.
즉, 하나의 고유값에 대해서 서로다른 하나의 고유벡터가 있다는 뜻이다.
대각화의 응용
다음과 같은 방정식을 풀어보자. (선형연립방정식이 아니다)
$$ u_{k+1} = A u_k $$
위 식은 차분방정식(또는 계차방정식)이다. 이때, 초기값은 k=0일 때, $u_0$라는 벡터이다.
이 차분방정식을 풀면 다음과 같다.
$$ u_1 = A u_0 $$
$$ u_2 = A^2 u_0 $$
$$ \vdots $$
$$ u_k = A^k u_0 $$
이 차분방정식은 1차 시스템(first-order system)이라고 부른다.
1차인 이유는 k에서 k+1로 딱 한단계(one level)만을 연결시키기 때문이다.
그리고 시스템(system)이라 부르는 이유는 벡터와 행렬이 식에 있기 때문이다.
그렇다면 $u_{100}$은 무엇일까?
아마 $A^{100} u_0$일 것이고 행렬 A를 100번 곱해야한다.
이걸 풀기 위해 아이디어로 $u_0$를 행렬 A의 고유벡터들의 선형 결합으로 보자.
$$ u_0 = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n $$
그리고 이걸 고유벡터행렬 S와 상수값 벡터인 c로 나눠보자.
$$ u_0 = \underset{S}{\begin{bmatrix} | & | & | & |\\ x_1 & x_2 & \cdots & x_n \\ | & | & | & | \end{bmatrix}} \underset{c}{\begin{bmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{bmatrix}} = Sc$$
$u_0$에 A를 곱하면 어떻게 되는지 봐보자.
$$ A u_0 = c_1 A x_1 + c_2 A x_2 + \cdots + c_n A x_n $$
$$ = c_1 \lambda_1 x_1 + c_2 \lambda_2 x_2 + \cdots + c_n \lambda_n x_n $$
A를 한번더 곱하자.
$$ AA u_0 = c_1 \lambda_1 A x_1 + c_2 \lambda_2 A x_2 + \cdots + c_n \lambda_n A x_n $$
$$ = c_1 \lambda_1^2 x_1 + c_2 \lambda_2^2 x_2 + \cdots + c_n \lambda_n^2 x_n $$
이런식으로 A를 100번 곱하면 다음과 같다.
$$ \vdots $$
$$ 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 $$
이것을 행렬곱셈으로 표시하면 다음과 같다.
$$ u_{100} = A^{100} u_0 = (S \Lambda^{100} S^{-1}) (S c) = S \Lambda^{100} c $$
$$ = \begin{bmatrix} | & | & | & |\\ x_1 & x_2 & \cdots & x_{100} \\ | & | & | & | \end{bmatrix} \begin{bmatrix} \lambda_1^{100} & 0 & \cdots & 0 \\ 0 & \lambda_2^{100} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_{100}^{100} \end{bmatrix} \begin{bmatrix} c_1 \\ c_2 \\ \vdots \\ c_{100} \end{bmatrix} $$
이런식으로 정리할 수 있다.
이번 예제는 피보나치 수열이다.
$$ F_0 \ \ F_1 \ \ F_2 \ \ F_3 \ \ F_4 \ \ F_5 \ \ F_6 \ \ F_7 \ \ F_8 \ \ \cdots \ \ F_{100} $$
$$ 0 \quad 1 \quad 1 \quad 2 \quad 3 \quad 5 \quad 8 \quad 13 \quad 21 \quad \cdots \quad ? $$
여기서 $F^{100}$은 얼마나 될까?
피보나치 수열의 규칙은 다음과 같다.
$$ F_{k+2} = F_{k+1} + F_k $$
이거는 단일 방정식이다. 즉, system이 아니다.
그리고 이것은 second-order이며 2차 차분방정식(second-order differential equation)이다.
우리가 원하는 것은 1차 시스템이다. 이것을 위해 다음과 같이 하면된다.
먼저 $F_{k+2}$는 2개의 입력값으로 정의되어 있다.
입력값은 $F_{k+1}$과 $F_k$가 될 것이고 이들을 $u_k$ 벡터로 정의하면 된다.
$$ u_k = \begin{bmatrix} F_{k+1} \\ F_k \end{bmatrix} $$
여기서 하나의 트릭을 사용하여 다음 식을 추가한다.
$$ F_{k+1} = F_{k+1} $$
$$ F_{k+2} = F_{k+1} + F_k $$
이 2개의 방정식을 이용하여 시스템 방정식을 구하면 다음과 같다.
$$ \begin{bmatrix} F_{k+2} \\ F_{k+1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{k+1} \\ F_k \end{bmatrix} $$
이런식으로 1차인 2x2 시스템 A를 얻을 수 있고, $u_k$로 정리하면 다음과 같다.
$$ u_{k+1} = A u_k $$
이렇게 2차 스칼라 문제(second-order scalar problem)를 1차 시스템(first-order system)으로 변경했다.
이제 시스템 행렬 A의 고유값과 고유벡터를 구해보자.
$$ A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} $$
일단, 행렬 A가 대칭행렬이기 때문에 고유값이 실수(real)로 나오는 것을 알 수 있다.
그리고 고유벡터는 서로 직교(orthogonal) 할 것이다.
$$ | A - \lambda I | = \begin{vmatrix} 1 - \lambda & 1 \\ 1 & - \lambda \end{vmatrix} = \lambda^2 - \lambda -1 = 0 $$
그리고 실제로 고유값에 대한 식을 구해보니 최초의 식과 같은 양상을 보인다.
$$ F_{k+2} - F_{k+1} - F_k = 0 $$
$$ \lambda^2 - \lambda - 1 = 0 $$
계속해서 고유값을 계산해보자.
$$ \lambda = \frac{ 1 \pm \sqrt{5} }{2} $$
$$ \therefore \quad \lambda_1 = \frac{1}{2} (1 + \sqrt{5} ) \approx 1.618 $$
$$ \therefore \quad \lambda_2 = \frac{1}{2} (1 - \sqrt{5} ) \approx -0.618 $$
2개의 고유값의 합은 행렬 A의 trace와 같고, 2개의 고유값의 곱은 행렬 A의 행렬식과 같고,
고유값 $\lambda_1$은 1보다 크고, $\lambda_2$는 1보다 작다.
또, 2개의 고유값이 서로 다르기 때문에 A는 2개의 독립인 고유벡터가 존재하며, 대각화가 가능하다.
그리고 피보나치 숫자들의 증가를 제어하는 것은 무엇일까? 결론은 고유값에 있다.
$$u_{100} = A^{100} u_0 $$
$$ = c_1 \lambda_1^{100} x_1 + c_2 \lambda_2^{100} x_2 $$
$$ = c_1 \left( \frac{1+ \sqrt{5}}{2} \right)^{100} x_1 + c_2 \left( \frac{1- \sqrt{5}}{2} \right)^{100} x_2 $$
아마 고유값 중에서 1보다 큰 즉, 둘중에 가장 큰 고유값($\lambda_1$)이 증가를 제어할 것이다.
그리고 $F_{100}$의 값은 $u_{100}$을 구하는 것과 같다. 따라서, 대략적으로 다음과 같을 것이다.
$$ F_{100} \approx c_1 \left( \frac{1+ \sqrt{5}}{2} \right)^{100} $$
이제 고유벡터를 구해보자.
$$ (A - \lambda I ) x = 0 $$
기존에 구하던 방법으로 가우스소거를 하고 free variable을 설정해서 구하면 되지만
여기서 고유값을 뺀 행렬이 특이행렬이기 때문에 고유벡터가 ($\lambda$, 1)임을 유추할 수 있다.
$$ \begin{bmatrix} 1- \lambda & 1 \\ 1 & - \lambda \end{bmatrix} \begin{bmatrix} \lambda \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix} $$
$$ \begin{bmatrix} - \lambda^2 + \lambda + 1 \\ \lambda - \lambda \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix} $$
고유벡터를 구하면 다음과 같다.
$$ \therefore \quad x_1 = \begin{bmatrix} \lambda_1 \\ 1 \end{bmatrix} = \begin{bmatrix} \frac{1}{2} (1+ \sqrt{5}) \\ 1 \end{bmatrix} $$
$$ \therefore \quad x_2 = \begin{bmatrix} \lambda_2 \\ 1 \end{bmatrix} = \begin{bmatrix} \frac{1}{2} (1 - \sqrt{5}) \\ 1 \end{bmatrix} $$
이제 마지막으로 $c_1$과 $c_2$를 구해야한다.
먼저, 초기값 $u_0$는 다음과 같다.
$$ u_0 = \begin{bmatrix} 1 \\ 0 \end{bmatrix} $$
그리고 $u_0$의 식을 다음과 같이 쓸 수 있다.
$$ 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_2 x_2 $$
$$ = \begin{bmatrix} \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \\ 1 & 1 \end{bmatrix} \begin{bmatrix} c_1 \\ c_2 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix} $$
이제 소거를 하면된다.
$$ = \begin{bmatrix} 1 & \frac{-1 + \sqrt{5}}{2} \\ 0 & \frac{5 - \sqrt{5}}{2} \end{bmatrix} \begin{bmatrix} c_1 \\ c_2 \end{bmatrix} = \begin{bmatrix} \frac{-1 + \sqrt{5}}{2} \\ \frac{1 - \sqrt{5}}{2} \end{bmatrix} $$
$$ \therefore c_1 = \frac{\sqrt{5}}{5} $$
$$ \therefore c_2 = \frac{- \sqrt{5}}{5} $$
