Eigenvalue-Revealing Factorizations

Linear endomorphisms $𝒇:{ℂ}^m\to {ℂ}^m$, represented by $𝑨\in {ℂ}^{m\times m}$, can exhibit invariant directions $𝒙\ne 𝟎$ for which

known as eigenvectors, with associated eigenvalue $\lambda \in ℂ$. Eigenvectors are non-zero elements of the null space of $𝑨-\lambda 𝑰$,

and the null-space is referred to as the eigenspace of $𝑨$ for eigenvalue $\lambda$, ${ℰ}_{𝑨}\left(\lambda \right)=N(𝑨-\lambda 𝑰)$.

Non-zero solutions are obtained if $𝑨-\lambda 𝑰$ is rank-deficient (singular), or has linearly dependent columns in which case

From the determinant definition as “sum of all products choosing an element from row/column”, it results that

known as the characteristic polynomial associated with the matrix 𝑨, and of degree $m$. The characteristic polynomial is monic, meaning that the coefficient of the highest power ${\lambda }^m$ is equal to one. The fundamental theorem of algebra states that $p_A\left(\lambda \right)$ of degree $m$ has $m$ roots, hence $𝑨\in {ℂ}^{m\times m}$ has $m$ eigenvalues (not necessarily distinct), and $m$ associated eigenvectors. This can be stated in matrix form as

with

the eigenvector matrix and eigenvalue matrix, respectively.

1.1.Coordinate transformations

The statement $𝑨𝒙=\lambda 𝒙$, that eigenvector $𝒙$ is an invariant direction of the operator $𝑨$ along which the effect of operator is scaling by $\lambda$, suggests that similar behavior would be obtained under a coordinate transformation $𝑻𝒚=𝑰𝒙=𝒙$. Assuming $𝑻$ is of full rank and introducing $𝑩={𝑻}^{-1}𝑨𝑻$, this leads to

Upon coordinate transformation, the eigenvalues (scaling factors along the invariant directions) stay the same. Metric-preserving coordinate transformations are of particular interest, in which case the transformation matrix is unitary $𝑩={𝑸}^{\ast }𝑨𝑸$.

Definition. Matrices $𝑨,𝑩\in {ℂ}^{m\times m}$ are said to be similar, $𝑩\sim 𝑨$, if there exists some full rank matrix $𝑻\in {ℂ}^{m\times m}$ such that $𝑩={𝑻}^{-1}𝑨𝑻$.

Proposition. Similar matrices $𝑨,𝑩\in {ℂ}^{m\times m}$, $𝑩={𝑻}^{-1}𝑨𝑻$, have the same eigenvalues, and eigenvectors $𝒙$ of $𝑨$, $𝒚$ of $𝑩$ are related through $𝒙=𝑻𝒚$.

Since the eigenvalues of $𝑩\sim 𝑨$ are the same, and a polynomial is completely specified by its roots and coefficient of highest power, the characteristic polynomials of $𝑨,𝑩$ must be the same

This can also be verified through the determinant definition

since $\det \left({𝑻}^{-1}\right)=1/\det \left(𝑻\right)$.

1.2.Paradigmatic eigenvalue problem solutions

$\circ$Reflection matrix. The matrix

${\displaystyle 𝑯=𝑰-2𝒒{𝒒}^T\in {ℝ}^{2\times 2},||𝒒||=1,}$

is the two-dimensional Householder reflector across $N\left({𝒒}^T\right)$. Vectors colinear with $𝒒$ change direction along the same orientation upon reflection, while vectors orthogonal to $𝒒$ (i.e., in the null space $𝑵\left({𝒒}^T\right)$) are unchanged. It is therefore to be expected that ${\lambda }_1=-1$, ${𝒙}_1=𝒒$, and ${\lambda }_2=1$, ${𝒒}^T{𝒙}_2=0$. This is readily verified

${\displaystyle 𝑯𝒒=(𝑰-2𝒒{𝒒}^T)𝒒=𝒒-2𝒒=-𝒒,}$ ${\displaystyle 𝑯{𝒙}_2=(𝑰-2𝒒{𝒒}^T){𝒙}_2={𝒙}_2.}$

Figure 1. Reflector in two dimensions

∴	v=[-1; 1]; q=v/norm(v); H=I-2*q*q';

∴	eigvals(H)

${\displaystyle \left[\begin{array}{c}-0.9999999999999996\\ 1.0\end{array}\right]}$

(1)

∴	eigvecs(H)

${\displaystyle \left[\begin{array}{cc}-0.7071067811865475& 0.7071067811865475\\ 0.7071067811865475& 0.7071067811865475\end{array}\right]}$

(2)

∴

∴ 

R=[1 -1; 1 1]/sqrt(2); eigvals(R)

∴ 

eigvecs(R)

∴ 

∴ 

m=4; o=ones(m-1,1)[:,1]; D=diagm(-1 => o, 1 => o)-2*I

∴ 

function ErrorλD(m)
  h=π/(m+1); ξ=1:m; o=ones(m-1); D=(diagm(-1=>o, 1=>o)-2*I)/h^2;
  λD = sort(eigvals(D),rev=true)
  λ = -(4/h^2)*sin.(ξ*h/2).^2
  ε=norm(λD .- λ)/norm(λ)
end;

∴ 

ε=ErrorλD.(20:20:100)';

∴ 

print(round.(ε; digits=3))

∴ 

function eigD(m)
  h=π/m; o=ones(m-1,1)[:,1]; D=diagm(-1 => o, 1 => o)-2*I;
  λD=sort(eigvals(D),rev=true)
  λ = -4*sin.(collect(1:m).*h/2).^2
  return [λD λ]
end;

∴ 

clf();

∴ 

for m=10:10:100
  local Λ=eigD(m)
  plot(1:m,Λ[:,1],"ob",markerfacecolor="none")
  plot(1:m,Λ[:,2],"xr")  
end

∴ 

xlabel("k"); ylabel("λ[k]");

∴ 

pre=homedir()*"/courses/MATH661/images/";

∴ 

savefig(pre*"L14D2eigs.eps");

∴ 

1.3.Matrix eigendecomposition

A solution $𝑿,𝚲$ to the eigenvalue problem $𝑨𝑿=𝑿𝚲$ always exists, but the eigenvectors of $𝑨$ do not always form a basis set, i.e., $𝑿$ is not always of full rank. The factorized form of the characteristic polynomial of $𝑨\in {ℂ}^{m\times m}$ is

with $K⩽m$ denoting the number of distinct roots of $p_{𝑨}\left(\lambda \right)$, and $m_k$ is the algebraic multiplicity of eigenvalue ${\lambda }_k$, defined as the number of times the root ${\lambda }_k$ is repeated. Let ${ℰ}_k$ denote the associated eigenspace ${ℰ}_k={ℰ}_{𝑨}\left({\lambda }_k\right)=N(𝑨-{\lambda }_k𝑰)$. The dimension of ${ℰ}_k$ denoted by $n_k$ is the geometric multiplicity of eigenvalue ${\lambda }_k$. The eigenvector matrix is of full rank when the vector sum of the eigenspaces covers ${ℂ}^m$, as established by the following results.

Proposition. If ${\lambda }_i\ne {\lambda }_j$ then ${ℰ}_i\cap {ℰ}_j=\left\{𝟎\right\}$ (the eigenspaces of distinct eigenvalues are disjoint)

Proof. Let $𝒙\in$${ℰ}_i$, hence $𝑨𝒙={\lambda }_i𝒙$ and $𝒙\in$${ℰ}_j$, hence $𝑨𝒙={\lambda }_j𝒙$. Subtraction gives

Since ${\lambda }_i\ne {\lambda }_j$ it results that $𝒙=𝟎$.$\square$

Proposition. The geometric multiplicity of an eigenvalue is less or equal to its algebraic multiplicity,

Proof. Let $𝑽\in {ℂ}^{m\times n_k}$ be an orthogonal basis for $N(𝑨-{\lambda }_k𝑰)$.$\square$

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

Proposition 2. A matrix is diagonalizable is the geometric multiplicity of each eigenvalue is equal to the algebraic multiplicity of that eigenvalue.

If the column vectors of $X$ are linearly independent, then $X$ is invertible and $A$ can be reduced to diagonal form

${\displaystyle A=X\Lambda X^{-1},A=U\Sigma V^T}$

• Diagonal forms are useful in solving linear ODE systems

  ${\displaystyle y^{\text{'}}=\mathrm{Ay}\iff \left(X^{-1}y\right)=\Lambda \left(X^{-1}y\right)}$

• Also useful in repeatedly applying $A$

  ${\displaystyle u_k=A^k{u}_0=AA\dots A{u}_0=(X\Lambda X^{-1})(X\Lambda X^{-1})\dots (X\Lambda X^{-1})u_0=X{\Lambda }^k{X}^{-1}{u}_0}$

• When can a matrix be reduced to diagonal form? When eigenvectors are linearly independent such that the inverse of $X$ exists

• Matrices with distinct eigenvalues are diagonalizable. Consider $A\in {ℝ}^{m\times m}$ with eigenvalues ${\lambda }_j\ne {\lambda }_k$ for $j\ne k$, $j,k\in \{1,\dots ,m\}$

  Proof. By contradiction. Take any two eigenvalues ${\lambda }_j\ne {\lambda }_k$ and assume that $x_j$ would depend linearly on $x_k$, $x_k=c{x}_j$ for some $c\ne 0$. Then

  ${\displaystyle \begin{array}{rcl}A{x}_1={\lambda }_1{x}_1& \Rightarrow & A{x}_1={\lambda }_1{x}_1\\ A{x}_2={\lambda }_2{x}_2& \Rightarrow & Ac{x}_1={\lambda }_{2}c{x}_1\end{array}}$

  and subtracting would give $0=({\lambda }_1-{\lambda }_2)x_1$. Since $x_1$ is an eigenvector, hence $x_1\ne 0$ we obtain a contradiction ${\lambda }_1={\lambda }_2$.

• The characteristic polynomial might have repeated roots. Establishing diagonalizability in that case requires additional concepts

• Finding eigenvalues as roots of the characteristic polynomial $p\left(\lambda \right)=\det (A-\lambda I)$ 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

octave] 

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

octave] 

p=poly(A); disp(p);

octave] 

r=roots(p); disp(r');

octave] 

• Find eigenvectors as non-trivial solutions of system $(𝑨-\lambda 𝑰)𝒙=0$

  ${\displaystyle {\lambda }_1=1\Rightarrow 𝑨-{\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

  octave]

  null(A+5*eye(3))'

  ans = [](0x3)

  octave]

• 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

octave> 

lambda=roots(poly(eye(3))); disp(lambda')

octave> 

• In the following example notice that if we slightly perturb $𝑨$ (by a quantity less than 0.0005=0.05%), the eigenvalues get perturb by a larger amount, e.g. 0.13%.

octave] 

A=[-2 1 -1; 5 -3 6; 5 -1 4]; disp([eig(A) eig(A+0.001*(rand(3,3)-0.5))])

octave] 

• Extracting eigenvalues and eigenvectors is a commonly encountered operation, and specialized functions exist to carry this out, including the eig function

octave> 

 [X,L]=eig(A); disp([L X]);

octave> 

disp(null(A-3*eye(3)))

octave> 

disp(null(A+2*eye(3)))

octave> 

• Recall definitions of eigenvalue algebraic ${𝒎}_{\lambda }$ and geometric multiplicities ${𝒏}_{\lambda }$.

Definition. A matrix which has $n_{\lambda }<m_{\lambda }$ for any of its eigenvalues is said to be defective.

octave> 

A=[-2 1 -1; 5 -3 6; 5 -1 4]; [X,L]=eig(A); disp(L);

octave> 

disp(X);

octave> 

disp(null(A+2*eye(3)));

octave> 

disp(rank(X))

octave> 

2.Computation of the SVD

• The SVD is determined by eigendecomposition of $A^{T}A$, and $A{A}^T$

  • $A^{T}A={(U\Sigma V^T)}^T(U\Sigma V^T)=V({\Sigma }^T\Sigma )V^T$, an eigendecomposition of $A^{T}A$. The columns of $V$ are eigenvectors of $A^{T}A$ and called right singular vectors of $A$

    ${\displaystyle B=A^{T}A=V{\Sigma }^T\Sigma V^T=V\Lambda V^T}$

  • $A{A}^T=(U\Sigma V^T){(U{\Sigma }^T{V}^T)}^T=U\left(\Sigma {\Sigma }^T\right)U^T$, an eigendecomposition of $A^{T}A$. The columns of $U$ are eigenvectors of $A{A}^T$ and called left singular vectors of $A$

  • The matrix $\Sigma$ has form

    ${\displaystyle \Sigma =\left(\begin{array}{cccccc}{\sigma }_1& & & & & \\ & {\sigma }_2& & & & \\ & & \ddots & & & \\ & & & {\sigma }_r& & \\ & & & & 0& \\ & & & & & \ddots \end{array}\right)\in {ℝ}_{+}^{m.\times n.}}$

    and ${\sigma }_i$ are the singular values of $A$.

• The singular value decomposition (SVD) furnishes complete information about $A$

  • $\mathrm{rank}\left(A\right)=r$ (the number of non-zero singular values)

  • $U,V$ are orthogonal basis for the domain and codomain of $A$