Eigenvalue and eigenvector

Eigenvalue와 eigenvector는 시간에 따라 변하는 함수값을 예측하는 자기회귀모델(AutoRegressive model)에서 함수값이 수렴하는지의 여부를 결정합니다.

자기회귀모델이란 변수의 과거 값의 선형 조합을 이용하여 관심 있는 변수를 예측하는 모델로, 차수가 $p$인 자기회귀모델(AR(p))은 다음과 같은 모양이 됩니다.¹
$x(t) = \alpha_1 x(t-1) + \cdots + \alpha_p x(t-p) + \epsilon(t)$

여기선 가장 기초적인 모델 $\epsilon(t) = 0$인 1차 자기회귀모델의 성질을 알아보고자 합니다.
$\mathbf{x}(t)$를 $ \begin{bmatrix} x_1(t) & \cdots & x_n(t) \end{bmatrix}^T $ 로 구성된 벡터라 하면, $n$개의 모델은 다음과 같은 행렬식으로 표현할 수 있습니다.

\[\begin{bmatrix} \\ \mathbf{x}(t) \\ \\ \end{bmatrix} = \begin{pmatrix} & & \\ & A & \\ & & \\ \end{pmatrix} \begin{bmatrix} \\ \mathbf{x}(t-1) \\ \\ \end{bmatrix}\]

1. Objective

알고자하는 것은 $ \mathbf{x}(t) = A \mathbf{x}(t-1) $ 에 대하여 $ \lim\limits_{t \to \infty} \mathbf{x}(t)$ 의 원소 중 하나라도 발산하는지 혹은 모든 원소가 수렴하는지 체크하는 것입니다. 다음은 이를 구하기 위한 알고리즘입니다.

2. Algorithm

$\mathbf{x}(t) = A \mathbf{x}(t-1)$
If $A$ is diagonal then,
$\mathbf{x}(t) = A^t \mathbf{x}(0)$
else,
Let $\ \mathbf{x}(t) = P \mathbf{y}(t)$ such that $P$ is regular.
Let $\ \Lambda = P^{-1}AP$ then,
$\ \mathbf{y}(t) = P^{-1}\mathbf{x}(t) = P^{-1}A\mathbf{x}(t-1) = P^{-1}AP\mathbf{y}(t-1) = \Lambda \mathbf{y}(t-1)$
Similarity transformation: $A \to \Lambda = P^{-1}AP$
Select proper $P$ so that $\Lambda$ should be diagonal.(Diagonalization)
Then, $\mathbf{y}(t)$’s convergence is equivalent to $\mathbf{x}(t)$
$AP = P\Lambda$ : definition of eigenvalue & eigenvector of $A$
If all eigenvalues of $A$ are different then,
Regular matrix $P$ s.t. diagonal $\Lambda = P^{-1}AP$ exists (eigenvectors are linearly independent)
$P$ is a matrix whose column vectors are eigenvector and $\Lambda$ is a eigenmatrix.
(eigenmatrix: diagonal matrix whose diagonals are eigenvalues)
$\mathbf{y}(t) = \Lambda^t \mathbf{y}(0)$
$A = P \Lambda P^{-1} \quad \cdots \quad$ Eigenvalue decomposition
$\therefore \ \mathbf{x}(t) = P \Lambda P^{-1} \mathbf{x}(t-1) = P \Lambda^t P^{-1} \mathbf{x}(0)$
If all eigenvalues of $A ≤ 1$ then,
$\mathbf{x}(t)$ will converge.
else,
$\mathbf{x}(t)$ will diverge.
else,
Regular matrix $P$ s.t. diagonal $\Lambda = P^{-1}AP$ does not exist.
But, regular matrix $P$ s.t. Jordan standard form² $J = P^{-1} A P$ can exist.
System $\mathbf{y}(t) =J \mathbf{y}(t-1)$ can be separated into a few subsystems.
If all eigenvalues of each subsystem matrix(Jordan cell) $≤ 1$ then,
$\mathbf{x}(t)$ will converge.
else,
$\mathbf{x}(t)$ will diverge.

3. Geometric meaning

Eigenvector: $A$에 따른 변환 후에도 신축만 되고, 방향은 변하지 않는 vector
Eigenvalue: 해당 eigenvector의 신축률

4. Characteristics

$\mathbf{\lambda}: \text{Eigenvalue of } A $
$\mathbf{p}: \text{Eigenvector of } A$
$A: (\mathbf{\lambda}, \mathbf{p}) \text{ means } \lambda \text{ is eigenvalue and } \mathbf{p} \text{ is eigenvector of } A $

$\lambda_i = 0 \Leftrightarrow A \text{ is singular}$
$\forall \alpha \neq 0 \ (A : (\alpha \mathbf{p}, \lambda))$
$\text{For } \mathbf{p + q} \neq 0, A: (\lambda, \mathbf{p}) \wedge A: (\lambda, \mathbf{q}) \to A: (\lambda, \mathbf{p + q})$
$\forall \alpha (\alpha A : (\alpha \lambda, \mathbf{p}))$
$\forall \alpha (A + \alpha I: (\lambda + \alpha, \mathbf{p})$
$\forall \alpha (A^\alpha: (\lambda^\alpha, \mathbf{p}))$
$ A^{-1}: (\lambda^{-1}, \mathbf{p}) $
$ \text{diag}(a_1, \cdots, a_n): ([a_1, \cdots, a_n], [\mathbf{e_1}, \cdots, \mathbf{e_n}]) $
$\text{For block matrix, } A: (\lambda, \mathbf{p}), \ B: (\mu, \mathbf{q}), \ C: (\nu, \mathbf{r})$
$D = \begin{pmatrix} A & O & O \\ O & B & O \\ O & O & C \\ \end{pmatrix} \quad \quad D: ([\lambda, \mu, \nu], [[\mathbf{p}, \mathbf{o}, \mathbf{o}]^T, [\mathbf{o}, \mathbf{q}, \mathbf{o}]^T, [\mathbf{o}, \mathbf{o}, \mathbf{r}]^T])$
$\text{For triangular matrix, diagonal elements are eigenvalues}$
$ \text{For regular matrix S, similarity transformed matrix } S^{-1}AS: (\lambda, S^{-1}\mathbf{p}) $
$\text{det} (A) = \Pi_i \lambda_i $
If $\lambda_1, \cdots, \lambda_n$ are different, $\mathbf{p_1}, \cdots, \mathbf{p_n} $ are linearly independent.
(역은 성립하지 않는다. 즉, linearly independent eigenvector들은 동일한 eigenvalue를 가질 수 있다.
(ex. Identity matrix))
Eigenvalue decomposition: $ A = P \Lambda P^{-1}$
If $A$ is symmetric, $\mathbf{p}$s are orthogonal, thus $P^{-1} = P’$
Eigenvalue decomposition becomes spectral decomposition of $A$: $A = P \Lambda P’$

5. Multiple eigenvalues

$n \times n$ 행렬의 eigenvalue의 개수는 중근의 개수를 전부 포함하여 총 $n$개가 됩니다.
동일한 eigenvalue의 개수와 선형독립인 eigenvector의 개수를 각각 algebraic multiplicities (대수적 중복도), geometric multiplicities (기하적 중복도) 라고 하며, 이에 따라 다음과 같이 분류해볼 수 있습니다.
(이하, eigenvalue: $\lambda$, eigenvector: $\mathbf{p}$)

1) 중근 X

$P$는 regular matrix가 되어 $\Lambda$가 diagonal matrix가 되는 대각화가 성립합니다.

2) 중근 O / $n$개의 linearly independent $\mathbf{p}$

마찬가지로 $P$는 regular matrix가 되어 $\Lambda$가 diagonal matrix가 되는 대각화가 성립합니다.

3) 중근 O / $n$개 미만의 linearly independent $\mathbf{p}$

$P$는 singular matrix가 되어 $\Lambda$가 diagonal matrix가 되는 대각화가 성립하지 않습니다.

PREVIOUSEtc