• You should read about eigenvectors and eigenvalues in MATH_6 to be able to understand the following.

2.7. Eigendecomposition

• We can understand better about a mathematical object if we breakdown them. For example, we can represent the number $12$ by the prime numbers: $12=2^2\times3$. From this representation, we can conclude some property, such as $12$ is divisible by $3$ and not divisible by $5$.

• Similarly, we can decompose a matrix into a set of eigenvectors and eigenvalues, it called eigendecompose.

  Note that: If $\vec v$ is an eigenvector of matrix $A$ then $s\vec v$ ($s\in\mathbb{R}, s\ne0$) is a eigenvector too. For this reason, we only look for unit eigenvectors.

• Suppose that a matrix $A$ has $n$ linearly independent eigenvectors $\{v^{(1)},...,v^{(n)}\}$ with corresponding eigenvalues $\{\lambda_1,...,\lambda_n\}$. The eigendecomposition of $A$ is:

  $$A=V\text{diag($\vec\lambda)$}V^{-1}$$

  where $V=[v^{(1)},...,v^{(n)}]$ and $\vec\lambda=[\lambda_1,...,\lambda_n]^T$

• We have seen constructing matrices with specific eigenvectors and eigenvalues allows us to stretch space in desired directions.

  

• However, not every matrix can be decomposed into eigenvectors and eigenvalues. In some cases, some eigenvalues are complex number. At this, we can use only real-valued eigenvalues and eigenvectors:

  $$A=Q\Lambda Q^\top$$

  where $Q$ is an orthogonal matrix composed of eigenvectors of $A$. $\Lambda$ is diagonal matrix, where the eigenvalue $\Lambda_{i,i}$ is associated with the eigenvector in column $i$ of $Q$.

• The eigendecomposition tells us some useful fact about the matrix:

  • The matrix is singular if and only if any the eigenvalues are zero.

  • The eigendecomposition of real symmetric matrix can be used to optimize quadratic expressions of the form $f(\mathbb{x})=\mathbb{x}^\top A\mathbb{x}$ subject to $||\mathbb{x}||_2=1$:

    • Whenever $\mathbb{x}$ is equal to an eigenvector of $A$, $f$ takes on the value of the corresponding eigenvalue.

    • $\min f(\mathbb{x})=\min_{i=1...n}\lambda_i$ , $\max f(\mathbb{x})=\max_{i=1...n}\lambda_i$. We can prove it:

      As $A$ is symmetric, $V\in\mathbb{R}^{n\times n}$ is an orthogonal basis, $V^\top A V=\text{diag}(\vec\lambda)$ and $V^\top V=I$.

      As $V$ is orthogonal, we have $||V^\top\mathbb{x}||=||\mathbb{x}||$.

      As $||\mathbb{x}||_2=1$,

      $$\begin{align} f(\mathbb{x})&=\mathbb{x}^\top A\mathbb{x}\\&=\mathbb{x}^\top V\text{diag}(\vec\lambda)V^\top\mathbb{x}\\&=y^\top\text{diag}(\vec\lambda)y\\&=\sum_{i=1}^ny_i^2\lambda_i \end{align}$$

      where $y=V^\top\mathbb{x}$, $||y||_2=1$ - it means $\sum y_i^2=1$. So we obtain $f(\mathbb{x})$ is a convex combination of $\lambda_i$. Thus, $\min f(\mathbb{x})=\min_{i=1...n}\lambda_i$ , $\max f(\mathbb{x})=\max_{i=1...n}\lambda_i$.

• A matrix whose eigenvalues are all positive is called positive definite. A matrix whose eigenvalues are all positive or zero valued is called positive semidefinite. If all eigenvalues are negative, the matrix is negative definite.

• Positive semidefinite matrices guarantee that $\forall \mathbb{x}$, $\mathbb{x}^\top A\mathbb{x}\ge0$. Positive definite matrices guarantee that $\mathbb{x}^\top A\mathbb{x}=0\Rightarrow \mathbb{x}=0$.

Reference:

• 2.7 | Deep Learning | Ian Goodfellow, Yoshua Bengio, Aaron Courville.
• Eigendecomposition - Optimization of quadratic expressions | Stack Exchange.