Lecture 22. 대각화와 A의 거듭제곱

$A^{100}$ 을 계산해야 한다고 하자. 행렬 곱을 백 번 하는 것은 어리석다. 그런데 만약 고유벡터를 기저로 쓴다면 어떻게 될까.

고유벡터 방향에서는 $A$ 를 곱하는 것이 그저 $\lambda$ 를 곱하는 것이다. 그러니 $A$ 를 백 번 곱하는 것은 $\lambda$ 를 백 번 곱하는 것, 곧 $\lambda^{100}$ 을 계산하는 것에 지나지 않는다. 문제는 우리가 쓰는 좌표계가 고유벡터 기저가 아니라는 것뿐이다.

그렇다면 좌표계를 갈아끼우면 되지 않을까. 고유기저로 옮겨 가서 계산하고 다시 돌아오면 된다. 이 세 단계를 한 줄로 쓴 것이 $A = S\Lambda S^{-1}$ 이다.

1. 고유벡터를 열에 세운다¶

$A$ 의 고유벡터 $\vv{s}_1, \dots, \vv{s}_n$ 을 열로 나란히 세운 행렬을 $S$ 라 하자. 그리고 그에 딸린 고윳값을 같은 순서로 대각에 놓은 것을 $\Lambda$ 라 하자.

S = \begin{bmatrix} \vv{s}_1 & \vv{s}_2 & \cdots & \vv{s}_n \end{bmatrix}, \qquad \Lambda = \begin{bmatrix} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \ddots & \\ & & & \lambda_n \end{bmatrix}

(1)

이제 $AS$ 를 계산해 보자. 행렬 곱을 열별로 보면(L3의 (6)) $AS$ 의 $j$ 열은 $A\vv{s}_j$ 이고, 그것이 $\lambda_j\vv{s}_j$ 이다.

AS = \begin{bmatrix} A\vv{s}_1 & \cdots & A\vv{s}_n \end{bmatrix} = \begin{bmatrix} \lambda_1\vv{s}_1 & \cdots & \lambda_n\vv{s}_n \end{bmatrix}

(2)

오른쪽 행렬이 무엇인지가 요점이다. $S\Lambda$ 의 $j$ 열은 $S$ 의 열들을 $\Lambda$ 의 $j$ 열로 결합한 것인데, $\Lambda$ 의 $j$ 열은 $j$ 자리에만 $\lambda_j$ 가 있으므로 결합의 결과가 $\lambda_j\vv{s}_j$ 이다. 곧 (2)의 오른쪽이 정확히 $S\Lambda$ 이다.

AS = S\Lambda

(3)

$S$ 가 가역이면 양변에 $S^{-1}$ 을 곱해 두 가지로 쓸 수 있다.

A = S\Lambda S^{-1}, \qquad S^{-1}AS = \Lambda

(4)

2. 번역, 계산, 역번역¶

$A = S\Lambda S^{-1}$ 을 공식으로 외우면 아무것도 남지 않는다. 이야기로 읽어야 한다. $A\vv{x}$ 를 계산하는 일을 $S\Lambda S^{-1}\vv{x}$ 로 놓고 오른쪽부터 읽어 보자.

첫째, $S^{-1}\vv{x}$ 는 좌표를 갈아끼우는 일이다. $\vv{c} = S^{-1}\vv{x}$ 로 두면 $\vv{x} = S\vv{c}$ 이고, 이것을 풀어 쓰면

\vv{x} = c_1\vv{s}_1 + c_2\vv{s}_2 + \cdots + c_n\vv{s}_n

(5)

이다. 곧 $\vv{c}$ 는 고유기저에서 본 $\vv{x}$ 의 좌표이다. 표준좌표를 고유좌표로 번역한 셈이다.

둘째, $\Lambda\vv{c}$ 는 성분마다 수를 곱하는 일이다. 대각행렬이므로 섞이는 것이 없다. $i$ 번째 성분에 $\lambda_i$ 를 곱하면 끝이다.

셋째, $S$ 를 곱하는 것은 표준좌표로 되돌리는 일이다.

Figure 1:위쪽 길과 아래쪽 길이 같은 곳에 도착한다. 아래쪽이 훨씬 쉽다.

이 관점이 앞으로 여러 번 되돌아온다. $S^{-1}AS$ 라는 꼴을 여기서 처음 보는데, L28에서 유사행렬로, L30과 L31에서 선형변환과 기저 변환으로 다시 만난다.

3. 거듭제곱이 공짜가 된다¶

이제 처음의 질문으로 돌아가자. $A^2$ 을 계산해 보면

A^2 = (S\Lambda S^{-1})(S\Lambda S^{-1}) = S\Lambda \underbrace{S^{-1}S}_{= I} \Lambda S^{-1} = S\Lambda^2 S^{-1}

(6)

이다. 가운데의 $S^{-1}S$ 가 사라진다. 한 번 더 곱해 보면 같은 일이 또 일어난다.

A^3 = A^2 \cdot A = (S\Lambda^2 S^{-1})(S\Lambda S^{-1}) = S\Lambda^2 \underbrace{S^{-1}S}_{= I} \Lambda S^{-1} = S\Lambda^3 S^{-1}

(7)

곱할 때마다 안쪽에서 $S^{-1}S$ 가 하나씩 지워지고 $\Lambda$ 의 지수만 하나씩 올라간다. $A^{k-1} = S\Lambda^{k-1}S^{-1}$ 을 가정하고 $A$ 를 한 번 더 곱하면 같은 계산이 그대로 반복되므로, 귀납적으로 모든 $k$ 에 대해 성립한다.

A^k = S\Lambda^k S^{-1}, \qquad \Lambda^k = \begin{bmatrix} \lambda_1^k & & \\ & \ddots & \\ & & \lambda_n^k \end{bmatrix}

(8)

$\Lambda^k$ 가 저런 모양인 이유도 확인해 두자. 대각행렬끼리의 곱은 대각 성분끼리만 곱해진다. $\Lambda$ 의 $i$ 행에는 $\lambda_i$ 하나뿐이라 다른 성분과 만날 일이 없기 때문이다. 그러므로 대각행렬의 거듭제곱은 대각 성분을 각각 $k$ 제곱하는 것뿐이다.

$A^{100}$ 을 직접 구하려면 $n \times n$ 행렬 곱을 99번 해야 하는데, 오른쪽은 수의 100제곱 $n$ 개로 끝난다. $k$ 가 100이든 10⁹ 이든 계산량이 같다.

$A^k$ 의 운명¶

$k$ 를 키우면 $A^k$ 는 어떻게 되는가. (8)의 식을 보면 답이 바로 나온다. $\Lambda^k$ 의 성분이 $\lambda_i^k$ 이므로

|\lambda_i| < 1 \text{ 이 모든 } i \text{ 에 대해 성립} \quad\Longleftrightarrow\quad A^k \to 0

(9)

이다. 하나라도 $|\lambda| > 1$ 이면 그 방향이 폭발한다.

Figure 2:왼쪽은 고윳값의 위치이고 오른쪽은 그 결과이다. 단위원 하나가 세 운명을 가른다.

가장 큰 것만 살아남는다¶

먼저 고유벡터 하나에 $A^k$ 를 곱하면 어떻게 되는지 보자. $A\vv{s}_i = \lambda_i\vv{s}_i$ 를 $k$ 번 되풀이하면 된다.

A^2\vv{s}_i = A(\lambda_i\vv{s}_i) = \lambda_i\,A\vv{s}_i = \lambda_i^2\,\vv{s}_i \qquad\Longrightarrow\qquad A^k\vv{s}_i = \lambda_i^k\,\vv{s}_i

(10)

이제 $\vv{x}$ 를 고유기저로 펼쳐 (5)처럼 쓰고 $A^k$ 를 곱한다. 행렬 곱이 선형이므로 항마다 따로 들어간다.

A^k\vv{x} = A^k\left(\sum_i c_i\vv{s}_i\right) = \sum_i c_i\,A^k\vv{s}_i = c_1\lambda_1^k\,\vv{s}_1 + c_2\lambda_2^k\,\vv{s}_2 + \cdots + c_n\lambda_n^k\,\vv{s}_n

(11)

$A$ 를 $k$ 번 곱하는 일이 각 항에 $\lambda_i^k$ 를 곱하는 일로 바뀌었다. 2절의 세 단계를 한 줄로 압축한 것이 이 식이다.

\frac{A^k\vv{x}}{\lambda_1^k} = c_1\vv{s}_1 + c_2\left(\frac{\lambda_2}{\lambda_1}\right)^{k}\vv{s}_2 + \cdots + c_n\left(\frac{\lambda_n}{\lambda_1}\right)^{k}\vv{s}_n

(12)

$i \ge 2$ 마다 $\left|\lambda_i/\lambda_1\right| < 1$ 이므로 그 $k$ 제곱이 0으로 간다. 남는 것은 첫 항뿐이다.

\frac{A^k\vv{x}}{\lambda_1^k} \longrightarrow c_1\vv{s}_1 \qquad\Longrightarrow\qquad A^k\vv{x} \approx c_1\lambda_1^k\,\vv{s}_1 \qquad (k \text{ 가 클 때})

(13)

가장 느리게 죽는 항이 $\lambda_2$ 쪽이므로, 수렴이 얼마나 빠른지는 $\left|\lambda_2/\lambda_1\right|$ 이 결정한다. 이 비를 고윳값 간격이라 부르고, 작을수록 빨리 수렴한다.

여러 번 곱하면 가장 큰 고윳값의 방향만 살아남는다. 이 $\lambda_1$ 을 지배 고윳값이라 한다. L24의 마코브 행렬이 이 이야기 위에 서 있고, 고윳값을 구하는 실용적인 방법 하나도 여기서 나온다.

4. 대각화가 안 되는 경우¶

$S^{-1}$ 이 있어야 (4)의 식을 쓸 수 있다. 곧 고유벡터 $n$ 개가 독립이어야 한다. 언제 그런가.

고윳값이 서로 다르면 독립이다¶

두 개짜리로 확인하자. 서로 다른 고윳값 $\lambda_1 \neq \lambda_2$ 의 고유벡터 $\vv{s}_1, \vv{s}_2$ 에 대해 $c_1\vv{s}_1 + c_2\vv{s}_2 = \vv{0}$ 이라 하자. 양변에 $A$ 를 곱하면

c_1\lambda_1\vv{s}_1 + c_2\lambda_2\vv{s}_2 = \vv{0}

(14)

이다. 처음 식에 $\lambda_2$ 를 곱해 빼면 두 번째 항이 사라진다.

c_1(\lambda_1 - \lambda_2)\,\vv{s}_1 = \vv{0}

(15)

$\lambda_1 \neq \lambda_2$ 이고 $\vv{s}_1 \neq \vv{0}$ 이므로 $c_1 = 0$ 이고, 그러면 처음 식이 $c_2\vv{s}_2 = \vv{0}$ 이 되어 $c_2 = 0$ 이다. 독립이다.

$n$ 개로 확장하는 것도 어렵지 않다. 위에서 한 일은 " $\lambda_2$ 를 곱해 뺀다"였는데, 그것을 행렬로 쓰면 $(A - \lambda_2 I)$ 를 곱하는 일이다. 실제로

(A - \lambda_2 I)\,\vv{s}_i = A\vv{s}_i - \lambda_2\vv{s}_i = (\lambda_i - \lambda_2)\,\vv{s}_i

(16)

이므로, 이 행렬은 $\vv{s}_2$ 를 죽이고( $i = 2$ 이면 계수가 0) 나머지는 살려 둔다. 죽이고 싶은 항마다 그런 행렬을 하나씩 곱하면 된다.

$c_1\vv{s}_1 + \cdots + c_n\vv{s}_n = \vv{0}$ 의 양변에 다음을 곱하자.

(A - \lambda_2 I)(A - \lambda_3 I)\cdots(A - \lambda_n I)

(17)

$i \ge 2$ 인 항은 $(A - \lambda_i I)$ 를 만나는 순간 계수가 $(\lambda_i - \lambda_i) = 0$ 이 되어 사라진다. $\vv{s}_1$ 만 살아남고, 계수는 각 인수가 남긴 것들의 곱이다.

c_1(\lambda_1 - \lambda_2)(\lambda_1 - \lambda_3)\cdots(\lambda_1 - \lambda_n)\,\vv{s}_1 = \vv{0}

(18)

고윳값이 서로 다르므로 괄호가 하나도 0이 아니고, $\vv{s}_1 \neq \vv{0}$ 이다. 따라서 $c_1 = 0$ 이어야 한다. 번호를 바꿔 가며 같은 일을 하면 모든 $c_i$ 가 0이다. 독립이다.

그러나 필요조건은 아니다¶

여기가 가장 흔한 오해가 생기는 자리이다. 고윳값이 서로 다른 것은 충분조건일 뿐이다. 같아도 대각화되는 경우가 있다.

3I = \begin{bmatrix} 3 & 0 \\ 0 & 3 \end{bmatrix}, \qquad B = \begin{bmatrix} 3 & 1 \\ 0 & 3 \end{bmatrix}

(19)

둘 다 고윳값이 3, 3 이다. 그런데 $3I$ 는 이미 대각행렬이고, 모든 방향이 고유벡터이다. $\Nul(3I - 3I) = \Nul(0)$ 이 $\R^2$ 전체이기 때문이다.

반면 $B$ 는 다르다.

B - 3I = \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}

(20)

랭크가 1이라 영공간이 1차원뿐이다. 독립인 고유벡터가 하나밖에 없으니 $S$ 의 두 열을 채울 수가 없다. 대각화할 수 없다.

Figure 3:고윳값이 같아도 운명이 갈린다. 중요한 것은 고유공간의 차원이다.

이런 행렬을 결함 행렬(defective matrix)이라 한다. 대각화가 안 되면 어떻게 하는가. 지금은 답하지 않는다. 여섯 강의 뒤 L28에서 조르당 형으로 다룬다.

5. 피보나치와 황금비¶

지금까지는 계산 이야기였다. 고윳값이 실제로 무언가를 설명하는 예를 하나 보자.

F_{k+1} = F_k + F_{k-1}, \qquad F_0 = 0,\quad F_1 = 1

(21)

수열 하나를 다루려면 벡터로 만들어야 한다. 연달아 두 개를 묶자.

\vv{u}_k = \begin{bmatrix} F_{k+1} \\ F_k \end{bmatrix} \qquad\Longrightarrow\qquad \vv{u}_{k+1} = \begin{bmatrix} F_{k+2} \\ F_{k+1} \end{bmatrix} = \begin{bmatrix} F_{k+1} + F_k \\ F_{k+1} \end{bmatrix}

(22)

오른쪽을 행렬로 쓰면 다음이 된다.

\vv{u}_{k+1} = A\vv{u}_k, \qquad A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}

(23)

점화식이 거듭제곱 문제로 바뀌었다. $\vv{u}_k = A^k\vv{u}_0$ 이다.

고윳값은 특성방정식을 세울 것도 없이 L21의 검산 도구로 나온다. $2 \times 2$ 의 특성다항식은 대각합과 행렬식만으로 적히기 때문이다(L21의 (12)).

\det(A - \lambda I) = \lambda^2 - \operatorname{tr}(A)\,\lambda + \det A

(24)

여기에 $\operatorname{tr}(A) = 1 + 0 = 1$ 과 $\det A = 1 \cdot 0 - 1 \cdot 1 = -1$ 을 넣으면

\lambda^2 - \lambda - 1 = 0 \qquad\Longrightarrow\qquad \lambda = \frac{1 \pm \sqrt5}{2}

(25)

이다. $\lambda_1 = \frac{1+\sqrt5}{2} \approx 1.618$ 이 황금비이고, $\lambda_2 = \frac{1-\sqrt5}{2} \approx -0.618$ 이다.

고유벡터도 구해 두자. $\lambda$ 가 고윳값일 때 $\vv{s} = (\lambda, 1)$ 이 고유벡터이다. 곱해 보면 확인된다.

A\begin{bmatrix} \lambda \\ 1 \end{bmatrix} = \begin{bmatrix} \lambda + 1 \\ \lambda \end{bmatrix} = \begin{bmatrix} \lambda^2 \\ \lambda \end{bmatrix} = \lambda\begin{bmatrix} \lambda \\ 1 \end{bmatrix}

(26)

가운데에서 $\lambda + 1$ 을 $\lambda^2$ 으로 바꿀 수 있는 것은 (25)의 특성방정식이 $\lambda^2 = \lambda + 1$ 이기 때문이다. 고유벡터의 두 성분의 비가 곧 고윳값이라는 점을 기억해 두자. 곧 쓸모가 있다.

$|\lambda_2| \approx 0.618 < 1$ 이라는 점이 중요하다. (13)에 의해 두 번째 항이 사라지므로

\vv{u}_k \approx c_1\lambda_1^k\,\vv{s}_1 = c_1\lambda_1^k \begin{bmatrix} \lambda_1 \\ 1 \end{bmatrix}

(27)

이다. 그런데 $\vv{u}_k = (F_{k+1}, F_k)$ 였다. 두 성분의 비를 보면 $c_1\lambda_1^k$ 이 약분되어 사라진다.

\frac{F_{k+1}}{F_k} \approx \frac{c_1\lambda_1^k \cdot \lambda_1}{c_1\lambda_1^k \cdot 1} = \lambda_1 \qquad\Longrightarrow\qquad \frac{F_{k+1}}{F_k} \longrightarrow \frac{1 + \sqrt5}{2}

(28)

비가 황금비로 수렴한다. 수렴이 빠른 것은 |\lambda_2/\lambda_1| \approx 0.38 이라 두 번째
항이 빠르게 죽기 때문이다. — Figure 4:비가 황금비로 수렴한다. 수렴이 빠른 것은 $|\lambda_2/\lambda_1| \approx 0.38$ 이라 두 번째 항이 빠르게 죽기 때문이다.

비네 공식 — 전개를 끝까지 쓴다¶

$\approx$ 를 $=$ 로 바꾸면, 곧 (11)의 두 항을 모두 살리면 $F_k$ 의 닫힌 꼴이 나온다. 필요한 것은 $c_1$ 과 $c_2$ 뿐이다.

시작 벡터는 $\vv{u}_0 = (F_1, F_0) = (1, 0)$ 이다. 이것을 두 고유벡터로 펼친다.

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

(29)

성분별로 쓰면 방정식이 둘이다.

c_1\lambda_1 + c_2\lambda_2 = 1, \qquad c_1 + c_2 = 0

(30)

아래 식에서 $c_2 = -c_1$ 이므로 위 식에 넣으면 $c_1$ 이 바로 나온다.

c_1(\lambda_1 - \lambda_2) = 1 \qquad\Longrightarrow\qquad c_1 = \frac{1}{\lambda_1 - \lambda_2}

(31)

두 고윳값의 차는 뿌리 부분만 남는다.

\lambda_1 - \lambda_2 = \frac{1+\sqrt5}{2} - \frac{1-\sqrt5}{2} = \sqrt5 \qquad\Longrightarrow\qquad c_1 = \frac{1}{\sqrt5}, \quad c_2 = -\frac{1}{\sqrt5}

(32)

$\sqrt5$ 가 여기서 들어온다. 이제 (11)의 전개를 그대로 쓴다.

\vv{u}_k = \frac{1}{\sqrt5}\lambda_1^k\begin{bmatrix} \lambda_1 \\ 1 \end{bmatrix} - \frac{1}{\sqrt5}\lambda_2^k\begin{bmatrix} \lambda_2 \\ 1 \end{bmatrix}

(33)

$F_k$ 는 $\vv{u}_k$ 의 둘째 성분이고, 두 고유벡터의 둘째 성분은 모두 1이다. 그러므로 둘째 줄만 읽으면 된다.

F_k = \frac{\lambda_1^k - \lambda_2^k}{\sqrt5} = \frac{1}{\sqrt5}\left[\left(\frac{1+\sqrt5}{2}\right)^k - \left(\frac{1-\sqrt5}{2}\right)^k\right]

(34)

비네 공식이라 부르는 것이다. $k = 10$ 을 넣으면 정확히 55가 나온다.

정수만 나오는 수열의 공식에 $\sqrt5$ 가 세 번이나 들어 있는 것이 재미있다. $\lambda_2$ 쪽 항은 $|\lambda_2| < 1$ 이라 $k$ 가 조금만 커져도 $\tfrac12$ 보다 작아지므로, $\lambda_1^k/\sqrt5$ 를 반올림하면 그것이 $F_k$ 이다.

6. 자주 하는 오해¶

고윳값이 서로 달라야 대각화된다¶

4절의 $3I$ 와 $B$ 대조가 이 오해를 겨냥한 것이다. 조건은 고유공간의 차원이다.

$S$ 의 열 순서와 $\Lambda$ 의 대각 순서를 다르게 놓는다¶

1절의 경고 그대로이다. 순서가 어긋나면 $AS = S\Lambda$ 가 성립하지 않는다.

$A^k \to 0$ 을 " $A$ 가 작아서"로 읽는다¶

3절의 상자 그대로이다. 성분이 아니라 고윳값의 크기이다.

대각화와 특이값 분해를 같은 것으로 여긴다¶

대각화는 기저가 한 벌이다. 들어갈 때와 나올 때 같은 $S$ 를 쓴다. 특이값 분해는 기저가 두 벌이라 들어가는 쪽과 나오는 쪽이 다르다. 그래서 특이값 분해는 정사각이 아닌 행렬에도, 대각화가 안 되는 행렬에도 언제나 존재한다. L29의 이야기이다.

마치며...¶

이번 강의에서 다룬 것을 정리하면 다음과 같다.

대상	내용
유도	$AS = S\Lambda$ 에서 $A = S\Lambda S^{-1}$
세 단계	$S^{-1}$ 로 번역, $\Lambda$ 로 계산, $S$ 로 역번역
거듭제곱	$A^k = S\Lambda^k S^{-1}$ . 가운데가 전부 상쇄된다
수렴	모든 $\lvert\lambda\rvert < 1$ 이면 $A^k \to 0$
지배 고윳값	여러 번 곱하면 가장 큰 것만 살아남는다
대각화 조건	독립인 고유벡터 $n$ 개. 고윳값이 다른 것은 충분조건일 뿐
결함 행렬	고유공간이 모자란 경우. L28에서 다룬다
피보나치	황금비가 지배 고윳값이라서 비가 그리로 간다

대각화란 결국 좋은 좌표계를 고르는 일이다. 이 관점은 앞으로 여러 번 되돌아온다. 그리고 고윳값의 절댓값이 1보다 작으면 거듭제곱이 0으로 수렴한다는 것도 배웠다. 복소평면의 단위원 하나로 시스템의 운명이 결정되는 셈이다.

이번에도 대각화가 안 되는 행렬을 그냥 지나쳤다. 언젠가는 답해야 할 물음이다. 그러나 그전에 할 일이 있다.

다음 강의에서는 방금 배운 대각화를 무기 삼아 전혀 달라 보이는 문제를 푼다. 미분방정식이다. 선형대수 강의에 왜 미분방정식이 나오는지 곧 알게 된다.

이번 강의의 내용을 파이썬으로 확인해 보려면 L22 실습 노트북으로 넘어가면 된다. $S\Lambda S^{-1}$ 로 $A^{100}$ 을 구해 직접 곱한 것과 대조하고, 고윳값의 위치에 따라 $A^k$ 가 어떻게 되는지 보며, 피보나치 비가 황금비로 가는 것을 확인할 수 있다.