Study Guides / Linear Algebra / Exercise session 12
EXERCISE SESSION 12 · ETH ZURICH · HS19 · linalg

Determinants, Eigenvalues and Diagonalisability

Permutation, symmetric group, determinant, eigenvalue & eigenvector, characteristic polynomial, trace

SB
Steven Battilana Quant · ex-ETH

Symmetric Group

Definition

A permutation is a bijective map:

p:{1,...,n}→{1,...,n}p: \{1, ..., n\} \to \{1, ..., n\}
Definition

The set of all permutations is called the symmetric group SnS_n.

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∈Snp \in S_n, then every pair i,j∈{1,...,n}i,j \in \{1, ..., n\} with

i<jbutp(i)>p(j),i<j \quad \text{but} \quad p(i) > p(j),

is called an inversion of pp.

Example 1

Given:

p=[123231]p = \begin{bmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{bmatrix}

Find: the inversions of pp

Show solutionHide solution

There are two inversions in total, namely

1<3,  but  2>1,and2<3,  but  3>1.1<3, \; \text{but} \; 2>1, \quad \text{and} \quad 2<3, \; \text{but} \; 3>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.\text{sign}(p) = (-1)^k = \begin{cases} 1, \hspace{0.5cm} \text{if } p \text{ has an \textit{even} number } k \text{ of inversions}\\ -1, \hspace{0.2cm} \text{if } p \text{ has an \textit{odd} number } k \text{ of inversions.} \end{cases}
Definition

We call p∈Snp \in S_n:

  • even if sign(p)=+1(p) = +1,
  • odd if sign(p)=−1(p) = -1.

Determinants

Definition

The determinant is a map:

det:  En×n→EA↦det(A)=∑p∈Snsign(p)⋅∏i=1naip(i)\begin{aligned} \text{det}: \; \mathbb{E}^{n \times n} &\to \mathbb{E}\\ A &\mapsto \text{det}(A) = \sum_{p \in S_n} \text{sign}(p) \cdot \prod_{i=1}^n a_{ip(i)} \end{aligned}
Remark

In the definition above we sum over n!n! terms.

Remark Tricks for computing determinants
  • 1×11 \times 1 matrix: det(a11)=∣a11∣=a11\quad \text{det}(a_{11}) = |a_{11}| = a_{11}
  • 2×22 \times 2 matrix:
det(abcd)=∣abcd∣=ad−bc\text{det} \begin{pmatrix} a & b\\ c & d \end{pmatrix} = \begin{vmatrix} a & b\\ c & d \end{vmatrix} = ad-bc
  • 3×33 \times 3 matrix (rule of Sarrus):
det(abcdefghi)=∣abcdefghi∣=aei+bfg+cdh−gec−hfa−idb\text{det} \begin{pmatrix} a & b & c\\ d & e & f\\ g & h & i \end{pmatrix} = \begin{vmatrix} a & b & c\\ d & e & f\\ g & h & i \end{vmatrix} = aei + bfg + cdh - gec - hfa - idb

The rule of Sarrus uses the following pattern:

+++abcabdefdeghigh−−−\begin{array}{ccc:cc} + & + & + & & \\ a & b & c & a & b\\ d & e & f & d & e\\ g & h & i & g & h\\ - & - & - & & \end{array}
Remark

For an n×nn \times n matrix you can compute the determinant via the definition with permutations, but this is very inefficient (effort proportional to n!n!).

Satz

Let A~\widetilde{A} be the row echelon form of AA (i.e. A~\widetilde{A} is an upper/lower triangular matrix), computed from AA by Gaussian elimination. Let k∈N0k \in \mathbb{N}_0 be the number of row swaps performed:

⇒det(A)=(−1)k⋅det(A~)=(−1)k∏i=1nA~ii,where   ∏i=1nA~ii is the product of the diagonal entries.\begin{aligned} \Rightarrow \quad &\text{det}(A) = (-1)^k \cdot \text{det}(\widetilde{A}) = (-1)^k \prod_{i=1}^n \widetilde{A}_{ii},\\ &\text{where } \; \prod_{i=1}^n \widetilde{A}_{ii} \text{ is the product of the diagonal entries.} \end{aligned}
Satz

Laplace expansion

Let A∈En×nA \in \mathbb{E}^{n \times n} and Aij′∈E(n−1)×(n−1)A'_{ij} \in \mathbb{E}^{(n-1) \times (n-1)} the minor matrix without the ii-th row and jj-th column.

⇒Expansion along the i-th row:  det(A)=∑j=1n(−1)i+j⋅aij⋅det(Aij′)\Rightarrow \quad \text{Expansion along the } i\text{-th row: \hspace{0.5cm} det} (A) = \sum_{j=1}^n (-1)^{i+j} \cdot a_{ij} \cdot \text{det} (A'_{ij})⇒Expansion along the j-th column:  det(A)=∑i=1n(−1)i+j⋅aij⋅det(Aij′).\Rightarrow \quad \text{Expansion along the } j\text{-th column: \hspace{0.25cm} det} (A) = \sum_{i=1}^n (-1)^{i+j} \cdot a_{ij} \cdot \text{det} (A'_{ij}).
Example 2

Given:

A=(1203−10105)A = \begin{pmatrix} 1 & 2 & 0\\ 3 & -1 & 0\\ 1 & 0 & 5 \end{pmatrix}

Find: det(A)\text{det}(A)

Show solutionHide solution

(1) Sarrus:

det(A)=1⋅(−1)⋅5+2⋅0⋅1+0⋅3⋅0−1⋅(−1)⋅0−0⋅0⋅1−5⋅3⋅2=−5−5⋅3⋅2=−5−30=−35\begin{aligned} \text{det}(A) &= 1 \cdot (-1) \cdot 5 + 2 \cdot 0 \cdot 1 + 0 \cdot 3 \cdot 0 - 1 \cdot (-1) \cdot 0 - 0 \cdot 0 \cdot 1 - 5 \cdot 3 \cdot 2\\ &= -5 - 5 \cdot 3 \cdot 2\\ &= -5 -30\\ &= -35 \end{aligned}

(2) Gauss:

  • without row swap
(1203−10105)⇝(ii)−l21⋅(i)(1200−70105)\begin{pmatrix} 1 & 2 & 0\\ 3 & -1 & 0\\ 1 & 0 & 5 \end{pmatrix} \stackrel{(ii) - l_{21} \cdot (i)}{\leadsto} \begin{pmatrix} 1 & 2 & 0\\ 0 & -7 & 0\\ 1 & 0 & 5 \end{pmatrix}⇝(iii)−l31⋅(i)  (1200−700−25)⇝(iii)−l32⋅(ii)  (1200−70005)=:A~\begin{aligned} \stackrel{(iii) - l_{31} \cdot (i)}{\leadsto} \; & \begin{pmatrix} 1 & 2 & 0\\ 0 & -7 & 0\\ 0 & -2 & 5 \end{pmatrix}\\[1.5ex] \stackrel{(iii) - l_{32} \cdot (ii)}{\leadsto} \; & \begin{pmatrix} 1 & 2 & 0\\ 0 & -7 & 0\\ 0 & 0 & 5 \end{pmatrix} =: \widetilde{A} \end{aligned}⇒det(A)=det(A~)=1⋅(−7)⋅5=−35\begin{aligned} \Rightarrow \quad \text{det}(A) &= \text{det}(\widetilde{A})\\ &= 1 \cdot (-7) \cdot 5\\ &= -35 \end{aligned}
  • with row swap
(1203−10105)⇝row swap(1053−10120)⇝(ii)−l21⋅(i)(1050−1−15120)\begin{pmatrix} 1 & 2 & 0\\ 3 & -1 & 0\\ 1 & 0 & 5 \end{pmatrix} \stackrel{\text{row swap}}{\leadsto} \begin{pmatrix} 1 & 0 & 5\\ 3 & -1 & 0\\ 1 & 2 & 0 \end{pmatrix} \stackrel{(ii) - l_{21} \cdot (i)}{\leadsto} \begin{pmatrix} 1 & 0 & 5\\ 0 & -1 & -15\\ 1 & 2 & 0 \end{pmatrix}⇝(iii)−l31⋅(i)(1050−1−1502−5)⇝(iii)−l32⋅(ii)(1050−1−1500−35)=:A~\stackrel{(iii) - l_{31} \cdot (i)}{\leadsto} \begin{pmatrix} 1 & 0 & 5\\ 0 & -1 & -15\\ 0 & 2 & -5 \end{pmatrix} \stackrel{(iii) - l_{32} \cdot (ii)}{\leadsto} \begin{pmatrix} 1 & 0 & 5\\ 0 & -1 & -15\\ 0 & 0 & -35 \end{pmatrix} =: \widetilde{A}⇒det(A)=(−1)⋅det(A~)=(−1)⋅[1⋅(−1)⋅(−35)]=−35\begin{aligned} \Rightarrow \quad \text{det}(A) &= (-1) \cdot \text{det}(\widetilde{A})\\ &= (-1) \cdot [1 \cdot (-1) \cdot (-35)]\\ &= -35 \end{aligned}

(3) Laplace:

  1. Expansion along the last column (most efficient):
∣1203−10105∣=5⋅∣123−1∣=5((−1)⋅1−3⋅2)=5⋅(−7)=−35\begin{aligned} \begin{vmatrix} 1 & 2 & 0\\ 3 & -1 & 0\\ 1 & 0 & 5 \end{vmatrix} &= 5 \cdot \begin{vmatrix} 1 & 2\\ 3 & -1 \end{vmatrix}\\ &= 5((-1) \cdot 1 - 3 \cdot 2)\\ &= 5 \cdot (-7)\\ &= -35 \end{aligned}
  1. Expansion along the first row (for illustration only, as it is inefficient):
∣1203−10105∣=1⋅∣−1005∣−2⋅∣3015∣=1⋅(−1)⋅5−2⋅3⋅5=−5−30=−35\begin{aligned} \begin{vmatrix} 1 & 2 & 0\\ 3 & -1 & 0\\ 1 & 0 & 5 \end{vmatrix} &= 1 \cdot \begin{vmatrix} -1 & 0\\ 0 & 5 \end{vmatrix} - 2 \cdot \begin{vmatrix} 3 & 0\\ 1 & 5 \end{vmatrix}\\ &= 1 \cdot (-1) \cdot 5 - 2 \cdot 3 \cdot 5\\ &= -5 -30\\ &= -35 \end{aligned}
Satz Axiomatic approach, properties of the determinant

The map

det:En×n→EA↦det(A)\begin{aligned} \text{det}: \mathbb{E}^{n \times n} &\to \mathbb{E}\\ A &\mapsto \text{det}(A) \end{aligned}

is called the determinant if the following properties hold: Let A∈En×nA \in \mathbb{E}^{n \times n} be a square matrix, then:

(D1) det(𝟙)=1\text{det}(\text{𝟙}) = 1

(D2) If AA has two equal or linearly dependent rows/columns, then

det(A)=0\text{det}(A)=0

(D3) Linearity in every row/column (also called nn-linearity in the literature)

det(v1,...,λvi+w,...,vn)=λdet(v1,...,vi,...,vn)+det(v1,...,w,...,vn)\text{det}(v_1, ..., \lambda v_i + w, ..., v_n) = \lambda \text{det}(v_1, ..., v_i, ..., v_n) + \text{det}(v_1, ..., w, ..., v_n)

The determinant has the following further properties, which can be derived from the first three:

(D4) det(λA)=λndet(A)\text{det}(\lambda A) = \lambda^n \text{det}(A) for all λ∈E\lambda \in \mathbb{E}

(D5) If a row/column is zero, then:

det(A)=0\text{det}(A)=0

(D6) If you swap two rows/columns of AA, the sign of det(A)\text{det}(A) changes:

det(v1,...,vi,...,vj,...,vn)=−det(v1,...,vj,...,vi,...,vn)\text{det}(v_1, ..., v_i, ..., v_j, ..., v_n) = - \text{det}(v_1, ..., v_j, ..., v_i, ..., v_n)

(D7) If BB arises from AA by adding λ\lambda times (λ≠0\lambda \neq 0) the ii-th row/column to the jj-th, then:

det(A)=det(B)\text{det}(A) = \text{det}(B)

(D8) If AA is an upper/lower triangular matrix, then:

det(A)=∏i=1naii\text{det}(A) = \prod_{i=1}^n a_{ii}

(D9) det(AB)=det(A)det(B)\text{det}(AB) = \text{det}(A)\text{det}(B)

(D10) det(A‾)=det(A)‾\text{det}(\overline{A}) = \overline{\text{det}(A)}

(D11) det(A−1)=1det(A)\text{det}(A^{-1}) = \frac{1}{\text{det}(A)}

(D12) det(AT)=det(A)\text{det}(A^T) = \text{det}(A)

(D13) If

A=(A1A20A3)then:det(A)=det(A1)⋅det(A3)A = \begin{pmatrix} A_1 & A_2\\ 0 & A_3 \end{pmatrix} \quad \text{then:} \quad \text{det}(A) = \text{det}(A_1) \cdot \text{det}(A_3)

and analogously:

det(B1∗⋯∗0⋱⋱⋮⋮⋱⋱∗0⋯0Bn)=det(B1)⋅...⋅det(Bn)\text{det} \begin{pmatrix} B_1 & * & \cdots & *\\ 0 & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & *\\ 0 & \cdots & 0 & B_n \end{pmatrix} = \text{det}(B_1) \cdot ... \cdot \text{det}(B_n)

(D14) det(A)=∏i=1nλi\text{det}(A) = \prod \limits_{i=1}^n \lambda_i, where λi\lambda_i is an eigenvalue of AA.

(D15) The definition of the determinant is basis-invariant:

det(B)=det(S−1BS)=1det(S)⋅det(B)⋅det(S)\text{det}(B) = \text{det}(S^{-1} B S) = \frac{1}{\text{det}(S)} \cdot \text{det}(B) \cdot \text{det}(S)

(D16) Orthogonal/unitary matrices AA have:

Orthogonal AA:

det(A)=±1,because    det(AAT)=det(A)det(AT)=det(A)det(A)=det(A)2=!det(𝟙)=1\begin{aligned} \text{det}(A) &= \pm 1,\\ \text{because} \;\; \text{det}(AA^T) &= \text{det}(A) \text{det}(A^T)\\ &= \text{det}(A) \text{det}(A)\\ &= \text{det}(A)^2\\ &\stackrel{!}{=} \text{det}(\text{𝟙})=1 \end{aligned}

Unitary AA:

∣det(A)∣=1,because    det(AAH)=det(A)det(A‾T)=det(A)det(A)‾=∣det(A)∣2=!det(𝟙)=1\begin{aligned} |\text{det}(A)| &= 1,\\ \text{because} \;\; \text{det}(AA^H) &= \text{det}(A) \text{det}(\overline{A}^T)\\ &= \text{det}(A) \overline{\text{det}(A)}\\ &= |\text{det}(A)|^2\\ &\stackrel{!}{=} \text{det}(\text{𝟙})=1 \end{aligned}

(D17) For Hermitian matrices (AH=A)(A^H=A) we have:

det(A)∈R,because  det(AH)=det(A‾T)=det(A‾)=det(A)‾=!det(A)\begin{aligned} \text{det}(A) \in \mathbb{R},\\ \text{because} \,\, \text{det}(A^H) &= \text{det}(\overline{A}^T)\\ &= \text{det}(\overline{A})\\ &= \overline{\text{det}(A)}\\ &\stackrel{!}{=} \text{det}(A) \end{aligned}
Satz
  • det(A)=0⇔A\text{det}(A) = 0 \Leftrightarrow A not invertible ⇔\Leftrightarrow rank(A)<n(A) < n
  • Ax=bAx = b uniquely solvable ⇔det(A)≠0\Leftrightarrow \text{det}(A) \neq 0.
Definition

For each element akla_{kl} of an n×nn \times n matrix AA, define the (n−1)×(n−1)(n-1) \times (n-1) submatrix A[k,l]A_{[k,l]} by deleting row kk and column ll of AA. The cofactor κkl\kappa_{kl} of akla_{kl} is then the number:

κkl:=(−1)k+l det(A[k,l]).\kappa_{kl} := (-1)^{k+l} \text{ det}\left(A_{[k,l]} \right).

Eigenvalues and Eigenvectors

In this section let VV be a vector space over E\mathbb{E}, dim(V)=n<∞(V)=n<\infty, A∈En×nA \in \mathbb{E}^{n \times n}.

Definition
  • λ∈E\lambda \in \mathbb{E} is called an eigenvalue of A⇔∃v∈V∖{0}:Av=λvA \quad \Leftrightarrow \quad \exists v \in V \setminus \{0\}: \quad Av=\lambda v.
  • v∈V∖{0}v \in V \setminus \{0\} is then called an eigenvector of AA for the eigenvalue λ\lambda.
  • Eλ(A)={v∈V∣Av=λv}E_\lambda(A) = \{v \in V | Av=\lambda v\} is called the eigenspace of AA for the eigenvalue λ\lambda.
  • σ(A):={λ  ∣  λ eigenvalues of A}\sigma(A) := \{\lambda\; |\; \lambda \text{ eigenvalues of } A \} is called the spectrum of AA.
Remark

Eλ(A)=E_\lambda(A)= ker(A−λ𝟙)(A-\lambda \text{𝟙}) is a non-trivial subspace of VV, i.e.:

{0}⊊Eλ(A)(strictly larger than just the zero space)\{0\} \subsetneq E_\lambda(A) \quad \text{(strictly larger than just the zero space)}
Remark

This definition carries over analogously to a linear map F:V→VF: V \to 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.\begin{aligned} &\lambda \text{ is an eigenvalue of } F, \; v \text{ is an eigenvector of } F\\ \Leftrightarrow \quad &\lambda \text{ is an eigenvalue of } A, \; v \text{ is an eigenvector of } A,\\ &\text{where } A \text{ denotes the matrix of } F. \end{aligned}
Remark Derivation of the characteristic polynomial χ_A

Consider

Av=λv⇔Av−λv=0⇔(A−λ𝟙)v=0(1)\begin{aligned} Av=\lambda v \quad &\Leftrightarrow \quad Av - \lambda v = 0\\ & \Leftrightarrow \quad (A- \lambda \text{𝟙})v = 0 \qquad (1) \end{aligned}

v=0v=0 solves (1)(1), but v=0v=0 is not allowed as an eigenvector. We require more solutions, i.e. ∞\infty many solutions (since a linear system always has 0,10,1 or ∞\infty many solutions). By the theorem from the review, we can achieve this by setting det(A−λ𝟙)=!0(A-\lambda \text{𝟙}) \stackrel{!}{=}0, because

det(A−λ𝟙)=0⇔SatzA−λ𝟙 singular⇒(A−λ𝟙)v=0 has ∞ many solutions, since v=0 is not allowed.\begin{aligned} \text{det}(A-\lambda \text{𝟙})=0 \quad &\stackrel{\text{Satz}}{\Leftrightarrow} \quad A-\lambda \text{𝟙} \text{ singular}\\ &\Rightarrow \quad (A- \lambda \text{𝟙})v = 0 \text{ has } \infty \text{ many solutions, since } v=0 \text{ is not allowed.} \end{aligned}
Definition

χA(λ)=\chi_A(\lambda) = det(A−λ𝟙)(A-\lambda \text{𝟙}) is called the characteristic polynomial.

Remark
  • χA(λ)\chi_A(\lambda) has degree nn
  • λ\lambda is an eigenvalue of AA ⇔λ\Leftrightarrow \lambda is a root of the characteristic polynomial χA(λ)\chi_A(\lambda).
Remark Quadratic formula (learn by heart)
ax2+bx+c=0⇒x1,2=−b±b2−4ac2a\begin{aligned} ax^2 + bx + c &= 0\\ \Rightarrow \quad x_{1,2} &= \frac{-b \pm \sqrt{b^2 -4ac}}{2a} \end{aligned}
Remark Computing eigenvalues and eigenvectors

Given: A∈En×nA \in \mathbb{E}^{n \times n} (if a linear map F:V→VF: V \to V is given, first find its matrix AA) Find: σ(A)\sigma(A) (i.e. ∀\forall eigenvalues of AA), Eλ(A)E_\lambda(A) with ∀λ∈σ(A)\forall \lambda \in \sigma(A)

1) Compute χA(λ)=\chi_A(\lambda) = det(A−λ𝟙)(A-\lambda \text{𝟙})

2) Set χA(λ)=!0\chi_A(\lambda) \stackrel{!}{=} 0:

⇒n roots λ1,...,λn⇒σ(A)={λ1,...,λn}\begin{aligned} &\Rightarrow n \text{ roots } \lambda_1, ..., \lambda_n\\ &\Rightarrow \sigma(A) = \{\lambda_1, ..., \lambda_n \} \end{aligned}

Remark. λ1,...,λn\lambda_1, ..., \lambda_n are not necessarily distinct; they are counted with multiplicity.

3) For each distinct eigenvalue λk\lambda_k, determine the basis of Eλk(A)=E_{\lambda_k}(A) = ker(A−λk𝟙)(A-\lambda_k \text{𝟙}) using Gaussian elimination.

4) The set of eigenvectors is

⋃k(Eλk(A)∖{0})\bigcup_k \left( E_{\lambda_k}(A) \setminus \{0\} \right)

(We take the union of all eigenspaces minus the zero vector)

Example 3

Given:

A=(123432005)A= \begin{pmatrix} 1 & 2 & 3\\ 4 & 3 & 2\\ 0 & 0 & 5 \end{pmatrix}

Find: eigenvalues, eigenvectors of AA

Show solutionHide solution

1)

χA(λ)=det(A−λ𝟙)=det((1−λ)234(3−λ)200(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)\begin{aligned} \chi_A(\lambda) &= \text{det}(A-\lambda \text{𝟙})\\ &= \text{det} \begin{pmatrix} (1-\lambda) & 2 & 3\\ 4 & (3-\lambda) & 2\\ 0 & 0 & (5-\lambda) \end{pmatrix}\\ &= (1-\lambda)(3-\lambda)(5-\lambda) - (5-\lambda)\cdot 4 \cdot 2\\ &= (5-\lambda)[(1-\lambda)(3-\lambda) - 4 \cdot 2]\\ &= (5-\lambda)[3-3\lambda-\lambda+\lambda^2 - 8]\\ &= (5-\lambda)[\lambda^2-4\lambda-5]\\ &= (5-\lambda)(\lambda-5)(\lambda+1) \quad \text{(if needed, using the quadratic formula)}\\ &= -(\lambda-5)(\lambda-5)(\lambda+1)\\ &= -(\lambda-5)^2(\lambda+1) \end{aligned}

2)

χA(λ)=!0⇔−(λ−5)2(λ+1)=0⇒λ1=λ2=5(later: the algebraic multiplicity of 5 is 2)λ3=−1⇒σ(A)={5,−1}\begin{aligned} \chi_A(\lambda) &\stackrel{!}{=} 0\\ \Leftrightarrow \quad -(\lambda-5)^2(\lambda+1) &= 0\\ \Rightarrow \qquad \lambda_1 &= \lambda_2 = 5 \qquad \text{(later: the algebraic multiplicity of 5 is 2)}\\ \lambda_3 &= -1\\ \Rightarrow \qquad \sigma(A) &= \{5,-1\} \end{aligned}

3)

  • λ1=λ2=5\lambda_1 = \lambda_2 = 5:
E5(A)=ker(A−5⋅𝟙)=ker(−4234−22000)E_5(A) = \text{ker}(A - 5 \cdot \text{𝟙}) = \text{ker} \begin{pmatrix} -4 & 2 & 3\\ 4 & -2 & 2\\ 0 & 0 & 0 \end{pmatrix}⇝Gaussker(2−10001000)=span{(120)}\stackrel{\text{Gauss}}{\leadsto} \text{ker} \begin{pmatrix} 2 & -1 & 0\\ 0 & 0 & 1\\ 0 & 0 & 0 \end{pmatrix} = \text{span} \left\{ \begin{pmatrix} 1\\ 2\\ 0 \end{pmatrix} \right\}
  • λ3=−1\lambda_3 = -1:
E−1(A)=ker(A−(−1)⋅𝟙)=ker(223442006)E_{-1}(A) = \text{ker}(A - (-1) \cdot \text{𝟙}) = \text{ker} \begin{pmatrix} 2 & 2 & 3\\ 4 & 4 & 2\\ 0 & 0 & 6 \end{pmatrix}⇝Gaussker(110001000)=span{(1−10)}\stackrel{\text{Gauss}}{\leadsto} \text{ker} \begin{pmatrix} 1 & 1 & 0\\ 0 & 0 & 1\\ 0 & 0 & 0 \end{pmatrix} = \text{span} \left\{ \begin{pmatrix} 1\\ -1\\ 0 \end{pmatrix} \right\}

4) Set of eigenvectors:

span{(120),(1−10)}∖{(000)}\text{span} \left\{ \begin{pmatrix} 1\\ 2\\ 0 \end{pmatrix}, \begin{pmatrix} 1\\ -1\\ 0 \end{pmatrix} \right\} \setminus \left\{ \begin{pmatrix} 0\\ 0\\ 0 \end{pmatrix} \right\}
Remark

It would be mathematically imprecise to say in example 3: "The eigenvectors are (1,2,0)T(1,2,0)^T and (1,−1,0)T(1,-1,0)^T". Because there are ∞\infty many eigenvectors. For example, let vv be an eigenvector of AA for the eigenvalue λ\lambda, i.e. Av=λvAv = \lambda v ⇒c⋅v\Rightarrow c \cdot v is an eigenvector of AA for λ\lambda for all c∈E∖{0}c \in \mathbb{E} \setminus \{0\}, since A(cv)=λ(cv)A(cv) = \lambda (cv) also holds. Usually it is still enough to take one basis vector v∈Eλ(A)∖{0}v \in E_\lambda(A) \setminus \{0\} as a "representative eigenvector".

Spectral Decomposition, Diagonalisability

Definition

Let λ\lambda be an eigenvalue of A∈En×nA \in \mathbb{E}^{n \times n}.

  • Algebraic multiplicity of λ\lambda:
aλ:="multiplicity of λ as a root of χA(λ)"a_\lambda := \text{"multiplicity of } \lambda \text{ as a root of } \chi_A(\lambda) \text{"}
  • Geometric multiplicity:
gλ:=dim(Eλ(A))=dim(ker(A−λ𝟙))=n−rank(A−λ𝟙)\begin{aligned} g_\lambda &:= \text{dim}(E_\lambda(A))\\ &= \text{dim}(\text{ker}(A-\lambda \text{𝟙}))\\ &= n - \text{rank}(A-\lambda \text{𝟙}) \end{aligned}
Definition

AA is called diagonalisable (a spectral decomposition exists)

⇔∃V∈En×n,  Λ∈En×n, with V regular, Λ diagonal, such that A=VΛV−1\begin{aligned} \Leftrightarrow \quad &\exists V \in \mathbb{E}^{n \times n}, \; \Lambda \in \mathbb{E}^{n \times n}, \text{ with } V \text{ regular, } \Lambda \text{ diagonal, such that }\\ &A = V \Lambda V^{-1} \end{aligned}

One also says: "AA is similar to a diagonal matrix".

Satz

AA is diagonalisable ⇔\Leftrightarrow The eigenvectors of AA form a basis of VV ⇔\Leftrightarrow For all eigenvalues λ\lambda of AA we have gλ=aλg_\lambda = a_\lambda.

Remark

A diagonalisation is a change of basis with transformation matrices VV and V−1V^{-1}.

Satz

A similarity transformation preserves:

  • eigenvalues and their algebraic and geometric multiplicity
  • rank
  • determinant
  • trace
  • characteristic polynomial χA(t)\chi_A(t)
  • not the eigenvectors!
Remark Computing the diagonal matrix

Given: A∈En×nA \in \mathbb{E}^{n \times n} diagonalisable Find: V,Λ∈En×nV, \Lambda \in \mathbb{E}^{n \times n}

1) Find the eigenvalues λ1,...,λn\lambda_1, ..., \lambda_n and the corresponding eigenvectors v1,...,vnv_1, ..., v_n of AA (where vi∈Eλi(A)v_i \in E_{\lambda_i}(A) and {vi}i=1n\{v_i\}_{i=1}^n linearly independent).

2) Define the diagonal matrix as follows:

Λ=(λ10⋯00⋱⋱⋮⋮⋱⋱00⋯0λn)with λ1≥...≥λn\Lambda = \begin{pmatrix} \lambda_1 & 0 & \cdots & 0\\ 0 & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & 0\\ 0 & \cdots & 0 & \lambda_n \end{pmatrix} \quad\quad \text{with } \lambda_1 \geq ... \geq \lambda_n

3) Write the eigenvectors vi∈Eλi(A)v_i \in E_{\lambda_i}(A) into a matrix:

V=(v1|⋯|vn)V = \left( v_1 \middle| \cdots \middle| v_n \right)

4) Check: A=?VΛV−1A \stackrel{?}{=} V \Lambda V^{-1}

Example 3 continued...

Let

A=(123432005) as in example 3 with χA(λ)=−(λ−5)2(λ+1)A= \begin{pmatrix} 1 & 2 & 3\\ 4 & 3 & 2\\ 0 & 0 & 5 \end{pmatrix} \qquad \text{ as in example 3 with } \chi_A(\lambda) = -(\lambda-5)^2(\lambda+1)

Find: algebraic and geometric multiplicity

Show solutionHide solution
  • Algebraic multiplicity:
λ1=5 with a5=2andλ2=−1 with a−1=1\lambda_1 = 5 \text{ with } a_5 = 2 \quad \text{and} \quad \lambda_2 = -1 \text{ with } a_{-1} = 1
  • Geometric multiplicity:
g5= dim(E5(A))=1≠a5=2g−1= dim(E−1(A))=1=a−1=1\begin{aligned} g_5 &= \text{ dim}(E_5(A)) = 1 \quad \neq a_5 = 2\\ g_{-1} &= \text{ dim}(E_{-1}(A)) = 1 \quad = a_{-1} = 1 \end{aligned}

Since g5≠a5⇒Ag_5 \neq a_5 \Rightarrow A is not diagonalisable.

Example 4

Given:

A=(0−11−3−23−2−23)A= \begin{pmatrix} 0 & -1 & 1\\ -3 & -2 & 3\\ -2 & -2 & 3 \end{pmatrix}

Find: the spectral decomposition.

Show solutionHide solution

1)

(i)

χA(λ)=det(A−λ𝟙)=∣−λ−11−3−2−λ3−2−23−λ∣=−λ(−2−λ)(3−λ)+(−1)⋅3⋅(−2)+1⋅(−3)⋅(−2)        −(−2)⋅(−2−λ)⋅1−(−2)⋅3⋅(−λ)−(3−λ)⋅(−3)⋅(−1)=6λ+3λ2−2λ2−λ3+6+6−4−2λ−6λ−9+3λ=−λ3+λ2+λ−1\begin{aligned} \chi_A(\lambda) &= \text{det}(A-\lambda \text{𝟙})\\ &= \begin{vmatrix} -\lambda & -1 & 1\\ -3 & -2-\lambda & 3\\ -2 & -2 & 3-\lambda \end{vmatrix}\\ &= -\lambda(-2-\lambda)(3-\lambda) + (-1) \cdot 3 \cdot (-2) + 1 \cdot (-3) \cdot (-2)\\ &\;\;\;\;- (-2) \cdot (-2-\lambda) \cdot 1 - (-2) \cdot 3 \cdot (-\lambda) - (3-\lambda) \cdot (-3) \cdot (-1)\\ &= 6\lambda + 3\lambda^2 -2\lambda^2 -\lambda^3 + 6 + 6 - 4 -2\lambda -6\lambda -9 +3\lambda\\ &= -\lambda^3 +\lambda^2 +\lambda-1 \end{aligned}

Remark. Here you need a trick: guess a root (try 1,−1,2,−21,-1,2,-2, etc.) and then perform polynomial long division.

λ1=1\lambda_1 = 1 is a root:

−t3+t2+t−1:  t−1=−t2+1−(−t3‾+t2)‾0+t−1−(t‾−1)‾0\begin{array}{rrrrl} -t^3 & +t^2 & +t & -1 & : \; t-1 = -t^2+1\\ \underline{-(-t^3} & \underline{+t^2)} & & & \\ & 0 & +t & -1 & \\ & & \underline{-(t} & \underline{-1)} & \\ & & & 0 & \end{array}⇒χA(λ)=(λ−1)(1−λ2)=(λ−1)(1−λ)(1+λ)=−(λ−1)(λ−1)(λ+1)=−(λ−1)2(λ+1)\begin{aligned} \Rightarrow \quad \chi_A(\lambda) &= (\lambda-1)(1-\lambda^2)\\ &= (\lambda-1)(1-\lambda)(1+\lambda)\\ &= -(\lambda-1)(\lambda-1)(\lambda+1)\\ &= -(\lambda-1)^2(\lambda+1) \end{aligned}

(ii)

χA(λ)=!0⇔0=−(λ−1)2(λ+1)⇒λ1=λ2=1,    a1=2λ3=−1,    a−1=1⇒σ(A)={−1,1}\begin{aligned} \chi_A(\lambda) &\stackrel{!}{=} 0\\ \Leftrightarrow 0 &= -(\lambda-1)^2(\lambda+1)\\ \Rightarrow \quad \lambda_1 &= \lambda_2 = 1, \;\; a_1 = 2\\ \lambda_3 &= -1, \;\; a_{-1} = 1\\ \Rightarrow \quad \sigma(A) &= \{-1,1\} \end{aligned}

(iii)

  • λ1=λ2=1\lambda_1=\lambda_2 = 1:
E1(A)=ker(A−𝟙)=ker(−1−11−3−33−2−22)⇝Gaussker(−1−11000000)=span{(1−10),(101)}⇒g1=2\begin{aligned} E_1(A) &= \text{ker}(A-\text{𝟙})\\ &= \text{ker} \begin{pmatrix} -1 & -1 & 1\\ -3 & -3 & 3\\ -2 & -2 & 2 \end{pmatrix}\\ &\stackrel{\text{Gauss}}{\leadsto} \text{ker} \begin{pmatrix} -1 & -1 & 1\\ 0 & 0 & 0\\ 0 & 0 & 0 \end{pmatrix} = \text{span}\left\{ \begin{pmatrix} 1\\ -1\\ 0 \end{pmatrix}, \begin{pmatrix} 1\\ 0\\ 1 \end{pmatrix} \right\}\\ \Rightarrow \quad g_1 &= 2 \end{aligned}
  • λ3=−1\lambda_3 = -1:
E−1(A)=ker(A+𝟙)=ker(1−11−3−13−2−24)⇝Gaussker(1−110−460−46)⇝Gaussker(1−1102−3000)=span{(132)}⇒g−1=1\begin{aligned} E_{-1}(A) &= \text{ker}(A+\text{𝟙})\\ &= \text{ker} \begin{pmatrix} 1 & -1 & 1\\ -3 & -1 & 3\\ -2 & -2 & 4 \end{pmatrix}\\ &\stackrel{\text{Gauss}}{\leadsto} \text{ker} \begin{pmatrix} 1 & -1 & 1\\ 0 & -4 & 6\\ 0 & -4 & 6 \end{pmatrix}\\ &\stackrel{\text{Gauss}}{\leadsto} \text{ker} \begin{pmatrix} 1 & -1 & 1\\ 0 & 2 & -3\\ 0 & 0 & 0 \end{pmatrix} = \text{span}\left\{ \begin{pmatrix} 1\\ 3\\ 2 \end{pmatrix} \right\}\\ \Rightarrow \quad g_{-1} &= 1 \end{aligned}

⟹a1=g1\Longrightarrow \quad \quad a_1=g_1 and a−1=g−1⇒Aa_{-1}=g_{-1} \Rightarrow A is diagonalisable.

(iv) Set of eigenvectors:

span{(1−10),(101),(132)}\text{span} \left\{ \begin{pmatrix} 1\\ -1\\ 0 \end{pmatrix}, \begin{pmatrix} 1\\ 0\\ 1 \end{pmatrix}, \begin{pmatrix} 1\\ 3\\ 2 \end{pmatrix} \right\}

2)

Λ=(10001000−1)\Lambda = \begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & -1 \end{pmatrix}

3)

V=(111−103012),V−1=(3212−32−1−121212−12),V = \begin{pmatrix} 1 & 1 & 1\\ -1 & 0 & 3\\ 0 & 1 & 2 \end{pmatrix}, \quad V^{-1} = \begin{pmatrix} \frac{3}{2} & \frac{1}{2} & -\frac{3}{2}\\ -1 & -1 & 2\\ \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} \end{pmatrix},

where you compute the inverse V−1V^{-1} with the usual recipe.

4) Check: A=VΛV−1✓\quad\quad A= V \Lambda V^{-1} \checkmark

Remark

Complex roots of the characteristic polynomial with real coefficients always occur in pairs: if λ∈C\lambda \in \mathbb{C} is a root, then so is λ‾\overline{\lambda}. Hence an orthogonal matrix of odd dimension must have at least one real eigenvalue ±1\pm1.

Definition

Definition.

The sum of the diagonal elements of A∈En×nA \in \mathbb{E}^{n \times n} is called the trace of AA:

tr(A):=∑i=1naii=a11+...+ann.\text{tr}(A) := \sum_{i=1}^n a_{ii} = a_{11} + ... + a_{nn}.
Lemma 9.6

A (square) matrix AA is singular if and only if it has 00 as an eigenvalue:

A singular⇔0∈σ(A).A \text{ singular} \quad \Leftrightarrow \quad 0 \in \sigma(A).
Satz 9.11

Eigenvectors for distinct eigenvalues are linearly independent.

Corollary 9.12

If the n eigenvalues of F:V→VF : V \to V (with n=dim(V)n = \text{dim}(V)) are distinct, then there is a basis of eigenvectors and the corresponding matrix is diagonal.

Satz 9.15

If A∈Cn×nA \in \mathbb{C}^{n \times n} is Hermitian, then:

  1. All eigenvalues λ1,...,λn\lambda_1, ..., \lambda_n are real.
  2. The eigenvectors for distinct eigenvalues are pairwise orthogonal in Cn\mathbb{C}^n.
  3. There is an orthonormal basis of Cn\mathbb{C}^n consisting of eigenvectors u1,...,unu_1, ..., u_n of AA.
  4. For the unitary matrix U:=(u1,...,un)U:=(u_1, ..., u_n) we have: UHAU=Λ=diag(λ1,...,λn).\displaystyle U^H A U = \Lambda = diag(\lambda_1, ..., \lambda_n).