The matrix A∈En×n is orthogonal/unitary if and only if the rows of A are pairwise orthonormal to each other (with respect to the standard inner product) and the columns of A are pairwise orthonormal to each other (with respect to the standard inner product).
Definition
A complex n×n matrix A is called unitary if AHA=AAH=𝟙.
A real n×n matrix A is called orthogonal if ATA=AAT=𝟙.
Remark
The notion of orthogonal/unitary matrices A∈En×n is independent of the inner product (by definition via the Euclidean inner product, i.e. AAH=AHA=𝟙). The notion of orthogonal vectors, on the other hand, depends on the inner product ⟨⋅,⋅⟩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, you would get the following:
AMAH=AHMA=𝟙
The matrix M of the M inner product is computed as follows, if the inner product is already given:
For the standard inner product you would then get the following:
A𝟙AH=AH𝟙A=𝟙⇔AAH=AHA=𝟙
Example 1
Consider the M inner product for symmetric positive definite M∈Rn×n:
⟨v,w⟩M:=vTMw
Then v is perpendicular to w with respect to ⟨⋅,⋅⟩M⇔vTMw=0.
Example 2
Given: ONBs (with respect to the standard inner product) A,B with
A={(10),(01)},B={(5354),(−5453)}.
Wanted: TBA and TAB
Show solutionHide solutionTAB=(5354−5453) is orthogonal with (TAB)−1=(TAB)TTBA=(TAB)−1=(TAB)T=(53−545453)
⇒ For orthogonal/unitary matrices it is easy to determine the inverse, i.e. once you have TAB you immediately get TBA.
Least Squares Method
Remarkidea
For A∈Em×n,m>n we consider the overdetermined linear system Ax=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−Ax should have minimal Euclidean norm, i.e. we look for x∈Rn such that
∥r∥22=k=1∑m∣rk∣2=k=1∑m∣yk−l=1∑naklxl∣2
is minimal.
Remark
The least squares method can be extended to general norms. (Example: HS17 S10A2)
Remark
For A∈Em×n,m>n consider the overdetermined linear system
Ax=!y
Least squares method: find x∈En such that the residual r=y−Ax has minimal norm. Formally:
x∈Enargmin∥y−Ax∥2
Approaches:
Normal equations
QR decomposition
Normal Equations
Lemma 7.3
If the columns of an A∈Em×n matrix are linearly independent, i.e. rank(A)=n(≤m), then AHA is regular.
Satz 7.4
The orthogonal projection PA:Em→ Im(A)⊂Em onto the column space Im(A) of an A∈Em×n matrix with rank n(≤m) is given by:
PA:=A(AHA)−1AH.
Satz 7.6
For an orthogonal projection P∈En×n:
∥y−Py∥2=z∈Im(P)min∥y−z∥2,∀y∈En
Remark
Assume the columns of A∈Em×n are linearly independent, so ker(A)={0} holds and AHA is regular by Lemma 7.3. By Satz 7.6 we know that ∥r∥ is minimal if:
Let A∈Em×n, rank(A)=n≤m,y∈Em. Then the overdetermined system Ax=y has a uniquely determined solution x in the least squares sense, i.e. x with
∥y−Ax∥22=x∈Enmin∥y−Ax∥22,x∈En(1)
x can be computed by solving the regular system of normal equations (remark after Satz 7.6). The residual vector r⊥ Im(A).
Example 3
Given:
A=01213−2,⇒m=3>2=n,y=224
Wanted: use the normal equations to determine x=(x1,x2)T such that ∥r∥22=∥y−Ax∥22 is minimal with respect to the standard inner product ⟨x,y⟩=xHy.
Show solutionHide solutionAx=yATA(ATA)−1ATy⟹(∗)x⇒ATAx=ATy⇔x=(ATA)−1ATy(∗)=(01132−2)01213−2=(5−1−114)=5⋅14−(−1)⋅(−1)1(14115)=691(14115)=(01132−2)224=(100)=691(14115)(100)=691(14010)
Example 4
Given: fit the best possible line (i.e. the distance between point and line is minimal) through P1,P2,P3,P4 where
P1=(0,6),P2=(1,0),P3=(2,0),P4=(3,−4)
Wanted: the equation of the line y=ax+b, where a,b∈R are unknown parameters.
Show solutionHide solutionPi=(x,y)⇒⎩⎨⎧6=a⋅0+b0=a⋅1+b0=a⋅2+b−4=a⋅3+b⇔=A01231111=x(ab)==y600−4Ax=yATA(ATA)−1ATy⇒ATAx=ATy⇔x=(ATA)−1ATy(∗)=(01112131)01231111=(14664)=14⋅4−6⋅61(4−6−614)=201(4−6−614)=101(2−3−37)=(01112131)600−4=(−122)⟹(∗)x⟹Line:y=(ATA)−1ATy=101(2−3−37)(−122)=51(2−3−37)(−61)=51(−1525)=(−35)=−3x+5
Remarknormal equations vs. QR decomposition
Normal equations
Pro:
"nice" to compute by hand
AHA is Hermitian positive definite ⇒ can be exploited for the Cholesky decomposition
Con:
If A is ill-conditioned, AHA is quadratically ill-conditioned. ⇒ 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 Q form an ONB of Im(A) (the orthogonal projection onto Im(A) is QQH)
Con:
"ugly" to compute by hand (square roots)
Symmetric Group
Definition
A permutation is a bijective map:
p:{1,...,n}→{1,...,n}
Definition
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, every pair i,j∈{1,...,n} with
i<jbutp(i)>p(j),
is called an inversion of p.
Example 5
Given:
p=[122331]
Wanted: the inversions of p
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 (cost 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 with 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 submatrix 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′).
Example 6
Given:
A=1312−10005
Wanted: det(A)
Satzaxiomatic approach, properties of the determinant
The map
det:En×nA→E↦det(A)
is called the determinant if the following properties hold:
Let A∈En×n be a square matrix, then:
(D1)det(𝟙)=1
(D2) If A has two equal or linearly dependent rows/columns, then
det(A)=0
(D3) Linearity in every row/column (in the literature also called n-linearity)
For every entry akl of an n×n matrix A, let the (n−1)×(n−1) submatrix A[k,l] be defined 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]).
Definition
The degreedj of the vertex j is defined as follows:
dj:=i=1∑n(A)ij.
SatzKirchhoff's theorem
Kirchhoff’s theorem states that the number of spanning trees of a graph equals the value of any cofactor of L, where L is defined as follows:
L:=D−Awith D=diag(d1,...,dn),di=^ degree of the vertex iandA=^ adjacency matrix with (Aij)={1,0,if i is connected to j by an edge otherwise.