Kurs:Lineare Algebra (Osnabrück 2015-2016)/Teil I/Vorlesung 18/kontrolle
- Permutationen
In dieser Vorlesung stellen wir eine weitere Beschreibung für die Determinante mit Hilfe von Permutationen vor.
Definition Referenznummer erstellen
Zu einer Menge nennt man die Menge
der bijektiven Selbstabbildungen die Automorphismengruppe oder die Permutationsgruppe zu .
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 nennt man auch eine Permutation.
Für eine endliche Menge schreibt man
Eine endliche Permutation kann man beispielsweise mit einer (vollständigen) Wertetabelle oder mit einem Pfeildiagramm beschreiben.
Definition Referenznummer erstellen
Es sei eine endliche Menge und eine Permutation auf . Man nennt einen Zykel der Ordnung , wenn es eine -elementige Teilmenge derart gibt, dass auf die Identität ist und die Elemente aus zyklisch vertauscht. Wenn ist, so schreibt man einfach
Ein Element mit nennt man Fixpunkt der Permutation. Der Wirkungsbereich einer Permutation ist die Menge der Punkte aus , die keine Fixpunkte sind. Bei einem Zykel ist der Wirkungsbereich. Jede Permutation ist ein Produkt von Zykeln, was wir hier ohne Beweis erwähnen. Eine solche Produktdarstellung heißt Zykeldarstellung.
Definition Referenznummer erstellen
Zu einer natürlichen Zahl nennt man die Zahl
die Fakultät von (sprich Fakultät).
Lemma Referenznummer erstellen
Es sei eine endliche Menge mit Elementen.
Dann besitzt die Permutationsgruppe genau Elemente.
Beweis
Es sei . Für die gibt es mögliche Bilder, für gibt es noch mögliche Bilder, für gibt es noch mögliche Bilder, usw. Daher gibt es insgesamt
mögliche Permutationen.
- Transpositionen
Definition Referenznummer erstellen
Eine Transposition auf einer endlichen Menge ist eine Permutation auf , die genau zwei Elemente miteinander vertauscht und alle anderen Elemente unverändert lässt.
Lemma Referenznummer erstellen
Jede Permutation auf einer endlichen Menge
kann man als Produkt von Transpositionen schreiben.
Beweis
Wir beweisen die Aussage durch Induktion über die Anzahl der Menge . Für ist nichts zu zeigen, sei also . Die Identität ist das leere Produkt aus Transpositionen. Es sei also nicht die Identität, und sei Es sei die Transposition, die und vertauscht. Dann ist ein Fixpunkt von , und man kann auffassen als eine Permutation auf . Nach Induktionsvoraussetzung gibt es dann Transpositionen auf mit auf . Dies gilt dann auch auf , und daher ist .
- Das Signum einer Permutation
Definition Referenznummer erstellen
Es sei und sei eine Permutation auf . Dann heißt die Zahl
das Signum (oder das Vorzeichen) der Permutation .
Das Signum ist oder , da im Zähler und im Nenner die bis auf das Vorzeichen gleichen Differenzen stehen. Es gibt für das Signum also nur zwei mögliche Werte. Bei spricht man von einer geraden Permutation und bei von einer ungeraden Permutation.
Lemma Referenznummer erstellen
Es sei und sei eine Permutation auf . Es sei die Anzahl der Fehlstände von .
Dann ist das Signum von gleich
Beweis
Wir schreiben
da nach dieser Umordnung sowohl im Zähler als auch im Nenner das Produkt aller positiven Differenzen steht.
Beispiel Referenznummer erstellen
Wir betrachten die Permutation
mit der Zyklendarstellung
Die Fehlstände sind
es gibt also Stück davon. Das Signum ist also und die Permutation ist ungerade.
Das Signum ist ein Gruppenhomomorphismus im Sinne der folgenden Definition.
Lemma Lemma 18.13 ändern
Es sei und sei eine Permutation auf . Es sei
als ein Produkt von Transpositionen geschrieben.
Dann gilt für das Signum die Darstellung
Beweis
Die Transposition vertausche die beiden Zahlen . Dann ist
Die letzte Gleichung ergibt sich daraus, dass im ersten und im zweiten Produkt alle Zähler und Nenner positiv sind und dass im dritten und im vierten Produkt die Zähler negativ und die Nenner positiv sind, so dass sich diese (wegen der gleichen Indexmenge) Minuszeichen wegkürzen.
Die Aussage folgt dann aus der Homomorphieeigenschaft.
Bemerkung Referenznummer erstellen
Es sei eine beliebige Menge mit Elementen, die nicht geordnet sein muss. Dann kann man nicht von Fehlständen sprechen und die Definition des Signums ist nicht direkt anwendbar. Man kann sich jedoch an Lemma 18.13 orientieren, um das Signum auch in dieser leicht allgemeineren Situation zu erklären. Dazu schreibt man eine Permutation auf als Produkt von Transpositionen und definiert
Um einzusehen, dass dies wohldefiniert ist, betrachtet man eine Bijektion
Die Permutation auf definiert auf die Permutation . Sei eine Darstellung als Produkt von Transpositionen auf . Dann gilt
mit . Dies sind ebenfalls Transpositionen, so dass die Parität von durch das Signum von festgelegt ist.
- Die Leibnizformel für die Determinante
Satz Referenznummer erstellen
Beweis
Wir führen Induktion über , wobei der Induktionsanfang klar ist. Es sei also . Die Menge der Permutationen kann man aufspalten, indem man nach sortiert und die bijektive Abbildung
als eine Permutation auf auffasst, indem man beide Mengen ordnungstreu mit identifiziert. Dies ergibt eine Bijektion , wobei hier die Menge der Permutationen auf bezeichnet, die auf abbilden. Zwischen den Signa besteht dabei die Beziehung
da man Transpositionen braucht, um die -te Stelle und die erste Stelle zu vertauschen. Es besteht also insgesamt eine natürliche Bijektion
Somit gilt
wobei die Streichungsmatrix zur ersten Zeile und -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 nach der ersten Zeile.