Chapter 10: Eigenvalues and Eigenvectors

---

In this chapter, we introduce the concepts of eigenvalues and eigenvectors of a square matrix. These concepts have numerous uses, for example, to better understand and visualize linear mappings, to understand the stability of mechanical constructions, for solving systems of differential equations, to recognize images, to interpret and visualize quadratic equations, and for image segmentation. First, let us start with two examples.

---

Let us start with the definition of eigenvalues and eigenvectors.

In Chapter 9, we saw that a linear mapping can be represented as matrix multiplication. For linear mappings, we define eigenvectors and eigenvalues in the corresponding way, i.e., for a linear mapping $F$, we say that a non-zero vector $\vc{v}$ is an eigenvector if $F(\vc{v})$ is parallel to $\vc{v}$. This means that $F(\vc{v}) = \lambda \vc{v}$. In the same way, $\lambda$ is called the eigenvalue.

In Interactive Illustration 10.3, you may have noticed that changing the length of the vector $\vc{v}$ does not change the fact that it is (or is not) an eigenvector. This follows from the linearity of the mapping, which is described in the following theorem.

---

So the eigenvectors can always be rescaled. However, remember that eigenvectors have to be non-zero.

---

In this section, we will describe how eigenvectors and eigenvalues can be calculated. (Note: The methods is based on finding roots to a polynomial. In practice, there are more efficient numerical methods for finding eigenvalues and eigenvectors. The connection between eigenvalues and roots are then used to calculate roots using eigenvalues and not the other way around).

---

---

Eigenvectors and eigenvalues are connected to a concept of diagonalization. The idea here is that a linear mapping is particularly simple if one chooses the eigenvectors as basis vectors. We will need a definition of diagonalization for both a linear mapping and for a matrix. These two definitions are essentially the same.

For the first definition, we should remember that a linear mapping $F(\vc{v})$ can be defined even without a basis. An example is the linear mapping where the output vector is just the input vector but twice as long - this can be understood regardless of the basis chosen. However, if we do select a basis for the linear mapping, we can write the linear mapping on the form $F(\vc{v}) = \mx{A}\vc{v}$, where $\mx{A}$ is called the transformation matrix. The transformation matrix depends on the basis chosen. With this refresher in mind we are now ready for the definition of diagonalizability for a linear mapping.

The matrix $\mx{A}$ is factorized as a product of three matrices $\mx{V}$, $\mx{D}$, and $\mx{V}^{-1}$. Such factorizations are extremely useful in many applications. We will give a few such applications later in this chapter.

To understand how diagonalization relates to eigenvectors and eigenvalues, we rearrange the matrix equation as

\begin{equation} \mx{A} \mx{V}= \mx{V} \mx{D} . \end{equation}

(10.19)

Let the column vectors of $\mx{V}$ be $(\vc{v}_1, \ldots, \vc{v}_n)$ and let the diagonal elements of $\mx{D}$ be $(\lambda_1, \ldots, \lambda_n)$. Using this notation, the equation can be written

\begin{equation} \mx{A} \begin{pmatrix} \vc{v}_1 & \ldots & \vc{v}_n \end{pmatrix} = \begin{pmatrix} \vc{v}_1 & \ldots & \vc{v}_n \end{pmatrix} \mx{D} \end{equation}

(10.20)

or

\begin{equation} \begin{pmatrix} \mx{A} \vc{v}_1 & \ldots & \mx{A} \vc{v}_n \end{pmatrix} = \begin{pmatrix} \lambda_1 \vc{v}_1 & \ldots & \lambda_n \vc{v}_n \end{pmatrix}. \end{equation}

(10.21)

In other words, column $k$ of the matrix equation reads

\begin{equation} \mx{A} \vc{v}_k = \lambda_k \vc{v}_k, \end{equation}

(10.22)

so the columns of $\mx{V}$ are eigenvectors to $\mx{A}$ and the corresponding eigenvalue is found at the corresponding diagonal element of $\mx{D}$. This can be summarized in a theorem.

For matrices of size $2 \times 2$, the characteristic polynomial is of degree 2 and there are therefore 2 roots (if you count complex roots and take multiplicity of roots into account). In Example 10.5, the two roots ($2$ and $3$) are different and there is a basis of eigenvectors. The same holds for general $n \times n$ matrices as is captured by the following theorem.

---

So if all roots are different, the matrix is diagonalizable. If there are roots with higher multiplicity, the matrix could be either diagonalizable (Example 10.7) or not (Example 10.8).

In Example 10.6, there were only single roots, and thus all eigenvalues are different. According to Theorem 10.4 such matrices are always diagonalizable. A matrix, whose characteristic polynomial has double roots (or roots with higher multiplicity) can be either diagonalizable as in Example 10.7 or not diagonalizable as in Example 10.8. Whether or not it works depends on how many linearly independent eigenvectors one can select from the nullspace of $(\lambda I - \mx{A})$ for each eigenvalue $\lambda$. Here it is useful to introduce the notion of algebraic and geometric multiplicity.

---

---

In both Example 10.7 and Example 10.8, there was only one eigenvalue. In both examples, the algebraic multiplicity was 2. In Example 10.7, the geometric multiplicity was only 1 and the matrix was therefore not diagonalizable. However, in Example 10.8, the geometric multiplicity was 2 and the matrix was therefore diagonalizable. Note that for random matrices, for example, if each element of matrix was drawn from independent normal distributions, the chance of obtaining a non-diagonalizable matrix is extremely small. In fact, if a true continuous normal distribution is used rather than a (discrete) computer approximation, the chance is actually zero. So in some sense, non-diagonalizable matrices are the exception. However, there are practical applications matrices that have inherent structure that makes them non-diagonalizable.

---

We have mostly worked with real matrices and vectors, but it is useful to work with matrices and vectors that contain complex numbers. Even for real matrices, it is sometimes useful to consider complex eigenvalues and eigenvectors. For both real and complex matrices $\mx{A}$, the definition of complex eigenvalues and eigenvectors are similar.

A useful property of symmetric matrices is summarized in the following theorem.

---

Notice that in the proof, we needed the fact that $\bar{\mx{A}}^\T = \mx{A}$. Thus we can prove that all eigenvalues are real even for complex matrices if they fulfill the constraint $\bar{\mx{A}}^\T = \mx{A}$.

---

---

---

In Example 10.4, we studied how long the output vector $F(\vc{v})$ could be if we fixed the length of the input vector. Here we will use the tools from Theorem 10.8 and Theorem 10.7 to understand this better. Given a real matrix $\mx{A}$ and the corresponding linear map $F(\vc{v}) = \mx{A} \vc{v}$ for real vectors $\vc{v}$, which input $\vc{v}$ gives the largest and smallest elongation $s = \frac{|| \mx{A} \vc{v}||}{||\vc{v}||}$? It is easier to study the square of the elongation, i.e.,

\begin{equation} s^2 =\left(\frac{|| \mx{A} \vc{v}||}{||\vc{v}||}\right)^2= \frac{\vc{v}^\T \mx{A}^\T \mx{A} \vc{v}}{\vc{v}^\T \vc{v}}, \end{equation}

(10.65)

where we assume the vector $\vc{v}$ is non-zero. Note that it is the matrix $\mx{A}^\T \mx{A}$ that is relevant here. This matrix is symmetric by construction. Thanks to Theorem 10.8, we know that it is possible to diagonalize the matrix using an orthonormal matrix $\mx{U}$,

\begin{equation} \mx{A}^\T \mx{A} = \mx{U} \mx{D} \mx{U}^\T . \end{equation}

(10.66)

The eigenvalues are real. Notice that $\mx{A}^\T \mx{A}$ is positive semi-definite. This can be seen by $ \vc{v}^T \mx{A}^\T \mx{A} \vc{v} = \left( || \mx{A} \vc{v}|| \right)^2 \geq 0$. From Theorem 10.9 we see that the eigenvalues are non-negative. Assume for simplicity that the eigenvalues are ordered so that $d_1 \geq d_2 \geq \ldots \geq d_n \geq 0$. This means that

\begin{equation} s^2 = \frac{\vc{v}^\T \mx{A}^\T \mx{A} \vc{v}}{\vc{v}^\T \vc{v}} = \frac{\vc{v}^\T \mx{U} \mx{D} \mx{U}^\T \vc{v}}{\vc{v}^\T \mx{U} \mx{U}^\T \vc{v}} . \end{equation}

(10.67)

By change of coordinates $\vc{w} = \mx{U}^\T \vc{v}$, we get

\begin{equation} s^2 = \frac{\vc{w}^\T \mx{D} \vc{w}}{\vc{w}^\T \vc{w}}. \end{equation}

(10.68)

To get a feel for how to maximize this quantity, we notice that the numerator is just

\begin{equation} w_1^2 d_1 + w_2^2 d_2 + \ldots + w_n^2 d_n, \end{equation}

(10.69)

where $d_1, d_2, \dots d_N$ are the diagonal elements in $\mx{D}$. Furthermore, the denominator is simply

\begin{equation} w_1^2 + w_2^2 + \ldots + w_n^2. \end{equation}

(10.70)

Hence, intuitively, if we want to maximize the numerator while keeping the denominator as small as possible, it seems reasonable to put maximum emphasis on the first term, since $d_1$ is the largest element, for instance by using $w_1 = 1$ and $w_j = 0$ for $j\neq1$.

If we want a formal proof for this intuition, we can proceed the following way. First we rewrite Equation (10.68) as

\begin{equation} s^2 = \frac{\sum_{i=1}^n d_i w_i^2 }{\sum_{i=1}^n w_i^2}. \end{equation}

(10.71)

To gain knowledge about the maximum, we find all stationary points by calculating the partial derivatives

\begin{equation} \frac{\partial (s^2)}{\partial w_i} = \frac{ (2 d_i w_i) (\sum_{i=1}^n w_i^2) - (\sum_{i=1}^n d_i w_i^2 )(2 w_i)}{(\sum_{i=1}^n w_i^2)^2} . \end{equation}

(10.72)

Since for stationary points $\frac{\partial (s^2)}{\partial w_i} = 0$ for all $i$, we have

\begin{equation} \begin{pmatrix} d_1 w_1 & w_1 \\ d_2 w_2 & w_2 \\ \vdots & \vdots \\ d_n w_n & w_n \end{pmatrix} \begin{pmatrix} \sum_{i=1}^n w_i^2 \\ \sum_{i=1}^n d_i w_i^2 \end{pmatrix} = \vc{0}. \end{equation}

(10.73)

We thus have a matrix times a vector resulting in zero. The vector is non-zero when the transformed vector $\vc{w}$ is non-zero since the top element is its squared length $||\vc{w}||^2$. Hence, if $\vc{w}\neq \vc{0}$, it must be the matrix that causes the expression to be zero, i.e., it has a null space of at least dimension 1 (nullity 1). This means that the matrix has at most rank 1, since Theorem 8.8 states that the rank plus the nullity must equal the number of columns. However, Theorem 8.9 states that rank is equal to the size of the largest minor (sub-determinant) that is non-zero. Therefore, the largest minor in this case is $1\times 1$. That in turn means that every $2 \times 2$ minor is zero, i.e.,

\begin{equation} \det \begin{pmatrix} d_i w_i & w_i \\ d_j w_j & w_j \end{pmatrix} =(d_i-d_j) w_i w_j = 0 \end{equation}

(10.74)

for all $i$ and $j$. One solution to this is to have only one non-zero element of $\vc{w}$. A global maximum is achieved for $\vc{w}_{max} = \begin{pmatrix} 1 & 0 & \ldots & 0 \end{pmatrix}$ with maximum elongation $d_1$ and a global minimum is achieved for $\vc{w}_{min} = \begin{pmatrix} 0 & 0 & \ldots & 1 \end{pmatrix}$ with minimal elongation $d_n$. Since $\vc{w} = \mx{U}^\T \vc{v}$, we have $\vc{v} = \mx{U} \vc{w}$, which means that the maximum elongation is achieved for $\vc{v}_1$, i.e., the eigenvector to $\mx{A}^\T \mx{A}$ corresponding to the largest eigenvalue and the minimal elongation is achieved for $\vc{v}_n$, i.e., the eigenvector to $\mx{A}^\T \mx{A}$ corresponding to the smallest eigenvalue.

---

In this section, we provide some useful results and properties of eigenvalues and eigenvectors.

---

---

This means that the eigenvalues of $ \mx{A}$ and $\mx{A}^\T$ are the same. However, the eigenvectors could be different.

---

---

---

In this section, we show that eigenvalues and eigenvectors can be truly useful using a set of examples.

Eigenvectors can be used to better understand linear mappings.

A plane was flying from Warsaw to Krakow. As they were going past some beautiful landmarks, the pilot came over the intercom and instructed all who were interested in seeing the landmark to look out the right side of the plane. Many passengers did so, and the plane promptly crashed. Why? There were too many poles in the right hand plane.

---

We round off this chapter with an example that illustrates that there is much more to learn on this topic.