Zum Inhalt springen

Kurs:Lineare Algebra (Osnabrück 2015-2016)/Teil I/Vorlesung 18

„Wahr ist wahre Freundschaft doch wohl nur, wenn sie begrenzt ist.“
Bertolt Brecht



Permutationen

In dieser Vorlesung stellen wir eine weitere Beschreibung für die Determinante mit Hilfe von Permutationen vor.


Zu einer Menge M nennt man die Menge

Aut⁡(M)=Perm⁡(M)={φ:M⟶M∣φ bijektiv}

der bijektiven Selbstabbildungen die Automorphismengruppe oder die Permutationsgruppe zu M.

Die Verknüpfung ist die Hintereinanderschaltung von Abbildungen und somit assoziativ, die Identität ist das neutrale Element. Das inverse Element zu einer bijektiven Abbildung ist einfach die Umkehrabbildung. Damit handelt es sich um eine Gruppe. Eine bijektive Selbstabbildung φ:M→M nennt man auch eine Permutation.

Für eine endliche Menge  I={1,…,n}  schreibt man

Sn=Perm⁡(I).

Eine endliche Permutation kann man beispielsweise mit einer (vollständigen) Wertetabelle oder mit einem Pfeildiagramm beschreiben.





Es sei M eine endliche Menge und π eine Permutation auf M. Man nennt π einen Zyklus der Ordnung r (oder der Länge r), wenn es eine r-elementige Teilmenge  Z⊆M  derart gibt, dass π auf M∖Z die Identität ist und π die Elemente aus Z zyklisch vertauscht. Wenn  Z={z,π(z),π2(z),…,πr−1(z)}  ist, so schreibt man einfach

π=⟨z,π(z),π2(z),…,πr−1(z)⟩.

Wir betrachten die Permutation

x 1 2 3 4 5
π(x) 2 1 5 3 4

Man kann sie als Produkt der beiden Zyklen ⟨1,2⟩ und ⟨3,5,4⟩ schreiben.


Ein Element  x∈M  mit  π(x)=x  nennt man Fixpunkt der Permutation. Der Wirkungsbereich einer Permutation ist die Menge der Punkte aus M, die keine Fixpunkte sind. Bei einem Zyklus ist Z der Wirkungsbereich. Jede Permutation ist ein Produkt von Zyklen, was wir hier ohne Beweis erwähnen. Eine solche Produktdarstellung heißt Zyklendarstellung.


Zu einer natürlichen Zahl n nennt man die Zahl

n!:=n(n−1)(n−2)⋯3⋅2⋅1

die Fakultät von n (sprich n Fakultät).



Lemma  

Es sei M eine endliche Menge mit n Elementen.

Dann besitzt die Permutationsgruppe  Perm⁡(M)≅Sn  genau n! Elemente.

Beweis  

Es sei  M={1,…,n}.  Für die 1 gibt es n mögliche Bilder, für 2 gibt es noch n−1 mögliche Bilder, für 3 gibt es noch n−2 mögliche Bilder, usw. Daher gibt es insgesamt

n(n−1)(n−2)⋯2⋅1=n!

mögliche Permutationen.

◻



Transpositionen

Eine Transposition auf einer endlichen Menge M ist eine Permutation auf M, die genau zwei Elemente miteinander vertauscht und alle anderen Elemente unverändert lässt.



Lemma  

Jede Permutation auf einer endlichen Menge M

kann man als Produkt von Transpositionen schreiben.

Beweis  

Wir beweisen die Aussage durch Induktion über die Anzahl der Menge M. Für  #(M)=1  ist nichts zu zeigen, sei also  #(M)≥2.  Die Identität ist das leere Produkt aus Transpositionen. Es sei also π nicht die Identität, und sei  π(x)=y≠x.  Es sei τ die Transposition, die x und y vertauscht. Dann ist y ein Fixpunkt von πτ, und man kann πτ auffassen als eine Permutation auf  M′=M∖{y}.  Nach Induktionsvoraussetzung gibt es dann Transpositionen τj auf M′ mit  πτ=∏jτj  auf M′. Dies gilt dann auch auf M, und daher ist  π=(∏jτj)τ. 

◻




Das Signum einer Permutation

Es sei  M={1,…,n}  und sei π eine Permutation auf M. Dann heißt die Zahl

sgn⁡(π)=∏i<jπ(j)−π(i)j−i

das Signum (oder das Vorzeichen) der Permutation π.

Das Signum ist 1 oder −1, da im Zähler und im Nenner die bis auf das Vorzeichen gleichen Differenzen ±(j−i) stehen. Es gibt für das Signum also nur zwei mögliche Werte. Bei sgn⁡(σ)=1 spricht man von einer geraden Permutation und bei sgn⁡(σ)=−1 von einer ungeraden Permutation.


Es sei  M={1,…,n}  und sei π eine Permutation auf M. Dann heißt ein Indexpaar

i<j

ein Fehlstand von π, wenn  π(i)>π(j)  ist.



Lemma  

Es sei  M={1,…,n}  und sei π eine Permutation auf M. Es sei  k=#(F)  die Anzahl der Fehlstände von π.

Dann ist das Signum von π gleich

sgn⁡(π)=(−1)k.

Beweis  

Wir schreiben

sgn⁡(π)=∏i<jπ(j)−π(i)j−i=∏(i,j)∈Fπ(j)−π(i)j−i∏(i,j)∉Fπ(j)−π(i)j−i=(−1)k∏(i,j)∈Fπ(i)−π(j)j−i∏(i,j)∉Fπ(j)−π(i)j−i=(−1)k,

da nach dieser Umordnung sowohl im Zähler als auch im Nenner das Produkt aller positiven Differenzen steht.

◻



Wir betrachten die Permutation

x 1 2 3 4 5 6
σ(x) 2 4 6 5 3 1

mit der Zyklendarstellung

⟨1,2,4,5,3,6⟩.

Die Fehlstände sind

(1,6),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6),

es gibt also 9 Stück davon. Das Signum ist also  (−1)9=−1  gemäß Satz 18.10, und die Permutation ist ungerade.


Das Signum ist ein Gruppenhomomorphismus im Sinne der folgenden Definition.


Es seien (G,∘,eG) und (H,∘,eH) Gruppen. Eine Abbildung

ψ:G⟶H

heißt Gruppenhomomorphismus, wenn die Gleichheit

ψ(g∘g′)=ψ(g)∘ψ(g′)

für alle  g,g′∈G  gilt.



Satz  

Die durch das Signum gegebene Zuordnung

Sn⟶{1,−1},π⟼sgn⁡(π),

ist ein Gruppenhomomorphismus.

Beweis  

Es seien zwei Permutationen π und ρ gegeben. Dann ist

sgn⁡(π∘ρ)=∏i<j(π∘ρ)(j)−(π∘ρ)(i)j−i=(∏i<j(π∘ρ)(j)−(π∘ρ)(i)ρ(j)−ρ(i))∏i<jρ(j)−ρ(i)j−i=(∏i<j,ρ(i)<ρ(j)π(ρ(j))−π(ρ(i))ρ(j)−ρ(i))(∏i<j,ρ(i)>ρ(j)π(ρ(j))−π(ρ(i))ρ(j)−ρ(i))sgn⁡(ρ)=(∏i<j,ρ(i)<ρ(j)π(ρ(j))−π(ρ(i))ρ(j)−ρ(i))(∏i<j,ρ(i)>ρ(j)π(ρ(i))−π(ρ(j))ρ(i)−ρ(j))sgn⁡(ρ)=∏k<ℓπ(ℓ)−π(k)ℓ−ksgn⁡(ρ)=sgn⁡(π)sgn⁡(ρ).
◻



Lemma  

Das Signum einer Transposition

ist −1.

Beweis  

Die Transposition τ vertausche  k<ℓ.  Wir berechnen die Anzahl der Fehlstände von τ. Wir bestimmen für ein Paar (i,j),  i<j,  ob ein Fehlstand vorliegt. Bei  i<k  liegt wegen

τ(i)=i<min⁡(k,j)=τ(j)

kein Fehlstand vor. Entsprechend liegt bei  j>ℓ  kein Fehlstand vor. Es sei also

k≤i<j≤ℓ.

Bei

k<i<j<ℓ

ist  τ(i)=i<j=τ(j)  und es liegt kein Fehlstand vor. Bei

k=i<j<ℓ

liegt wegen

τ(k)=ℓ>j=τ(j)

ein Fehlstand vor und ebenso liegt bei

k<i<j=ℓ

ein Fehlstand vor. Ferner ist  k<ℓ  ein Fehlstand. Dies ergibt insgesamt

(ℓ−k−1)+(ℓ−k−1)+1=2ℓ−2k−1

Fehlstände. Daher ist die Anzahl der Fehlstände ungerade und das Signum einer Transposition ist −1 nach Satz 18.10.

◻


Es sei I eine beliebige Menge mit n Elementen, die nicht geordnet sein muss, und sei π eine Permutation auf I. Dann kann man nicht von Fehlständen sprechen und die Definition des Signums ist nicht direkt anwendbar. Man kann sich jedoch an Lemma 18.14 orientieren, um das Signum auch in dieser leicht allgemeineren Situation zu erklären. Dazu schreibt man π als Produkt von r Transpositionen und definiert

sgn⁡(π)={1, falls r gerade ist,−1, falls r ungerade ist.

Um einzusehen, dass dies wohldefiniert ist, betrachtet man eine Bijektion

φ:I⟶{1,…,n}.

Die Permutation π auf I definiert auf {1,…,n} die Permutation  π′=φπφ−1.  Sei  π=τ1⋯τr  eine Darstellung als Produkt von r Transpositionen auf I. Dann gilt

π′=φπφ−1=φτ1⋯τrφ−1=φτ1φ−1φτ2φ−1φ⋯φ−1φτrφ−1=τ1′τ2′⋯τr′

mit  τj′=φτjφ−1.  Dies sind ebenfalls Transpositionen, sodass die Parität von r durch das Signum von π′ festgelegt ist.




Die Leibnizformel für die Determinante



Satz  

Für die Determinante einer n×n-Matrix

M=(aij)ij

gilt

det⁡M=∑π∈Snsgn⁡(π)a1π(1)⋯anπ(n).

Beweis  

Wir führen Induktion über  n≥1,  wobei der Induktionsanfang klar ist. Es sei also  n≥2.  Die Menge der Permutationen  π∈Sn  kann man aufspalten, indem man nach  π(1)=i  sortiert und die bijektive Abbildung

π|{2,…,n}:{2,…,n}⟶{1,…,n}∖{i}

als eine Permutation ρ auf {1,…,n−1} auffasst, indem man beide Mengen ordnungstreu mit {1,…,n−1} identifiziert. Dies ergibt eine Bijektion  Sn,i≅Sn−1,  wobei hier Sn,i die Menge der Permutationen auf {1,…,n} bezeichnet, die 1 auf i abbilden. Zwischen den Signa besteht dabei die Beziehung

sgn⁡(π)=(−1)i−1sgn⁡(ρ)=(−1)i+1sgn⁡(ρ),

da man i−1 Transpositionen braucht, um die i-te Stelle und die erste Stelle zu vertauschen. Es besteht also insgesamt eine natürliche Bijektion

Sn=⨄i∈{1,…,n}Sn,i=⨄i∈{1,…,n}Sn−1.

Somit gilt

∑π∈Snsgn⁡(π)a1π(1)⋯anπ(n)=∑i=1n∑π∈Sn,isgn⁡(π)∏j=1najπ(j)=∑i=1na1i∑π∈Sn,isgn⁡(π)∏j=2najπ(j)=∑i=1na1i∑ρ∈Sn−1(−1)i+1sgn⁡(ρ)∏k=1n−1(M1i)kρ(k)=∑i=1n(−1)i+1a1idet⁡M1i=det⁡M,

wobei M1i die Streichungsmatrix zur ersten Zeile und i-ten Spalte ist (und sich die Indizierung auf diese Matrix bezieht). Für die vorletzte Gleichung geht die Induktionsvoraussetzung ein und die letzte Gleichung beruht auf der Entwicklung der Determinante nach der ersten Zeile.

◻


<< | Kurs:Lineare Algebra (Osnabrück 2015-2016)/Teil I | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)