MATH347 L22: Eigenvalue theory

• New concepts:

  • Algebraic, geometric multiplicities

  • Diagonalizability

  • Computing eigenvalues

  • Computing eigenvectors

  • Ill-conditioning of finding roots of characteristic polynomial

  • Diagonalizable matrices

  • Utility of diagonal representation

Algebraic, geometric multiplicity

Definition 1. The algebraic multiplicity of an eigenvalue $\lambda$ is the number of times it appears as a repeated root of the characteristic polynomial $p\left(\lambda \right)=\det (A-\lambda I)$

Example. $p\left(\lambda \right)=\lambda (\lambda -1){(\lambda -2)}^2$ has two single roots ${\lambda }_1=0$, ${\lambda }_2=1$ and a repeated root ${\lambda }_{3,4}=2$. The eigenvalue $\lambda =2$ has an algebraic multiplicity of 2

Definition 2. The geometric multiplicity of an eigenvalue $\lambda$ is the dimension of the null space of $A-\lambda I$

Definition 3. An eigenvalue for which the geometric multiplicity is less than the algebraic multiplicity is said to be defective

Theorem. A matrix is diagonalizable if the geometric multiplicity of each eigenvalue is equal to the algebraic multiplicity of that eigenvalue.

Computing eigenvalues

• Finding eigenvalues as roots of characteristic polynomial $p\left(\lambda \right)=\det (\lambda 𝑰-𝑨)$ is suitable for small matrices $𝑨\in {ℝ}^{m\times m}$.

  • analytical root-finding formulas are available only for $m⩽4$

  • small errors in characteristic polynomial coefficients can lead to large errors in roots

• Octave/Matlab procedures to find characteristic polynomial

  • poly(A) function returns the coefficients

  • roots(p) function computes roots of the polynomial

  matlab>>

  A=[5 -4 2; 5 -4 1; -2 2 -3]; p=poly(A); disp(p)

  >> 1.0000 2.0000 -1.0000 -2.0000

  matlab>>

  roots(p)'

  >>${\displaystyle \left(\begin{array}{ccc}1& -2& -1\end{array}\right)}$

  matlab>>

Computing eigenvectors

• Find eigenvectors as non-trivial solutions of system $(𝑨-\lambda 𝑰)𝒙=0$, e.g., ${\lambda }_1=1$

  ${\displaystyle 𝑨-{\lambda }_1𝑰=\left(\begin{array}{ccc}4& -4& 2\\ 5& -5& 1\\ -2& 2& -4\end{array}\right)\sim \left(\begin{array}{ccc}-2& 2& -4\\ 0& 0& -6\\ 5& -5& 1\end{array}\right)\sim \left(\begin{array}{ccc}-2& 2& -4\\ 0& 0& -6\\ 0& 0& 0\end{array}\right)}$

  Note convenient choice of row operations to reduce amount of arithmetic, and use of knowledge that $𝑨-{\lambda }_1𝑰$ is singular to deduce that last row must be null

• In traditional form the above row-echelon reduced system corresponds to

  ${\displaystyle \{\begin{array}{lll}-2x_1+2x_2-4x_3& =& 0\\ 0x_1+0x_2-6x_3& =& 0\\ 0x_1+0x_2+0x_3& =& 0\end{array}\Rightarrow 𝒙=\alpha \left(\begin{array}{c}1\\ 1\\ 0\end{array}\right),.||𝒙||=1\Rightarrow \alpha =1/\sqrt{2}}$

• In Octave/Matlab the computations are carried out by the null function

  matlab>>

  null(A-eye(3))'

  >>${\displaystyle \left(\begin{array}{ccc}-0.70711& -0.70711& 5.5511e-17\end{array}\right)}$

Ill-conditioning of root-finding, alternative computational procedures

• Ill-conditioning: small errors in input produce large errors in output

• The eigenvalues of $𝑰\in {ℝ}^{3\times 3}$ are ${\lambda }_{1,2,3}=1$, but small errors in numerical computation can give roots of the characteristic polynomial with imaginary parts

  matlab>>

  roots(poly(eye(3)))'

  >>${\displaystyle \left(\begin{array}{ccc}1& 1-4.7606e-06\cdot 𝒊& 1+4.7606e-06\cdot 𝒊\end{array}\right)}$

  Avoid ill-conditioning of root finding by numerical methods (MATH566, MATH661)

  matlab>>

  eig(eye(3))'

  >>${\displaystyle \left(\begin{array}{ccc}1& 1& 1\end{array}\right)}$

  Eigenvalue numerical methods use following properties:

  • $𝑨𝒙=\lambda 𝒙\Rightarrow {𝑨}^{-1}𝒙={\lambda }^{-1}𝒙$ if ${𝑨}^{-1}$ exists. “Inverse matrix has inverse eigenvalues”

  • $𝑨𝒙=\lambda 𝒙\Rightarrow (𝑨+\mu 𝑰)𝒙=(\lambda +\mu )𝒙$. “Shifted matrix has shifted eigenvalues”

  • $𝑨𝒙=\lambda 𝒙$, $𝒙=𝑩𝒚\Rightarrow 𝑨𝑩𝒚=\lambda 𝑩𝒚\Rightarrow {𝑩}^{-1}𝑨𝑩𝒚=\lambda 𝒚$, if ${𝑩}^{-1}$ exists

  Matrix $𝑨$ is similar to matrix $𝑪$ if there exists $𝑩$ nonsingular for which $𝑪={𝑩}^{-1}𝑨𝑩$

  Similar matrices have the same eigenvalues

Matrices known to be diagonalizable, orthogonal diagonalization

• If $𝑨\in {ℝ}^{m\times m}$ has distinct eigenvalues then $𝑨$ is diagonalizable

• Even for $𝑨\in {ℝ}^{m\times m}$, eigenvalues might be complex

• Complex number $𝒛\in ℂ$ has real part $x$, imaginary part $y$

• Recall that for $𝒖\in {ℝ}^m$, ${||𝒖||}_2^2={𝒖}^T𝒖$. Extend to $𝒖\in {ℂ}^m$ by

  ${\displaystyle {||𝒖||}_2^2={\left(\overline{𝒖}\right)}^T𝒖={𝒖}^{\ast }𝒖}$

• $𝑨\in {ℝ}^{m\times m}$ is unitarily diagonalizable if there exists $𝑸\in {ℂ}^{m\times m}$ such that

  ${\displaystyle 𝑸{𝑸}^{\ast }={𝑸}^{\ast }𝑸=𝑰,𝑨𝑸=𝑸𝚲\Rightarrow 𝑨=𝑸𝚲{𝑸}^{\ast },}$

  with $𝚲$ diagonal eigenvalue matrix, $𝑸$ unitary eigenvector matrix

• $𝑨\in {ℝ}^{m\times m}$ is orthogonally diagonalizable if there exists $𝑸\in {ℝ}^{m\times m}$ such that

  ${\displaystyle 𝑸{𝑸}^T={𝑸}^T𝑸=𝑰,𝑨𝑸=𝑸𝚲\Rightarrow 𝑨=𝑸𝚲{𝑸}^T,}$

  with $𝚲$ diagonal eigenvalue matrix, $𝑸$ orthogonal eigenvector matrix.

• For $𝑨\in {ℝ}^{m\times m}$, symmetric matrices ($𝑨={𝑨}^T$), antisymmetric matrices ($𝑨=-{𝑨}^T$), normal matrices ($𝑨{𝑨}^T={𝑨}^T𝑨$) are orthogonally diagonalizable.

When is diagonal factorization useful?

• Suppose $𝑨\in {ℝ}^{m\times m}$ diagonalizable, $𝑨=𝑿𝚲{𝑿}^{-1}$

• Repeated application of $𝑨$

  ${\displaystyle {𝑨}^2=(𝑿𝚲{𝑿}^{-1})(𝑿𝚲{𝑿}^{-1})=𝑿{𝚲}^2{𝑿}^{-1}}$ ${\displaystyle {𝑨}^k=(𝑿𝚲{𝑿}^{-1})\cdot \cdots \cdot (𝑿𝚲{𝑿}^{-1})=𝑿{𝚲}^k{𝑿}^{-1}}$

• Above allows definition of $e^{𝑨},\sin \left(𝑨\right),\cos \left(𝑨\right)$, for example

  ${\displaystyle e^x=\frac{1}{0!}{x}^0+\frac{1}{1!}x+\frac{1}{2!}{x}^2+\cdots +\frac{1}{k!}{x}^k+\cdots \Rightarrow }$ ${\displaystyle e^{𝑨}=𝑿(\frac{1}{0!}{𝚲}^0+\frac{1}{1!}𝚲+\frac{1}{2!}{𝚲}^2+\cdots +\frac{1}{k!}{𝚲}^k+\cdots ){𝑿}^{-1}}$

• The differential system ${𝒚}^{\text{'}}=𝑨𝒚$ has solution $𝒚\left(t\right)=e^{𝑨t}y\left(0\right)$.