선형대수 note 22: Diagonalization and Powers of A

행렬의 대각화

n \times n 행렬 A 에서 n 개의 선형독립인 고유벡터 \mathbf{x}_i 가 존재한다고 가정하자.1 행렬 S 의 열들은 \mathbf{x}_i 로 이루어져 있다고 할때,

    \[\begin{aligned} AS &=  A \begin{bmatrix}     \mathbf{x}_1 & \mathbf{x}_2 & \cdots & \mathbf{x}_n \end{bmatrix} \\ &= \begin{bmatrix}     \lambda_1 \mathbf{x}_1 & \lambda_2 \mathbf{x}_2 \cdots & \lambda_n \mathbf{x}_n \end{bmatrix} \\ & = \begin{bmatrix}     \mathbf{x}_1 & \mathbf{x}_2 & \cdots & \mathbf{x}_n \end{bmatrix} \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 \end{aligned}\]

양변의 좌측에 S^{-1} 를 곱하면,

    \[S^{-1} A S = \Lambda\]

이것을 행렬의 대각화 (Diagonalization) 라고 한다.2
S 의 열들이 선형독립이므로 S^{-1} 이 존재한다. 만약 행렬 A 로 부터 n 개의 선형독립인 고유벡터가 존재하지 않는다면 대각화할 수 없다.

대각화 가능 행렬

n \times n 행렬 A고유값이 n 개의 서로 다른 값을 가진다면 n 개의 선형독립인 고유벡터가 존재하는 것을 보장한다. 그러므로 A 는 대각화가 가능하다. 하지만 중복되는 고유값을 가진다면 n 개의 선형독립인 고유벡터가 존재하지 않을 수도 있다.

증명)

서로 다른 고유값에 대응하는 고유벡터 \mathbf{x}_1, \mathbf{x}_2 가 있다고 하자. \mathbf{x}_1, \mathbf{x}_2 는 선형독립인지 아닌지 아직 알 수 없다. 하지만 c_1 \mathbf{x}_1 + c_2 \mathbf{x}_2 = 0 를 만족하는 c_1, c_2 가 오직 0 임을 보이면 \mathbf{x}_1, \mathbf{x}_2 는 선형 독립이다. A 를 곱하면,

    \[c_1 \lambda_1 \mathbf{x}_1 + c_2 \lambda_2 \mathbf{x}_2 = 0\]

A 대신에 \lambda_2 을 곱하면,

    \[c_1 \lambda_2 \mathbf{x}_1 + c_2 \lambda_2 \mathbf{x}_2 = 0\]

이제 두 식을 빼면,

    \[c_2 (\lambda_1 - \lambda_2) \mathbf{x}_1 = 0\]

고유값들은 서로 다르고, \mathbf{x}_1 \neq \mathbf{0} 이므로 위의 식을 만족하려면 c_10 이어야 한다. 같은 방법으로 c_20 이어야 한다는 결론에 도달한다. c_1 = c_2 = 0 이 아닌 다른 어떤 선형 결합도 c_1 \mathbf{x}_1 + c_2 \mathbf{x}_2 = 0 을 만족하지 않는다. 즉, \mathbf{x}_1, \mathbf{x}_2 는 선형 독립이다.

고유값 분해 (Eigendecomposition)

AS = S\Lambda 에서 양변의 우측에 S^{-1} 를 곱하면,

    \[A = S \Lambda S^{-1}\]

이것을 고유값 분해 (Eigendecomposition) 또는 스펙트럼 분해 (Spectral decomposition) 라고 부른다. 고유값 분해는 언제 유용할까?
같은 행렬을 여러번 곱해야 하는 경우를 생각해보자. A 는 대각화 가능할 때,

    \[\begin{aligned} A^k &= S \Lambda S^{-1} S \Lambda S^{-1} \dots S \Lambda S^{-1} \\ &= S \Lambda^{k} S^{-1} \\ &= S \begin{bmatrix} \lambda_1^k & 0 & \cdots & 0 \\     0 & \lambda_2^k & \cdots & 0 \\     \vdots & \vdots & \ddots & \vdots \\     0 & 0 & \cdots & \lambda_n^k \end{bmatrix} S^{-1} \end{aligned}\]

이런식으로 행렬의 거듭제곱은 대각행렬 \Lambda 의 거듭제곱 형태로 나타낼 수 있다. 대각행렬의 제곱은 각 대각 성분 별 제곱의 형태가 된다. 행렬 A^kx 의 결과는 |\lambda_i| < 1 이면 점점 0 에 가까워지고, |\lambda_i| > 1 이면 점점 값이 커진다는 것을 알 수 있다.

행렬의 거듭 제곱 \mathbf{u}_k = A^k \mathbf{u}_0

고유값 분해를 이용해서 실제로 거듭제곱 형태를 풀 수 있다.
초기값 벡터 \mathbf{u}_0 에서 \mathbf{u}_1 으로의 변환 행렬 A 를 가정해보자. A 가 대각화 가능할 때 \mathbf{u}_0A 의 고유벡터들의 선형 결합으로 나타낼 수 있다.

    \[\mathbf{u}_0 &= c_1 \mathbf{x}_1 + c_2 \mathbf{x}_2 + \dots c_n \mathbf{x}_n = S\mathbf{c}\]

여기에 A 를 곱하면,

    \[A \mathbf{u}_0 = \mathbf{u}_1 = c_1 \lambda_1 \mathbf{x}_1 + c_2 \lambda_2 \mathbf{x}_2 + \dots c_n \lambda_n \mathbf{x}_n = S\Lambda\mathbf{c}\]

    \[A^k \mathbf{u}_0 = \mathbf{u}_k = c_1 \lambda_1^k \mathbf{x}_1 + c_2 \lambda_2^k \mathbf{x}_2 + \dots c_n \lambda_n^k \mathbf{x}_n = S\Lambda^k\mathbf{c}\]

이제 대각화 가능 행렬 A 의 고유값, 고유벡터와 u_0 의 고유벡터 계수 c 를 구하면 u_k 를 구할 수 있다.

피보나치 수열

피보나치 수열 (Fibonacci Numbers) 은 01 로 시작하며, 다음 두 피보나치 수는 바로 앞의 두 피보나치 수의 합이 된다. 일반적으로 피보나치 수열의 100 번째 값을 구하려면 100 번의 연산이 필요하다.

    \[0, 1, 1, 2, 3, 5, 8, 13, \dots \quad F_{k+2} = F_{k+1} + F_k\]

이것을 선형 변환 행렬 A 로 나타내면,

    \[\begin{aligned} F_{k+2} &= F_{k+1} + F_k \\ F_{k+1} &= F_{k+1} \end{aligned} \quad \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} \quad A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\]

행렬 A 의 고유값은,

    \[det(A - \lambda I)  = \begin{vmatrix} 1 - \lambda & 1 \\ 1 & -\lambda \end{vmatrix}  = (1 - \lambda) (-\lambda) - 1  = \lambda^2 - \lambda - 1 = 0\]

의 해가 되어 \lambda_1 = \frac{1 + \sqrt{5}}{2}, \lambda_2 = \frac{1 - \sqrt{5}}{2} 가 된다. \lambda_1, \lambda_2 는 서로 다른 고유값이므로 A 는 대각화가 가능하다. 이어서 고유벡터들을 구하면,

    \[\begin{bmatrix} 1 - \lambda & 1 \\ 1 & -\lambda \end{bmatrix} \mathbf{x}  = 0 \quad \mathbf{x}_1 = \begin{bmatrix} \lambda_1 \\ 1 \end{bmatrix},\  \mathbf{x}_2 = \begin{bmatrix} \lambda_2 \\ 1 \end{bmatrix}\]

초기값은 \mathbf{u}_0 = \begin{bmatrix} 1 \\ 0 \end{bmatrix} 이므로 선형결합 계수 벡터 \mathbf{c} 는,

    \[\mathbf{u}_0 = c_1 \mathbf{x_1} + c_2 \mathbf{x_2}  = c_1 \begin{bmatrix} \lambda_1 \\ 1 \end{bmatrix} +  c_2 \begin{bmatrix} \lambda_2 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}\]

    \[c_1 = \frac{1}{\lambda_1 - \lambda_2},\ c_2 = -\frac{1}{\lambda_1 - \lambda_2}\]

가 되고 \mathbf{u}_k 는,

    \[\begin{aligned} \mathbf{u}_k &= S \Lambda^k \mathbf{c} \\ &= \begin{bmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} \lambda_1 ^k & 0 \\ 0 & \lambda_2 ^k \end{bmatrix}  \begin{bmatrix} \frac{1}{\lambda_1 - \lambda_2} \\ -\frac{1}{\lambda_1 - \lambda_2} \end{bmatrix} \\ & = \begin{bmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} \frac{\lambda_1^k}{\lambda_1 - \lambda_2} \\ -\frac{\lambda_2^k}{\lambda_1 - \lambda_2} \end{bmatrix} \end{aligned}\]

k 번째 피보나치 수 F_k\mathbf{u}_k 의 두번째 성분이므로,

    \[\begin{aligned} F_{k} &= \frac{\lambda_1^k - \lambda_2^k}{\lambda_1 - \lambda_2},\quad \lambda_1 = \frac{1 + \sqrt{5}}{2},\ \lambda_2 = \frac{1 - \sqrt{5}}{2} \\ &= \frac{1}{\sqrt{5}} \left( \left(\frac{1 + \sqrt{5}}{2}\right)^k - \left(\frac{1 - \sqrt{5}}{2}\right)^k \right) \end{aligned}\]

아래는 피보나치 수를 구하는 swift 코드다.


선형대수 note 목록

  1. 항상 선형독립인 고유벡터가 존재하는 건 아니다.
  2. AS 에 의해서 대각화된다.

Leave a Reply

Your email address will not be published. Required fields are marked *