Eigendecomposition and Diagonalization

Diagonal matrix(대각 행렬)는 대각 성분이 아닌 요소들이 모두 0인 행렬이며, 다음과 같습니다.

\[\boldsymbol{D} = \begin{bmatrix}c_{1}&\cdots&0\\\vdots&\ddots&\cdots\\0&\cdots&c_n\end{bmatrix} \tag{4.49}\]

대각 행렬에서는 determinants(행렬식), powers(거듭제곱), inverses(역행렬)를 빠르게 계산할 수 있습니다. 대각 행렬의 determinant는 대각 성분들의 곱이며, 대각 행렬의 거듭제곱 $\boldsymbol{D}^k$ 는 각 대각 성분들을 k 거듭제곱하면 됩니다. 그리고 역행렬 $\boldsymbol{D}^{-1}$ 은 0이 아닌 대각 성분들의 역수를 취한 것과 같습니다.

4.4장에서는 행렬을 대각 행렬의 형태로 변환하는 방법에 대해 살펴봅니다. 여기에서 2.7.2장에서 논의한 basis change와 4.2장에서 살펴본 eigenvalues가 활용됩니다.

만약 $\boldsymbol{D} = \boldsymbol{P}^{-1}\boldsymbol{AP}$ 를 만족시키는 역행렬이 존재하는 행렬 $\boldsymbol{P}$ 가 존재할 때, 두 행렬 $\boldsymbol{A},\boldsymbol{D}$ 는 similar (2.7.2장 Definition 2.22 참조) 합니다.

조금 더 구체적으로 대각 요소들이 $\boldsymbol{A}$ 의 eigenvalue인 대각 행렬 $\boldsymbol{D}$ 에 similar 한 $\boldsymbol{A}$ 에 대해 살펴보도록 하겠습니다.

Definition 4.19 (Diagonalizable)

만약 행렬 $\boldsymbol{A} \in \mathbb{R}^{n\times n}$ 가 diagonal matrix와 similar 한다면, 즉, $\boldsymbol{D} = \boldsymbol{P}^{-1}\boldsymbol{AP}$ 를 만족시키는 역행렬이 존재하는 행렬 $\boldsymbol{P}$ 가 존재한다면, 행렬 $\boldsymbol{A}$ 를 diagonalizable, 즉, 대각화가 가능하다고 말합니다.

이어서 행렬 $\boldsymbol{A}$ 를 대각화하는 것은 다른 basis의 동일한 linear mapping이며, 이 basis는 결국 $\boldsymbol{A}$ 의 eigenvector로 구성되어 있다는 것을 확인해보도록 하겠습니다.

$\boldsymbol{A}\in\mathbb{R}^{n\times n}$ 이 있고, $\lambda_1, \dotsc, \lambda_n$ 은 스칼라들의 집합, $\boldsymbol{p}_1, \dotsc, \boldsymbol{p}_n$ 은 $\mathbb{R}^n$ 에서의 벡터 집합이라고 합시다. 그리고 $\boldsymbol{P} := \lbrack\boldsymbol{p}_1, \dotsc, \boldsymbol{p}_n\rbrack$ 를 정의하고, $\boldsymbol{D} \in \mathbb{R}^{n\times n}$ 을 대각 요소들이 $\lambda_1,\dotsc,\lambda_n$ 인 대각 행렬이라고 정의합니다.

그러면, 만약 $\lambda_1,\dotsc,\lambda_n$ 이 $\boldsymbol{A}$ 의 eigenvalues이고, $\boldsymbol{p}_1, \dotsc, \boldsymbol{p}_n$ 이 $\boldsymbol{A}$ 의 eigenvectors일 때, 다음의 식이 만족함을 볼 수 있습니다.

\[\boldsymbol{AP} = \boldsymbol{PD} \tag{4.50}\]

아래의 만족하기 때문에 식 (4.50)이 만족함을 알 수 있습니다.

\[\begin{align*} \boldsymbol{AP} &= \boldsymbol{A}\lbrack\boldsymbol{p}_1,\dotsc,\boldsymbol{p}_n\rbrack = \lbrack\boldsymbol{Ap}_1,\dotsc,\boldsymbol{Ap}_n\rbrack \tag{4.51} \\ \boldsymbol{PD} &= \lbrack\boldsymbol{p}_1,\dotsc,\boldsymbol{p}_n\rbrack\begin{bmatrix}\lambda_1&&0\\&\ddots&\\0&&\lambda_n\end{bmatrix} = \lbrack\lambda_1\boldsymbol{p}_1,\dotsc,\lambda_n\boldsymbol{p}_n\rbrack \tag{4.52} \end{align*}\]

따라서, 위 식들에 의해서 (4.50)이 다음과 같이 성립된다는 것을 알 수 있으며,

\[\begin{align*} \boldsymbol{Ap}_1 = \lambda_1\boldsymbol{p}_1 \tag{4.53} \\ \vdots \\ \boldsymbol{Ap}_n = \lambda_n\boldsymbol{p}_n \tag{4.54} \end{align*}\]

즉, $\boldsymbol{P}$ 의 column들은 반드시 $\boldsymbol{A}$ 의 eigenvectors 입니다.

Diagonalization의 정의는 행렬 $\boldsymbol{P} \in \mathbb{R}^{n\times n}$ 가 invertible하다는 것을 필요로 합니다. 즉, $\boldsymbol{P}$ 는 full rank이어야 합니다 (Theorem 4.3 참조). 이는 결국 n개의 linearly indepedent eigenvectors $\boldsymbol{p}_1,\dotsc, \boldsymbol{p}_n$ 을 요구하는 것이며, 따라서, $\boldsymbol{p}_i$ 는 $\mathbb{R}^n$ 의 basis를 형성합니다.

Theorem 4.20 (Eigendecomposition). Square matrix $\boldsymbol{A} \in \mathbb{R}^{n\times n}$ 은 $\boldsymbol{A}$ 의 eigenvectors가 $\boldsymbol{R}^n$ 의 basis를 형성할 때, 다음과 같이 분해될 수 있습니다.

\[\boldsymbol{A} = \boldsymbol{PDP}^{-1} \tag{4.55}\]

이때, $\boldsymbol{P} \in \mathbb{R}^{n\times n}$ 이고, $\boldsymbol{D}$ 는 대각 요소들이 $\boldsymbol{A}$ 의 eigenvalues인 diagonal matrix 입니다.

Theorem 4.20은 오직 non-defective matrix만 대각화할 수 있다는 것과 $\boldsymbol{P}$ 의 column들은 $\boldsymbol{A}$ 의 n개의 eigenvectors라는 것을 암시합니다.

대칭 행렬(symmetric matrices)의 경우, eigenvalue decomposition을 통해 더 강력한 결과를 얻을 수 있습니다.

Theorem 4.21. Symmetric matrix $\boldsymbol{S}\in\mathbb{R}^{n\times n}$ 은 항상 대각화가 가능합니다.

Theorem 4.21은 spectral theorem 4.15(4.2장)으로부터 이어지는 theorem 입니다. Spectral theorem은 우리가 $\mathbb{R}^n$ 의 eigenvectors의 ONB(orthonormal basis)를 찾을 수 있다고 말해주며, 이는 $\boldsymbol{P}$ 를 orthogonal matrix로 만들어 $\boldsymbol{D} = \boldsymbol{P}^\top\boldsymbol{AP}$ 가 되도록 합니다.

---

행렬의 eigendecomposition은 다음과 같이 해석할 수 있습니다 (위의 그림도 참조바랍니다).

먼저 행렬 $\boldsymbol{A}$ 를 standard basis에 대한 linear mapping의 transformation matrix라고 하겠습니다. $\boldsymbol{P}^{-1}$ 은 standard basis에서 eigenbasis로의 basis change를 수행합니다. 이는 eigenvectors $\boldsymbol{p}_i$ (그림의 red/orange 화살표)를 standard basis vectors $\boldsymbol{e}_i$ 로 만듭니다. 그리고, 대각 행렬 $\boldsymbol{D}$ 는 eigenvalues $\lambda_i$ 만큼 축을 따라 scaling 합니다. 마지막으로 $\boldsymbol{P}$ 는 scaling된 벡터들을 다시 standard/canonical coordinates로 변환하며 이는 $\lambda_i\boldsymbol{p}_i$ 와 같습니다.

Example 4.11 (Eigendecomposition)

$\boldsymbol{A} = \frac{1}{2}\begin{bmatrix}5&-2\\ -2&5\end{bmatrix}$ 의 eigendecomposition을 계산해보도록 하겠습니다.

Step 1: Compute eigenvalues and eigenvectors.

$\boldsymbol{A}$ 의 특성 다항식(characteristic polynomial; 4.1장 참조)을 통해 eigenvalues를 구합니다.

\[\begin{align*} \det(\boldsymbol{A}-\lambda\boldsymbol{I}) &= \det\left(\begin{bmatrix}\frac{5}{2}-\lambda&-1\\-1&\frac{5}{2}-\lambda\end{bmatrix}\right) \tag{4.56a} \\ &= (\frac{5}{2}-\lambda)^2 - 1 = \lambda^2-5\lambda+\frac{21}{4}=(\lambda-\frac{7}{2})(\lambda-\frac{3}{2}) \tag{4.56b} \end{align*}\]

따라서, $\boldsymbol{A}$ 의 eigenvalues는 $\lambda_1 = \frac{7}{2}, \lambda_2=\frac{3}{2}$ 이며, 이와 연관된 eigenvectors는 다음의 식읕 통해 얻을 수 있습니다.

\[\boldsymbol{Ap}_1 = \frac{7}{2}\boldsymbol{p}_1, \quad \boldsymbol{Ap}_2 = \frac{3}{2}\boldsymbol{p}_2 \tag{4.57}\]

위 식을 풀면, 다음의 결과를 얻습니다.

\[\boldsymbol{p}_1 = \frac{1}{\sqrt{2}}\begin{bmatrix}1\\-1\end{bmatrix}, \quad \boldsymbol{p}_2 = \frac{1}{\sqrt{2}}\begin{bmatrix}1\\1\end{bmatrix} \tag{4.58}\]

Step 2: Check for existence.

Eigenvectors $\boldsymbol{p}_1, \boldsymbol{p}_2$ 가 $\mathbb{R}^2$ 의 basis 를 형성합니다. 따라서 $\boldsymbol{A}$ 는 대각화가 가능합니다.

Step 3: Construct the matrix $\boldsymbol{P}$ to diagonalize $\boldsymbol{A}$ .

$\boldsymbol{P}$ 는 $\boldsymbol{A}$ 의 eigenvectors를 column으로 구성되므로, 다음과 같습니다.

\[\boldsymbol{P} = \lbrack\boldsymbol{p}_1, \boldsymbol{p}_2\rbrack = \frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\-1&1\end{bmatrix} \tag{4.59}\]

그러면 다음의 식을 얻을 수 있습니다.

\[\boldsymbol{P}^{-1}\boldsymbol{AP} = \begin{bmatrix}\frac{7}{2}&0\\0&\frac{3}{2}\end{bmatrix} = \boldsymbol{D} \tag{4.60}\]

또한, 이 예제에서 eigenvectors $\boldsymbol{p}_1$ 과 $\boldsymbol{p}_2$ 가 서로 ONB를 형성하기 때문에 $\boldsymbol{P}^{-1} = \boldsymbol{P}^\top$ 을 활용하여 다음의 식을 얻을 수 있습니다.

\[\underbrace{\frac{1}{2}\begin{bmatrix}5&-2\\-2&5\end{bmatrix}}_{\boldsymbol{A}} = \underbrace{\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\-1&1\end{bmatrix}}_{\boldsymbol{P}}\underbrace{\begin{bmatrix}\frac{7}{2}&0\\0&\frac{3}{2}\end{bmatrix}}_{\boldsymbol{D}}\underbrace{\frac{1}{\sqrt{2}}\begin{bmatrix}1&-1\\1&1\end{bmatrix}}_{\boldsymbol{P}^{-1}} \tag{4.61}\]

• Diagonal matrix $\boldsymbol{D}$ 를 사용하면 거듭제곱을 효율적으로 계산할 수 있습니다. 그러므로, $\boldsymbol{A}\in\mathbb{R}^{n\times n}$ 행렬의 거듭제곱은 eigenvalue decomposition을 사용하면 다음과 같이 계산할 수 있습니다. 또한, $\boldsymbol{D}^k$ 는 각 대각 요소들만 거듭제곱해주면 되므로 효율적으로 계산할 수 있습니다.

\[\boldsymbol{A}^k = (\boldsymbol{PDP}^{-1})^k = \boldsymbol{PD}^k\boldsymbol{P}^{-1} \tag{4.62}\]

• Eigendecomposition $\boldsymbol{A} = \boldsymbol{PDP}^{-1}$ 이 존재한다고 가정해보겠습니다. 그러면, 다음의 식을 통해 $\boldsymbol{A}$ 의 determinant를 효율적으로 계산할 수 있습니다.

\[\begin{align*} \det(\boldsymbol{A}) &= \det(\boldsymbol{PDP}^{-1}) = \det(\boldsymbol{P})\det(\boldsymbol{D})\det(\boldsymbol{P}^{-1}) \tag{4.63a} \\ &= \det(\boldsymbol{D}) = \prod_i d_{ii} \tag{4.63b} \end{align*}\]

지금까지 살펴본 것과 같이 eigenvalue decomposition은 매우 편리합니다. 하지만 eigenvalue decomposition은 square matrix에서만 적용할 수 있으며, 항상 적용할 수 없습니다. 따라서, 모다 더 일반적인 행렬에 대한 decomposition을 수행하는 것이 필요하며, 4.5장에서는 보다 더 일반적인 행렬을 분해하는 기법인 Singular Value Decomposition(특잇값 분해)에 대해 살펴보도록 하겠습니다.