In this section let V be a vector space over E, dim(V)=n<∞, A∈En×n.
Definition
λ∈E is called an eigenvalue of A⇔∃v∈V∖{0}:Av=λv.
v∈V∖{0} is then called an eigenvector of A for the eigenvalue λ.
Eλ(A)={v∈V∣Av=λv} is called the eigenspace of A for the eigenvalue λ.
σ(A):={λ∣λ eigenvalues of A} is called the spectrum of A.
Remark
Eλ(A)=ker(A−λ𝟙) is a non-trivial subspace of V, i.e.:
{0}⊊Eλ(A)(strictly larger than just the zero space)
Remark
This definition carries over analogously to a linear map F:V→V. We have:
⇔λ is an eigenvalue of F,v is an eigenvector of Fλ is an eigenvalue of A,v is an eigenvector of A,where A denotes the matrix of F.
RemarkDerivation of the characteristic polynomial χ_A
Consider
Av=λv⇔Av−λv=0⇔(A−λ𝟙)v=0(1)
v=0 solves (1), but v=0 is not allowed as an eigenvector. We require more solutions, i.e. ∞ many solutions (since a linear system always has 0,1 or ∞ many solutions). By the theorem from the review, we can achieve this by setting det(A−λ𝟙)=!0, because
det(A−λ𝟙)=0⇔SatzA−λ𝟙 singular⇒(A−λ𝟙)v=0 has ∞ many solutions, since v=0 is not allowed.
Definition
χA(λ)=det(A−λ𝟙) is called the characteristic polynomial.
Remark
χA(λ) has degree n
λ is an eigenvalue of A ⇔λ is a root of the characteristic polynomial χA(λ).
Remark
Quadratic formula (learn by heart)
ax2+bx+c⇒x1,2=0=2a−b±b2−4ac
AlgorithmComputing eigenvalues and eigenvectors
Given: A∈En×n
(if a linear map F:V→V is given, first find its matrix A)
Find: σ(A) (i.e. ∀ eigenvalues of A), Eλ(A) with ∀λ∈σ(A)
Compute χA(λ)=det(A−λ𝟙)
Set χA(λ)=!0:
⇒n roots λ1,...,λn⇒σ(A)={λ1,...,λn}
Remark.λ1,...,λn are not necessarily distinct; they are counted with multiplicity.
For each distinct eigenvalue λk, determine the basis of Eλk(A)=ker(A−λk𝟙) using Gaussian elimination.
The set of eigenvectors is
k⋃(Eλk(A)∖{0})
(We take the union of all eigenspaces minus the zero vector)
Example 1
Given:
A=140230325
Find: eigenvalues, eigenvectors of A
Show solutionHide solution
χA(λ)=det(A−λ𝟙)=det(1−λ)402(3−λ)032(5−λ)=(1−λ)(3−λ)(5−λ)−(5−λ)⋅4⋅2=(5−λ)[(1−λ)(3−λ)−4⋅2]=(5−λ)[3−3λ−λ+λ2−8]=(5−λ)[λ2−4λ−5]=(5−λ)(λ−5)(λ+1)(if needed, using the quadratic formula)=−(λ−5)(λ−5)(λ+1)=−(λ−5)2(λ+1)
χA(λ)⇔−(λ−5)2(λ+1)⇒λ1λ3⇒σ(A)=!0=0=λ2=5(later: the algebraic multiplicity of 5 is 2)=−1={5,−1}
It would be mathematically imprecise to say in example 1: "The eigenvectors are (1,2,0)T and (1,−1,0)T". Because there are ∞ many eigenvectors.
For example, let v be an eigenvector of A for the eigenvalue λ, i.e. Av=λv ⇒c⋅v is an eigenvector of A for λ for all c∈E∖{0}, since A(cv)=λ(cv) also holds.
Usually it is still enough to take one basis vector v∈Eλ(A)∖{0} as a "representative eigenvector".
Spectral Decomposition, Diagonalisability
Definition
Let λ be an eigenvalue of A∈En×n.
Algebraic multiplicity of λ:
aλ:="multiplicity of λ as a root of χA(λ)"
Geometric multiplicity:
gλ:=dim(Eλ(A))=dim(ker(A−λ𝟙))=n−rank(A−λ𝟙)
Definition
A is called diagonalisable (a spectral decomposition exists)
⇔∃V∈En×n,Λ∈En×n, with V regular, Λ diagonal, such that A=VΛV−1
One also says: "A is similar to a diagonal matrix".
Satz
A is diagonalisable ⇔ The eigenvectors of A form a basis of V ⇔ For all eigenvalues λ of A we have gλ=aλ.
Remark
A diagonalisation is a change of basis with transformation matrices V and V−1.
Satz
A similarity transformation preserves:
eigenvalues and their algebraic and geometric multiplicity
rank
determinant
trace
characteristic polynomial χA(t)
not the eigenvectors!
AlgorithmComputing the diagonal matrix
Given: A∈En×n diagonalisable
Find: V,Λ∈En×n
Find the eigenvalues λ1,...,λn and the corresponding eigenvectors v1,...,vn of A (where vi∈Eλi(A) and {vi}i=1n linearly independent).
Define the diagonal matrix as follows:
Λ=λ10⋮00⋱⋱⋯⋯⋱⋱00⋮0λnwith λ1≥...≥λn
Write the eigenvectors vi∈Eλi(A) into a matrix:
V=(v1∣⋯∣vn)
Check: A=?VΛV−1
Example 1continued …
Let
A=140230325 as in example 3 with χA(λ)=−(λ−5)2(λ+1)
where you compute the inverse V−1 with the usual recipe.
Check: A=VΛV−1✓
Remark
Complex roots of the characteristic polynomial with real coefficients always occur in pairs: if λ∈C is a root, then so is λ. Hence an orthogonal matrix of odd dimension must have at least one real eigenvalue ±1.
Definition
The sum of the diagonal elements of A∈En×n is called the trace of A:
tr(A):=i=1∑naii=a11+...+ann.
Lemma 9.6
A (square) matrix A is singular if and only if it has 0 as an eigenvalue:
A singular⇔0∈σ(A).
Satz 9.11
Eigenvectors for distinct eigenvalues are linearly independent.
Corollary 9.12
If the n eigenvalues of F:V→V (with n=dim(V)) are distinct, then there is a basis of eigenvectors and the corresponding matrix is diagonal.
Satz 9.15
If A∈Cn×n is Hermitian, then:
All eigenvalues λ1,...,λn are real.
The eigenvectors for distinct eigenvalues are pairwise orthogonal in Cn.
There is an orthonormal basis of Cn consisting of eigenvectors u1,...,un of A.
For the unitary matrix U:=(u1,...,un) we have: UHAU=Λ=diag(λ1,...,λn).
Singular Value Decomposition
Satz
Let A∈En×n be symmetric (AT=A) or Hermitian (AH=AT=AT=A), then:
A has only real eigenvalues
Eigenvectors for distinct eigenvalues are pairwise orthogonal
Remark 1
To obtain an orthonormal basis of eigenvectors of a symmetric/Hermitian matrix, you only need to normalise the eigenvectors and, if necessary, orthogonalise them with Gram-Schmidt (you do this if there is an eigenvalue with geometric multiplicity >1).
SatzSingular value decomposition
Let A∈Em×n, rank(A)=:r≤min{m,n}. Then there exist U∈Em×m orthogonal/unitary, V∈En×n orthogonal/unitary, Σ∈Rm×n, where
⇒σi=λi, where λi are the positive real eigenvalues of AHA.
RemarkApplications
The singular value decomposition is, in a sense, a generalisation of the spectral decomposition to rectangular matrices.
Solving singular linear systems and least-squares problems.
Image compression. An image is viewed as a matrix of colour values, whose singular value decomposition is computed. When transforming back from UΣVH to A, however, only the singular values that "deviate strongly from 0" are kept; singular values that are small in absolute value are discarded.
Compute the eigenvalues of B and "number" them by size:
λ1≥...≥λr>λr+1=...=λn=0,
where r=rank(B)=rank(AHA)
Σij={σi=λi,i=j0,otherwise
Build the orthonormal basis {w1,...,wn} with Gram-Schmidt from the eigenvectors {v1,...,vn} of B. (Note that B=AHA is Hermitian, i.e. use remark 1)
⇒V=(w1∣⋯∣wn)
∀i∈{1,...,r}define ui:=σi1Awi⇒ui are orthonormal/unitary
Extend {u1,...,ur} to an orthonormal basis of Em with Gram-Schmidt
⇒U=(u1∣...∣um)
Check: A=?UΣVH✓
Example 3
Given:
A=120011
Find: U,Σ,V such that A=UΣVH; additional question: describe the four fundamental subspaces according to Satz 11.1 (see lecture notes).