25 Eigenvalues, Eigenvectors, Complete Set of Eigenvectors, Diagonalization, Eigendecomposition

Lecture from 11.12.2024 | Video: Videos ETHZ

Eigenvalues and Eigenvectors: A Summary

Let’s recap some key properties of eigenvalues and eigenvectors for a matrix $A\in {\mathbb{R}}^{n\times n}$:

• Complex Conjugate Eigenvalue: If $(\lambda ,\mathbf{v})$ is an eigenvalue-eigenvector pair of $A$, then $(\bar{\lambda },\bar{\mathbf{v}})$ is also an eigenvalue-eigenvector pair, where $\bar{\lambda }$ and $\bar{\mathbf{v}}$ denote the complex conjugates.
• Eigenvalues of $A$ and $A^T$: $A$ and $A^T$ share the same eigenvalues, but their eigenvectors are generally different.
• Eigenvalues of $A^{-1}$: If $A$ is invertible and $(\lambda ,\mathbf{v})$ is an eigenvalue-eigenvector pair, then $(1/\lambda ,\mathbf{v})$ is an eigenvalue-eigenvector pair for $A^{-1}$. Note that $\lambda \ne 0$ since $A$ is invertible.
• Linearity of Eigenvalues: Eigenvalues do not behave linearly under matrix addition or multiplication. In general, the eigenvalues of $A+B$ are not the sum of the eigenvalues of $A$ and $B$, and the eigenvalues of $AB$ are not the product of the eigenvalues of $A$ and $B$.
• Gaussian Elimination and Eigenvalues: Gaussian elimination does not preserve eigenvalues.
• Eigenvalues of Orthogonal Matrices: If $Q$ is an orthogonal matrix ($Q^{T}Q=I$) and $\lambda$ is an eigenvalue of $Q$, then $|\lambda |=1$.

Theorem: Basis of Eigenvectors for Distinct Eigenvalues

If $A\in {\mathbb{R}}^{n\times n}$ has $n$ distinct real eigenvalues, then there exists a basis for ${\mathbb{R}}^n$ consisting of the eigenvectors of $A$. This basis enables diagonalization, simplifying various computations involving $A$. However, what happens when eigenvalues are repeated?

Repeated Eigenvalues: Challenges in Building a Basis

When eigenvalues are repeated, constructing a basis of eigenvectors becomes more challenging.

Definition: The algebraic multiplicity of an eigenvalue is the number of times it appears as a root of the characteristic polynomial.

Example

1. $A=\left[\begin{array}{cc}0& 1\\ 0& 0\end{array}\right]$ The characteristic polynomial is $\det (A-\lambda I)={\lambda }^2$. The eigenvalue 0 has algebraic multiplicity 2. The eigenspace corresponding to $\lambda =0$ is $N(A)$, which is spanned by the vector $\left[\begin{array}{c}1\\ 0\end{array}\right]$. Its dimension is 1. Thus, there is only one linearly independent eigenvector.

2. $A=\left[\begin{array}{cc}0& 0\\ 0& 0\end{array}\right]$ The characteristic polynomial is ${\lambda }^2$. $\lambda =0$ is the only eigenvalue, again with algebraic multiplicity 2. However, the eigenspace is all of ${\mathbb{R}}^2$ (any vector is an eigenvector), which has dimension 2. We have two linearly independent eigenvectors $\left[\begin{array}{c}1\\ 0\end{array}\right]$ and $\left[\begin{array}{c}0\\ 1\end{array}\right]$.

These examples illustrate that a repeated eigenvalue might not yield enough linearly independent eigenvectors to form a basis. This leads to the following definition:

Complete Set of Real Eigenvectors

Definition: A matrix $A\in {\mathbb{R}}^{n\times n}$ has a complete set of real eigenvectors if there exists a basis for ${\mathbb{R}}^n$ consisting of eigenvectors of $A$. So in our example the first matrix doesn’t have such a complete set of eigenvectors, the second matrix however does have such a set.

When Do We Have a Complete Set of Real Eigenvectors?

A crucial question in linear algebra is whether a given matrix possesses a complete set of eigenvectors that form a basis for the vector space. This property, known as diagonalizability, significantly simplifies matrix computations and analysis.

Definition: Complete Set of Eigenvectors: A matrix $A\in {\mathbb{R}}^{n\times n}$ has a complete set of real eigenvectors if there exists a basis for ${\mathbb{R}}^n$ consisting entirely of eigenvectors of $A$.

Let’s examine specific cases:

1. Distinct Eigenvalues

Proposition: If a matrix $A\in {\mathbb{R}}^{n\times n}$ has $n$ distinct real eigenvalues, then it has a complete set of linearly independent eigenvectors, hence forming a basis for ${\mathbb{R}}^n$.

Proof: We have already proved (in the last lecture note [[24 Explicit Fibonacci Formula, Eigenvalue and Eigenvector properties, Trace#Key Properties and Results#Linear Independence of Eigenvectors]]) that eigenvectors corresponding to distinct eigenvalues are linearly independent. If a matrix has $n$ distinct eigenvalues, it consequently has $n$ linearly independent eigenvectors. Since these eigenvectors reside in ${\mathbb{R}}^n$, $n$ linearly independent vectors form a basis. Therefore, the matrix has a complete set of eigenvectors.

2. Diagonal Matrices

Proposition: A diagonal matrix $D\in {\mathbb{R}}^{n\times n}$ always has a complete set of linearly independent eigenvectors.

Proof: Let $D=\text{diag}(d_1,d_2,\dots ,d_n)$ be a diagonal matrix. The characteristic polynomial is given by:

$\det (D-\lambda I)=(d_1-\lambda )(d_2-\lambda )\dots (d_n-\lambda )$

Setting the characteristic polynomial to zero, we find that the eigenvalues are the diagonal entries: ${\lambda }_i=d_i$ for $i=1,\dots ,n.$ Now let’s consider the standard basis vectors ${\mathbf{e}}_i$ (a vector with 1 in the $i$-th position and 0 elsewhere). Observe:

$D{\mathbf{e}}_i=d_i{\mathbf{e}}_i={\lambda }_i{\mathbf{e}}_i$

Thus, each standard basis vector ${\mathbf{e}}_i$ is an eigenvector corresponding to the eigenvalue ${\lambda }_i=d_i$. Since the standard basis vectors are linearly independent and span ${\mathbb{R}}^n$, the diagonal matrix $D$ has a complete set of linearly independent eigenvectors. Note that if there are repeated entries on the diagonal, we still have a complete set of linearly independent eigenvectors; it’s just that multiple eigenvectors will correspond to the same eigenvalue.

3. Repeated Eigenvalues: Algebraic and Geometric Multiplicity

When an eigenvalue is repeated (i.e., its algebraic multiplicity is greater than 1), the situation is more nuanced.

Definition: Algebraic Multiplicity

The algebraic multiplicity of an eigenvalue $\lambda$ is the number of times it appears as a root of the characteristic polynomial.

Definition: Geometric Multiplicity

The geometric multiplicity of an eigenvalue $\lambda$ is the dimension of its eigenspace, $N(A-\lambda I)$ - the number of linearly independent eigenvectors associated with that eigenvalue.

Explanation:

• Algebraic multiplicity counts how many times an eigenvalue appears as a root of the characteristic polynomial. This tells us how many eigenvectors we expect for that eigenvalue.

• Geometric multiplicity counts the maximum number of linearly independent eigenvectors we can actually find for an eigenvalue. This is the dimension of the eigenspace.

To form a basis, we need $n$ linearly independent eigenvectors for an $n\times n$ matrix.

If the geometric multiplicity of an eigenvalue is less than its algebraic multiplicity, we have “missing” eigenvectors—we don’t have enough linearly independent vectors for that eigenvalue to contribute its “full share” to a basis.

Only when the geometric multiplicity equals the algebraic multiplicity for all eigenvalues do we have enough linearly independent eigenvectors to span the entire space and form a complete set, thus making the matrix diagonalizable.

Crucial Condition for a Complete Set

A matrix $A$ has a complete set of eigenvectors if and only if for every eigenvalue, its geometric multiplicity is equal to its algebraic multiplicity.

Example (Repeated Eigenvalue, Insufficient Eigenvectors)

$A=\left[\begin{array}{cc}2& 1\\ 0& 2\end{array}\right]$ The characteristic polynomial is $(2-\lambda {)}^2$, so $\lambda =2$ has algebraic multiplicity 2. However, the eigenspace $N(A-2I)$ has dimension 1 (spanned by $[10{]}^T$), so the geometric multiplicity is 1. Since the geometric multiplicity is less than the algebraic multiplicity, this matrix does not have a complete set of eigenvectors and is not diagonalizable.

Projection Matrices and Complete Sets of Eigenvectors

Projection matrices, representing projections onto subspaces, possess a special eigenstructure that always guarantees a complete set of eigenvectors.

Proposition: Let $P$ be the orthogonal projection matrix onto a subspace $S\subset {\mathbb{R}}^n$. Then $P$ has two eigenvalues: 0 and 1, and it always has a complete set of real eigenvectors that form a basis for ${\mathbb{R}}^n.$

Proof

Eigenvalues 0 and 1

Let $\mathbf{x}\in {\mathbb{R}}^n$. We can uniquely decompose $\mathbf{x}$ as $\mathbf{x}={\mathbf{x}}_S+{\mathbf{x}}_{S^{\perp }}$ where ${\mathbf{x}}_S\in S$ and ${\mathbf{x}}_{S^{\perp }}\in S^{\perp }$ (the orthogonal complement of $S$). By definition of orthogonal projection:

$P\mathbf{x}={\mathbf{x}}_S.$

• Eigenvalue 1: If $\mathbf{x}\in S$, then $P\mathbf{x}=\mathbf{x}=1\mathbf{x}$. Thus, any non-zero vector in $S$ is an eigenvector of $P$ with eigenvalue 1.
• Eigenvalue 0: If $\mathbf{x}\in S^{\perp }$, then $P\mathbf{x}=0=0\mathbf{x}$. Thus, any non-zero vector in $S^{\perp }$ is an eigenvector of $P$ with eigenvalue 0.

Complete Set of Eigenvectors

Let $m=\dim (S)$. Let $\{{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_m\}$ be an orthonormal basis for $S$, and let $\{{\mathbf{v}}_{m+1},{\mathbf{v}}_{m+2},\dots ,{\mathbf{v}}_n\}$ be an orthonormal basis for $S^{\perp }$.

• Eigenvectors for eigenvalue 1: The vectors $\{{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_m\}$ are eigenvectors of $P$ with eigenvalue 1 (as shown above).

• Eigenvectors for eigenvalue 0: The vectors $\{{\mathbf{v}}_{m+1},{\mathbf{v}}_{m+2},\dots ,{\mathbf{v}}_n\}$ are eigenvectors of $P$ with eigenvalue 0 (as shown above).

• Combined Set: The set $\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_m,{\mathbf{v}}_{m+1},\dots ,{\mathbf{v}}_n\}$ forms an orthonormal basis for ${\mathbb{R}}^n$ consisting entirely of eigenvectors of $P.$

  • Linear Independence: Since it is a basis for ${\mathbb{R}}^n$ the set of vectors are linearly independent.
  • Spanning Property: The set spans all of ${\mathbb{R}}^n$ as it is a basis.

Explicit Form of Eigenvectors: The eigenvectors of the projection matrix $P$ are any set of orthonormal vectors that form bases for the subspace $S$ and its orthogonal complement $S^{\perp }$.

Diagonalization: Leveraging a Complete Set of Eigenvectors

Theorem: Let $A\in {\mathbb{R}}^{n\times n}$ have a complete set of eigenvectors ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$ associated with eigenvalues ${\lambda }_1,\dots ,{\lambda }_n$, respectively. Let $V$ be the matrix whose columns are these eigenvectors. Then:

$A=V\Lambda V^{-1}$

where $\Lambda$ is a diagonal matrix with the eigenvalues ${\lambda }_1,\dots ,{\lambda }_n$ on the diagonal. This process is called diagonalization.

Diagonalization and Powers of A... (MIT)

Proof

1. Invertibility of $V$: Since $A$ has a complete set of eigenvectors, these eigenvectors form a basis for ${\mathbb{R}}^n,$ which mean they are linearly independent. Consequently, the matrix $V$, having these linearly independent vectors as its columns, is invertible.

2. Eigenvalue Equation in Matrix Form: The individual eigenvalue equations $A{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$ for $i=1,2,\dots ,n$, can be expressed concisely in matrix form:

   $AV=A[{\mathbf{v}}_1{\mathbf{v}}_2\dots {\mathbf{v}}_n]=[A{\mathbf{v}}_{1}A{\mathbf{v}}_2\dots A{\mathbf{v}}_n]=[{\lambda }_1{\mathbf{v}}_1{\lambda }_2{\mathbf{v}}_2\dots {\lambda }_n{\mathbf{v}}_n]$

3. Introducing $\Lambda$: Notice that the rightmost expression in the previous step can be written as the product of $V$ and the diagonal matrix $\Lambda$: Let’s see why:

   $[{\lambda }_1{\mathbf{v}}_1{\lambda }_2{\mathbf{v}}_2\dots {\lambda }_n{\mathbf{v}}_n]=[{\mathbf{v}}_1{\mathbf{v}}_2\dots {\mathbf{v}}_n]\left[\begin{array}{cccc}{\lambda }_1& 0& \dots & 0\\ 0& {\lambda }_2& \dots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \dots & {\lambda }_n\end{array}\right]=V\Lambda$

4. Diagonalization: Combining the steps, we have $AV=V\Lambda$. Since $V$ is invertible, we can multiply both sides on the left by $V^{-1}$: $V^{-1}AV=V^{-1}V\Lambda =I\Lambda =\Lambda$

   This equation demonstrates that $A$ is similar to the diagonal matrix $\Lambda .$

5. Rewriting the Equation: Finally, to obtain the diagonalization of $A$, we can multiply both sides of $V^{-1}AV=\Lambda$ on the left by $V$ and on the right by $V^{-1}$:

   $V(V^{-1}AV)V^{-1}=V\Lambda V^{-1}⟹(V{V}^{-1})A(V{V}^{-1})=V\Lambda V^{-1}⟹A=V\Lambda V^{-1}$

Similar Matrices

Definition: Two matrices $A$ and $B$ are similar if there exists an invertible matrix $S$ such that $B=S^{-1}AS.$

Proposition: Similar matrices have the same eigenvalues.

Proof

If $A\mathbf{v}=\lambda \mathbf{v}$, and $B=S^{-1}AS$, then:

$B(S^{-1}\mathbf{v})=S^{-1}AS(S^{-1}\mathbf{v})=S^{-1}A\mathbf{v}=S^{-1}(\lambda \mathbf{v})=\lambda (S^{-1}\mathbf{v})$

Thus, if $\lambda$ is an eigenvalue of $A$ with eigenvector $\mathbf{v}$, then $\lambda$ is an eigenvalue of $B$ with eigenvector $S^{-1}\mathbf{v}.$

Diagonalization, when possible, finds a similar matrix that is diagonal, greatly simplifying computations and revealing the core structure of the linear transformation.

Why Diagonalization Matters

Diagonalization simplifies many matrix computations. For instance, calculating powers of $A$ becomes much easier:

$A^k=(V\Lambda V^{-1}{)}^k=V{\Lambda }^k{V}^{-1}$ Since $\Lambda$ is diagonal, ${\Lambda }^k$ is simply computed by raising the diagonal entries (eigenvalues) to the power $k$. This simplification extends to other matrix functions, making diagonalization a powerful technique in various applications.

Change of Basis and Diagonalization

Diagonalization, when possible, provides a way to simplify the representation of a linear transformation by choosing a basis of eigenvectors. In this basis, the transformation acts as a simple scaling along each eigenvector direction. Let’s explore this concept in detail, starting with the general case of a linear transformation and then specializing to diagonalizable matrices.

General Case: Change of Basis

Consider a linear transformation $L:{\mathbb{R}}^n\to {\mathbb{R}}^m$ and two sets of bases:

• $\{{\mathbf{u}}_1,{\mathbf{u}}_2,\dots ,{\mathbf{u}}_n\}$ for ${\mathbb{R}}^n$ (the “old” basis).
• $\{{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_m\}$ for ${\mathbb{R}}^m$ (the “new” basis).

Let $U=[{\mathbf{u}}_1{\mathbf{u}}_2\dots {\mathbf{u}}_n]\in {\mathbb{R}}^{n\times n}$ and $V=[{\mathbf{v}}_1{\mathbf{v}}_2\dots {\mathbf{v}}_m]\in {\mathbb{R}}^{m\times m}$ be the matrices whose columns are the respective basis vectors. These matrices are invertible since their columns are linearly independent. Any vector $\mathbf{x}\in {\mathbb{R}}^n$ can be expressed in the old basis as $\mathbf{x}={\sum }_{j=1}^n{\alpha }_j{\mathbf{u}}_j$. Let $\mathbf{\alpha }=\left[\begin{array}{c}{\alpha }_1\\ ⋮\\ {\alpha }_n\end{array}\right]$. Then $\mathbf{x}=U\mathbf{\alpha }$.

The transformation $L(\mathbf{x})$ results in a vector in ${\mathbb{R}}^m$, which can be expressed in the new basis as $L(\mathbf{x})={\sum }_{i=1}^m{\beta }_i{\mathbf{v}}_i$. Similarly, let $\mathbf{\beta }=\left[\begin{array}{c}{\beta }_1\\ ⋮\\ {\beta }_m\end{array}\right].$ Then $L(\mathbf{x})=V\mathbf{\beta }.$

We want to find a matrix $B$ that represents the transformation $L$ with respect to these new bases, such that $\mathbf{\beta }=B\mathbf{\alpha }$. To do this, let $A$ be the matrix representing the linear transformation $L$ in the standard bases. Then $L(\mathbf{x})=A\mathbf{x}$.

Using the change of basis matrices: $L(\mathbf{x})=V\mathbf{\beta }=A\mathbf{x}=AU\mathbf{\alpha }$ To find $B$, we need to express $\mathbf{\beta }$ in terms of $\mathbf{\alpha }$: $\mathbf{\beta }=V^{-1}AU\mathbf{\alpha }$ Thus, the matrix representing the transformation $L$ in the new bases is: $B=V^{-1}AU$

Diagonalization: A Special Case of Change of Basis

When $A\in {\mathbb{R}}^{n\times n}$ is diagonalizable (i.e., it has a complete set of $n$ linearly independent eigenvectors), we can choose the eigenvectors as the new basis for both the domain and codomain (${\mathbb{R}}^n$).

Let $V$ be the matrix whose columns are the eigenvectors of $A$. Then, in this eigenvector basis, the transformation is represented by the diagonal matrix $\Lambda =V^{-1}AV,$ where $\Lambda$ has the eigenvalues of $A$ on its diagonal.

In this case, the change of basis simplifies the transformation to a scaling along each eigenvector direction, as the matrix representing the transformation becomes diagonal.

Continue here: 26 Symmetric Matrices, Spectral Theorem, Rayleigh Quotient