Eigen Values and Eigen Vectors
Basic Definitions
\[\begin{gather*} Ax = \lambda x \end{gather*}\]- $x$ is an eigen vector, $\lambda$ is an eigen value
Important properties
- Only square matrices have eigen values and vectors
How To Find Eigen Values and Eigen Vectors
- Solve the characteristic equation:
This gives eigen values $\lambda_1…$
- For each eigen value:
This is a singular system (whose determinant is 0). The system has non-trivial solutions. One can use Gaussian elimination to solve for v.
Eigen value Decomposition
Say a matrix $A$ has two eigen vectors $v_1$, $v_2$, and their corresponding eigen values are: $\sigma_1$, $\sigma_2$
Then, we have
\[\begin{gather*} A \begin{bmatrix} v_1 & v_2 \end{bmatrix} = \begin{bmatrix} v_1 & v_2 \end{bmatrix} \begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix} \end{gather*}\]So, we can get Eigen Value Decomposition:
\[\begin{gather*} V = \begin{bmatrix} v_1 & v_2 \end{bmatrix}, \Lambda = \begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix} \\ => A = V \Lambda V^{-1} \end{gather*}\]Applications
Series of self-multiplications
Assume we want to apply the same linear transform 8 times. Say, $A^8$
Matrix multiplication is expensive. One can use divide and conquer, and do the multiplication in the order of $log2(8)$ times.
But with Eigen Value Decomposition, this problem becomes:
\[\begin{gather*} A^8 = V \Lambda^8 V^{-1} \end{gather*}\]$\Lambda^8$ is easy to calculate, because it’s just a diagonal matrix.
Covariance Matrix
\[\begin{gather*} \begin{aligned} & \Sigma = \frac{1}{N-1} (X-\mu) (X-\mu)^T \end{aligned} \end{gather*}\]In other words, $\Sigma = A^TA$ where A is a normalized and scaled $X$. $\Sigma$ is symmetric, and positive semi-definite.
The eigen vectors of $\Sigma$ are orthogonal. For an arbitrary eigen vector, $v$, there is $\Sigma v = \lambda v = A^TA v$. The eigen vector with the largest eigen value is the vector of the fitted line. Why?
\[\begin{gather*} \begin{aligned} & v^T \Sigma v = v^T A^TA v = v^T \lambda v \\ & = (Av)^T (Av) = \lambda \end{aligned} \end{gather*}\]Note that each row in A is a normalized point p in X. So $Av$ is the projection of the vector op on the eigen vector, v. The largest $\lambda_m$ gives the eigen vector $v_m$ with the largest total projection.
