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

Eigen Value Decomposition(EVD)

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

\begin{aligned} A v_{1} = λ_{1} v_{1} \\ A v_{2} = λ_{2} v_{2} \end{aligned}

다음과 식을 생각했을때…

\begin{array}{r} A [\begin{array}{c} v_{1} v_{2} \end{array}] = [\begin{array}{c} A v_{1} A v_{2} \end{array}] = [\begin{array}{c} λ_{1} v_{1} λ_{2} v_{2} \end{array}] = [\begin{array}{c} v_{1} v_{2} \end{array}] [\begin{array}{c} λ_{1} & 0 \\ 0 & λ_{2} \end{array}] \end{array}

$V = [\begin{matrix} v_{1} v_{2} \end{matrix}], Λ = [\begin{matrix} λ_{1} & 0 \\ 0 & λ_{2} \end{matrix}]$ 라 하면 다음과 같이 정리할 수 있다.

\begin{aligned} A V = V Λ \\ ⟺ A = V Λ V^{- 1} \end{aligned}

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

Diagonalizable

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

\begin{aligned} A P = P D \\ ⟺ A = P D P^{- 1} \\ ⟺ P^{- 1} A P = D \end{aligned}

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

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

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

대각화 관련 동치명제 정리

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

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

분해했을 때 좋은 점

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

\begin{array}{r} A^{k} = V Λ V^{- 1} V Λ V^{- 1} V Λ V^{- 1} \dots V Λ V^{- 1} = V Λ^{k} V^{- 1} \end{array}

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

$A^{- 1} = (V Λ V^{- 1})^{- 1} = V Λ^{- 1} V^{- 1}$

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

\begin{aligned} det (A) = det (V Λ V^{- 1}) = det (V) det (Λ) det (V^{- 1}) = det (Λ) = \prod_{i = 1}^{n} λ_{i} \\ where, Λ = diag (λ_{1}, λ_{2}, \dots, λ_{n}) \end{aligned}

eigenvector를 모두 더하면 trace이다.

$tr (A) = tr (V Λ V^{- 1}) \overset{tracetrick}{=} tr (V^{- 1} V Λ) = tr (Λ) = \sum_{i = 1}^{n} λ_{i}$

$λ = 0$ 인 eigenvalue의 존재여부 파악가능하다.

\begin{aligned} 행렬 A가 rank - defficient 이 다 . \\ ⟺ det (A) = 0 \\ ⟺ \prod_{i = 1}^{n} λ_{i} = 0 \\ ⟺ 0인 eigen value가 하나 이상 존재한다. \end{aligned}

알아둬야 할 것들

1. $A^{T}$ 의 eigen value와 $A$ 의 eigen value는 같다.

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

\begin{aligned} det (A - λ I) & = det ((A - λ I)^{T}) (by | A | = | A^{T} |) \\ = det (A^{T} - λ I) \end{aligned}

2. $Q$ 가 orthonormal matrix $⟹$ $λ = 1 or λ = - 1$

\begin{aligned} Q v = λ v \\ ⟷ (Q v)^{T} Q v = v^{T} Q^{T} Q v = v^{T} v = | v |_{2}^{2} = λ^{2} | v |_{2}^{2} \\ ∴ λ = 1 or λ = - 1 \end{aligned}

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

증명1 : 먼저 대칭행렬이 positive definite $\to \forall i, λ_{i} > 0$ 임을 보인다.

\begin{aligned} A & = V Λ V^{T} = [\begin{array}{c} v_{1} & v_{2} & \dots & v_{n} \end{array}] [\begin{array}{c} λ_{1} & 0 & \dots & 0 \\ 0 & λ_{2} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & λ_{n} \end{array}] [\begin{array}{c} v_{1}^{T} \\ v_{2}^{T} \\ ⋮ \\ v_{n}^{T} \end{array}] \\ = [\begin{array}{c} λ_{1} v_{1} & λ_{2} v_{2} & \dots & λ_{n} v_{n} \end{array}] [\begin{array}{c} v_{1}^{T} \\ v_{2}^{T} \\ ⋮ \\ v_{n}^{T} \end{array}] \\ = \sum_{i = 1}^{n} λ_{i} v_{i} v_{i}^{T} \end{aligned}

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

\begin{aligned} \forall j \in (1, \dots, n), v_{j}^{T} A v_{j} > 0 \\ ⟷ \forall j \in (1, \dots, n), v_{j}^{T} (\sum_{i = 1}^{n} λ_{i} v_{i} v_{i}^{T}) v_{j} > 0 \end{aligned}

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

\begin{aligned} \forall j \in (1, \dots, n), v_{j}^{T} (\sum_{i = 1}^{n} λ_{i} v_{i} v_{i}^{T}) v_{j} > 0 \\ ⟷ \forall j \in (1, \dots, n), v_{j}^{T} (λ_{1} v_{1} + λ_{2} v_{2} + \dots + λ_{j} v_{j} + \dots λ_{n} v_{n}) v_{j} > 0 \\ ⟷ \forall j \in (1, \dots, n), λ_{j} v_{j}^{T} v_{j} = λ_{j} | v_{j} |_{2}^{2} > 0 \\ ⟷ \forall j \in (1, \dots, n), λ_{j} > 0 \end{aligned}

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

\begin{aligned} x^{T} A x & = x^{T} (\sum_{i = 1}^{n} λ_{i} v_{i} v_{i}^{T}) x = \sum_{i = 1}^{n} λ_{i} x^{T} v_{i} v_{i}^{T} x = \sum_{i = 1}^{n} λ_{i} x^{T} v_{i} (x^{T} v_{i})^{T} \\ = \sum_{i = 1}^{n} λ_{i} (x^{T} v_{i})^{T} x^{T} v_{i} = \sum_{i = 1}^{n} λ_{i} | | x^{T} v_{i} | |^{2} \\ = λ_{1} | | x^{T} v_{1} | |^{2} + λ_{2} | | x^{T} v_{2} | |^{2} + \dots + λ_{n} | | x^{T} v_{n} | |^{2} \end{aligned}

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

$| | x^{T} v_{1} | |^{2} + | | x^{T} v_{2} | |^{2} + \dots + | | x^{T} v_{n} | |^{2} > 0$

결과적으로, $\forall i, λ_{i} > 0$ 이라고 가정했으므로 다음과 같다.

$x^{T} A x = λ_{1} | | x^{T} v_{1} | |^{2} + λ_{2} | | x^{T} v_{2} | |^{2} + \dots + λ_{n} | | x^{T} v_{n} | |^{2} > 0$

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

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

\begin{array}{r} A = V Λ V^{- 1} \end{array}

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

\begin{aligned} rank (A) = rank (V Λ V^{- 1}) = rank (Λ) \\ where Λ = [\begin{array}{c} λ_{1} & 0 & \dots & 0 \\ 0 & λ_{2} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & λ_{n} \end{array}] \end{aligned}

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