Eigenvalues, Eigenvectors and Upper Triangularization

Andrew Thangaraj

Aug-Nov 2020

Recap

  • Vector space \(V\) over a scalar field \(F\)
    • \(F\): real field \(\mathbb{R}\) or complex field \(\mathbb{C}\) in this course
  • \(m\times n\) matrix A represents a linear map \(T:F^n\to F^m\)
    • dim null \(T\) + dim range \(T\) = dim \(V\)
  • Linear equation: \(Ax=b\)
    • Solution (if it exists): \(u+\) null\((A)\)
  • Four fundamental subspaces of a matrix
    • Column space, row space, null space, left null space
  • Eigenvalue \(\lambda\) and Eigenvector \(v\): \(Tv=\lambda v\)
    • Distinct eigenvalues have independent eigenvectors
    • Basis of eigenvectors results in a diagonal matrix for \(T\)

Invariant subspaces and matrices of operators

\(T:V\to V\), operator and \(U\subseteq V\), invariant subspace

Pick subspace \(W\) s.t. \(V=U\oplus W\)

Basis for \(V\): \(\{u_1,\ldots,u_k,w_1,\ldots,w_{n-k}\}\)

\(\{u_1,\ldots,u_k\}\): basis for \(U\), \(\{w_1,\ldots,w_{n-k}\}\): basis for \(W\)

Matrix of \(T\) in above basis

\(\begin{bmatrix} \vdots&\cdots&\vdots&\vdots&\cdots&\vdots\\ Tu_1&\cdots&Tu_k&Tw_1&\cdots&Tw_{n-k}\\ \vdots&\cdots&\vdots&\vdots&\cdots&\vdots \end{bmatrix}\)

What happens because of invariance of \(U\)?

\(Tu_i = a_{1i}u_1+\cdots+a_{ki}u_k+0w_1+\cdots+0w_{n-k}\)

Invariant subspaces, eigenvalues and matrices of operators

Form of matrix for \(T\)

\(\begin{bmatrix} a_{11}&\cdots&a_{1k}&&\cdots&\\ \vdots&\vdots&\vdots&\vdots&\cdots&\vdots\\ a_{k1}&\cdots&a_{kk}&Tw_1&\cdots&Tw_{n-k}\\ 0&\cdots&0 &\vdots&\cdots&\vdots\\ \vdots&\vdots&\vdots&&\cdots&\\ 0&\cdots&0 &&\cdots& \end{bmatrix}\)

\(V\): over \(\mathbb{C}\). \(Tv_1=\lambda v_1\). Basis for \(V\): \(\{v_1,w_1,\ldots,w_{n-1}\}\)

\(Tw_j = b_{0j}v_1+b_{1j}w_1+\cdots+b_{n-1,j}w_{n-1}\)

\(\begin{bmatrix} \lambda&b_{0j}&\cdots&b_{0,n-1}\\ 0&b_{11}&\cdots&b_{1,n-1}\\ \vdots&\vdots&\cdots&\vdots\\ 0&b_{n-1,1}&\cdots&b_{n-1,n-1} \end{bmatrix}\)

Example

Towards upper triangularization

\(\begin{bmatrix} b_{0j}&\cdots&b_{0,n-1} \end{bmatrix}\leftrightarrow T_0:W\to\) span\(\{v_1\}\) in basis \(\{w_1,\ldots,w_{n-1}\}\)

\(\begin{bmatrix} b_{11}&\cdots&b_{1,n-1}\\ \vdots&\cdots&\vdots\\ b_{n-1,1}&\cdots&b_{n-1,n-1} \end{bmatrix}\leftrightarrow T_1:W\to W\) in basis \(\{w_1,\ldots,w_{n-1}\}\)

\(v\in V\): \(v=c_1v_1+w'\), where \(w'=d_1w_1+\cdots+d_{n-1}w_{n-1}\in W\)

\(Tv=c_1\lambda v_1+T_0w'+T_1w'=(c_1\lambda+c_{w'})v_1+T_1w'\)

\(T_1w=\lambda_1 w\). Change basis for \(T\) from \(\{v_1,w_1,\ldots,w_{n-1}\}\) to \(\{v_1,w,w'_1,\ldots,w'_{n-2}\}\)

\(\begin{bmatrix} \lambda&*&*&\cdots&*\\ 0&\lambda_1&*&\cdots&*\\ 0&0&*&\cdots&*\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ 0&0&*&\cdots&*\\ \end{bmatrix}\)

Upper triangularization

Every linear operator (over \(\mathbb{C}\)) has an upper triangular matrix representation.

Proof

Continue previous process - one eigenvalue at a time

All eigenvalues are on the diagonal in the upper triangular matrix representation

  • Algebraic multiplicity of an eigenvalue: number of times it appears on the diagonal

Geometric multiplicity of an eigenvalue \(\le\) algebraic multiplicity

Proof

\(A\): upper triangular matrix of \(T\)

AM\((\lambda)=\) number of times \(\lambda\) appears on diagonal

rank\((A-\lambda I)\ge n-\) AM\((\lambda)\)

Eigenspaces and diagonalization

Eigenspace of an eigenvalue \(\lambda\): \(E(\lambda, T)=\) null\((T-\lambda I)\)

  • Eigenspace is the set of all eigenvectors along with \(0\)

  • GM\((\lambda)=\) dim \(E(\lambda,T)\le\) AM\((\lambda)\)

  • dim \(E(\lambda,T)\): number of linearly independent eigenvectors

  • \(E(\lambda,T)\) and \(E(\lambda',T)\) intersect only at \(0\), if \(\lambda\ne \lambda'\)

\(T:V\to V\) with distinct eigenvalues \(\lambda_1,\ldots,\lambda_m\).

  • Eigenspaces: \(E(\lambda_1,T), \ldots, E(\lambda_m,T)\)

When is a linear map diagonalizable?

  • GM\((\lambda_i) =\) AM\((\lambda_i)\) for \(i=1,\ldots,m\)

  • \(V=E(\lambda_1,T)\oplus\cdots\oplus E(\lambda_m,T)\)

Example: MATLAB