코딩 더 매트릭스 - 13장 고유벡터 (1)

필립 클라인의 저서 코딩 더 매트릭스 13장 고유벡터

---

1. 대각행렬과 벡터의 곱, 피보나치 행렬을 보고 행렬의 대각화를 이해합니다.
2. 고유값과 고유벡터에 대해 알아봅니다.
3. 유사행렬과 대각화가 가능한 조건에 대해 알아봅니다.
4. 대칭행렬과 상삼각행렬에 대한 대각화의 경우를 알아봅니다.
5. 누승법에 대해 알아봅니다.

---

대각행렬과의 곱

이자가 붙는 두 개의 은행 계좌에 돈을 예치한다고 가정해 보겠습니다. 첫번째 계좌는 연간 5%, 두번째 계좌는 연간 3%의 이자를 줍니다. $t$년이 경과한 후 두 계좌의 잔고를 2-벡터로 다음과 같이 표현할 수 있습니다.

$$x_{t + 1} = \begin{bmatrix} 1.05 & 0 \\ 0 & 1.03 \end{bmatrix} x_t$$

$A = \begin{bmatrix}1.05 & 0 \\ 0 & 1.03 \end{bmatrix}$일 때 $A$는 대각행렬입니다. 100년이 경과했다면 아래와 같이 쓸 수 있습니다.

$$\begin{aligned} x_{100} & = Ax_{99} \\ & = A(Ax_{98}) \\ & ... \\ & = \underbrace{A ... A}_{100} x_0 \end{aligned}$$

여기서 행렬 $A ... A = A^{100}$이고 $A$는 대각행렬이므로 $A$의 대각원소는 $1.05^{100} \approx 131$, $1.03^{100} \approx 19$입니다. 시간이 경과함에 따라 첫번째 계좌의 잔고는 두번째 계좌의 잔고보다 압도적으로 많아지게 됩니다.

이번에는 피보나치 수열의 행렬 곱셈 표현을 살펴보겠습니다. 피보나치 수열은 다음과 같은 규칙을 가집니다.

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

피보나치 수는 토끼의 개체 수 증가에 대한 문제로부터 유래했습니다. 개체 수 문제를 다음과 같이 단순화해 정리해 보겠습니다.

• 매월 각 성인 토끼는 한 마리의 아기 토끼를 낳는다.
• 아기 토끼는 성인이 되는데 한 달이 걸린다.
• 토끼는 죽지 않는다.

$x_1$은 성인 토끼 수, $x_2$는 아기 토끼 수라 할 때 2-벡터 $x = \begin{bmatrix}x_1 \\ x_2\end{bmatrix}$는 현재 토끼의 개체 수를 나타냅니다. $t$개월 후의 토끼 수를 $x_t$라 할 때 다음과 같이 쓸 수 있습니다.

$$x_{t + 1} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} x_t$$

은행계좌에서와 같이 $x_t = A^tx_0$라 쓸 수 있습니다. 이 때 은행계좌 문제와는 달리 $A$가 대각행렬이 아니므로 직접 행렬 곱셈 $A^tx_0$를 수행해야할 것처럼 보입니다. 하지만 다음을 만족하는 행렬 $S$와 대각행렬 $\Lambda$가 존재합니다.

$$\begin{aligned} A = S \Lambda S^{-1} \\ \Lambda = S^{-1} A S \end{aligned}$$

$A = S \Lambda S^{-1}$를 식 $x_t = A^tx_0$에 적용하면 다음을 얻습니다.

$$\begin{aligned} x_t & = (S \Lambda S^{-1})^t x_0 \\ & = \underbrace{(S \Lambda S^{-1}) (S \Lambda S^{-1}) ... (S \Lambda S^{-1})}_{t} x_0 \\ & = S \Lambda^t S^{-1} x_0 \end{aligned}$$

행렬 $A = \begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}$는 실제 아래와 같은 행렬 $S$와 대각행렬 $\Lambda$로 표현할 수 있습니다.

$$S = \begin{bmatrix} \frac{1 + \sqrt{5}}{2} & \frac{1 - \sqrt{5}}{2} \\ 1 & 1 \end{bmatrix} \Lambda = \begin{bmatrix} \frac{1 + \sqrt{5}}{2} & 0 \\ 0 & \frac{1 - \sqrt{5}}{2} \end{bmatrix}$$

피보나치 행렬의 대각화

토끼의 개체수 문제 중 식 $x_t = S \Lambda^t S^{-1}x_0$은 분석하기에 용이하지 않습니다. 벡터 $x_t$를 행렬 $S$의 열벡터를 기저로 한 좌표표현으로 변환해 보겠습니다. 그러면 아래와 같이 쓸 수 있습니다.

$$\begin{aligned} x_t = S u_t \\ S^{-1} x_t = u_t \end{aligned}$$

$x_t = S \Lambda^t S^{-1}x_0$에 위 식을 대입하면 다음과 같습니다.

$$\begin{aligned} & x_t = S \Lambda^t S^{-1}x_0 \\ & S u_t = S \Lambda^t u_0 \\ & S^{-1} S u_t = S^{-1} S \Lambda^t u_0 \\ & u_t = \Lambda^t u_0 \end{aligned}$$

$\Lambda$는 대각행렬이므로 이전보다 좀 더 응용하기에 용이해졌습니다.

어떤 정방행렬을 그 오른쪽에 행렬 $S$, 왼쪽에 행렬 $S^{-1}$을 곱함으로써 대각행렬을 만드는 기법을 대각화라고 합니다.

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

고유값과 고유벡터

정방행렬 $A$와 스칼라 $\lambda$, 영이 아닌 벡터 $v$에 대해 $Av = \lambda v$가 만족되는 경우 $\lambda$를 $A$의 고유값(eigen value), $v$를 대응하는 고유벡터(eigen vector)라 합니다.

만약 $\lambda$가 $A$의 고유값이면 대응하는 고유벡터는 무수히 많습니다. 집합 $\{v : Av = \lambda v\}$는 벡터공간이며 고유값 $\lambda$에 대응하는 고유공간이라 합니다. 일반적으로 norm이 1인 고유벡터를 선택합니다. 피보나치 수를 분석하는데 쓰인 행렬 $\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}$의 고유값은 $\lambda_1 = \frac{1 + \sqrt{5}}{2}$, $\lambda_2 = \frac{1 - \sqrt{5}}{2}$ 이고 대응하는 고유벡터는 각각 $\begin{bmatrix}\frac{1 + \sqrt{5}}{2} \\ 1\end{bmatrix}$, $\begin{bmatrix}\frac{1 - \sqrt{5}}{2} \\ 1\end{bmatrix}$ 였습니다.

한편 행렬 $A$의 한 고유값이 0이면 이 고유값에 대응하는 고유벡터 $v$는 $A$의 영공간입니다. $Av = 0v$ 일 때 $v$가 영벡터가 아니기 때문입니다. 역으로 $A$의 영공간이 자명하지 않으면(영벡터가 아니면) $A$는 고유값 0을 갖습니다.

0이 아닌 고유값에 대응하는 고유벡터는 어떻게 찾을 수 있을까요? 식 $Av = \lambda v$를 아래와 같이 바꿔 쓸 수 있습니다.

$$(A - \Lambda I)v = 0$$

고유값 $\lambda$에 대해 벡터 $v$는 $A - \Lambda I$의 영공간에 속하는 영이 아닌 벡터입니다. $A - \Lambda I$가 역행렬이 존재한다면 $v = 0$이므로 고유벡터의 정의에 어긋납니다. 따라서 $A - \Lambda I$는 비가역적입니다. 정리하면 다음과 같이 쓸 수 있습니다.

• $\lambda$ 가 $A$의 고유값이 될 필요충분조건은 $A - \Lambda I$가 비가역적인 경우입니다.
• 만약 $\lambda$가 $A$의 고유값이면 대응하는 고유공간은 $A - \Lambda I$의 영공간입니다.

식 $(A - \Lambda I)v = 0$에서 $(A - \Lambda I)^T = A^T - \Lambda I$입니다. 따라서 $\lambda$는 $A$와 $A^T$의 고유값입니다.

유사 행렬과 대각화 가능성

정방행렬 $A$에 대해 $B = S^{-1} A S$를 만족하는 정방행렬 $B$가 있다면 $B$는 $A$의 유사 행렬이라 합니다. 유사행렬은 같은 고유값을 가집니다. $A$의 고유값 $\lambda$에 대한 식 $Av = \lambda v$와 $B = S^{-1} A S$ 식으로 이를 증명할 수 있습니다.

먼저 $B = S^{-1} A S$는 $A = S B S^{-1}$로 바꿔 쓸 수 있습니다. 이를 식 $Av = \lambda v$에 대입하면 아래와 같습니다.

$$S B S^{-1}v = \lambda v$$

위 식의 앙변에 $S^{-1}$를 곱하면 아래와 같은 식을 얻습니다.

$$B S^{-1}v = S^{-1} \lambda v = \lambda S^{-1} v$$

$w = S^{-1}v$라 하면 $Bw = \lambda w$라 쓸 수 있고 이는 고유값 $\lambda$와 대응하는 고유벡터 $w = S^{-1}v$가 존재함을 뜻합니다. 따라서 $\lambda$는 $B$의 고유값입니다.

만약 어떤 행렬 $A$가 대각행렬과 유사행렬이면, 즉 대각행렬 $\Lambda$에 대해 $S^{-1} A S = \Lambda$를 만족하는 $S$가 존재하면 $A$는 대각화 가능하다(diagonalizable)고 합니다.

만약 $\Lambda$가 대각행렬 $\begin{bmatrix} \lambda_1 & \text{ } & \text{ } \\ \text{ } & ... & \text{ } \\ \text{ } & \text{ } & \lambda_n \\ \end{bmatrix}$ 라면 행렬의 고유값은 $\lambda_1, ..., \lambda_n$입니다. 행렬 $A$와 $\Lambda$가 유사행렬이라면 $A$의 고유값은 $\Lambda$의 고유값, 즉 $\Lambda$의 대각 원소들입니다.

식 $S^{-1} A S = \Lambda$는 양변에 $S$를 곱해 $AS = S \Lambda$로 쓸 수 있습니다. 양변을 행렬-벡터 곱셈의 관점에서 해석해 보겠습니다. 좌변의 $i$번째 열은 행렬 $A$와 $S$의 $i$번째 열의 행렬-벡터 곱셈입니다. 우변의 $i$번째 열은 $S$의 $i$번째 열과 $\Lambda$의 $i$번째 대각원소의 스칼라-벡터 곱입니다. 이 해석은 $Av = \lambda v$와 같습니다. 따라서 $S$의 한 열벡터는 $\Lambda$의 대각원소, 즉 고유값에 대응하는 고유벡터입니다. 행렬 $S$의 열벡터들은 가역적이므로 일차독립입니다. 따라서 고유벡터들은 일차독립입니다. 역으로 $A$가 일차독립인 고유벡터들을 가진다고 할 때 행렬 $S$를 $\begin{bmatrix} \text{ } & \text{ } & \text{ } \\ v_1 & ... & v_n \\ \text{ } & \text{ } & \text{ } \end{bmatrix}$라 하면 $AS = S \Lambda$가 성립하고 $S$는 가역적이므로 양변에 $S^{-1}$을 곱해 $A = S \Lambda S^{-1}$ 형태로 대각화 가능합니다. 정리하면, 행렬이 대각화 가능할 필요충분조건은 이 행렬이 $n$개의 일차독립인 고유벡터를 가지는 것입니다.

고유벡터에 대한 좌표표현

앞서 $S$의 열벡터를 기저로 하는 좌표표현으로의 변경을 위해 식 $x_t = S u_t$와 $x_t = A^t x_0 = S \Lambda^t S^{-1} x_0$을 이용해 $u_t = \Lambda^t u_0$을 이끌어 냈습니다. 이것을 다른 각도에서 한번 살펴보겠습니다.

행렬 $A$의 고유벡터들 $v_1, ..., v_n$이 있을 때 이들은 $\Bbb{R^n}$의 기저를 형성합니다. 임의의 벡터 $x$는 아래와 같이 표현가능합니다.

$$x = \alpha_1 v_1 + ... + \alpha_n v_n$$

위 식의 양변에 $A$를 곱하면 다음과 같습니다.

$$\begin{aligned} Ax & = \alpha_1 A v_1 + ... + \alpha_n A v_n \\ & = \alpha_1 \lambda_1 v_1 + ... + \alpha_n \lambda_n v_n (\because Av = \lambda v) \end{aligned}$$

위 식에 다시 한번 $A$를 곱하면 $A^2x = \alpha_1 \lambda_1^2 v_1 + ... + \alpha_n \lambda_n^2 v_n$을 얻습니다. 연속해서 $A$를 곱할 때 $A^t x = \alpha_1 \lambda_1^t v_1 + ... + \alpha_n \lambda_n^t v_n$을 얻습니다. 만약 $\lambda_1$의 절대값이 다른 고유값들보다 크다면 충분히 큰 $t$에 대해 다음을 얻게 됩니다.

$$A^t x \approx \alpha_1 \lambda_1^t v_1$$

실제로 절대값이 1보다 작은 고유값을 포함한 항은 $t$가 증가함에 따라 점점 작아지게 됩니다.

인터넷 웜

웜은 네트워크를 통해 복제되어 퍼져 나가는 프로그램입니다. 하나의 컴퓨터에서 실행되는 프로그램 인스턴스가 다른 주변 컴퓨터에 침투하여 이들 컴퓨터에 자신의 복사본을 만들어 실행하게 합니다. 이러한 웜의 동작을 나타내는 단순한 모델을 분석해보겠습니다. 인터넷은 삼각형으로 연결된 세 개의 컴퓨터로 단순화합니다. 웜은 매 이터레이션마다 $\frac{1}{10}$의 확률로 이웃하는 컴퓨터에 자신의 복제본을 생성합니다. 그리고 $\frac{1}{7}$의 확률로 절대 죽지 않는(immortal) 웜이 됩니다. $x_i$를 컴퓨터 $i$의 일반적인(mortal) 웜, $y_i$를 죽지 않는 웜이라 하면 다음과 같은 행렬-벡터 곱셈을 쓸 수 있습니다.

$$\begin{bmatrix} 0 & 0 & \frac{1}{10} & \frac{1}{10} & \frac{1}{10} & \frac{1}{10} \\ \frac{1}{7} & 1 & 0 & 0 & 0 & 0 \\ \frac{1}{10} & \frac{1}{10} & 0 & 0 & \frac{1}{10} & \frac{1}{10} \\ 0 & 0 & \frac{1}{7} & 1 & 0 & 0 \\ \frac{1}{10} & \frac{1}{10} & \frac{1}{10} & \frac{1}{10} & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{7} & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ y_1 \\ x_2 \\ y_2 \\ x_3 \\ y_3 \end{bmatrix} = \begin{bmatrix} x_{1-next} \\ y_{1-next} \\ x_{2-next} \\ y_{2-next} \\ x_{3-next} \\ y_{3-next} \end{bmatrix}$$

위 식은 $x_t = A^t x_0$로 일반화 할 수 있고 이 때 행렬 $A$의 가장 큰 고유값은 $1.034$ 입니다. 따라서 $A^t$의 고유값은 $1.034^t$이고 이는 이터레이션이 늘어날 때마다 웜수는 기하급수적으로 늘어남을 의미합니다.

고유값의 존재

어떤 상황에서 행렬이 고유값을 가지게 될까요? 임의의 가역행렬 $A$에 대해 $A^T A$를 살펴 보겠습니다. $A$를 특이값 분해하면 다음과 같습니다.

$$A = U \Sigma V^T$$

$A^T A$는 다음과 같습니다.

$$\begin{aligned} A^T A & = V \Sigma U^T U \Sigma V^T \\ & = V \Sigma I \Sigma V^T \\ & = V \Sigma^2 V^T \end{aligned}$$

위 식에서 $V$는 정규직교 행렬이고 정규직교 행렬은 $V V^T = I$와 같은 성질을 가지므로 $V^T$는 $V$의 역행렬입니다. 따라서 $V \Sigma^2 V^T$와 같은 형태는 $V^{-1} \Sigma^2 V$ 또는 $V \Sigma^2 V^{-1}$와 같고 이는 $A^T A$가 고유값을 가짐을 의미합니다. 이 때 고유값은 $A$의 특이값의 제곱입니다. 한편 $A^T A$는 $(A^T A)^T = A^T A$인 대칭행렬입니다.

앞서 식 $AS = S \Lambda$에서 행렬 $S$가 가역적이므로 고유벡터들은 일차독립임을 보았습니다. 행렬 $A$의 고유값으로 이루어진 집합 $T$에 대해 대응하는 고유벡터들은 일차독립임을 증명해 보겠습니다.

고유벡터들 $v_1, ..., v_r$이 일차종속이면 아래 식의 계수 $\alpha_1, ..., \alpha_r$은 적어도 하나는 0이 아닙니다.

$$\alpha_1 v_1 + ... + \alpha_r v_r = 0$$

이 때 위 식의 선형결합은 최소로 필요한 벡터 $v_i$를 선택했다고 하겠습니다. $\lambda_1, ..., \lambda_r$이 대응하는 고유값이라면 다음이 성립합니다.

$$\begin{aligned} 0 & = A(0) \\ & = A(\alpha_1 v_1 + ... + \alpha_r v_r) \\ & = \alpha_1 \lambda_1 v_1 + ... + \alpha_r \lambda_r v_r \end{aligned}$$

식 $\alpha_1 v_1 + ... + \alpha_r v_r = 0$에 $\lambda_1$을 곱하고 위 식에서 빼면 다음을 얻습니다.

$$0 = \alpha_2 (\lambda_1 - \lambda_2) + ... + \alpha_r (\lambda_1 - \lambda_r)$$

식 $\alpha_1 v_1 + ... + \alpha_r v_r = 0$은 최소의 벡터들 $v_i$를 선택했지만 위 식에서 그보다 적은 벡터로 일차종속임을 보였으므로 이는 일차종속의 가정에 어긋납니다. 따라서 고유벡터 $v_1, ..., v_r$은 일차독립입니다.

대칭행렬과 상삼각행렬

대칭행렬의 대각행렬은 $\Lambda = S^T A S$의 형태를 가집니다. $A = S \Lambda S^{-1}$과 $A^T = (S^{-1})^T \Lambda^T S^T$을 바탕으로 이를 이끌어 낼 수 있습니다.

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

위 식에서 $S^{-1} = S^T$일 때 양변이 같아집니다. 따라서 $\Lambda = S^T A S$ 이 성립합니다.

상삼각행렬의 경우 대각원소가 곧 고유값입니다. 상삼각행렬 $U$가 있다고 할 때 $U - \Lambda I$가 비가역적이면 고유값을 가지게 됩니다. 이 때 $U - \Lambda I$는 상삼각행렬이고 상삼각행렬이 가역적일 필요충분조건은 대각 원소가 모두 0이 아닌 경우입니다. 역으로 비가역적일 조건은 대각 원소 중 하나라도 0인 경우입니다. $\Lambda$의 한 대각 원소가 $\lambda$이고 $U$의 대응하는 한 대각원소가 $\lambda$라면 비가역적일 조건이 충족됩니다. 따라서 고유값 $\lambda$는 $U$의 대각원소입니다.

누승법

$A$가 대각화 가능한 행렬로 $n$개의 서로 다른 고유값 $\lambda_1, ..., \lambda_n$을 가질 때 고유값을 크기 순으로 정렬하면 $|\lambda_1| \ge |\lambda_2| ... \ge |\lambda_n|$ 입니다. 대응하는 일차독립인 고유벡터 $v_1, ..., v_n$이 있을 때 랜덤벡터 $x_0$는 다음과 같이 $\Bbb{R^n}$의 기저를 형성하는 고유벡터들의 선형결합으로 나타낼 수 있습니다.

$$x_0 = \alpha_1 v_1 + ... + \alpha_n v_n$$

$x_t = A^t x_0$ 라 할 때 $x_t$는 아래와 같이 쓸 수 있습니다.

$$\begin{aligned} x_t & = \alpha_1 A v_1 + ... + \alpha_n A v_n \\ & = \alpha_1 \lambda_1^t v_1 + ... + \alpha_n \lambda_n^t v_n \end{aligned}$$

이 때 $t$가 증가할 때마다 $v_1$의 계수 $\alpha_1 \lambda_1^t$는 압도적으로 커져 $x_t$는 $\alpha_1 \lambda_1^t v_1 + error$로 쓸 수 있습니다. 여기서 $error$는 $\alpha_1 \lambda_1^t v_1$보다 훨씬 작은 벡터입니다. $v_1$이 고유벡터이므로 $\alpha_1 \lambda_1^t v_1$도 고유벡터입니다. $x_t$는 결국 고유벡터에 근사한 벡터, 즉 근사 고유벡터(approximate eigen vector)가 됩니다. 더욱이 $A x_t$는 $\lambda_1 x_t$로 수렴할 것입니다.

이처럼 절대값이 가장 큰 고유값에 가까운 근사 고유값과 이 근사 고유값에 대응하는 고유벡터를 찾는 방법을 누승법이라 합니다.