유투브 - 혁펜하임님의 선형대수학강의를 정리하기 위해 작성한 글입니다.

Eigen Value Decomposition(EVD)

고윳값분해는 행렬을 분해하는 방법 중 하나로 행렬이 1)full rank인 정사각행렬이거나 2)정사각행렬이면서 대칭행렬인 경우에 사용할 수 있다.
정사각행렬이며 대칭행렬의 경우에는 항상 EVD 가능하지만 일반적인 정사각행렬인 경우 모든 column,row가 선형독립(full rank)이어야 한다.
행렬 \(A \in \mathbb{R}^{2 \times 2}\)의 eigen value는 \(2\)개 eigen vector도 \(2\)개라 해보자>

\[\begin{aligned} &Av_1 = \lambda_1v_1 \\ &Av_2 = \lambda_2v_2 \\ \end{aligned}\]

다음과 식을 생각했을때…

\[\begin{aligned} A\begin{bmatrix}v_1\,v_2\end{bmatrix} = \begin{bmatrix}Av_1\,Av_2\end{bmatrix} = \begin{bmatrix}\lambda_1v_1\,\lambda_2v_2\end{bmatrix} = \begin{bmatrix}v_1\,v_2\end{bmatrix}\begin{bmatrix}\lambda_1 & 0 \\ 0 & \lambda_2\end{bmatrix} \end{aligned}\]

\(V = \begin{bmatrix}v_1\,v_2\end{bmatrix},\Lambda = \begin{bmatrix}\lambda_1 & 0 \\ 0& \lambda_2\end{bmatrix}\)라 하면 다음과 같이 정리할 수 있다.

\[\begin{aligned} &AV = V\Lambda \\ &\Longleftrightarrow A = V\Lambda V^{-1} \end{aligned}\]

위와같이 하나의 행렬을 몇 개의 행렬들로 인수분해했을때, 행렬A를 decomposition했다고 하며 고윳값,고유벡터를 통해서 decompose하면 eigen (value) decomposition이라고 한다.

Diagonalizable

임의의 정방행렬 A에 대해서 다음이 성립한다고 하자.

\[\begin{aligned} &AP = PD \\ &\Longleftrightarrow A = PDP^{-1}\\ &\Longleftrightarrow P^{-1}AP = D \end{aligned}\]

\(D\)는 대각행렬이며 \(P\)는 유사행렬이라고 하며 역행렬이 존재하는 정방행렬이라고 한다.
위와 같은 경우 \(A\)는 diagonalizable(대각화 가능하다)이라고 한다.

정방행렬의 EVD와 Diagonalizable의 연관성

대각화(diagonalization)와 고윳값분해(EVD)는 매우 연관된 개념이다.
어떤 행렬이 Diagonalizable하다는 의미는 대각행렬(diagonal matrix)과 유사행렬(similar matrix)의 곱으로 표현할 수 있다는 의미이다.
이때 고윳값을 대각원소로 하는 대각행렬을 만들고 고유벡터를 열벡터로 유사행렬을 만들면 고윳값분해를 통해 대각화를 할 수 있는 것이다.
정리하자면 정방행렬의 대각화는 고윳값 분해를 이루어질 수 있다고 할 수 있다.

대각화 관련 동치명제 정리

\(A \in \mathbb{R}^{n \times n}\)이라 했을때 다음의 명제는 동치이다.

\[\begin{aligned} &A\text{가 diagonalizable하다.} \\ &\longleftrightarrow A \text{가 eigen decomposition이 가능하다.}\\ &\longleftrightarrow V^{-1}\text{를 구할 수 있다.} \\ &\longleftrightarrow \text{det(V)가 존재한다.} \\ &\longleftrightarrow \text{V에 존재하는 n개의 vector는 선형독립이다.} \\ &\longleftrightarrow A \text{에 대한 선형독립인 eigenvector가 n개 존재한다.} \end{aligned}\]

분해했을 때 좋은 점

행렬의 거듭제곱을 간단히 구한다.

\[\begin{aligned} A^k = V\Lambda V^{-1}V\Lambda V^{-1}V\Lambda V^{-1} \dots V\Lambda V^{-1} = V\Lambda^kV^{-1} \end{aligned}\]

inverse matrix의 계산이 간단해진다.

\[A^{-1} = (V\Lambda V^{-1})^{-1} = V\Lambda ^{-1}V^{-1}\]

eigen value를 모두 곱하면 determinant
- 임의의 행렬에 대해서 \(\text{det}(A^{-1}) = \frac{1}{\text{det}(A)}\)이다.
- 또한 대각행렬의 행렬식은 주대각선에 있는 원소를 모두 곱하는 것과 같다. 그러므로 다음과 같다.

\[\begin{aligned} &\text{det}(A) = \text{det}(V\Lambda V^{-1}) = \text{det}(V)\text{det}(\Lambda)\text{det}(V^{-1}) = \text{det}(\Lambda) = \prod_{i=1}^n\lambda_i \\ &\text{where, } \Lambda = \text{diag}(\lambda_1,\lambda_2,\dots,\lambda_n) \end{aligned}\]

eigenvector를 모두 더하면 trace이다.

\[\text{tr}(A) = \text{tr}(V\Lambda V^{-1}) \overset{\text{tracetrick}}{=} \text{tr}(V^{-1}V\Lambda) = \text{tr}(\Lambda) = \sum_{i=1}^n\lambda_i\]

\(\lambda = 0\)인 eigenvalue의 존재여부 파악가능하다.

\[\begin{aligned} &\text{행렬 A가 rank - defficient}이다. \\ &\Longleftrightarrow \text{det}(A) = 0 \\ &\Longleftrightarrow \prod_{i=1}^n\lambda_i = 0 \\ &\Longleftrightarrow \text{0인 eigen value가 하나 이상 존재한다.} \end{aligned}\]

알아둬야 할 것들

1. \(A^T\)의 eigen value와 \(A\)의 eigen value는 같다.

eigen value를 구하는 characteristic equation이 같기 때문이다.

\[\begin{aligned} \text{det}(A-\lambda I) &= \text{det}((A-\lambda I)^T)\quad(\text{ by} |A| = |A^T|)\\ &= \text{det}(A^T - \lambda I) \end{aligned}\]

2. \(Q\)가 orthonormal matrix \(\Longrightarrow\) \(\lambda = 1 \text{ or } \lambda = -1\)

\[\begin{aligned} &Qv = \lambda v \\ &\longleftrightarrow (Qv)^TQv = v^TQ^TQv = v^Tv = |v|_2^2 = \lambda^2|v|_2^2\\ &\therefore \lambda = 1 \text{ or } \lambda = -1 \end{aligned}\]

3. 대칭행렬이 positive definite \(\leftrightarrow \forall i,\lambda_i > 0\) (단,\(A=A^T\)인 symmetric matrix,\(\lambda_i\)는 행렬A의 모든 고윳값)

증명1 : 먼저 대칭행렬이 positive definite \(\rightarrow \forall i,\lambda_i > 0\)임을 보인다.

\[\begin{aligned} A &= V\Lambda V^T = \begin{bmatrix}v_1 & v_2 & \dots & v_n\end{bmatrix} \begin{bmatrix} \lambda_1 & 0 &\dots & 0 \\ 0 & \lambda_2 &\dots &0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0& \dots & \lambda_n \end{bmatrix} \begin{bmatrix} v_1^T \\ v_2^T \\ \vdots \\ v_n^T \end{bmatrix} \\ &= \begin{bmatrix} \lambda_1v_1 & \lambda_2v_2 & \dots & \lambda_nv_n \end{bmatrix} \begin{bmatrix} v_1^T \\ v_2^T \\ \vdots \\ v_n^T \end{bmatrix} \\ &=\sum_{i=1}^{n}\lambda_iv_iv_i^T \end{aligned}\]

대칭행렬\(A\)가 양의 정부호일 경우 \({\bf{x}}^TA{\bf{x}} >0\) 이므로 \(x\)를 행렬A의 임의의 고유벡터인 \(v_j\)로 놓아도 성립해야한다. 즉 다음과 같다.

\[\begin{aligned} &\forall j\in(1,\dots,n),\,v_j^TAv_j >0 \\ &\longleftrightarrow\forall j\in(1,\dots,n),\,v_j^T(\sum_{i=1}^n\lambda_iv_iv_i^T)v_j >0 \end{aligned}\]

그런데 대칭행렬의 경우 고유벡터는 직교(orthogonal)한다. 즉 다음과 같이 정리된다.

\[\begin{aligned} &\forall j\in(1,\dots,n),\,v_j^T(\sum_{i=1}^n\lambda_iv_iv_i^T)v_j >0\\ &\longleftrightarrow\forall j\in(1,\dots,n),\, v_j^T(\lambda_1v_1 + \lambda_2v_2 + \dots + \lambda_jv_j + \dots \lambda_nv_n)v_j >0\\ &\longleftrightarrow\forall j\in(1,\dots,n),\,\lambda_jv_j^Tv_j = \lambda_j|v_j|_2^2>0\\ &\longleftrightarrow\forall j\in(1,\dots,n),\,\lambda_j>0 \end{aligned}\]

그러므로, 고윳값은 항상0보다 크다.
증명2 : 그 다음 \(\forall i,\lambda_i > 0 \rightarrow\) 대칭행렬이 positive definite임을 증명한다.
이차형식은 다음과 같다.

\[\begin{aligned} {\bf{x}}^TA{\bf{x}} &= {\bf{x}}^T(\sum_{i=1}^{n}\lambda_iv_iv_i^T){\bf{x}} = \sum_{i=1}^n\lambda_i{\bf{x}}^Tv_iv_i^T{\bf{x}} = \sum_{i=1}^n\lambda_i{\bf{x}}^Tv_i({\bf{x}}^Tv_i)^T \\ &=\sum_{i=1}^n\lambda_i({\bf{x}}^Tv_i)^T{\bf{x}}^Tv_i = \sum_{i=1}^n\lambda_i||{\bf{x}}^Tv_i||^2\\ &=\lambda_1||{\bf{x}}^Tv_1||^2 + \lambda_2||{\bf{x}}^Tv_2||^2 + \dots + \lambda_n||{\bf{x}}^Tv_n||^2 \end{aligned}\]

행렬A의 고유벡터의 집합을 \(B = {v_1,v_2,\dots,v_n}\)으로 두면 고유벡터는 서로간에 직교하므로 orthogonal set이며 이는 \(\mathbb{R}^n\)의 직교기저가 될 수 있음을 의미한다.그러므로, \({\bf{x}} \in \mathbb{R}^n\)인 \({\bf{x}}\)에 대하여 내적\({\bf{x}}^Tv_i\)의 값은 적어도 하나는 고유벡터에서는 0보다 커야한다.(간단히 2차원상에 존재하는 벡터는 2차원 공간을 span하는 기저와 모두 직교할 수 없으며 적어도 하나의 기저와는 내적을 했을때 0보다 크다.)

\[||{\bf{x}}^Tv_1||^2 + ||{\bf{x}}^Tv_2||^2 + \dots + ||{\bf{x}}^Tv_n||^2 > 0\]

결과적으로,\(\forall i,\lambda_i>0\)이라고 가정했으므로 다음과 같다.

\[{\bf{x}}^TA{\bf{x}} = \lambda_1||{\bf{x}}^Tv_1||^2 + \lambda_2||{\bf{x}}^Tv_2||^2 + \dots + \lambda_n||{\bf{x}}^Tv_n||^2 > 0\]

4. Diagonalizable matrix의 non-zero eigenvalue의 수는 rank(A)이다.(중요)

diagonalizable할 경우 EVD가 가능하다. 따라서 다음과 같이 고유분해 할 수 있다.

\[\begin{aligned} A = V\Lambda V^{-1} \end{aligned}\]

임의의 행렬이 서로다른 행렬의 곱인 경우에 행렬의 랭크는 곱해진 행렬 중 가장작은 랭크를 따라간다. 윗 식에서 \(V,V^{-1}\)는 역행렬이 존재하며 full rank이므로 랭크는 \(\Lambda\)에 달려있다.

\[\begin{aligned} &\text{rank}(A) = \text{rank}(V\Lambda V^{-1}) = \text{rank}(\Lambda)\\ &\text{where } \Lambda = \begin{bmatrix} \lambda_1 & 0 &\dots & 0 \\ 0 & \lambda_2 &\dots &0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0& \dots & \lambda_n \end{bmatrix} \end{aligned}\]

따라서 \(\text{rank}(A) =\) 0이아닌 고윳값의 갯수와 같음을 알 수 있다.