Data Stability

• Consider square matrix $A\in {ℝ}^{m\times m}$. The eigenvalue problem asks for vectors $x\in {ℂ}^m$, $x\ne 0$, scalars $\lambda \in ℂ$ such that

  ${\displaystyle Ax=\lambda x}$

  (1)

• Eigenvectors are those special vectors whose direction is not modified by the matrix $A$

• Rewrite (1): $(A-\lambda I)x=0$, and deduce that $A-\lambda I$ must be singular in order to have non-trivial solutions $\det (A-\lambda I)=0$

• Consider the determinant

  ${\displaystyle \det (A-\lambda I)=\left|\begin{array}{cccc}{a}_{11}-\lambda & a_{12}& \dots & a_{1m}\\ a_{21}& a_{22}-\lambda & \dots & a_{2m}\\ ⋮& ⋮& \ddots & ⋮\\ a_{m1}& a_{m2}& \dots & a_{mm}-\lambda \end{array}\right|}$

• From determinant definition “sum of all products choosing an element from row/column”

is the characteristic polynomial associated with the matrix $A$, and is of degree $m$

• $A\in {ℝ}^{m\times m}$ has characteristic polynomial $p_A\left(\lambda \right)$ of degree $m$, which has $m$ roots (Fundamental theorem of algebra)

• Example

octave] 

theta=pi/3.; A=[cos(theta) -sin(theta); sin(theta) cos(theta)]

octave] 

eig(A)

octave] 

[R,lambda]=eig(A);

octave] 

disp(R);

octave] 

disp(lambda)

octave] 

A=[-2 1 0 0 0 0; 1 -2 1 0 0 0; 0 1 -2 1 0 0; 0 0 1 -2 1 0; 0 0 0 1 -2 1; 0 0 0 0 1 -2];

octave] 

disp(A)

octave] 

lambda=eig(A);

octave] 

disp(lambda);

octave] 

• For $A\in {ℝ}^{m\times m}$, the eigenvalue problem 5 ($x\ne 0$) can be written in matrix form as

  ${\displaystyle AX=X\Lambda ,X=\left(x_1\dots x_m\right)\mathrm{eigenvector},\Lambda =\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_m)\mathrm{eigenvalue}\mathrm{matrices}}$

• 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

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

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

• 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$