[LA] 예제: Eigenvalue, Eigenvector 구하기

출처

Linear Algebra and Its Applications (5th ed.), David C. Lay, Pearson 2014
Chapter 7.4 Example 1 

문제

$A=\begin{bmatrix}4 & 11 &14 \\ 8 & 7&-2\end{bmatrix}$를
standard matrix로 가지는 linear transformation $\textbf{x}\mapsto A\textbf{x}$에서
$\|A\textbf{x}\|$를 최대화시키는 unit vector $\textbf{x}$를 구하고,
해당 unit vector가 매핑된 vector $A\textbf{x}$의 length를 구하라.

---

풀이

해당 문제는 다음의 Constrained Optimzaion 문제임.

$$\underset{\textbf{x}}{\text{arg max}}\|A\textbf{x}\|=\underset{\textbf{x}}{\text{arg max}}\|A\textbf{x}\|^2$$

where

• $\|\textbf{x}\|=1$ : 즉 $\textbf{x}$는 unit vector임.

Quadratic Form을 이용하는 경우,

같은 $\textbf{x}$를 구하면서도 보다 쉽게 구할 수 있음.

 

이는 아래와 같이 $A^\top A$라는 Symmetric Matrix를 이용하기 때문임.

$$\|A\textbf{x}\|^2=(A\textbf{x})^\top (A\textbf{x})=\textbf{x}^\top A^\top A\textbf{x}=\textbf{x}^\top(A^\top A)\textbf{x}$$

위의 Quadratic Form에서 unit vector $\textbf{x}$의 경우

• 최대값은 $A^\top A$의 Eigenvalue중에서 가장 큰 값에 해당하며,
• 최소값은 Eigenvalue 중 가장 작은 값에 해당하므로

$A^\top A$의 Eigenvalue 중 최대값을 구하고, 이에 해당하는 Eigenvector를 구하면 됨.

 

우선 $A^\top A$를 구하면 다음과 같음.

$$A^\top A=\begin{bmatrix}4 & 8 \\11 & 7 \\14& -2\end{bmatrix}\begin{bmatrix}4 & 11 & 14\\8 & 7 & -2\end{bmatrix}=\begin{bmatrix}80 & 100 & 40\\100 & 170 & 140\\40 & 140 & 200\end{bmatrix}$$

 

$A^\top A$의 Eigenvalue $\lambda$와 Eignevector $\textbf{x}$는 다음이 성립.

$$\begin{aligned}A^\top A\textbf{x} &= \lambda\textbf{x} \\ A^\top A\textbf{x} &= \lambda I \textbf{x}\\(A^\top A-\lambda I)\textbf{x} &= \textbf{0} \end{aligned}$$

$\textbf{x}$가 Eignevector이므로 $\textbf{x}\ne\textbf{0}$이 성립한다.

• Eigenvalue는 0이 될 수 있지만,
• Eigenvector는 zero vector가 될 수 없음을 기억.

 

이를 이용하여 $\lambda$를 구할 수 있음.

$$ \text{det}(A^\top A-\lambda I)=0\\ \left| \begin{matrix} 80-\lambda & 100 & 40 \\ 100 & 170-\lambda & 140 \\ 40 & 140 & 200-\lambda \end{matrix}\right|=0\\ (-\lambda+80)\{(-\lambda+170)(-\lambda+200)-140^2\} + 100 \{140\cdot40-100(-\lambda+200)\} + 40 (100\cdot 140-(-\lambda+170)40\}=0\\ (-\lambda+80)(-\lambda+170)(-\lambda+200)-140^2(-\lambda+80)+100\cdot140\cdot 40 -100^2(-\lambda+200) +40\cdot100\cdot140-40^2(-\lambda+170)=0\\ -\lambda^3+450\lambda^2-32400\lambda=0\\ -\lambda(\lambda^2-450\lambda+32400)=0\\-\lambda(\lambda-90)(\lambda-360)=0$$

이는 $\|A\textbf{x}\|^2$의 최대값이 바로 360임을 의미함.

 

여기에 가장 큰 Eigenvalue인 360에 대한 Eigenvector $\textbf{x}$를 구함.

$$(A^\top A-360I)\textbf{x}=\textbf{0}$$

Gauss Elimination 으로 풀면 다음과 같음.

$$\begin{aligned}\begin{bmatrix}-280 & 100 & 40 & 0 \\ 100 &-190 & 140 & 0\\ 40 & 140 & -160 & 0\end{bmatrix} &\sim \begin{bmatrix}1 & \frac{-5}{14} & \frac{-1}{7} & 0 \\ 100 &-190 & 140 & 0\\ 40 & 140 & -160 & 0\end{bmatrix}\\ &\sim \begin{bmatrix}1 & \frac{-5}{14} & \frac{-1}{7} & 0\\ 0 & \frac{-1080}{7} & \frac{1080}{7} & 0\\ 0  & \frac{1080}{7} & \frac{-1080}{7} & 0\end{bmatrix} \\ &\sim \begin{bmatrix}1 & \frac{-5}{14} & \frac{-1}{7} & 0\\ 0 & \frac{-1080}{7} & \frac{1080}{7} & 0\\ 0 & 0 & 0 & 0\end{bmatrix} \\ &\sim \begin{bmatrix}1 & \frac{-5}{14} & \frac{-1}{7} & 0\\ 0 & 1 & -1 & 0\\ 0 & 0 & 0 & 0\end{bmatrix} \\ &\sim \begin{bmatrix}1 & 0 & \frac{-1}{2} & 0\\ 0 & 1 & -1 & 0\\ 0 & 0 & 0 & 0\end{bmatrix} \end{aligned}$$

즉 다음이 성립.

$$x_1=\frac{1}{2}x_3 \\ x_2=x_3$$

Unit Eigenvector $\textbf{x}$를 다음과 같은 Vector로 취할 수 있음.

$$\textbf{x}=\begin{bmatrix}\frac{1}{3}\\\frac{2}{3}\\\frac{2}{3}\end{bmatrix}$$

 

결국, $\|A\textbf{x}\|$의 최대값은 $\sqrt{360}=6\sqrt{10}$이고, 이때의 unit vector $\textbf{x}=\begin{bmatrix}\frac{1}{3}\\\frac{2}{3}\\\frac{2}{3}\end{bmatrix}$임.

 

---

같이보면 좋은 자료

2024.11.06 - [.../Linear Algebra] - [LA] Eigenvalue and Eigenvector

[LA] Eigenvalue and Eigenvector

---