MATH347

MATH347 L21: Eigenvalue problems

Previous linear algebra problems

Coordinates in a new basis, solving a linear system $𝑨 𝒙 = 𝑰 𝒃$ , $𝑨 \in ℝ^{m \times n}$
1. Compute $𝑳 𝑼$ factorization, $𝑳 𝑼 = 𝑨$
2. Solve $𝑳 𝒚 = 𝒃$ by forward substitution
3. Solve $𝑼 𝒙 = 𝒚$ by backward substition
Approximate $𝒃 \in ℝ^{m}$ , $𝒃 ≅ 𝑨 𝒙$ , $𝑨 \in ℝ^{m \times n}$ , the least squares problem
- Find $𝑸 𝑹$ factorization, $𝑸 𝑹 = 𝑨$ . Projector onto $C (𝑨) = C (𝑸)$ is $𝑷_{𝑸} = 𝑸 𝑸^{T}$
- Projection of $𝒃$ onto $C (𝑨)$ is $𝑸 𝑸^{T} 𝒃$ . Set this equal to a linear combination of columns of $𝑨$ , $𝑨 𝒙 = 𝑸 𝑸^{T} 𝒃$ . Since $𝑨 = 𝑸 𝑹$ , solve the triangular system $𝑹 𝒙 = 𝑸^{T} 𝒃$ to find $𝒙$ .

.

The eigenvalue problem

For square matrix $𝑨 \in ℝ^{m \times m}$ find non-zero vectors whose directions are not changed by multiplication by $𝑨$ , $𝑨 𝒙 = λ 𝒙$ , $λ$ is scalar, the eigenvalue problem.
Consider the eigenproblem $𝑨 𝒙 = λ 𝒙$ for $𝑨 \in ℝ^{m \times m}$ . Rewrite as
$𝑨 𝒙 = λ 𝒙 \Rightarrow (𝑨 - λ 𝑰) 𝒙 = 𝟎 .$
Since $𝒙 \neq 𝟎$ , a solution to eigenproblem exists only if $𝑨 - λ 𝑰$ is singular.
$𝑨 - λ 𝑰$ singular implies $\det (𝑨 - λ 𝑰) = 0$ .
Investigate form of $\det (𝑨 - λ 𝑰) = 0$
$\det (𝑨 - λ 𝑰) = | \begin{array}{ccccc} a_{11} - λ & a & a_{13} & \dots & a_{1 m} \\ a_{21} & a_{22} - λ & a_{23} & \dots & a_{2 m} \\ a_{31} & a_{32} & a_{33} - λ & \dots & a_{3 m} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ a_{m 1} & a_{m 2} & a_{m 3} & \dots & a_{m m} - λ \end{array} |$
$p_{m} (λ) = \det (λ 𝑰 - 𝑨)$ , an $m^{th}$ -degree polynomial in $λ$ , characteristic polynomial of $𝑨$ , with $m$ roots, $λ_{1}, λ_{2}, \dots, λ_{m}$ , the eigenvalues of $𝑨$

Eigenproblem in matrix form

$𝑨 \in ℝ^{m \times m}$ , eigenvalue problem $𝑨 𝒙 = λ 𝒙$ ( $𝒙 \neq 𝟎$ ) in matrix form:
$𝑨 𝑿 = 𝑿 𝚲$ $𝑿 = [\begin{array}{lll} 𝒙_{1} & \dots & 𝒙_{m} \end{array}], 𝚲 = diag (λ_{1}, \dots, λ_{m}) = [\begin{array}{llll} λ_{1} & 0 & \dots & 0 \\ 0 & λ_{2} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & λ_{m} \end{array}] .$
$𝑿$ is the eigenvector matrix, $𝚲$ is the (diagonal) eigenvalue matrix
If column vectors of $𝑿$ are linearly independent, then $𝑿$ is invertible
$𝑨 = 𝑿 𝚲 𝑿^{- 1},$
the eigendecomposition of $𝑨$ (compare to $𝑨 = 𝑳 𝑼$ , $𝑨 = 𝑸 𝑹$ )
Rule “determinant of product = product of determinants” implies
$\det (𝑨 𝑿) = \det (𝑿 𝚲) \Rightarrow \det (𝑨) = \det (𝚲) (for \det (X) \neq 0) .$

Simple cases

Eigendecomposition of $𝑰 \in ℝ^{m \times m}$ . Compare $𝑨 𝑿 = 𝑿 𝚲$
$𝑰 𝑰 = 𝑰 𝑰, 𝑨 = 𝑰, 𝑿 = 𝑰, 𝚲 = 𝑰$
to find eigenvalues $λ_{1} = 1, \dots$ , $λ_{m} = 1$ , eigenvectors $𝒙_{1} = 𝒆_{1}, \dots$ , $𝒙_{m} = 𝒆_{m}$ .
Eigendecomposition of $𝑨 = diag (s_{1}, s_{2}, \dots, s_{m})$ . Compare $𝑨 𝑿 = 𝑿 𝚲$
$𝑨 𝑰 = 𝑰 𝑨$
to find eigenvalues $λ_{1} = s_{1}, \dots, λ_{m} = s_{m}$ , eigenvectors $𝒙_{1} = 𝒆_{1}, \dots, 𝒙_{m} = 𝒆_{m}$ .
Reflection across $x_{1}$ -axis in $ℝ^{2}$
$𝑨 = [\begin{array}{ll} 1 & 0 \\ 0 & - 1 \end{array}]$
is a diagonal matrix, $λ_{1} = 1$ , $λ_{2} = - 1$ , $𝒙_{1} = 𝒆_{1}$ , $𝒙_{2} = 𝒆_{2}$

ℝ^{3}

rotation matrix eigenvalues

Rotate by $θ$ around $x_{3}$ axis in $ℝ^{3}$
$𝑨 = [\begin{array}{lll} \cos θ & - \sin θ & 0 \\ \sin θ & \cos θ & 0 \\ 0 & 0 & 1 \end{array}] \in ℝ^{3 \times 3}, m = 3$
One direction not change by rotation is $𝒙_{3} = 𝒆_{3}$ with $λ_{3} = 1$
Where are the other two directions?
- Compute characteristic polynomial $p_{3} (λ) = \det (λ 𝑰 - 𝑨)$
  $p_{3} (λ) = | \begin{array}{lll} λ - \cos θ & \sin θ & 0 \\ - \sin θ & λ - \cos θ & 0 \\ 0 & 0 & λ - 1 \end{array} | = (λ - 1) (λ^{2} - 2 λ \cos θ + 1)$
- One root of $p_{3} (λ)$ is $λ_{3} = 1$ , as expected.
- Solve $λ^{2} - 2 λ \cos θ + 1 = 0$ to find remaining eigenvalues to be complex
  $λ_{1, 2} = \cos θ \pm \sqrt{\cos^{2} θ - 1} = \cos θ \pm i \sin θ = e^{\pm i θ} \in ℂ, i^{2} = - 1 .$

Complex numbers primer

$z \in ℂ$ can be represented in
- Cartesian form $z = x + i y$
- Polar form $z = r e^{i θ} = r (\cos θ + i \sin θ)$
Complex conjugate of $z \in ℂ$ negates imaginary part $\overline{z} = x - i y = r e^{- i θ}$
Absolute value of $z \in ℂ$ is $| z | = {(x^{2} + y^{2})}^{1 / 2} = r$
Argument of $z$ is angle $θ$ from polar form $z = r e^{i θ}$
Absolute value can be expressed as $| z | = {(\overline{z} z)}^{1 / 2}$
Recall for $𝒙 \in ℝ^{m}$
${|| 𝒙 ||}_{2}^{2} = 𝒙^{T} 𝒙 = x_{1}^{2} + \dots + x_{m}^{2},$
stating that squared 2-norm of real vector $𝒙$ is sum of squares of components.
Extend above to vector of complex numbers $𝒖 \in ℂ^{m}$ by
${|| 𝒖 ||}_{2}^{2} = {| u_{1} |}^{2} + \dots + {| u_{m} |}^{2} = {(\overline{𝒖})}^{T} 𝒖 .$
Taking the complex conjugate and transposing arises frequently, notation
$𝒖^{*} = {(\overline{𝒖})}^{T}, adjoint of 𝒖$

ℝ^{3}

rotation matrix eigenvectors

Consider $λ_{2} = e^{i θ} = \exp (i θ) = \cos θ + i \sin θ$ . Eigenvector $𝒙_{2}$ satisfies
$(𝑨 - λ_{2} 𝑰) 𝒙_{2} = 𝟎,$
which implies $𝒙_{2} \in N (𝑨 - λ_{2} 𝑰)$
Compute basis vector for $N (𝑨 - λ_{2} 𝑰)$
$𝑨 - λ_{2} 𝑰 = [\begin{array}{lll} - i \sin θ & - \sin θ & 0 \\ \sin θ & - i \sin θ & 0 \\ 0 & 0 & - e^{i θ} \end{array}] \sim [\begin{array}{lll} - i \sin θ & - \sin θ & 0 \\ 0 & 0 & 0 \\ 0 & 0 & - e^{i θ} \end{array}] .$
Find eigenvector
$𝒙_{2} = [\begin{array}{l} i \\ 1 \\ 0 \end{array}]$
Repeat for $λ_{2} = e^{- i θ}$ , find $𝒙_{3} = [\begin{array}{l} - i \\ 1 \\ 0 \end{array}]$

Verify

ℝ^{3}

rotation eigenvectors, eigenvalues

Compute $𝑨 𝒙_{2} - λ_{2} 𝒙_{2} = (𝑨 - λ_{2} 𝑰) 𝒙_{2}$
$(𝑨 - λ_{2} 𝑰) 𝒙_{2} = [\begin{array}{lll} - i \sin θ & - \sin θ & 0 \\ \sin θ & - i \sin θ & 0 \\ 0 & 0 & - e^{i θ} \end{array}] [\begin{array}{l} i \\ 1 \\ 0 \end{array}] = [\begin{array}{l} 0 \\ 0 \\ 0 \end{array}] = 𝟎 . ?$
In general a polynomial of degree $m$ $p_{m} (λ)$ with real coefficients has $m$ complext roots $λ_{1}, \dots, λ_{m} \in ℂ$

Not all eigenvector matrices are invertible

Consider
$𝑨 = [\begin{array}{ll} 1 & 1 \\ 0 & 1 \end{array}]$
Eigenvalues $λ_{1} = λ_{2} = 1$ , a repeated root, since
$\det (λ 𝑰 - 𝑨) = | \begin{array}{ll} λ - 1 & 1 \\ 0 & λ - 1 \end{array} | = {(λ - 1)}^{2} .$
However
$𝑨 - λ_{1} 𝑰 = [\begin{array}{ll} 0 & 1 \\ 0 & 0 \end{array}]$
$rank (𝑨 - λ_{1} 𝑰) = 1 = \dim C ({(𝑨 - λ_{1} 𝑰)}^{T})$ , FTLA $\Rightarrow \dim N (𝑨 - λ_{1} 𝑰) = 1$ , only one non-zero eigenvector