# Week 12 - Eigenvalues and Eigenvectors

## The Algebraic Eigenvalue Problem

• The algebraic eigenvalue problem is given by $$Ax = \lambda x$$

• where $A \in \mathbb{R}^{n \times n}$ is a square matrix, $\lambda$ is a scalar, and $x$ is a nonzero vector.

• If $x \ne 0$, then $\lambda$ is said to be an eigenvalue and x is said to be an eigenvector associated with the eigenvalue $\lambda$.
• The tuple $(\lambda, x)$ is said to be an eigenpair.
• The set of all vectors x that satisfy $Ax = \lambda x$ is a subspace, called eigenspace.
• Equivalent statements:

• $Ax = \lambda x$, where $x \ne 0$.
• $(A - \lambda I) x = 0$, where $x \ne 0$.
• $A - \lambda I$ is singular.
• $\mathcal{N}(A - \lambda I)$ contains a nonzero vector x.
• This is a consequence of there being a vector $x \ne 0$ such that $(A - \lambda I)x = 0$.
• $\text{dim}(\mathcal{N}(A - \lambda I)) > 0$.
• $\text{det}(A - \lambda I) = 0$.
• => $\mathcal{N}(A - \lambda I) \ne \{0\}$
• A is a square matrix => $(A - \lambda I)$ is not invertible
• => $(A - \lambda I) x = 0$ has many solutions.
• More proves in Week 7#Showing that A^T A is invertible
• If we ﬁnd a vector $x \ne 0$ such that $Ax = \lambda x$, it is certainly not unique.

• For any scalar $\alpha$, $A(\alpha x) = \lambda (\alpha x)$ also holds.
• If $Ax = \lambda x$ and $Ay = \lambda y$, then $A(x + y) = Ax + Ay = \lambda x + \lambda y = \lambda (x + y)$
• We conclude that the set of all vectors $x$ that satisfy $Ax = \lambda x$ is a subspace.

## Simple cases

• The eigenvalue of the zero matrix is the scalar $\lambda = 0$. All nonzero vectors are eigenvectors.
• The eigenvalue of the identity matrix is the scalar $\lambda = 1$. All nonzero vectors are eigenvectors.
• The eigenvalues of a diagonal matrix are its elements on the diagonal. The unit basis vectors are eigenvectors.
• The eigenvalues of a triangular matrix are its elements on the diagonal.
• Because if there is a zero on the diagonal, it is singular.
• The eigenvalues of a 2 × 2 matrix can be found by finding the roots of $p_2(\lambda) = \text{det}(A - \lambda I) = 0$
• The eigenvalues of a 3 × 3 matrix can be found by finding the roots of $p_3(\lambda) = \text{det}(A - \lambda I) = 0$

### Compute the eigenvalues and eigenvectors of 2×2 matrices

• Compute $$\text{det}(\begin{pmatrix} (\alpha_{0,0} - \lambda) & \alpha_{0,1} \ \alpha_{1,0} & (\alpha_{1,1} - \lambda)\end{pmatrix}) = (\alpha_{0,0} - \lambda)(\alpha_{1,1} - \lambda) - \alpha_{0,1}\alpha_{1,0} = 0$$
• Recognize that this is a second degree polynomial in $\lambda$.
• It is called the characteristic polynomial of the matrix $A, p_2(\lambda)$.
• Compute the coefficients of $p_2(\lambda)$ so that $$p_2(\lambda) = - \lambda^2 + \beta \lambda + \gamma$$
• Solve $$- \lambda^2 + \beta \lambda + \gamma = 0$$
• for its roots. You can do this either by examination, or by using the quadratic formula: $$\lambda = \frac{-\beta \pm \sqrt{\beta^2 + 4 \gamma} }{-2}$$
• Find all of the eigenvectors that satisﬁes $$\begin{pmatrix} (\alpha_{0,0} - \lambda) & \alpha_{0,1} \ \alpha_{1,0} & (\alpha_{1,1} - \lambda)\end{pmatrix}\begin{pmatrix} \chi_0 \ \chi_1\end{pmatrix} = \begin{pmatrix} 0 \ 0\end{pmatrix}$$
• Transform $\begin{pmatrix} (\alpha_{0,0} - \lambda) & \alpha_{0,1} \\ \alpha_{1,0} & (\alpha_{1,1} - \lambda)\end{pmatrix}$ to row-echelon form with different $\lambda$s, find the eigenspaces.
• Check your answer! It is a matter of plugging it into $Ax = \lambda x$ and seeing if the computed $\lambda$ and $x$ satisfy the equation.

#### Example

• $A = \begin{bmatrix} 1 & 2 \\ 4 & 3 \end{bmatrix}$
• $\text{det}(\begin{bmatrix} 1 - \lambda & 2 \\ 4 & 3 - \lambda \end{bmatrix}) = 0$
• $(1 - \lambda) (3 - \lambda)- 8 = 0$
• => $\lambda = 5 \text{ or } \lambda = -1$
• For any eigenvalues $\lambda$, $\mathcal{E}_A(\lambda) = \mathcal{N}(\lambda I_n - A)$
• $\mathcal{E}_A(\lambda)$: eigenspace.
• when $\lambda = 5$, then $\mathcal{E}_A(5) = \mathcal{N}(\begin{bmatrix} 4 & -2 \\ -4 & 2 \end{bmatrix})$.
• Transform to row-echelon form, we get $\begin{bmatrix} 1 & -1/2 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} \chi_0 \\ \chi_1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$
• then $\chi_0 = \frac{1}{2} \chi_1$
• $\mathcal{E}_A(5) = \{\begin{bmatrix} \chi_0 \\ \chi_1 \end{bmatrix} = \epsilon \begin{bmatrix} 1/2 \\ 1 \end{bmatrix}, \epsilon \in \mathbb{R}\}$
• $\mathcal{E}_A(5) = \text{Span}(\begin{bmatrix} 1/2 \\ 1 \end{bmatrix})$
• Same way, we get $\mathcal{E}_A(-1) = \text{Span}(\begin{bmatrix} -1 \\ 1 \end{bmatrix})$

## Diagonalization

• Theorem: Let $A \in \mathbb{R}^{n \times n}$. Then there exists a nonsingular matrix $X$ such that $X^{-1} A X = \Lambda$ iff $A$ has n linearly independent eigenvectors. Then \begin{aligned} X^{-1} A X &= \Lambda \ A X &= X \Lambda \ A &= X \Lambda X^{-1}\end{aligned}
• $\Lambda = \begin{pmatrix} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \ddots & \\ & & & \lambda_n \end{pmatrix}$

• If $\Lambda$ is in addition diagonal, then the diagonal elements of $\Lambda$ are eigenvalues of A and the columns of X are eigenvectors of A.
• For example:
• $A = \begin{pmatrix} 1 & -1 \\ 2 & 4 \end{pmatrix}$
• the eigenpairs are $(2, \begin{pmatrix} -1 \\ 1 \end{pmatrix}), (3 \begin{pmatrix} -1 \\ 2 \end{pmatrix})$
• Then:
• • The matrix A can be diagonalized.

### Defective matrices

• A defective matrix is a square matrix that does not have a complete basis of eigenvectors, and is therefore not diagonalizable. In particular, an n × n matrix is defective if and only if it does not have n linearly independent eigenvectors.

#### Jordan Block

• In general, the k ×k matrix $J_k(\lambda)$ given by

• $J_k(\lambda) = \begin{pmatrix} \lambda & 1 & 0 & \cdots & 0 & 0 \\ 0 & \lambda & 1 & \cdots & 0 & 0 \\ 0 & 0 & \lambda & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & \lambda & 1 \\ 0 & 0 & 0 & \cdots & 0 & \lambda \end{pmatrix}$

• a simple example: $$\begin{pmatrix} \lambda & 1 \ 0 & \lambda \end{pmatrix}$$

• Any nontrivial Jordan block of size 2×2 or larger (that is, not completely diagonal) is defective.

• Example

• A simple example of a defective matrix is: $${ {\begin{bmatrix}3&1\0&3\end{bmatrix} } }$$
• which has a double eigenvalue of 3 but only one distinct eigenvector $${\begin{bmatrix}1\0\end{bmatrix} }$$

## General case

• Theorem: The matrix $A \in \mathbb{R}^{n \times n}$ is nonsingular iff $\text{det}(A) \ne 0$.

• Theorem: Given $A \in \mathbb{R}^{n \times n}$, $$p_n(\lambda) = \text{det}(A - \lambda I) = \lambda^n + \gamma_{n-1} \lambda^{n-1} + \cdots + \gamma_1 \lambda + \gamma_0$$ for some coefficients $\gamma_1, \ldots, \gamma_{n-1} \in \mathbb{R}$

• Definition: Given $A \in \mathbb{R}^{n \times n}$, $p_n(\lambda) = \text{det}(A - \lambda I)$ is called the characteristic polynomial.

• ## Properties of eigenvalues and eigenvectors

• Definition: Given $A \in \mathbb{R}^{n \times n}$ and nonzero vector $x \in \mathbb{R}^{n}$ , the scalar $x^T Ax/x^T x$ is known as the Rayleigh quotient.
• Theorem: Let $A \in \mathbb{R}^{n \times n}$ and x equal an eigenvector of A. Assume that x is real valued as is the T eigenvalue λ with $Ax = \lambda x$. Then $\lambda = x x^T Ax x$ is the eigenvalue associated with the eigenvector x.
• Theorem: Let $A \in \mathbb{R}^{n \times n}$ , β be a scalar, and $\lambda \in \Lambda(A)$. Then $\beta \lambda \in \Lambda(\beta A)$.
• Theorem: Let $A \in \mathbb{R}^{n \times n}$ be nonsingular, $\lambda \in \Lambda(A)$, and $Ax = \lambda x$. Then $A^{-1} x = \frac{1}{\lambda} x$.
• Theorem: Let $A \in \mathbb{R}^{n \times n}$, $\lambda \in \Lambda(A)$, Then $(\lambda - \mu ) \in \Lambda(A - \mu I)$.

## Relative Definitions

### Eigenspaces

• the nullspace $A - I\lambda$ is the eigenspace of A for λ denoted by $\mathcal{E}_A(\lambda)$. In other words, $\mathcal{E}_A(\lambda)$ consists of all the eigenvectors of A for λ and the zero vector.

### Algebraic and Geometric Multiplicity

• Example: Let $A = \begin{bmatrix} 1 & 2 \\ 1 & 0 \end{bmatrix}$
• -1 is an eigenvalue of A. and the correspond eigenvector is $\begin{bmatrix} -1 \\ 1 \end{bmatrix}$
• $\mathcal{E}_A(-1) = \text{Span}(\begin{bmatrix} -1 \\ 1\end{bmatrix})$
• The geometric multiplicity of an eigenvalue λ of A is the dimension of $\mathcal{E}_A(\lambda)$
• the geometric multiplicity of −1 is 1.
• The algebraic multiplicity of an eigenvalue λ of A is the number of times λ appears as a root of $p_A$.
• −1 appears only once as a root. the algebraic multiplicity of -1 is 1.
• In general, the algebraic multiplicity and geometric multiplicity of an eigenvalue can differ. However, the geometric multiplicity can never exceed the algebraic multiplicity.
• If for every eigenvalue of A, the geometric multiplicity equals the algebraic multiplicity, then A is said to be diagonalizable.

### Singular Matrix

• A matrix is singular if and only if 0 is one of its eigenvalues. A singular matrix can be either diagonalizable or not diagonalizable. For example:
• $\left(\begin{array}{c c} 1 & 0 \\ 0 & 0\end{array}\right)$ is diagonalizable
• $\left(\begin{array}{c c} 0 & 1 \\ 0 & 0\end{array}\right)$ is not diagonalizable.

### Polynomial Roots

• A root of a polynomial $P(z)$ is a number $z_i$ such that $P(z_i)=0$. The fundamental theorem of algebra states that a polynomial $P(z)$ of degree n has n roots, some of which may be degenerate.
• For example, the roots of the polynomial $x^3-2x^2-x+2=(x-2)(x-1)(x+1)$ are -1, 1, and 2.

## Words

• eigenvalue ['aiɡən,vælju:] n. [数] 特征值
• eigenvector ['aiɡən,vektə] n. [数] 特征向量；本征矢量
• diagonalization [dai,æɡənəlai’zeiʃən, -li’z-] n. [数] 对角化；对角线化
• multiplicity [,mʌlti’plisəti] n. 多样性；[物] 多重性
• algebraic and geometric multiplicity 代数重数与几何重数
• companion matrix 友（矩）[数] 阵
• spectrum ['spektrəm] n. 光谱；频谱；范围；余象