The set of all permutations is called the symmetric groupSn.
Definition
A permutation that swaps only two elements is called a transposition.
Satz
Every permutation can be written as a product (composition of maps) of transpositions.
Remark
The representation of a permutation as a product of transpositions is not unique. But the number of transpositions needed is uniquely either even or odd.
Definition
If p∈Sn, then every pair i,j∈{1,...,n} with
i<jbutp(i)>p(j),
is called an inversion of p.
Example 1
Given:
p=[122331]
Find: the inversions of p
Show solutionHide solution
There are two inversions in total, namely
1<3,but2>1,and2<3,but3>1.
Definition
The sign of a permutation is defined as
sign(p)=(−1)k={1,if p has an even number k of inversions−1,if p has an odd number k of inversions.
For an n×n matrix you can compute the determinant via the definition with permutations, but this is very inefficient (effort proportional to n!).
Satz
Let A be the row echelon form of A (i.e. A is an upper/lower triangular matrix), computed from A by Gaussian elimination. Let k∈N0 be the number of row swaps performed:
⇒det(A)=(−1)k⋅det(A)=(−1)ki=1∏nAii,where i=1∏nAii is the product of the diagonal entries.
Satz
Laplace expansion
Let A∈En×n and Aij′∈E(n−1)×(n−1) the minor matrix without the i-th row and j-th column.
⇒Expansion along the i-th row: det(A)=j=1∑n(−1)i+j⋅aij⋅det(Aij′)⇒Expansion along the j-th column: det(A)=i=1∑n(−1)i+j⋅aij⋅det(Aij′).
For each element akl of an n×n matrix A, define the (n−1)×(n−1) submatrix A[k,l] by deleting row k and column l of A. The cofactorκkl of akl is then the number:
κkl:=(−1)k+l det(A[k,l]).
Eigenvalues and Eigenvectors
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(λ).
RemarkQuadratic formula (learn by heart)
ax2+bx+c⇒x1,2=0=2a−b±b2−4ac
RemarkComputing 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)
1) Compute χA(λ)= det(A−λ𝟙)
2) Set χA(λ)=!0:
⇒n roots λ1,...,λn⇒σ(A)={λ1,...,λn}
Remark.λ1,...,λn are not necessarily distinct; they are counted with multiplicity.
3) For each distinct eigenvalue λk, determine the basis of Eλk(A)= ker(A−λk𝟙) using Gaussian elimination.
4) The set of eigenvectors is
k⋃(Eλk(A)∖{0})
(We take the union of all eigenspaces minus the zero vector)
Example 3
Given:
A=140230325
Find: eigenvalues, eigenvectors of A
Show solutionHide solution
1)
χ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)
2)
χ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 3: "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!
RemarkComputing the diagonal matrix
Given: A∈En×n diagonalisable
Find: V,Λ∈En×n
1) Find the eigenvalues λ1,...,λn and the corresponding eigenvectors v1,...,vn of A (where vi∈Eλi(A) and {vi}i=1n linearly independent).
2) Define the diagonal matrix as follows:
Λ=λ10⋮00⋱⋱⋯⋯⋱⋱00⋮0λnwith λ1≥...≥λn
3) Write the eigenvectors vi∈Eλi(A) into a matrix:
V=(v1∣⋯∣vn)
4) Check: A=?VΛV−1
Example 3continued...
Let
A=140230325 as in example 3 with χA(λ)=−(λ−5)2(λ+1)
where you compute the inverse V−1 with the usual recipe.
4) 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
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).