Study Guides / Linear Algebra / Exercise session 13
EXERCISE SESSION 13 · ETH ZURICH · HS19 · linalg

Eigenvalues, Diagonalisability and Singular Value Decomposition

Eigenvalue & eigenvector, characteristic polynomial, trace, singular value decomposition (SVD)

SB
Steven Battilana Quant · ex-ETH

Eigenvalues and Eigenvectors

In this section let VV be a vector space over E\mathbb{E}, dim(V)=n<∞\text{dim}(V)=n<\infty, A∈En×nA \in \mathbb{E}^{n \times n}.

Definition
  • λ∈E\lambda \in \mathbb{E} is called an eigenvalue of A⇔∃v∈V∖{0}:Av=λvA \quad \Leftrightarrow \quad \exists v \in V \setminus \{0\}: \quad Av=\lambda v.
  • v∈V∖{0}v \in V \setminus \{0\} is then called an eigenvector of AA for the eigenvalue λ\lambda.
  • Eλ(A)={v∈V∣Av=λv}E_\lambda(A) = \{v \in V | Av=\lambda v\} is called the eigenspace of AA for the eigenvalue λ\lambda.
  • σ(A):={λ  ∣  λ eigenvalues of A}\sigma(A) := \{\lambda\; |\; \lambda \text{ eigenvalues of } A \} is called the spectrum of AA.
Remark

Eλ(A)=ker(A−λ𝟙)E_\lambda(A)=\text{ker}(A-\lambda \text{𝟙}) is a non-trivial subspace of VV, i.e.:

{0}⊊Eλ(A)(strictly larger than just the zero space)\{0\} \subsetneq E_\lambda(A) \quad \text{(strictly larger than just the zero space)}
Remark

This definition carries over analogously to a linear map F:V→VF: V \to V. We have:

λ is an eigenvalue of F,  v is an eigenvector of F⇔λ is an eigenvalue of A,  v is an eigenvector of A,where A denotes the matrix of F.\begin{aligned} &\lambda \text{ is an eigenvalue of } F, \; v \text{ is an eigenvector of } F\\ \Leftrightarrow \quad &\lambda \text{ is an eigenvalue of } A, \; v \text{ is an eigenvector of } A,\\ &\text{where } A \text{ denotes the matrix of } F. \end{aligned}
Remark Derivation of the characteristic polynomial χ_A

Consider

Av=λv⇔Av−λv=0⇔(A−λ𝟙)v=0(1)\begin{aligned} Av=\lambda v \quad &\Leftrightarrow \quad Av - \lambda v = 0\\ & \Leftrightarrow \quad (A- \lambda \text{𝟙})v = 0 \qquad\qquad\qquad\qquad (1) \end{aligned}

v=0v=0 solves (1)(1), but v=0v=0 is not allowed as an eigenvector. We require more solutions, i.e. ∞\infty many solutions (since a linear system always has 0,10,1 or ∞\infty many solutions). By the theorem from the review, we can achieve this by setting det(A−λ𝟙)=!0\text{det}(A-\lambda \text{𝟙}) \overset{!}{=}0, because

det(A−λ𝟙)=0⇔SatzA−λ𝟙 singular⇒(A−λ𝟙)v=0 has ∞ many solutions, since v=0 is not allowed.\begin{aligned} \text{det}(A-\lambda \text{𝟙})=0 \quad &\overset{\text{Satz}}{\Leftrightarrow} \quad A-\lambda \text{𝟙} \text{ singular}\\ &\Rightarrow \quad (A- \lambda \text{𝟙})v = 0 \text{ has } \infty \text{ many solutions, since } v=0 \text{ is not allowed.} \end{aligned}
Definition

χA(λ)=det(A−λ𝟙)\chi_A(\lambda) = \text{det}(A-\lambda \text{𝟙}) is called the characteristic polynomial.

Remark
  • χA(λ)\chi_A(\lambda) has degree nn
  • λ\lambda is an eigenvalue of AA
    ⇔λ\Leftrightarrow \lambda is a root of the characteristic polynomial χA(λ)\chi_A(\lambda).
Remark

Quadratic formula (learn by heart)

ax2+bx+c=0⇒x1,2=−b±b2−4ac2a\begin{aligned} ax^2 + bx + c &= 0\\ \Rightarrow \quad x_{1,2} &= \frac{-b \pm \sqrt{b^2 -4ac}}{2a} \end{aligned}
Algorithm Computing eigenvalues and eigenvectors

Given: A∈En×nA \in \mathbb{E}^{n \times n}
(if a linear map F:V→VF: V \to V is given, first find its matrix AA)
Find: σ(A)\sigma(A) (i.e. ∀\forall eigenvalues of AA), Eλ(A)E_\lambda(A) with ∀λ∈σ(A)\forall \lambda \in \sigma(A)

  1. Compute χA(λ)=det(A−λ𝟙)\chi_A(\lambda) = \text{det}(A-\lambda \text{𝟙})

  2. Set χA(λ)=!0\chi_A(\lambda) \overset{!}{=} 0:

    ⇒n roots λ1,...,λn⇒σ(A)={λ1,...,λn}\begin{aligned} &\Rightarrow n \text{ roots } \lambda_1, ..., \lambda_n\\ &\Rightarrow \sigma(A) = \{\lambda_1, ..., \lambda_n \} \end{aligned}

    Remark. λ1,...,λn\lambda_1, ..., \lambda_n are not necessarily distinct; they are counted with multiplicity.

  3. For each distinct eigenvalue λk\lambda_k, determine the basis of Eλk(A)=ker(A−λk𝟙)E_{\lambda_k}(A) = \text{ker}(A-\lambda_k \text{𝟙}) using Gaussian elimination.

  4. The set of eigenvectors is

    ⋃k(Eλk(A)∖{0})\bigcup_k \left( E_{\lambda_k}(A) \setminus \{0\} \right)

    (We take the union of all eigenspaces minus the zero vector)

Example 1

Given:

A=(123432005)A= \begin{pmatrix} 1 & 2 & 3\\ 4 & 3 & 2\\ 0 & 0 & 5 \end{pmatrix}

Find: eigenvalues, eigenvectors of AA

Show solutionHide solution
  1. χA(λ)=det(A−λ𝟙)=det((1−λ)234(3−λ)200(5−λ))=(1−λ)(3−λ)(5−λ)−(5−λ)⋅4⋅2=(5−λ)[(1−λ)(3−λ)−4⋅2]=(5−λ)[3−3λ−λ+λ2−8]=(5−λ)[λ2−4λ−5]=(5−λ)(λ−5)(λ+1)(if needed, using the quadratic formula)=−(λ−5)(λ−5)(λ+1)=−(λ−5)2(λ+1)\begin{aligned} \chi_A(\lambda) &= \text{det}(A-\lambda \text{𝟙})\\ &= \text{det} \begin{pmatrix} (1-\lambda) & 2 & 3\\ 4 & (3-\lambda) & 2\\ 0 & 0 & (5-\lambda) \end{pmatrix}\\ &= (1-\lambda)(3-\lambda)(5-\lambda) - (5-\lambda)\cdot 4 \cdot 2\\ &= (5-\lambda)[(1-\lambda)(3-\lambda) - 4 \cdot 2]\\ &= (5-\lambda)[3-3\lambda-\lambda+\lambda^2 - 8]\\ &= (5-\lambda)[\lambda^2-4\lambda-5]\\ &= (5-\lambda)(\lambda-5)(\lambda+1) \quad \text{(if needed, using the quadratic formula)}\\ &= -(\lambda-5)(\lambda-5)(\lambda+1)\\ &= -(\lambda-5)^2(\lambda+1) \end{aligned}
  2. χA(λ)=!0⇔−(λ−5)2(λ+1)=0⇒λ1=λ2=5(later: the algebraic multiplicity of 5 is 2)λ3=−1⇒σ(A)={5,−1}\begin{aligned} \chi_A(\lambda) &\overset{!}{=} 0\\ \Leftrightarrow \quad -(\lambda-5)^2(\lambda+1) &= 0\\ \Rightarrow \qquad \lambda_1 &= \lambda_2 = 5 \qquad \text{(later: the algebraic multiplicity of 5 is 2)}\\ \lambda_3 &= -1\\ \Rightarrow \qquad \sigma(A) &= \{5,-1\} \end{aligned}
    • λ1=λ2=5\lambda_1 = \lambda_2 = 5:

      E5(A)=ker(A−5⋅𝟙)=ker(−4234−22000)E_5(A) = \text{ker}(A - 5 \cdot \text{𝟙}) = \text{ker} \begin{pmatrix} -4 & 2 & 3\\ 4 & -2 & 2\\ 0 & 0 & 0 \end{pmatrix} ⇝Gaussker(2−10001000)=span{(120)}\overset{\text{Gauss}}{\leadsto} \text{ker} \begin{pmatrix} 2 & -1 & 0\\ 0 & 0 & 1\\ 0 & 0 & 0 \end{pmatrix} = \text{span} \left\{ \begin{pmatrix} 1\\ 2\\ 0 \end{pmatrix} \right\}
    • λ3=−1\lambda_3 = -1:

      E−1(A)=ker(A−(−1)⋅𝟙)=ker(223442006)E_{-1}(A) = \text{ker}(A - (-1) \cdot \text{𝟙}) = \text{ker} \begin{pmatrix} 2 & 2 & 3\\ 4 & 4 & 2\\ 0 & 0 & 6 \end{pmatrix} ⇝Gaussker(110001000)=span{(1−10)}\overset{\text{Gauss}}{\leadsto} \text{ker} \begin{pmatrix} 1 & 1 & 0\\ 0 & 0 & 1\\ 0 & 0 & 0 \end{pmatrix} = \text{span} \left\{ \begin{pmatrix} 1\\ -1\\ 0 \end{pmatrix} \right\}
  3. Set of eigenvectors:

    span{(120),(1−10)}∖{(000)}\text{span} \left\{ \begin{pmatrix} 1\\ 2\\ 0 \end{pmatrix}, \begin{pmatrix} 1\\ -1\\ 0 \end{pmatrix} \right\} \setminus \left\{ \begin{pmatrix} 0\\ 0\\ 0 \end{pmatrix} \right\}
Remark

It would be mathematically imprecise to say in example 1: "The eigenvectors are (1,2,0)T(1,2,0)^T and (1,−1,0)T(1,-1,0)^T". Because there are ∞\infty many eigenvectors.
For example, let vv be an eigenvector of AA for the eigenvalue λ\lambda, i.e. Av=λvAv = \lambda v
⇒c⋅v\Rightarrow c \cdot v is an eigenvector of AA for λ\lambda for all c∈E∖{0}c \in \mathbb{E} \setminus \{0\}, since A(cv)=λ(cv)A(cv) = \lambda (cv) also holds.
Usually it is still enough to take one basis vector v∈Eλ(A)∖{0}v \in E_\lambda(A) \setminus \{0\} as a "representative eigenvector".

Spectral Decomposition, Diagonalisability

Definition

Let λ\lambda be an eigenvalue of A∈En×nA \in \mathbb{E}^{n \times n}.

  • Algebraic multiplicity of λ\lambda:

    aλ:="multiplicity of λ as a root of χA(λ)"a_\lambda := \text{"multiplicity of } \lambda \text{ as a root of } \chi_A(\lambda) \text{"}
  • Geometric multiplicity:

    gλ:=dim(Eλ(A))=dim(ker(A−λ𝟙))=n−rank(A−λ𝟙)\begin{aligned} g_\lambda &:= \text{dim}(E_\lambda(A))\\ &= \text{dim}(\text{ker}(A-\lambda \text{𝟙}))\\ &= n - \text{rank}(A-\lambda \text{𝟙}) \end{aligned}
Definition

AA is called diagonalisable (a spectral decomposition exists)

⇔∃V∈En×n,  Λ∈En×n, with V regular, Λ diagonal, such that A=VΛV−1\begin{aligned} \Leftrightarrow \quad &\exists V \in \mathbb{E}^{n \times n}, \; \Lambda \in \mathbb{E}^{n \times n}, \text{ with } V \text{ regular, } \Lambda \text{ diagonal, such that }\\ &A = V \Lambda V^{-1} \end{aligned}

One also says: "AA is similar to a diagonal matrix".

Satz

AA is diagonalisable
⇔\Leftrightarrow The eigenvectors of AA form a basis of VV
⇔\Leftrightarrow For all eigenvalues λ\lambda of AA we have gλ=aλg_\lambda = a_\lambda.

Remark

A diagonalisation is a change of basis with transformation matrices VV and V−1V^{-1}.

Satz

A similarity transformation preserves:

  • eigenvalues and their algebraic and geometric multiplicity
  • rank
  • determinant
  • trace
  • characteristic polynomial χA(t)\chi_A(t)
  • not the eigenvectors!
Algorithm Computing the diagonal matrix

Given: A∈En×nA \in \mathbb{E}^{n \times n} diagonalisable
Find: V,Λ∈En×nV, \Lambda \in \mathbb{E}^{n \times n}

  1. Find the eigenvalues λ1,...,λn\lambda_1, ..., \lambda_n and the corresponding eigenvectors v1,...,vnv_1, ..., v_n of AA (where vi∈Eλi(A)v_i \in E_{\lambda_i}(A) and {vi}i=1n\{v_i\}_{i=1}^n linearly independent).

  2. Define the diagonal matrix as follows:

    Λ=(λ10⋯00⋱⋱⋮⋮⋱⋱00⋯0λn)with λ1≥...≥λn\Lambda = \begin{pmatrix} \lambda_1 & 0 & \cdots & 0\\ 0 & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & 0\\ 0 & \cdots & 0 & \lambda_n \end{pmatrix} \quad\quad \text{with } \lambda_1 \geq ... \geq \lambda_n
  3. Write the eigenvectors vi∈Eλi(A)v_i \in E_{\lambda_i}(A) into a matrix:

    V=(v1|⋯|vn)V = \left( v_1 \middle| \cdots \middle| v_n \right)
  4. Check: A=?VΛV−1A \overset{?}{=} V \Lambda V^{-1}

Example 1 continued …

Let

A=(123432005) as in example 3 with χA(λ)=−(λ−5)2(λ+1)A= \begin{pmatrix} 1 & 2 & 3\\ 4 & 3 & 2\\ 0 & 0 & 5 \end{pmatrix} \qquad \text{ as in example 3 with } \chi_A(\lambda) = -(\lambda-5)^2(\lambda+1)

Find: algebraic and geometric multiplicity

Show solutionHide solution
  • Algebraic multiplicity:

    λ1=5 with a5=2andλ2=−1 with a−1=1\lambda_1 = 5 \text{ with } a_5 = 2 \quad \text{and} \quad \lambda_2 = -1 \text{ with } a_{-1} = 1
  • Geometric multiplicity:

    g5= dim(E5(A))=1≠a5=2g−1= dim(E−1(A))=1=a−1=1\begin{aligned} g_5 &= \text{ dim}(E_5(A)) = 1 \quad \neq a_5 = 2\\ g_{-1} &= \text{ dim}(E_{-1}(A)) = 1 \quad = a_{-1} = 1 \end{aligned}

Since g5≠a5⇒Ag_5 \neq a_5 \Rightarrow A is not diagonalisable.

Example 2

Given:

A=(0−11−3−23−2−23)A= \begin{pmatrix} 0 & -1 & 1\\ -3 & -2 & 3\\ -2 & -2 & 3 \end{pmatrix}

Find: the spectral decomposition.

Show solutionHide solution
    1. χA(λ)=det(A−λ𝟙)=∣−λ−11−3−2−λ3−2−23−λ∣=−λ(−2−λ)(3−λ)+(−1)⋅3⋅(−2)+1⋅(−3)⋅(−2)        −(−2)⋅(−2−λ)⋅1−(−2)⋅3⋅(−λ)−(3−λ)⋅(−3)⋅(−1)=6λ+3λ2−2λ2−λ3+6+6−4−2λ−6λ−9+3λ=−λ3+λ2+λ−1\begin{aligned} \chi_A(\lambda) &= \text{det}(A-\lambda \text{𝟙})\\ &= \begin{vmatrix} -\lambda & -1 & 1\\ -3 & -2-\lambda & 3\\ -2 & -2 & 3-\lambda \end{vmatrix}\\ &= -\lambda(-2-\lambda)(3-\lambda) + (-1) \cdot 3 \cdot (-2) + 1 \cdot (-3) \cdot (-2)\\ &\;\;\;\;- (-2) \cdot (-2-\lambda) \cdot 1 - (-2) \cdot 3 \cdot (-\lambda) - (3-\lambda) \cdot (-3) \cdot (-1)\\ &= 6\lambda + 3\lambda^2 -2\lambda^2 -\lambda^3 + 6 + 6 - 4 -2\lambda -6\lambda -9 +3\lambda\\ &= -\lambda^3 +\lambda^2 +\lambda-1 \end{aligned}

      Remark. Here you need a trick: guess a root (try 1,−1,2,−21,-1,2,-2, etc.) and then perform polynomial long division.

      λ1=1\lambda_1 = 1 is a root:

      (−t3+t2+t−1):(t−1)=−t2+1(-t^3+t^2+t-1) : (t-1) = -t^2+1−t3+t2+t−1−(−t3+t2)0+t−1−(t−1)0\begin{array}{rrrr} -t^3 & +t^2 & +t & -1 \\ -(-t^3 & +t^2) & & \\ \hline & 0 & +t & -1 \\ & & -(t & -1) \\ \hline & & & 0 \end{array}⇒χA(λ)=(λ−1)(1−λ2)=(λ−1)(1−λ)(1+λ)=−(λ−1)(λ−1)(λ+1)=−(λ−1)2(λ+1)\begin{aligned} \Rightarrow \quad \chi_A(\lambda) &= (\lambda-1)(1-\lambda^2)\\ &= (\lambda-1)(1-\lambda)(1+\lambda)\\ &= -(\lambda-1)(\lambda-1)(\lambda+1)\\ &= -(\lambda-1)^2(\lambda+1) \end{aligned}
    2. χA(λ)=!0⇔0=−(λ−1)2(λ+1)⇒λ1=λ2=1,    a1=2λ3=−1,    a−1=1⇒σ(A)={−1,1}\begin{aligned} \chi_A(\lambda) &\overset{!}{=} 0\\ \Leftrightarrow 0 &= -(\lambda-1)^2(\lambda+1)\\ \Rightarrow \quad \lambda_1 &= \lambda_2 = 1, \;\; a_1 = 2\\ \lambda_3 &= -1, \;\; a_{-1} = 1\\ \Rightarrow \quad \sigma(A) &= \{-1,1\} \end{aligned}
      • λ1=λ2=1\lambda_1=\lambda_2 = 1:

        E1(A)=ker(A−𝟙)=ker(−1−11−3−33−2−22)⇝Gaussker(−1−11000000)=span{(1−10),(101)}⇒g1=2\begin{aligned} E_1(A) &= \text{ker}(A-\text{𝟙})\\ &= \text{ker} \begin{pmatrix} -1 & -1 & 1\\ -3 & -3 & 3\\ -2 & -2 & 2 \end{pmatrix}\\ &\overset{\text{Gauss}}{\leadsto} \text{ker} \begin{pmatrix} -1 & -1 & 1\\ 0 & 0 & 0\\ 0 & 0 & 0 \end{pmatrix} = \text{span}\left\{ \begin{pmatrix} 1\\ -1\\ 0 \end{pmatrix}, \begin{pmatrix} 1\\ 0\\ 1 \end{pmatrix} \right\}\\ \Rightarrow \quad g_1 &= 2 \end{aligned}
      • λ3=−1\lambda_3 = -1:

        E−1(A)=ker(A+𝟙)=ker(1−11−3−13−2−24)⇝Gaussker(1−110−460−46)⇝Gaussker(1−1102−3000)=span{(132)}⇒g−1=1\begin{aligned} E_{-1}(A) &= \text{ker}(A+\text{𝟙})\\ &= \text{ker} \begin{pmatrix} 1 & -1 & 1\\ -3 & -1 & 3\\ -2 & -2 & 4 \end{pmatrix}\\ &\overset{\text{Gauss}}{\leadsto} \text{ker} \begin{pmatrix} 1 & -1 & 1\\ 0 & -4 & 6\\ 0 & -4 & 6 \end{pmatrix}\\ &\overset{\text{Gauss}}{\leadsto} \text{ker} \begin{pmatrix} 1 & -1 & 1\\ 0 & 2 & -3\\ 0 & 0 & 0 \end{pmatrix} = \text{span}\left\{ \begin{pmatrix} 1\\ 3\\ 2 \end{pmatrix} \right\}\\ \Rightarrow \quad g_{-1} &= 1 \end{aligned}

      ⟹a1=g1\Longrightarrow \quad \quad a_1=g_1 and a−1=g−1⇒Aa_{-1}=g_{-1} \Rightarrow A is diagonalisable.

    3. Set of eigenvectors:

      span{(1−10),(101),(132)}\text{span} \left\{ \begin{pmatrix} 1\\ -1\\ 0 \end{pmatrix}, \begin{pmatrix} 1\\ 0\\ 1 \end{pmatrix}, \begin{pmatrix} 1\\ 3\\ 2 \end{pmatrix} \right\}
  1. Λ=(10001000−1)\Lambda = \begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & -1 \end{pmatrix}
  2. V=(111−103012),V−1=(3212−32−1−121212−12),V = \begin{pmatrix} 1 & 1 & 1\\ -1 & 0 & 3\\ 0 & 1 & 2 \end{pmatrix}, \quad V^{-1} = \begin{pmatrix} \frac{3}{2} & \frac{1}{2} & -\frac{3}{2}\\ -1 & -1 & 2\\ \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} \end{pmatrix},

    where you compute the inverse V−1V^{-1} with the usual recipe.

  3. Check: A=VΛV−1✓\quad\quad A= V \Lambda V^{-1} \checkmark

Remark

Complex roots of the characteristic polynomial with real coefficients always occur in pairs: if λ∈C\lambda \in \mathbb{C} is a root, then so is λ‾\overline{\lambda}. Hence an orthogonal matrix of odd dimension must have at least one real eigenvalue ±1\pm1.

Definition

The sum of the diagonal elements of A∈En×nA \in \mathbb{E}^{n \times n} is called the trace of AA:

tr(A):=∑i=1naii=a11+...+ann.\text{tr}(A) := \sum_{i=1}^n a_{ii} = a_{11} + ... + a_{nn}.
Lemma 9.6

A (square) matrix AA is singular if and only if it has 00 as an eigenvalue:

A singular⇔0∈σ(A).A \text{ singular} \quad \Leftrightarrow \quad 0 \in \sigma(A).
Satz 9.11

Eigenvectors for distinct eigenvalues are linearly independent.

Corollary 9.12

If the n eigenvalues of F:V→VF : V \to V (with n=dim(V)n = \text{dim}(V)) are distinct, then there is a basis of eigenvectors and the corresponding matrix is diagonal.

Satz 9.15

If A∈Cn×nA \in \mathbb{C}^{n \times n} is Hermitian, then:

  1. All eigenvalues λ1,...,λn\lambda_1, ..., \lambda_n are real.
  2. The eigenvectors for distinct eigenvalues are pairwise orthogonal in Cn\mathbb{C}^n.
  3. There is an orthonormal basis of Cn\mathbb{C}^n consisting of eigenvectors u1,...,unu_1, ..., u_n of AA.
  4. For the unitary matrix U:=(u1,...,un)U:=(u_1, ..., u_n) we have: UHAU=Λ=diag(λ1,...,λn).U^H A U = \Lambda = diag(\lambda_1, ..., \lambda_n).

Singular Value Decomposition

Satz

Let A∈En×nA \in \mathbb{E}^{n \times n} be symmetric (AT=A)(A^T=A) or Hermitian (AH=A‾T=AT‾=A)(A^H= \overline{A}^T = \overline{A^T}=A), then:

  1. AA has only real eigenvalues
  2. Eigenvectors for distinct eigenvalues are pairwise orthogonal
Remark 1

To obtain an orthonormal basis of eigenvectors of a symmetric/Hermitian matrix, you only need to normalise the eigenvectors and, if necessary, orthogonalise them with Gram-Schmidt (you do this if there is an eigenvalue with geometric multiplicity >1> 1).

Satz Singular value decomposition

Let A∈Em×nA \in \mathbb{E}^{m \times n}, rank(A)=:r≤min{m,n}\text{rank}(A)=: r \leq \text{min}\{m,n\}. Then there exist U∈Em×mU \in \mathbb{E}^{m \times m} orthogonal/unitary, V∈En×nV \in \mathbb{E}^{n \times n} orthogonal/unitary, Σ∈Rm×n\Sigma \in \mathbb{R}^{m \times n}, where

Σ=(Σr00⏟r0⏟n−r)[0]}r[00]}m−r,with Σr=(σ10⋯00⋱⋱⋮⋮⋱⋱00⋯0σr),σ1≥...≥σr>0\Sigma = \begin{pmatrix} \Sigma_r & \boldsymbol{0}\\ \underbrace{\boldsymbol{0}}_r & \underbrace{\boldsymbol{0}}_{n-r} \end{pmatrix} \begin{matrix} \left.\vphantom{\begin{bmatrix} 0 \end{bmatrix}}\right\} r \\ \left.\vphantom{\begin{bmatrix} 0\\ 0 \end{bmatrix}}\right\} m-r \end{matrix}, \qquad \text{with } \Sigma_r = \begin{pmatrix} \sigma_1 & 0 & \cdots & 0\\ 0 & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & 0\\ 0 & \cdots & 0 & \sigma_r \end{pmatrix}, \quad \sigma_1 \geq ... \geq \sigma_r > 0

is a generalised diagonal matrix with singular values σ1,...,σr\sigma_1, ..., \sigma_r, such that A=UΣVHA=U \Sigma V^H, i.e. AA has a singular value decomposition.

Satz

Let A∈Em×nA \in \mathbb{E}^{m \times n}.

AHA=(UΣVH)HUΣVH=VΣH⏟=ΣTUHU⏟=𝟙m since U unitaryΣVH=VΣTΣVH\begin{aligned} A^HA &= (U \Sigma V^H)^H U \Sigma V^H\\ &= V \underbrace{\Sigma^H}_{= \Sigma^T} \quad \underbrace{U^HU}_{=\text{𝟙}_m \text{ since } U \text{ unitary}} \Sigma V^H\\ &= V \Sigma^T \Sigma V^H \end{aligned}

⇒AHA\Rightarrow A^HA is similar (in the sense of a unitary spectral decomposition) to

ΣTΣ=(σ120⋯00⋯00⋱⋱⋮⋮⋮⋮⋱⋱0⋮⋮0⋯0σr20⋯00⋯⋯00⋯0⋮⋮⋮⋮0⋯⋯00⋯0)∈Rn×n\Sigma^T \Sigma = \begin{pmatrix} \sigma_1^2 & 0 & \cdots & 0 & 0 & \cdots & 0\\ 0 & \ddots & \ddots & \vdots & \vdots & & \vdots\\ \vdots & \ddots & \ddots & 0 & \vdots & & \vdots\\ 0 & \cdots & 0 & \sigma_r^2 & 0 & \cdots & 0\\ 0 & \cdots & \cdots & 0 & 0 & \cdots & 0\\ \vdots & & & \vdots & \vdots & & \vdots\\ 0 & \cdots & \cdots & 0 & 0 & \cdots & 0 \end{pmatrix} \in \mathbb{R}^{n \times n}

⇒σi=λi\Rightarrow \sigma_i = \sqrt{\lambda_i}, where λi\lambda_i are the positive real eigenvalues of AHAA^HA.

Remark Applications
  1. The singular value decomposition is, in a sense, a generalisation of the spectral decomposition to rectangular matrices.
  2. Solving singular linear systems and least-squares problems.
  3. Image compression. An image is viewed as a matrix of colour values, whose singular value decomposition is computed. When transforming back from UΣVHU \Sigma V^H to AA, however, only the singular values that "deviate strongly from 00" are kept; singular values that are small in absolute value are discarded.
Algorithm Singular value decomposition

Given: A∈Em×n,    m≥nA \in \mathbb{E}^{m \times n}, \;\; m \geq n (otherwise consider AHA^H)
Find: U∈Em×m,Σ∈Rm×n,V∈En×nU \in \mathbb{E}^{m \times m}, \Sigma \in \mathbb{R}^{m \times n}, V \in \mathbb{E}^{n \times n}

  1. Compute B=AHA∈En×nB = A^HA \in \mathbb{E}^{n \times n}

  2. Compute the eigenvalues of BB and "number" them by size:

    λ1≥...≥λr>λr+1=...=λn=0,\lambda_1 \geq ... \geq \lambda_r > \lambda_{r+1} = ... = \lambda_n = 0,

    where r=rank(B)=rank(AHA)r = \text{rank}(B) = \text{rank}(A^HA)

  3. Σij={σi=λi,i=j0,    otherwise\Sigma_{ij} = \begin{cases} \sigma_i = \sqrt{\lambda_i}, \quad i=j\\ 0, \qquad\qquad\;\; \text{otherwise} \end{cases}
  4. Build the orthonormal basis {w1,...,wn}\{ w_1, ..., w_n \} with Gram-Schmidt from the eigenvectors {v1,...,vn}\{v_1, ..., v_n\} of BB. (Note that B=AHAB=A^HA is Hermitian, i.e. use remark 1)

    ⇒V=(w1∣⋯∣wn)\Rightarrow \quad V = ( w_1 | \cdots | w_n)
  5. ∀i∈{1,...,r}    define     ui:=1σiAwi⇒ui are orthonormal/unitary\forall i \in \{1, ..., r \} \;\; \text{define } \;\; u_i := \frac{1}{\sigma_i} A w_i \quad \Rightarrow \quad u_i \text{ are orthonormal/unitary}

    Extend {u1,...,ur}\{u_1, ..., u_r \} to an orthonormal basis of Em\mathbb{E}^{m} with Gram-Schmidt

    ⇒U=(u1∣...∣um)\Rightarrow \quad U=(u_1 | ... | u_m)
  6. Check: A=?UΣVH✓\quad A \overset{?}{=} U \Sigma V^H \quad \checkmark

Example 3

Given:

A=(102101)A = \begin{pmatrix} 1 & 0\\ 2 & 1\\ 0 & 1 \end{pmatrix}

Find: U,Σ,VU, \Sigma, V such that A=UΣVHA=U \Sigma V^H; additional question: describe the four fundamental subspaces according to Satz 11.1 (see lecture notes).

Show solutionHide solution
  1. B=AHA=ATA=(5222)B = A^HA = A^TA = \begin{pmatrix} 5 & 2\\ 2 & 2 \end{pmatrix}
  2. Compute the eigenvalues of BB:

    χB(λ)=∣5−λ222−λ∣=(5−λ)(2−λ)−4=10−2λ−5λ+λ2−4=λ2−7λ+6=(λ−1)(λ−6)=!0⇒λ1=6>λ2=1\begin{aligned} \chi_B(\lambda) &= \begin{vmatrix} 5-\lambda & 2\\ 2 & 2 -\lambda \end{vmatrix}\\ &= (5-\lambda)(2-\lambda) -4\\ &= 10 - 2\lambda - 5\lambda + \lambda^2 -4\\ &= \lambda^2 - 7\lambda + 6\\ &= (\lambda -1)(\lambda -6) \overset{!}{=} 0\\ \Rightarrow \quad \lambda_1 &= 6 > \lambda_2 = 1 \end{aligned}
  3. σ1=6,    σ2=1=1⇒Σ=(600100)\sigma_1 = \sqrt{6}, \;\; \sigma_2 = \sqrt{1} = 1 \quad \Rightarrow \quad \Sigma = \begin{pmatrix} \sqrt{6} & 0\\ 0 & 1\\ 0 & 0 \end{pmatrix}
  4. E6=ker(B−6𝟙)=span{(21)}⇒v1=(21)⇝normalisew1=15(21)E_6 = \text{ker}(B-6\text{𝟙}) = \text{span} \left\{ \begin{pmatrix} 2\\ 1 \end{pmatrix} \right\} \Rightarrow v_1 = \begin{pmatrix} 2\\ 1 \end{pmatrix} \overset{\text{normalise}}{\leadsto} w_1 = \frac{1}{\sqrt{5}} \begin{pmatrix} 2\\ 1 \end{pmatrix} E1=ker(B−𝟙)=span{(1−2)}⇒v2=(1−2)⇝normalisew2=15(1−2)E_1 = \text{ker}(B-\text{𝟙}) = \text{span} \left\{ \begin{pmatrix} 1\\ -2 \end{pmatrix} \right\} \Rightarrow v_2 = \begin{pmatrix} 1\\ -2 \end{pmatrix} \overset{\text{normalise}}{\leadsto} w_2 = \frac{1}{\sqrt{5}} \begin{pmatrix} 1\\ -2 \end{pmatrix} ⇒V=15(211−2)\Rightarrow \quad V = \frac{1}{\sqrt{5}} \begin{pmatrix} 2 & 1\\ 1 & -2 \end{pmatrix}
  5. u1=1615(102101)(21)=130(251)u_1 = \frac{1}{\sqrt{6}} \frac{1}{\sqrt{5}} \begin{pmatrix} 1 & 0\\ 2 & 1\\ 0 & 1 \end{pmatrix} \begin{pmatrix} 2\\ 1 \end{pmatrix} = \frac{1}{\sqrt{30}} \begin{pmatrix} 2\\ 5\\ 1 \end{pmatrix} u2=1115(102101)(1−2)=15(10−2)u_2 = \frac{1}{\sqrt{1}} \frac{1}{\sqrt{5}} \begin{pmatrix} 1 & 0\\ 2 & 1\\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1\\ -2 \end{pmatrix} = \frac{1}{\sqrt{5}} \begin{pmatrix} 1\\ 0\\ -2 \end{pmatrix} u3~=e2−⟨e2,u1⟩u1−⟨e2,u2⟩u2=(010)−130130⟨(010),(251)⟩(251)−1515⟨(010),(10−2)⟩(10−2)=(010)−530(251)−0⋅(10−2)=(010)−16(251)=16(−21−1)\begin{aligned} \widetilde{u_3} &= e_2 - \langle e_2,u_1 \rangle u_1 - \langle e_2,u_2 \rangle u_2\\ &= \begin{pmatrix} 0\\ 1\\ 0 \end{pmatrix} - \frac{1}{\sqrt{30}} \frac{1}{\sqrt{30}} \langle \begin{pmatrix} 0\\ 1\\ 0 \end{pmatrix}, \begin{pmatrix} 2\\ 5\\ 1 \end{pmatrix} \rangle \begin{pmatrix} 2\\ 5\\ 1 \end{pmatrix} - \frac{1}{\sqrt{5}} \frac{1}{\sqrt{5}} \langle \begin{pmatrix} 0\\ 1\\ 0 \end{pmatrix}, \begin{pmatrix} 1\\ 0\\ -2 \end{pmatrix} \rangle \begin{pmatrix} 1\\ 0\\ -2 \end{pmatrix}\\ &= \begin{pmatrix} 0\\ 1\\ 0 \end{pmatrix} - \frac{5}{30} \begin{pmatrix} 2\\ 5\\ 1 \end{pmatrix} - 0 \cdot \begin{pmatrix} 1\\ 0\\ -2 \end{pmatrix}\\ &= \begin{pmatrix} 0\\ 1\\ 0 \end{pmatrix} - \frac{1}{6} \begin{pmatrix} 2\\ 5\\ 1 \end{pmatrix}\\ &= \frac{1}{6} \begin{pmatrix} -2\\ 1\\ -1 \end{pmatrix} \end{aligned} u3=u3~∥u3~∥=16(−21−1)u_3 = \frac{\widetilde{u_3}}{\left\lVert \widetilde{u_3} \right\rVert} = \frac{1}{\sqrt{6}} \begin{pmatrix} -2\\ 1\\ -1 \end{pmatrix} ⇒U=(23015−26530016130−25−16)\Rightarrow U = \begin{pmatrix} \frac{2}{\sqrt{30}} & \frac{1}{\sqrt{5}} & -\frac{2}{\sqrt{6}}\\ \frac{5}{\sqrt{30}} & 0 & \frac{1}{\sqrt{6}}\\ \frac{1}{\sqrt{30}} & -\frac{2}{\sqrt{5}} & -\frac{1}{\sqrt{6}} \end{pmatrix}
  6. Check: A=UΣVH✓A = U \Sigma V^H \quad \checkmark

  7. The four fundamental subspaces:

    im(A)={u1,u2}im(AH)={w1,w2}ker(AH)={u3}ker(A)={}\begin{aligned} \text{im}(A) &= \{u_1, u_2\}\\ \text{im}(A^H) &= \{w_1, w_2\}\\ \text{ker}(A^H) &= \{u_3\}\\ \text{ker}(A) &= \{\} \end{aligned}
Example 4

Given:

A=(1011−11)A = \begin{pmatrix} 1 & 0\\ 1 & 1\\ -1 & 1 \end{pmatrix}

Find: U,Σ,VU, \Sigma, V such that A=UΣVHA=U \Sigma V^H

Show solutionHide solution Σ=(300200),V=(1001)=𝟙2,U=(130261312−16−131216)\Sigma = \begin{pmatrix} \sqrt{3} & 0\\ 0 & \sqrt{2}\\ 0 & 0 \end{pmatrix}, \quad V = \begin{pmatrix} 1 & 0\\ 0 & 1 \end{pmatrix} = \text{𝟙}_2, \quad U = \begin{pmatrix} \frac{1}{\sqrt{3}} & 0 & \frac{2}{\sqrt{6}}\\ \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{6}}\\ -\frac{1}{\sqrt{3}} & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} \end{pmatrix}