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

Aus Wikiversity
Zur Navigation springen Zur Suche springen
„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.


Definition  

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.

Permutation8.png


Composicion de permutaciones.svg


050712 perm 0.png



Definition  

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


Beispiel  

Wir betrachten die Permutation

Man kann sie als Produkt der beiden Zykel und schreiben.


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  

Zu einer natürlichen Zahl nennt man die Zahl

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



Lemma  

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  

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  

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. 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  

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.


Definition  

Sei und sei eine Permutation auf . Dann heißt ein Indexpaar

ein Fehlstand, wenn ist.



Lemma  

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  

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.


Definition  

Seien und Gruppen. Eine Abbildung

heißt Gruppenhomomorphismus, wenn die Gleichheit

für alle gilt.



Satz  

Die durch das Signum gegebene Zuordnung

ist ein Gruppenhomomorphismus.

Beweis  

Seien zwei Permutationen und gegeben. Dann ist




Lemma  

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  

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  

Für die Determinante einer -Matrix

gilt

Beweis  

Wir führen Induktion über , wobei der Induktionsanfang klar ist. 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.


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

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)