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

Least Squares, Permutations and Determinants

Method of least squares, normal equations, permutation, symmetric group, determinant, Kirchhoff's theorem

SB
Steven Battilana Quant · ex-ETH

Review: Orthogonal and Unitary Matrices (II)

Definition

The matrix A∈En×nA \in \mathbb{E}^{n \times n} is orthogonal/unitary if and only if the rows of AA are pairwise orthonormal to each other (with respect to the standard inner product) and the columns of AA are pairwise orthonormal to each other (with respect to the standard inner product).

Definition

A complex n×nn \times n matrix AA is called unitary if AHA=AAH=𝟙A^HA = AA^H = \text{𝟙}. A real n×nn \times n matrix AA is called orthogonal if ATA=AAT=𝟙A^TA = AA^T = \text{𝟙}.

Remark

The notion of orthogonal/unitary matrices A∈En×nA \in \mathbb{E}^{n \times n} is independent of the inner product (by definition via the Euclidean inner product, i.e. AAH=AHA=𝟙AA^H = A^HA = \text{𝟙}). The notion of orthogonal vectors, on the other hand, depends on the inner product ⟨⋅,⋅⟩V\langle \cdot, \cdot \rangle_V under consideration.

Remark

Warning: this remark is a thought experiment and serves to deepen the understanding you have already gained. If you extended the definition of an orthogonal/unitary matrix to a general inner product ⟨⋅,⋅⟩M\langle \cdot, \cdot \rangle_M, you would get the following:

AMAH=AHMA=𝟙AMA^H = A^HMA = \text{𝟙}

The matrix MM of the MM inner product is computed as follows, if the inner product is already given:

M=(⟨e1,e1⟩M⟨e1,e2⟩M⋯⟨e1,en⟩M⟨e2,e1⟩M⟨e2,e2⟩M⋱⋮⋮⋱⋱⟨en−1,en⟩M⟨en,e1⟩M⋯⟨en,en−1⟩M⟨en,en⟩M)M = \begin{pmatrix} \langle e_1, e_1 \rangle_M & \langle e_1, e_2 \rangle_M & \cdots & \langle e_1, e_n \rangle_M\\ \langle e_2, e_1 \rangle_M & \langle e_2, e_2 \rangle_M & \ddots & \vdots\\ \vdots & \ddots & \ddots & \langle e_{n-1}, e_n \rangle_M\\ \langle e_n, e_1 \rangle_M & \cdots & \langle e_n, e_{n-1} \rangle_M & \langle e_n, e_n \rangle_M \end{pmatrix}
Remark

For the standard inner product you would then get the following:

A𝟙AH=AH𝟙A=𝟙⇔AAH=AHA=𝟙A\text{𝟙}A^H = A^H\text{𝟙}A = \text{𝟙} \Leftrightarrow AA^H = A^HA = \text{𝟙}
Example 1

Consider the MM inner product for symmetric positive definite M∈Rn×nM \in \mathbb{R}^{n \times n}:

⟨v,w⟩M:=vTMw\langle v,w \rangle_M := v^T M w

Then vv is perpendicular to ww with respect to ⟨⋅,⋅⟩M⇔vTMw=0\langle \cdot, \cdot \rangle_M \Leftrightarrow v^T M w = 0.

Example 2

Given: ONBs (with respect to the standard inner product) A, B\mathcal{A},\, \mathcal{B} with

A={(10),(01)},B={(3545),(−4535)}.\mathcal{A} = \left \{ \begin{pmatrix} 1\\ 0 \end{pmatrix}, \begin{pmatrix} 0\\ 1 \end{pmatrix} \right \}, \quad \mathcal{B} = \left \{ \begin{pmatrix} \frac{3}{5}\\ \frac{4}{5} \end{pmatrix}, \begin{pmatrix} -\frac{4}{5}\\ \frac{3}{5} \end{pmatrix} \right \}.

Wanted: TBAT_B^A and TABT_A^B

Show solutionHide solution TAB=(35−454535) is orthogonal with (TAB)−1=(TAB)TT_A^B = \begin{pmatrix} \frac{3}{5} & -\frac{4}{5}\\ \frac{4}{5} & \frac{3}{5} \end{pmatrix} \text{ is orthogonal with } (T_A^B)^{-1} = (T_A^B)^TTBA=(TAB)−1=(TAB)T=(3545−4535)T_B^A = (T_A^B)^{-1} = (T_A^B)^T = \begin{pmatrix} \frac{3}{5} & \frac{4}{5}\\ -\frac{4}{5} & \frac{3}{5} \end{pmatrix}

⇒\Rightarrow For orthogonal/unitary matrices it is easy to determine the inverse, i.e. once you have TABT_A^B you immediately get TBAT_B^A.

Least Squares Method

Remark idea

For A∈Em×n,  m>nA \in \mathbb{E}^{m \times n}, \,\, m>n we consider the overdetermined linear system Ax=yAx=y. Such systems often have no (exact) solution, so you solve them with approximation methods, which introduces an error. The least squares method (sometimes also called linear regression) tries to minimise this error. The residual vector (the residual, the error) r:=y−Axr := y - Ax should have minimal Euclidean norm, i.e. we look for x∈Rnx \in \mathbb{R}^n such that

∥r∥22=∑k=1m∣rk∣2=∑k=1m∣yk−∑l=1naklxl∣2\left\lVert r \right\rVert_2^2 = \sum_{k=1}^m |r_k|^2 = \sum_{k=1}^m | y_k -\sum_{l=1}^n a_{kl} x_l |^2

is minimal.

Remark

The least squares method can be extended to general norms. (Example: HS17 S10A2)

Remark

For A∈Em×n,  m>nA \in \mathbb{E}^{m \times n}, \,\, m>n consider the overdetermined linear system

Ax=!yAx\stackrel{!}{=}y

Least squares method: find x∈Enx \in \mathbb{E}^n such that the residual r=y−Axr = y - Ax has minimal norm. Formally:

arg min⁡x∈En∥y−Ax∥2\operatorname*{arg\,min} \limits_{x \in \mathbb{E}^n} \left\lVert y - Ax \right\rVert_2

Approaches:

  1. Normal equations
  2. QR decomposition

Normal Equations

Lemma 7.3

If the columns of an A∈Em×nA \in \mathbb{E}^{m \times n} matrix are linearly independent, i.e. rank(A)=n(≤m)(A) = n (\leq m), then AHAA^HA is regular.

Satz 7.4

The orthogonal projection PA:Em→P_A : \mathbb{E}^m \to Im(A)⊂Em(A) \subset \mathbb{E}^m onto the column space Im(A)(A) of an A∈Em×nA \in \mathbb{E}^{m \times n} matrix with rank n(≤m)n (\leq m) is given by:

PA:=A(AHA)−1AH.P_A := A(A^HA)^{-1} A^H.
Satz 7.6

For an orthogonal projection P∈En×nP \in \mathbb{E}^{n \times n}:

∥y−Py∥2=min⁡z∈Im(P)∥y−z∥2,∀y∈En\left\lVert y - Py \right\rVert_2 = \min \limits_{z \in \text{Im}(P)} \left\lVert y - z \right\rVert_2, \quad \forall y \in \mathbb{E}^n
Remark

Assume the columns of A∈Em×nA \in \mathbb{E}^{m \times n} are linearly independent, so ker(A)={0}(A)=\{0\} holds and AHAA^HA is regular by Lemma 7.3. By Satz 7.6 we know that ∥r∥\left\lVert r \right\rVert is minimal if:

Ax=PAy⟹Satz 7.4Ax=A(AHA)−1AHy⟹ker(A)={0}x=(AHA)−1AHy⇒AHAx=AHynormal equations\begin{aligned} Ax = P_Ay &\stackrel{\text{Satz 7.4}}{\Longrightarrow} Ax = A(A^HA)^{-1} A^Hy\\ &\stackrel{\text{ker}(A)=\{0\}}{\Longrightarrow} x = (A^HA)^{-1}A^Hy\\ &\Rightarrow A^HAx = A^Hy \quad \text{\textit{normal equations}} \end{aligned}
Definition pseudoinverse
A†:=(AHA)−1AH⇒A†A=(AHA)−1AHA=𝟙⟹BUTAA†=A(AHA)−1AH≠in general𝟙\begin{aligned} A^\dag &:= (A^HA)^{-1}A^H\\ &\Rightarrow A^\dag A = (A^HA)^{-1}A^HA = \text{𝟙}\\ &\stackrel{\text{BUT}}{\Longrightarrow} AA^\dag = A (A^HA)^{-1}A^H \stackrel{\text{in general}}{\neq} \text{𝟙} \end{aligned}
Satz 7.7

Let A∈Em×nA \in \mathbb{E}^{m \times n}, rank(A)=n≤m,  y∈Em(A) = n \leq m, \,\, y \in \mathbb{E}^m. Then the overdetermined system Ax=yAx = y has a uniquely determined solution xx in the least squares sense, i.e. xx with

∥y−Ax∥22=min⁡x~∈En∥y−Ax~∥22,x∈En(1)\left\lVert y - Ax \right\rVert_2^2 = \min \limits_{\widetilde{x} \in \mathbb{E}^n} \left\lVert y - A\widetilde{x} \right\rVert_2^2, \quad x \in \mathbb{E}^n \tag{1}

xx can be computed by solving the regular system of normal equations (remark after Satz 7.6). The residual vector r⊥r \perp Im(A)(A).

Example 3

Given:

A=(01132−2),⇒m=3>2=n,y=(224)A = \begin{pmatrix} 0 & 1\\ 1 & 3\\ 2 & -2 \end{pmatrix}, \quad \Rightarrow \quad m=3 > 2=n, \quad y = \begin{pmatrix} 2\\ 2\\ 4 \end{pmatrix}

Wanted: use the normal equations to determine x=(x1,x2)Tx = (x_1, x_2)^T such that ∥r∥22=∥y−Ax∥22\left\lVert r \right\rVert_2^2 = \left\lVert y - Ax \right\rVert_2^2 is minimal with respect to the standard inner product ⟨x,y⟩=xHy\langle x,y \rangle = x^Hy.

Show solutionHide solution Ax=y⇒ATAx=ATy⇔x=(ATA)−1ATy(∗)ATA=(01213−2)(01132−2)=(5−1−114)(ATA)−1=15⋅14−(−1)⋅(−1)(14115)=169(14115)ATy=(01213−2)(224)=(100)⟹(∗)x=169(14115)(100)=169(14010)\begin{aligned} Ax = y &\Rightarrow A^TAx = A^Ty\\ &\Leftrightarrow x = (A^TA)^{-1}A^Ty \quad (*)\\ A^TA &= \begin{pmatrix} 0 & 1 & 2\\ 1 & 3 & -2 \end{pmatrix} \begin{pmatrix} 0 & 1\\ 1 & 3\\ 2 & -2 \end{pmatrix} = \begin{pmatrix} 5 & -1\\ -1 & 14 \end{pmatrix}\\ (A^TA)^{-1} &= \frac{1}{5 \cdot 14 - (-1) \cdot (-1)} \begin{pmatrix} 14 & 1\\ 1 & 5 \end{pmatrix} = \frac{1}{69} \begin{pmatrix} 14 & 1\\ 1 & 5 \end{pmatrix}\\ A^Ty &= \begin{pmatrix} 0 & 1 & 2\\ 1 & 3 & -2 \end{pmatrix} \begin{pmatrix} 2\\ 2\\ 4 \end{pmatrix} = \begin{pmatrix} 10\\ 0 \end{pmatrix}\\ \stackrel{(*)}{\Longrightarrow} x &= \frac{1}{69} \begin{pmatrix} 14 & 1\\ 1 & 5 \end{pmatrix} \begin{pmatrix} 10\\ 0 \end{pmatrix} = \frac{1}{69} \begin{pmatrix} 140\\ 10 \end{pmatrix} \end{aligned}
Example 4

Given: fit the best possible line (i.e. the distance between point and line is minimal) through P1,P2,P3,P4P_1, P_2, P_3, P_4 where

P1=(0,6),  P2=(1,0),  P3=(2,0),  P4=(3,−4)P_1 = (0, 6), \,\, P_2 = (1, 0), \,\, P_3 = (2,0), \,\, P_4 = (3,-4)

Wanted: the equation of the line y=ax+b,y = ax + b, where a,b∈Ra,b \in \mathbb{R} are unknown parameters.

Show solutionHide solution Pi=(x,y)⇒{6=a⋅0+b0=a⋅1+b0=a⋅2+b−4=a⋅3+b⇔(01112131)⏟=A(ab)⏟=x=(600−4)⏟=yP_i = (x,y) \Rightarrow \begin{cases} 6 = a \cdot 0 + b\\ 0 = a \cdot 1 + b\\ 0 = a \cdot 2 + b\\ -4 = a \cdot 3 + b \end{cases} \quad \Leftrightarrow \quad \underbrace{ \begin{pmatrix} 0 & 1\\ 1 & 1\\ 2 & 1\\ 3 & 1 \end{pmatrix}}_{=A} \underbrace{ \begin{pmatrix} a\\ b \end{pmatrix}}_{=x} = \underbrace{ \begin{pmatrix} 6\\ 0\\ 0\\ -4 \end{pmatrix}}_{=y}Ax=y⇒ATAx=ATy⇔x=(ATA)−1ATy(∗)ATA=(01231111)(01112131)=(14664)(ATA)−1=114⋅4−6⋅6(4−6−614)=120(4−6−614)=110(2−3−37)ATy=(01231111)(600−4)=(−122)\begin{aligned} Ax = y &\Rightarrow A^TAx = A^Ty\\ &\Leftrightarrow x = (A^TA)^{-1}A^Ty \quad (*)\\ A^TA &= \begin{pmatrix} 0 & 1 & 2 & 3\\ 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1\\ 1 & 1\\ 2 & 1\\ 3 & 1 \end{pmatrix} = \begin{pmatrix} 14 & 6\\ 6 & 4 \end{pmatrix}\\ (A^TA)^{-1} &= \frac{1}{14 \cdot 4 - 6 \cdot 6} \begin{pmatrix} 4 & -6\\ -6 & 14 \end{pmatrix} = \frac{1}{20} \begin{pmatrix} 4 & -6\\ -6 & 14 \end{pmatrix} = \frac{1}{10} \begin{pmatrix} 2 & -3\\ -3 & 7 \end{pmatrix}\\ A^Ty &= \begin{pmatrix} 0 & 1 & 2 & 3\\ 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 6\\ 0\\ 0\\ -4 \end{pmatrix} = \begin{pmatrix} -12\\ 2 \end{pmatrix} \end{aligned}⟹(∗)x=(ATA)−1ATy=110(2−3−37)(−122)=15(2−3−37)(−61)=15(−1525)=(−35)⟹Line:  y=−3x+5\begin{aligned} \stackrel{(*)}{\Longrightarrow} x &= (A^TA)^{-1}A^Ty\\ &= \frac{1}{10} \begin{pmatrix} 2 & -3\\ -3 & 7 \end{pmatrix} \begin{pmatrix} -12\\ 2 \end{pmatrix}\\ &= \frac{1}{5} \begin{pmatrix} 2 & -3\\ -3 & 7 \end{pmatrix} \begin{pmatrix} -6\\ 1 \end{pmatrix}\\ &= \frac{1}{5} \begin{pmatrix} -15\\ 25 \end{pmatrix}\\ &= \begin{pmatrix} -3\\ 5 \end{pmatrix}\\ \Longrightarrow \quad \text{Line:} \,\, y &= -3x + 5 \end{aligned}
Remark normal equations vs. QR decomposition

Normal equations

  • Pro:
    • "nice" to compute by hand
    • AHAA^HA is Hermitian positive definite ⇒\Rightarrow can be exploited for the Cholesky decomposition
  • Con:
    • If AA is ill-conditioned, AHAA^HA is quadratically ill-conditioned. ⇒\Rightarrow Cholesky delivers useless results (rounding errors massively amplified, implementation unstable)

QR decomposition

  • Pro:
    • can be implemented in a numerically stable way (the method depends less on the condition)
    • The columns of QQ form an ONB of Im(A)(A) (the orthogonal projection onto Im(A)(A) is QQHQQ^H)
  • Con:
    • "ugly" to compute by hand (square roots)

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, 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 5

Given:

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

Wanted: the inversions of pp

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

p∈Snp \in S_n is called:

  • 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 (cost 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 with 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 submatrix 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 6

Given:

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

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

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 (in the literature also called nn-linearity)

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 every entry akla_{kl} of an n×nn \times n matrix AA, let the (n−1)×(n−1)(n-1) \times (n-1) submatrix A[k,l]A_{[k,l]} be defined 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).
Definition

The degree djd_j of the vertex jj is defined as follows:

dj:=∑i=1n(A)ij.d_j := \sum_{i=1}^n (A)_{ij}.
Satz Kirchhoff's theorem

Kirchhoff’s theorem states that the number of spanning trees of a graph equals the value of any cofactor of LL, where LL is defined as follows:

L:=D−Awith D=diag(d1,...,dn),    di=^ degree of the vertex iandA=^ adjacency matrix with (Aij)={1,if i is connected to j by an edge0, otherwise.\begin{aligned} L &:= D-A\\ &\text{with } \quad D = \text{diag}(d_1, ..., d_n), \;\; d_i \mathrel{\hat{=}} \text{ degree of the vertex } i\\ &\text{and} \quad A \mathrel{\hat{=}} \text{ adjacency matrix with } \left( A_{ij} \right) = \begin{cases} 1, &\text{if $i$ is connected to $j$ by an edge}\\ 0, &\text{ otherwise}. \end{cases} \end{aligned}