Diagonalization and powers of A

1. 행렬의 대각화(Diagonalization)

1.1 $AS = S \Lambda, \;  S^{-1} A S = \Lambda$

■ 고유방정식 $A \mathbf{x} = \lambda \mathbf{x}$에서 $\lambda$는 고윳값, $\mathbf{x}$는 고유벡터이다. 

■ 고유방정식은 행렬 $A$에 의해 선형변환된 $A \mathbf{x}$가 방향은 유지하면서 길이(크기)만 달라지는(즉, 스칼라배가 되는) 특수한 벡터인 고유벡터와 그때 적용되는 스칼라인(길이(크기)의 변화량을 나타내는) 고윳값 $\lambda$을 나타낸다.

■ 선형변환은 선형변환의 행렬표현인 $A$가 $\mathbf{x}$에 적용될 때, 대부분의 벡터는 크기와 방향이 모두 달라지지만, 특별한 경우 선형변환된 $A \mathbf{x}$가 원래 벡터 $\mathbf{x}$와 단지 길이(크기)가 고윳값 $\lambda$만큼 변화된  $\mathbf{x}$와 평행한 벡터가 된다. 이때의 $\lambda$가 고윳값, $\mathbf{x}$가 고유벡터가 된다.

■ 고윳값과 고유벡터를 알면, 선형변환의 행렬표현인 행렬 $A$의 특성을 알 수 있으며, 이를 응용할 수 있는데 그 중 하나가 행렬의 대각화이다.

■ 행렬의 대각화에 대한 식은 $S^{-1} A S = \Lambda$이다.

- 여기서 행렬 행렬 $A$는 $n \times n$ 크기의 행렬로 $n$개의 고윳값과 고유벡터를 갖는다.

- 행렬 $A$는 $n \times n$ 정방행렬이므로 행렬 $S$도 $n \times n$ 크기의 정방행렬이다. 

- 행렬 $S$는 행렬 $A$의 고유벡터들이 열벡터로 구성된 행렬이다. 이 행렬 $S$를 고유벡터 행렬이라고 부른다.

- 행렬 $A$의 앞에는 $S^{-1}$과 뒤에는 $S$가 곱해지며, $S^{-1} A S$의 계산 결과가 대각행렬 $\Lambda$이다. 이 대각행렬의 대각 원소들은 고윳값들의 순서대로 $\lambda_1, \lambda_2, \cdots, \lambda_n$ 채워진다.

■ \( S^{-1} A S = \Lambda \)에서 행렬 $S$는  행렬 $A$의 고유벡터들이 열벡터로 구성된 행렬이다. 그러므로, $S^{-1}$처럼 $S$가 역행렬을 가지려면(비특이행렬이 되려면) 이는 $A$의 $n$개의 고유벡터들이 모두 독립 관계를 갖는 벡터들이어야 한다는 것을 의미한다.

■ 행렬 $A$가 $n$개의 독립인 고유벡터들을 가진다는 조건 하에, 행렬 $A$와 $S$를 곱한 $AS$는 $AS = A \begin{bmatrix} | & | & & | \\ \mathbf{x}_1 & \mathbf{x}_2 & \cdots & \mathbf{x}_n \\ | & | & & | \end{bmatrix}$가 된다.

■ 행렬 $A$의 고윳값 $\lambda_i$와 $\lambda_i$에 대응하는 고유벡터 $mathbf{x}_i$는 $A \mathbf{x}_i = \lambda_i \mathbf{x}_i, \; i = 1, 2, \cdots, n$의 관계를 만족하며, 행렬 $S$는 $S = \begin{bmatrix} | & | & & | \\ \mathbf{x}_1 & \mathbf{x}_2 & \cdots & \mathbf{x}_n \\ | & | & & | \end{bmatrix}$이므로,

■ 행렬곱 $AS$를 $A$의 열벡터들의 일차결합으로 이해했을 때, $AS = A \begin{bmatrix} | & | & & | \\ \mathbf{x}_1 & \mathbf{x}_2 & \cdots & \mathbf{x}_n \\ | & | & & | \end{bmatrix} = \begin{bmatrix} | & | & & | \\ A \mathbf{x}_1 & A \mathbf{x}_2 & \cdots & A \mathbf{x}_n \\ | & | & & | \end{bmatrix}$이며 $A \mathbf{x}_i = \lambda_i \mathbf{x}_i$이므로 $AS = A \begin{bmatrix} | & | & & | \\ \mathbf{x}_1 & \mathbf{x}_2 & \cdots & \mathbf{x}_n \\ | & | & & | \end{bmatrix}  = \begin{bmatrix} | & | & & | \\ A \mathbf{x}_1 & A \mathbf{x}_2 & \cdots & A \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}$가 성립한다.

■ 다음 단계는, 곱해지는 스칼라인 고윳값들 $\lambda_i$를 $\mathbf{x}_i$로부터 분리하는 것으로, 다음과 같이 행렬 $S$를 앞에 두고 고윳값 $\lambda_i$이 대각 원소로 구성된 대각행렬을 $S$ 뒤에 곱하는 것이다.

$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$

■ 행렬곱 $AS$를 통해 만들어진 $S \Lambda$에서 $\Lambda$가 행렬 $A$의 고윳값들로 구성된 대각행렬이다.

■ 행렬 $A$가 $n$개의 독립적인 고유벡터들을 가질 때, $AS = S \Lambda$가 의미하는 것은 행렬 $A$에 $A$의 고유벡터들로 구성된 고유벡터 행렬 $S$를 곱하면, 그 결과는 고유벡터 행렬에 $A$의 고윳값으로 구성된 대각행렬을 곱한 것과 같다는 것이다.

■ 행렬 $A$가 $n$개의 독립적인 고유벡터들을 가져 고유벡터 행렬 $S$는 비특이행렬이므로, 양변의 왼쪽에 $S$의 역행렬인 $S^{-1}$을 곱할 수 있다. 그 결과는 다음과 같다.

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

■ 그러므로 $S^{-1} A S = \Lambda$식에서 $S^{-1} A S$는 $n \times n$ 정방행렬 $A$를 대각화하는 과정을 나타내는 식이라고 할 수 있다.

- 이 식이 성립하는 중요한 조건은 $A$가 $n \times n$일 때, $n$개의 독립적인 고유벡터들을 가져야 한다는 것이다. 그래야 $S$가 가역행렬이 되어 $S^{-1} A S = \Lambda$식을 유도할 수 있다.

- 참고로 대부분의 $n \times n$의 대부분의 행렬들은 $n$개의 독립적인 고유벡터를 가지고 있으므로, 대부분의 경우 대각화할 수 있다.

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

■ $S^{-1} A S = \Lambda$식에서 반대로 $S^{-1}$과 $S$를 우변에 넘기면 행렬 $A$에 대한 식 $A = S \Lambda S^{-1}$이 성립한다. 

- $AS = S \Lambda$에서는 양변의 우측에 $S^{-1}$을 곱하면 $A = S \Lambda S^{-1}$을 얻을 수 있다.

■ $A = S \Lambda S^{-1}$식은 가우스 소거법에서의 $LU$분해 또는 그람-슈미트의 $QR$분해처럼 정방행렬 $A$를 행렬 $A$의 고윳값과 고유벡터들의 행렬들로 인수분해(factorization)하는 방법이다.

■ $A = S \Lambda S^{-1}$을 이용하면 $A$가 $n \times n$행렬이고 $S$가 가역행렬일 때, $A$를 $k$번 곱한 $A^k$나 $Lambda$를 $k$번 곱한 $\Lambda^k$를 쉽게 계산할 수 있다.

■ $A \mathbf{x} = \lambda \mathbf{x}$의 양변의 좌측에 $A$를 곱하면 $\lambda$는 스칼라이므로 $A^2 \mathbf{x} = \lambda A \mathbf{x}$가 되고 $A \mathbf{x} = \lambda \mathbf{x}$이므로 다음과 같은 식이 성립한다.

$A^2 \mathbf{x} = \lambda A \mathbf{x} \Leftrightarrow A^2 \mathbf{x} = \lambda^2 \mathbf{x}$

■ 이를 통해,  행렬 $A$의 고윳값 $\lambda$는 $A$의 제곱과 동일하게 움직이고, 고유벡터는 $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$를 3번, 4번, $\cdots, \; k$번 곱해도 $S^{-1} S = I$이 되므로 $A^k = S \lambda^k S^{-1}$이 성립한다.

- 이것이 가능한 이유는 $A$를 $k$번 곱했을 때, $A$의 고유벡터 행렬인 $S$는 그대로 유지되고, $A$의 고윳값을 원소로 가지는 대각행렬 $\Lambda$만 $A$의 제곱과 동일하게 움직이기 때문이다.

- 대각행렬인 $\Lambda$ 행렬의 대각 원소는 스칼라인 $\lambda_1, \lambda_2, \cdots , \lambda_n$이므로 $k$번 제곱했을 때, $\Lambda^k$의 대각 원소는 스칼라 $\lambda^k_1, \lambda^k_2, \cdots, \lambda^k_n$이 된다.

■ $A = LU$에서 $A$를 100번 곱한다면, 백개의 $LU$를 갖게되므로 어떤 작업을 하기 어렵다. 하지만, $A^k = S \lambda^k S^{-1}$는 그 과정에서 $S^{-1} S = I$로 상쇄된다. 즉, 고윳값들은 행렬의 거듭제곱에 대해 이전에 접근할 수 없었던 방식을 알려준다.

■ 예를 들어, $k \rightarrow \infty$로 갈 때, $A^k \rightarrow 0$. 즉, 정방행렬 $A$를 거듭제곱(power) 할수록 $A^k$가 0으로 수렴한다고 했을 때, 행렬 $A$를 안정행렬(stable matrix)이라고 한다.

- $A$의 더 높은 거듭제곱을 취할 때 $A^k, \; k = 1, 2, 3, \cdots$이 점점 작아지기 위한 조건은 고윳값들의 절댓값이 1보다 작아야 한다.

- 절댓값을 쓰는 이유는 고윳값들이 음수일 수도 있고, 복소수일 수도 있기 때문이다. 그러므로 절댓값을 취한다.

■ 정리하면, 모든 고윳값들의 절댓값이 1보다 작다는 조건 하에, $| \lambda_i | < 1$

$n$개의 독립적인 고유벡터들을 가지는 행렬 $A$에 대해서 $k \rightarrow \infty$으로 갈 때, $A^k \rightarrow 0$. 즉, 행렬 $A$가 0으로 수렴하면, 이때의 행렬 $A$를 안정적(stable)이다 라고 하며, $A$를 안정행렬(stable matrix)라고 한다.

■ 이렇게 $A$의 고윳값들을 알고 있는 상태에서,  $A^k = S \Lambda^k S^{-1}$를 이용하면 행렬 $A$의 거듭제곱을 무한대로 했을 때의 결과를 예측할 수 있고, $S^{-1} A S = \Lambda$의 $\Lambda$를 통해 선형변환의 특성을 알 수 있다.

 

2. 대각화 가능한 행렬(Diagonalizable matrices)

2.1 Diagonalizable 

■ 대각화 가능한 행렬의 조건. 즉, \( S^{-1} A S = \Lambda \)나 $A = S \Lambda S^{-1}$이 성립하기 위한 조건은 $n \times n$행렬 $A$가 $n$개의 독립적인 고유벡터들을 가져야 한다는 것이다.

그리고 고유벡터들은 하나의 고윳값 $\lambda$에 대응된다는 점을 고려하면, 가장 좋은 경우는 모든 $\lambda$가 다를 때이다.

$\lambda$가 모두 다르다는 것은 $i = 1, 2, \cdots, n$에서 $\lambda_i$가 모두 다른 것이며, 이는 $\lambda_i$가 만드는 고유공간이 모두 다르다는 것을 의미한다. 

$\lambda_i$가 만드는 고유공간이 모두 다르면, 각 $\lambda_i$에 대응하는 고유벡터 $\mathbf{x}_i$가 모두 다르다는 것이기 때문에(고유벡터 $\mathbf{x}_i$가 속하는 고유공간이 각각 다르므로 고유벡터 $\mathbf{x}_i$가 모두 다를 수밖에 없다.) $A$는 $n$개의 독립적인 고유벡터들 $\mathbf{x}_{i = 1, 2, \cdots, n}$을 가질 수 있다.

■ 가장 좋은 경우는 모든 $\lambda$가 다른 경우이다. 하지만, 고유방정식에서 $\lambda$가 중근을 갖는다면. 즉, $\lambda_i$가 반복된다면 확인이 필요하다. $\lambda$가 중근을 갖는다면, $n$개의 독립적인 고유벡터들을 가질 수 있고, 가지지 않을 수도 있다.

■ 고유방정식에서 $\lambda$가 중근을 갖을 때, 즉 고윳값 $\lambda$가 반복될 때, $n$개의 독립적인 고유벡터를 가지는 행렬로 단위행렬이 있다.

■ 예를 들어 행렬 $A$가 $2 \times 2$ 단위행렬이라면, $A = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$ $A$의 고윳값은 $\lambda_1 = 1, \; \lambda_2 = 1$로 고윳값은 중근을 갖는다. 하지만 $(A - \lambda I) \mathbf{x} = 0$을 통해 $\lambda_1$에 대응하는 고유벡터와 $\lambda_2$에 대응하는 고유벡터는 각각 $\mathbf{x}_1 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}, \; \mathbf{x}_2 = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$로 서로 독립인 2개의 고유벡터가 나온다.

- 고유벡터 $\mathbf{x}_1, \mathbf{x}_2$말고도 $\lambda_1, \lambda_2$에 대응하는 고유벡터는 무수히 많다. $\mathbf{x}_1$과 $\mathbf{x}_2$에 스칼라배를 적용한 고유벡터는 모두 각각 $\lambda_1$과 $\lambda_2$에 대응하는 고유공간에 있는 고유벡터이기 때문이다.

■ 그리고 $2 \times 2$ 단위행렬인 $A$에 대해 $S^{-1}AS$로 대각화하면 $\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$으로, 이렇게 $S^{-1} A S = \Lambda$이 성립하는 것을 볼 수 있다. 

■ 그러므로 $n \times n$ 크기를 갖는 단위행렬은 동일한 고윳값을 가져도 $n$개의 독립적인 고유벡터들을 갖는다.

■ $n \times n$ 단위행렬처럼 고윳값이 중근이아도 $n$개의 독립적인 고유벡터들을 갖는 또 다른 경우는 바로 회전행렬이다. 회전행렬 $Q$가 $Q = \begin{bmatrix} -1 & 0 \\ 0 & -1 \end{bmatrix}$라면, $\lambda_1 = -1, \lambda_2 = -1$으로 고윳값이 중근을 가져도, $\lambda_1, \lambda_2$에 대응하는 고유벡터는 독립 관계를 갖으며, $S^{-1} A S = \Lambda$도 성립한다.

■ 반대로 $n \times n$ 행렬 $A$의 고윳값이 중근을 가질 때, $n$개의 독립적인 고유벡터들을 가지지 않는 경우는 행렬이 삼각행렬인 경우이다.

■ 예를 들어 삼각행렬 $A$가 $A = \begin{bmatrix} 2 & 1 \\ 0 & 2 \end{bmatrix}$라면, 삼각행렬의 대각 원소들이 삼각행렬의 고윳값이므로 $A$의 고윳값은 $\lambda_1 = 2, \; \lambda_2 = 2$로 중근을 갖는다.

- 이렇게 되는 이유는 $\det{(A - \lambda I)}$를 계산할 때, 반대편 대각 원소가 0이므로  $\det{(A - \lambda I)}$ 계산에 포함되지 않기 때문이다.

- 고윳값이 반복되는 횟수는 대수적 중복도이다. 이 예에서는 $\lambda =2, 2$로 이중근을 갖으므로 대수적 중복도는 2이다.

■ 이 예에서 고윳값에 대응하는 고유벡터를 찾기 위해 $A - 2I$의 영공간을 찾아야 하는데, $(A - 2I) \mathbf{x} = 0$

$(A - 2I) \mathbf{x} = 0 \Leftrightarrow \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}$이므로 $\mathbf{x} = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$에서 $x_1$에는 임의의 값을 넣을 수 있지만, $x_2$는 무조건 0이어야 한다. 그러므로 유일한 고유벡터는 $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$이다. 

■ 고윳값의 대수적 중복도는 행렬 $A$가 서로 다른 $k$개의 고윳값을 가지며 $\lambda_i$가 $a_i$개만큼 중복될 때, 고윳값 $\lambda_i$가 대수적 중복도 $a_i$를 갖는다고 정의한다. 이 예에서 대수적 중복도는 2이다.

■ 고윳값의 기하적 중복도는 행렬 $A$의 고윳값 $\lambda_i$를 공유하되(같은 고윳값을 갖되), 그 고윳값에 대응하는 선형 독립적인 고유벡터의 수를 의미한다. 이 예에서 고유벡터는 $t \in \mathbb{R}$이라 할 때, $\begin{bmatrix} t \\ 0 \end{bmatrix}$이므로 단 1개의 고유벡터만 존재한다. 기하적 중복도는 1이다. 즉, 이 예에서 $(A - \lambda I)$의 영공간은 1차원이다. 

■ 이렇게 되면 $n$개의 독립적인 고유벡터가 존재하지 않으므로 삼각행렬 $A$는 대각화가 불가능하다.

■ 이 예의 고유방정식은 $2 - \lambda)^2$으로 $(2 - \lambda)$가 2번 곱해져있다. $(x - \lambda)$가 몇 번 곱해졌는지를 대수적 중복도(algebraic multiplicity)라 하고

■ 고유공간의 차원을 기하적 중복도(geometric multiplicity)라 한다. 행렬 $A$의 고유공간은 $(A - \lambda I)$의 영공간이므로, 기하적 중복도는 $(A - \lambda I)$의 영공간의 차원이다.

■ 위에서 단위행렬이나 회전행렬의 경우 대수적 중복도는 2, 기하적 중복도도 2로 대수적 중복도와 기하적 중복도가 동일했다. 이때, 단위행렬과 회전행렬은 대각화 가능했다. 하지만 삼각행렬 예에서는 대수적 중복도와 기하적 중복도가 다르며, 대각화가 불가능한 것을 알 수 있다. 또한 단위행렬, 회전행렬, 삼각행렬의 예시는 $2 \times 2$행렬이므로 전체 차원은 2차원이다. 이때, 대각화가 가능한 단위행렬이나 회전행렬의 대수적 중복도 = 기하적 중복도 = 2로 전체 차원과 동일한 것을 알 수 있다. 반면, 대각화가 불가능한 삼각행렬의 경우 대수적 중복도 $\neq$ 기하적 중복도임을 알 수 있다.

■ 그러므로 대각화가 가능할 필요충분조건은 모든 고윳값에 대한 대수적 중복도와 기하적 중복도가 동일하며, '대수적 중복도 = 기하적 중복도 = 전체 차원'이라고 할 수 있다.

■ 정리하면, $n \times n$ 행렬 $A$가 서로 다른 고윳값을 가지는 경우, $A$는 서로 독립적인 $n$개의 고유벡터를 가지며, 행렬 $A$는 대각화 가능하다.

반면, 행렬 $A$의 고윳값이 중근인 경우(고윳값이 반복되는 경우), $A$는 서로 독립적인 $n$개의 고유벡터를 가질 수도, 가지지 않을 수도 있으며, 서로 독립적인 $n$개의 고유벡터를 가지는 경우는 $A$의 모든 고윳값에 대한 대수적 중복도와 기하적 중복도가 동일하며 '대수적 중복도 = 기하적 중복도 = 전체 차원'을 만족하는 경우이다.

 

3. 대각화와 차분 방정식(Difference Equation)

3.1 Difference Equation

■ 대각화를 이용하면 차분 방정식(계차 방정식)을 쉽게 풀 수 있다. 

■ 차분(difference)이란, 임의의 두 점에서의 함수값들의 차이이다. 

- 함수가 $f$라고 했을 때, 차분은 $f_{k+1} - f_{k}$

■ 차분 방정식은 미분방정식의 이산적인 표현. 즉, 이산적 현상에 대한 모델링을 의미한다. 차분 방정식의 형태는 수열의 점화식과 같은 형태를 취한다. $a_{n+1} = a_n + a_{n-1}$

- 예를 들어, 번식하는 종들의 개체수 증가라는 이산적인 문제를 모델링할 때 차분 방정식을 사용한다.

-  번식하는 종들의 개체수 증가 문제는 예를 들어 1초에 개체수가 $2$배 증가한다면, 처음 개체수가 2일 때, 100초 후 개체수를 구하는 문제

■ 미분 방정식(differential equation)은 차분 방정식과 반대로, 어떤 연속적인 현상에 대한 모델링을 의미한다. 

- 미분 방정식은, 예를 들어 시간에 따른 변화율 문제 같이 연속적인 현상에 대한 문제를 모델링할 때 사용한다. 미분 방정식의 형태는 $\dfrac{dy}{dx}$로 $x$가 아주 작은 값인 delta만큼 변화했을 때( = $dx$), $y$가 얼마만큼 변했는지(= $dy$)에 대한 비율이다. 

■ 초깃값이 $\mathbf{u}_0$일 때, $\mathbf{u}_{k+1} = A \mathbf{u}_k$라는 식이 선형대수에서 차분 방정식이다. 이 식은 $\mathbf{u}$에 대한 차분 방정식이며 $k$번째 $\mathbf{u}$를 행렬 $A$와 계산했을 때, 다음 시점인 $k+1$번째 $\mathbf{u}$를 구하는 방정식이다. 이를 찾기 위해  0번째 $\mathbf{u}$인 초깃값 $\mathbf{u}_0$을 이용한다.

■ 이 차분 방정식을 푸는 아이디어는, 초깃값 $\mathbf{u}_0$가 주어지면,  $\mathbf{u}_0$를 이용해서 $\mathbf{u}_1 = A \mathbf{u}_0$으로 $\mathbf{u}_1$를 계산할 수 있다. 

$\mathbf{u}_2$도 계산한 $\mathbf{u}_1$을 이용하여 $\mathbf{u}_2 = A \mathbf{u}_1$으로 계산할 수 있다. 이와 같은 방식으로 $\mathbf{u}_{k+1} = A \mathbf{u}_k$를 통해 $k+1$번째 $\mathbf{u}$인 $\mathbf{u}_{k+1}$을 계산할 수 있다. 

이때, $\mathbf{u}_2 = A \mathbf{u}_1$의 과정에서 $\mathbf{u}_2$를 계산하기 위해 $A \mathbf{u}_1$를 계산하는 것을 볼 수 있다. 이때의 $\mathbf{u}_1$은 $\mathbf{u}_1 = A \mathbf{u}_0$이므로

$\mathbf{u}_2 = A \mathbf{u}_1 = AA \mathbf{u}_0$을 계산하는 것으로 볼 수 있다. 이 과정을 일반화하면, $\mathbf{u}_k = A^k \mathbf{u}_0$으로 나타낼 수 있다. 즉, $k$번째 $\mathbf{u}$인 $\mathbf{u}_k$를 계산하는 방법은 $A^k$에 초깃값인 $\mathbf{u}_0$를 곱해주기만 하면 된다.

그리고 이 차분 방정식  $\mathbf{u}_{k+1} = A \mathbf{u}_k$을 1차 차분 방정식(계차 방정식)이라고 부른다. $k$에서 $k +1$로 한 단계만 올라가는(연결하는) 방정식이기 때문이다.

■ 앞서 $A$가 대각화 가능한 행렬이라면 $A^k$는 $A^k = S \Lambda^k S^{-1}$로 쉽게 구할 수 있음을 확인하였다. 

■ 이를 이용하면, $u_{100}, \; u_{1000}, \; \cdots$을 구하기 위해 행렬 $A$를 100번, 1000번, ... 곱해서 구할 수 있지만, $A^k = S \Lambda^k S^{-1}$를 이용하면 1차 차분 방정식을 쉽게 계산할 수 있다.

■ $n \times n$ 크기를 갖는 $A$가 $n$개의 독립적인 고유벡터들을 갖는다고 하자.(= $A$가 대각화 가능이라고 하자.) 

■ 차분 방정식을 푸는 과정은 먼저, 초깃값인 $\mathbf{u}_0$ 벡터를 행렬 $A$의 고유벡터들의 선형결합으로 표현한다. $\mathbf{u}_0 = c_1 \mathbf{x}_1 + c_2 \mathbf{x}_2 + \cdots + c_n \mathbf{x}_n$

이 표현에서 $c$는 상수 $\mathbf{x}$는 고유벡터이며, 이 선형결합 표현은 다음과 같이 $A$의 $n$개의 독립적인 고유벡터들을 열벡터로 구성하는 고유벡터 행렬 $S$와 상수값 벡터 $c$의 곱으로 나타낼 수 있다. $\mathbf{u}_0 = c_1 \mathbf{x}_1 + c_2 \mathbf{x}_2 + \cdots + c_n \mathbf{x}_n = S\vec{c}$

$S \vec{c} = \begin{bmatrix} | & | & & | \\ \mathbf{x}_1 & \mathbf{x}_2 & \cdots & \mathbf{x}_n \\ | & | & & | \end{bmatrix} \begin{bmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{bmatrix}$

- $\mathbf{u}_0$을 $A$의 서로 독립적인 $n$개의 고유벡터들의 선형결합으로 표현할 수 있는 이유는 다음과 같다.

- 행렬 $A$가 $n \times n$이며 $n$개의 독립적인 고유벡터를 갖는다면, $n$개의 독립적인 고유벡터가 $n$차원 공간인 $\mathbb{R}^n$을 생성하는 기저이다. 

- 이때의 $\mathbf{u}_0$이라는 벡터는 전체 공간 내에 존재하는 벡터이므로, $n$개의 독립적인 고유벡터들의 선형결합으로 $\mathbf{u}_0$를 만들 수 있는 것이다.

■ $\mathbf{u}_0 = c_1 \mathbf{x}_1 + c_2 \mathbf{x}_2 + \cdots + c_n \mathbf{x}_n$이므로 $A \mathbf{u}_0$은 $A \mathbf{u}_0 = c_1 A \mathbf{x}_1 + c_2 A \mathbf{x}_2 + \cdots + c_n A \mathbf{x}_n$이며, $A \mathbf{x}_i = \lambda \mathbf{x}_i$이므로

$A \mathbf{u}_0 = c_1 A \mathbf{x}_1 + c_2 A \mathbf{x}_2 + \cdots + c_n A \mathbf{x}_n = c_1 \lambda_1 \mathbf{x}_1 + c_2 \lambda_2 \mathbf{x}_2 + \cdots + c_n \lambda_n \mathbf{x}_n$이 성립한다.

■ 이렇게 초깃값 $\mathbf{u}_0$에 행렬 $A$를 적용시킨 결과는 $A \mathbf{u}_0 = c_1 \lambda_1 \mathbf{x}_1 + c_2 \lambda_2 \mathbf{x}_2 + \cdots + c_n \lambda_n \mathbf{x}_n$으로 고윳값과 고유벡터의 선형결합 형태로 표현할 수 있다.

■ 여기서 $AA \mathbf{u}_0 = A^2 \mathbf{u}_0$을 전개하면, $A^2 \mathbf{u}_0 = c_1 \lambda_1 A \mathbf{x}_1 + c_2 \lambda_2 A \mathbf{x}_2 + \cdots + c_n \lambda_n A \mathbf{x}_n$이므로 $A \mathbf{x}_i = \lambda_i \mathbf{x}_i$에 의해 $A^2 \mathbf{u}_0 = c_1 \lambda^2_1 \mathbf{x}_1 + c_2 \lambda^2_2 \mathbf{x}_2 + \cdots + c_n \lambda^2_n \mathbf{x}_n$가 성립한다. 

■ 여기서, 예를 들어 $\mathbf{u}_{100} = A^{100} \mathbf{u}_0$를 구하고 싶다면, 이는 $A^{100} \mathbf{u}_0 = c_1 \lambda^{100}_1 \mathbf{x}_1 + c_2 \lambda^{100}_2 \mathbf{x}_2 + \cdots + c_n \lambda^{100}_n \mathbf{x}_n$가 될 것이다. 

■ 이 문제를 행렬의 대각화를 이용하여 계산한다면, $\mathbf{u}_{100} = A^{100} \mathbf{u}_0 = S \Lambda^{100} S^{-1} S \vec{c}$이며 $S^{-1} S = I$이므로 $\mathbf{u}_{100} = A^{100} \mathbf{u}_0 = S \Lambda^{100} \vec{c}$가 성립한다. 

■ 이 식을 일반화하면 $\mathbf{u}_k = A^k \mathbf{u}_0 = S \Lambda^k \vec{c}$가 된다.

■ 예를 들어 피보나치 수열의 $F_0 = 0, F_1 = 1$일 때, $F_0, F_1, F_2, \cdots$은 0, 1, 1, 2, 3, 5, 8, 13, 21, ... 이 된다. 이때 $F_{100}$의 값을 구해 피보나치 수들이 얼마나 빠르게 증가하는지에 대한 문제는 시간에 따라 어떤 규칙에 의해 값이 변화하는 문제이므로 차분 방정식을 통해 풀 수 있는 문제이다.

■ 이전 시점의 두 개의 값의 합이 현재의 값이 되는 규칙을 가지므로  $F_{k+2} = F_{k+1} + F_{k}$로 나타낼 수 있다.

■ $F_{k+2} = F_{k+1} + F_{k}$는 단일 방정식이고 2개의 단계에 대한 식이기 때문에 2차 도함수가 있는 2차 미분 방정식과 같다.

- $F_{k+2} = F_{k+1} + F_{k}$는 $k$가 2번 변화했을 때, 그 값에 대한 변화를 보는 식이기 때문에 2차 미분 방정식과 같다.

■ 여기서 1차 차분을 얻고 싶으면 벡터 $\mathbf{u}_k$를 사용해야 하는데, 약간의 트릭을 이용하면 된다. 바로 $F_{k+2} = F_{k+1} + F_{k}$의 입력값인 $F_{k+1}$과 $F_k$를 벡터 $\mathbf{u}_k$로 정의하는 것이다. $\mathbf{u}_k = \begin{bmatrix} F_{k+1} \\ F_k \end{bmatrix}$

■ 1차 차분 방정식을 만들기 위해선 $\mathbf{u}_k$와 $\mathbf{u}_{k+1}$이 필요한데, $\mathbf{u}_k = \begin{bmatrix} F_{k+1} \\ F_k \end{bmatrix}$로 정의하였으니, $\mathbf{u}_{k+1}$은 $\mathbf{u}_{k+1} = \begin{bmatrix} F_{k+2} \\ F_{k+1} \end{bmatrix}$로 정의할 수 있다.

■ 1차 차분 방정식에 필요한 $\mathbf{u}_k$와 $\mathbf{u}_{k+1}$를 정의한 다음, 필요한 것은 행렬 $A$이다. 행렬 $A$를 미지수  $\mathbf{u}_k$를 적용했을 때(곱했을 때),  $\mathbf{u}_{k+1}$로 미지수가 변화한다. 즉, 행렬 $A$는 이 문제에 대한 관계(방정식)에서 구해야 하는데, 이는 $F_{k+2} = F_{k+1} = F_k$라는 방정식과 $F_{k+1} = F_{k+1}$이라는 방정식을 통해 행렬 $A$를 정의할 수 있다. 

- $F_{k+1} = F_{k+1}$ 방정식은 행렬 $A$를 정의하기 위한 트릭이다.

■ 방정식 $\begin{align} F_{k+2} &= F_{k+1} + F_k \\ F_{k+1} &= F_{k+1} \end{align}$를 이용하면 1차 차분 방정식 $\mathbf{u}_{k+1} = A \mathbf{u}_k$는 $\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}$로 나타낼 수 있다.

- 이렇게 2차 미분방정식 형태였던 피보나치 수열 문제를 1차 차분 방정식으로 바꿀 수 있다.

■ 행렬 $A$에 대한 고유방정식은 $\lambda^2 - \lambda - 1 = 0$이다. 이 고유방정식은 피보나치 수열의 차분방정식 행렬 $A$를 통해 만든 것이고, 행렬 $A$는 피보나치 수열의 규칙인 $F_{k+2} = F_{k+1} + F_{k}$라는 2차 미분 방정식 형태에서 트릭을 이용해 만든 것이다. 

■ $F_{k+2} = F_{k+1} + F_{k}$식을 $\lambda^2 - \lambda - 1 = 0$ 형태로 나타내면 $F_{k+2} - F{k+1} - F_k = 0$으로 고유방정식과 같은 모양을 보인다.

- $F_{k+2}$는 $\lambda^2$, $-F_{k+1}$은 $- \lambda$, $- F_k$는 $-1$

■ 즉, 행렬 $A$의 고유방정식은 어떤 문제에 대한 특성을 나타내는 식이 된다.

- 이 예에서는 피보나치 수열에 대한 식 $F_{k+2} = F_{k+1} + F_{k}$이 행렬 $A$의 고유방정식 $\lambda^2 - \lambda - 1 = 0$으로 나타난 것이다.

■ $\lambda^2 - \lambda - 1 = 0$에서 고윳값 $\lambda = \dfrac{1 \pm \sqrt{5}}{2}$이므로 $\lambda_1 = \dfrac{1 + \sqrt{5}}{2}$이고 $\lambda_2 = \dfrac{1 - \sqrt{5}}{2}$로 실수(real number)값을 갖는다. 그리고 각 고윳값이 서로 다르기 때문에 $A$는 서로 독립인 고유벡터가 존재하므로 $A$는 대각화 가능하다.

■ 그러므로 $F_{100}$을 구하는 문제는 $\mathbf{u}_{100}$을 구하는 문제로 바뀌었으며,  $\mathbf{u}_{100} = A^{100} \mathbf{u}_0$을 계산하면 된다.

■ 이때, 피보나치 수열이 얼마나 빠르게 증가하는지도 $\mathbf{u}_{100} = A^{100} \mathbf{u}_0$을 통해 알 수 있다. $A^{100} \mathbf{u}_0 = c_1 \lambda_1^{100} \mathbf{x}_1 + c_2 \lambda_2^{100} \mathbf{x}_2 = c_1 \left( \dfrac{1+\sqrt{5}}{2} \right)^{100} \mathbf{x}_1 + c_2 \left( \dfrac{1-\sqrt{5}}{2} \right)^{100} \mathbf{x}_2$에서 두 번째 고윳값인 $\lambda_2$의 절댓값은 1보다 작은 수이므로 $A$에 거듭제곱을 할수록 0으로 수렴한다는 것을 알 수 있다. 즉, 이 식에서 유의미한 것은 첫 번째 항이며, 이 첫 번째 항에서 피보나치 수열의 값의 증가 속도를 결정하는 요소는 정수 1보다 큰 $\lambda_1$이다.

- $\lambda_1$은 약 1.6, $\lambda_2$는 약 -0.6

■ 고유벡터를 구하기 위해 $(A - \lambda I) \mathbf{x} = 0$을 계산해야 한다. 이때 $(A- \lambda I) = \begin{bmatrix} 1 - \lambda & 1 \\ 1 & - \lambda \end{bmatrix}$이며 이 행렬과 $\mathbf{x}$의 곱을 통해 0이 되야하므로 $\mathbf{x} = \begin{bmatrix} \lambda \\ 1 \end{bmatrix}$가 되야한다.

- $\lambda^2 - \lambda -1 = 0$이므로 $\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}$이 된다.

■ $\mathbf{x} = \begin{bmatrix} \lambda \\ 1 \end{bmatrix}$이므로 고유벡터 $\mathbf{x}_1 = \begin{bmatrix} \lambda_1 \\ 1 \end{bmatrix} =  \begin{bmatrix} \dfrac{1+\sqrt{5}}{2} \\ 1 \end{bmatrix}$이며, $\mathbf{x}_2 = \begin{bmatrix} \lambda_2 \\ 1 \end{bmatrix} = \begin{bmatrix} \dfrac{1 - \sqrt{5}}{2} \\ 1 \end{bmatrix}$가 된다.

■ $\mathbf{x}_1$과 $\mathbf{x}_2$를 알았으니, $c_1, c_2$를 구할 수 있다. $c_1, c_2$는 $\mathbf{u}_0 = A^0 \mathbf{u}_0$이며 $A^0 \mathbf{u}_0 = c_1 x_1 + c_2 x_2$임을 이용하면 $\mathbf{u}_0 = \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}$
$c_1 = \sqrt{5} / 5, c_2 = - \sqrt{5} / 5$

- $\mathbf{u}_0$의 원소는 $F_1, F_0$이므로 $\mathbf{u}_0 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$

■ 현재 구해야 하는 $F_{100}$는 $\mathbf{u}_{100}$을 구하는 문제로 바뀌었으며, $\mathbf{u}_{100}$은 $\mathbf{u}_{100} = A^{100} \mathbf{u}_0 = c_1 \lambda_1^{100} \mathbf{x}_1 + c_2 \lambda_2^{100} \mathbf{x}_2 = c_1 \left( \frac{1+\sqrt{5}}{2} \right)^{100} \mathbf{x}_1 + c_2 \left( \frac{1-\sqrt{5}}{2} \right)^{100} \mathbf{x}_2$을 계산해야 한다. 이 계산에 필요한 $c_1, c_2, \mathbf{x}_1, \mathbf{x}_2$을 모두 구하였으니, 이 값들을 대입하면, 피보나치 수열의 100번째 값인 $F_100$ 값을 구할 수 있다.