[LA] 예제 : Eigen value, Eigen vector 구하기

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 transformatino $\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^TA$라는 symmetric matrix를 이용하기 때문임.

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

위의 Quadratic form에서 unit vector $\textbf{x}$의 경우 최대값은 $A^TA$의 eigen value중에서 가장 큰 값에 해당하며, 최소값도 eigen value 중 가장 작은 값에 해당하므로 $A^TA$의 eigen value 중 최대값을 구하고, 이에 해당하는 eigen vector를 구하면 됨.

 

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

$$A^TA=\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^TA$의 eigen value $\lambda$와 eigne vector $\textbf{x}$는 다음이 성립.

$$A^TA\textbf{x}=\lambda\textbf{x} \\ A^TA\textbf{x}-\lambda\textbf{x}=\textbf{0}\\(A^TA-\lambda I)\textbf{x}=\textbf{0}$$

$\textbf{x}$가 eigne vector이므로 $\textbf{x}\ne\textbf{0}$이 성립한다. (eigen value는 0이 될 수 있지만, eigen vector는 zero vector가 될 수 없음을 기억.)

 

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

$$ \text{det}(A^TA-\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임을 의미함.

 

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

$$(A^TA-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 eigen vector $\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}$임.