[Artikel] Gruppenoperationen

Neue Frage »

jester. Auf diesen Beitrag antworten »
[Artikel] Gruppenoperationen
Nötige Vorkenntnisse

Um diesen Artikel zu verstehen, sollte man mit dem Begriff der Gruppe vertraut sein und außerdem elementare Mengenlehre und Äquivalenzrelationen kennen.
Hilfreich für das Verstehen der Beispiele ist außerdem die Kenntnis der Zykeldarstellung von Permutationen.

Inhalt
  1. Einleitung
  2. Der Bahnensatz, verschiedene Arten von Operationen und Invarianten
  3. Verschiedenes
  4. Anwendungen in der Kombinatorik
  5. Klassifikation transitiver -Mengen


Gruppenoperationen

Die Definition: Sei eine Gruppe und eine Menge. Existiert eine Abbildung , welche die zwei Eigenschaften
  • , wobei das neutrale Element der Gruppe ist.
  • ,

so nennt man diese Abbildung eine Operation der Gruppe auf der Menge und man sagt auch, dass auf operiert.
Streng genommen bezeichnet man eine solche Operation als Linksoperation, wir wollen uns in diesem Artikel aber ausschließlich mit solchen Operationen befassen und werden daher schlicht von Operationen sprechen.
Man nennt die Menge mit der zugehörigen Operation auch eine -Menge.

Bahn und Stabilisator

Es operiere die Gruppe auf der Menge . Dann wollen wir folgende Bezeichnungen festlegen:

heißt die Bahn von (unter ).
heißt der Stabilisator von (unter der Operation von ).

Bemerkung: ist für jedes feste eine Untergruppe von .
Beweis: Seien . Dann gilt , also . Es gilt weiterhin ; die Behauptung folgt.

Bemerkung: Die Bahnen unter einer Operation einer Gruppe auf eine Menge bilden eine Partition von , es gilt also .
Beweis:
  • Eine Bahn ist stets nichtleer, denn für liegt das Element in der Bahn .
  • Seien und wir nehmen an, dass , also . Dann existieren also sodass .
    Es folgt und für beliebiges gilt somit , also . Analog folgert man , die Bahnen sind also gleich. Zwei Bahnen sind also disjunkt oder gleich.
  • Zu zeigen bleibt noch . Jede Bahn ist eine Teilmenge von , somit gilt .
    Im ersten Punkt des Beweises haben wir außerdem gesehen, dass jedes in liegt, also .

In der gleichen Bahn unter einer Operation einer Gruppe zu liegen, ist also eine Äquivalenzrelation.

Erste Beispiele

Jede Gruppe operiert auf sich selbst durch Linksmultiplikation durch .
Dies ist sofort klar, da eine Gruppe eine assoziative Verknüpfung mit einem neutralen Element besitzt.

Jede Gruppe operiert zudem auf sich selbst durch Konjugation: .
Beweis: Sei das neutrale Element von . Dann gilt für jedes .
Seien nun . Dann gilt für alle :


Sei ein Vektorraum und . Bekanntlich ist eine Gruppe. Diese operiert auf durch .
Beweis: Das neutrale Element der ist die Identitätsabbildung und es gilt .
Seien nun . Dann gilt für alle :
.

Ist ein Vektorraum und ein Unterraum, so operiert der Unterraum (als additive Untergruppe der additiven Gruppe ) auf durch . Die Menge der Bahnen ist hier auch als Faktorraum bekannt.
Ist nun ein Endomorphismus von , so ist ebenfalls ein Unterraum von , der in der oben beschriebenen Weise operiert. Dann bedeutet Bildgleichheit unter in der gleichen Bahn unter der Operation des Kerns zu liegen.
jester. Auf diesen Beitrag antworten »

Der Bahnensatz

Es operiere die Gruppe auf der Menge . Dann ist die Abbildung eine Bijektion.

Zitat:
Beweis: Die Abbildung ist wohldefiniert, denn seien , also . Es gilt dann .

Injektivität: Seien wieder und , also .
Es folgt , also , was die Gleichheit der Nebenklassen liefert.

Surjektivität: Zu jedem ist ein Urbild unter .


Daraus folgern wir für festes . Alternativ formuliert man dies auch als .

Verschiedene Arten von Operationen

Es operiere die Gruppe auf der Menge . Die Operation heißt
  • transitiv, falls die Operation nur eine Bahn hat, also für ein ist.
  • regulär, wenn die Operation transitiv ist und der Stabilisator jedes Punktes trivial ist, also nur aus dem neutralen Element der operierenden Gruppe besteht.
  • treu, wenn gilt.
Mit diesen neuen Begrifflichkeiten lässt sich beispielsweise die Definition eines affinen Raums sehr kurz fassen: Ein affiner Raum ist eine Menge, auf der ein Vektorraum regulär operiert.

Beispiel: Die Ordnung von

Als eine erste Anwendung wollen wir die Ordnung der vollen linearen Gruppe vom Grad über dem endlichen Körper bestimmen.

Die operiert transitiv auf (durch Linksmultiplikation), denn: seien , dann gibt es stets ein mit , da man und jeweils zu Basen des Vektorraums ergänzen kann und eine lineare Abbildung dadurch festlegt, dass auf geschickt wird. Die Länge der einzigen Bahn unter dieser Operation ist also . Nun untersuchen wir den Stabilisator des Punktes :
.
Also: .

Aus dem Bahnensatz gewinnen wir also die Rekursion .
Damit beweist man die Beauptung durch vollständige Induktion mit dem Induktionsanfang .

Anmerkung: Das ist nicht unbedingt die schnellste Methode, um sich die Ordnung dieser Gruppe zu überlegen. Trotzdem vermittelt dieses Beispiel eine sinnvolle Anwendung der bisher vorgestellten Konzepte.

Invarianten und trennende Invarianten

Es operiere die Gruppe auf der Menge , sei eine beliebige weitere Menge. Die Abbildung heißt eine Invariante der Operation, wenn gilt.
Die Invariante heißt trennend, wenn für gilt .

Zum besseren Verständnis ein Beispiel: Bekanntlich ist eine Gruppe. Wir zeigen nun, dass eine Operation auf beschreibt und dass eine trennende Invariante dieser Operation ist.

Zunächst ist das neutrale Element der Gruppe und es ist für jedes .
Seien nun . Dann gilt . Es liegt also eine Operation vor.
Seien nun und . Dann gilt . Also ist eine Invariante der Operation.
Sei nun zusätzlich noch und es gelte , also . Jetzt möchten wir ein angeben, sodass gilt. Dazu lösen wir hier in der zweiten Komponente nach auf und erhalten . Dass dieses nun auch in der ersten Komponente das gewünschte Ergebnis liefert, erhalten wir aus , woraus wir folgern. Somit liegen also und in der selben Bahn unter , was bedeutet, dass die Invariante trennend ist.

Dieses Konzept ist sehr nützlich und beispielsweise in der linearen Algebra weit verbreitet. Ein großer Teilbereich der linearen Algebra basiert nämlich auf der Operation und der Suche nach (trennenden) Invarianten unter dieser Operation.
Bekannte Invarianten sind die Spur, die Determinante, der Rang, das charakteristische und das Minimalpolynom, die Eigenwerte, etc.
Trennende Invarianten sind die Jordan-, Frobenius- oder Weierstraß-Normalformen.
jester. Auf diesen Beitrag antworten »

Verschiedenes

  1. Es operiere die Gruppe auf der Menge . Dann ist für ein .
  2. Diagonale Operation: Es operiere auf den zwei Mengen . Dann operiert auch auf durch und diese Operation nennt man auch "diagonale Operation".
  3. Operiert auf den zwei Mengen und ist transitiv auf , so stehen die -Bahnen auf in Bijektion zu den -Bahnen auf für ein festes .
  4. Jede Operation einer Gruppe auf einer Menge liefert einen Homomorphismus .
  5. Eine Operation ist genau dann treu, wenn der gerade genannte Homomorphismus injektiv ist.


Beweis:
  1. Es sei . Zeige dann, dass den Punkt stabilisiert:
    Ist umgekehrt , so muss nachgewiesen werden, dass das Element festlässt. Dies rechnet man genauso leicht nach.
  2. Diese Bemerkung ist klar.
  3. Wir zeigen: Die Abbildung ist eine wohldefinierte Bijektion (hierbei kennzeichnet die Menge der -Bahnen auf , falls eine auf operierende Gruppe ist).
    Man sollte als erstes feststellen, dass aufgrund der Transitivität von auf jede -Bahn auf jede Bahn von der Form (weiterhin mit festem ) ist.
    Seien nun mit . Dann gibt es also ein mit , also und , und liegen also in der gleichen Bahn unter . D.h. zwei gleiche -Bahnen auf werden auf die gleiche -Bahn abgebildet.
    Die Surjektivität der Abbildung ist offensichtlich.
    Seien nun . Dann gibt es ein mit . Es folgt , womit die Abbildung injektiv ist.
  4. Es ist zunächst zu zeigen, dass jedes auch tatsächlich auf eine bijektive Abbildung abgebildet wird. Die Abbildung hat jedoch offensichtlich die Umkehrabbildung .
    Seien nun und die betrachtete Abbildung sei der Einfachheit halber mit bezeichnet. Dann gilt für jedes :
    .
  5. Bezeichnet wieder den Homomorphismus, so ist
    . Dass gilt, ist äquivalent zur Injektivität von , andererseits ist dies genau die Definition einer treuen Operation.


Der Homomorphismus aus Punkt 4 lässt sich beispielsweise zur Lösung folgender Aufgabe verwenden: Es sei eine einfache Gruppe der Ordnung 168. Man zeige, dass es keine transitive -Menge mit 6 Elementen gibt.

Lösung: Angenommen es gibt eine solche Menge, dann liefert die Operation von einen Homomorphismus . Da die Operation transitiv sein soll, kann der Homomorphismus nicht trivial sein. Daher muss der Kern des Homomorphismus sein, da einfach ist. Dann wäre eine Untergruppe der von Ordnung 168. Jedoch teilt 168 nicht , Widerspruch.
jester. Auf diesen Beitrag antworten »

Anwendungen in der Kombinatorik

Hier werden wir uns eine Anwendung der bisher vorgestellten Theorie auf kombinatorische Fragestellungen ansehen.
Wir möchten die Frage beantworten, auf wieviele Arten wir ein Dreieck mit zwei Farben einfärben können (dabei ist gemeint, dass wir die Eckpunkte einfärben möchten).

Um ein Modell zu haben, nummerieren wir die Eckpunkte des Dreiecks durch, als "Dreieck" betrachten wir also . Bekanntlich ist die (symmetrische Gruppe auf 3 Punkten) die Symmetriegruppe des Dreiecks in der Ebene; diese operiert auf durch anwenden ().
Die "Färbungen" des Dreiecks realisieren wir als Abbildungen von in die zweielementige Menge (beispielsweise könnte r für rot und b für blau stehen). Die Menge der Färbungen ist also , auf der die ebenfalls operiert: . Wir möchten nun Färbungen als gleich ansehen, wenn sie in der gleichen Bahn unter liegen.

Damit stoßen wir auch schon zum Kern des Problems vor: wir haben nämlich die anfangs vorgestellte kombinatorische Fragestellung auf eine algebraische Frage, nämlich die nach der Anzahl der Bahnen einer Operation, zurückgeführt.
Um diese Frage beantworten zu können, verwenden wir das folgende Lemma:

Burnside'sches Fixpunktlemma

Es operiere die Gruppe auf einer Menge , wir möchten hier annehmen.
Zunächst definieren wir für ein : .
Es gilt dann , wobei die Menge der -Bahnen auf kennzeichnet.

Zitat:
Beweis: Wir betrachten die Matrix mit .
Dann gilt:
(wobei wir hier das oben gesehene Resultat anwenden)
(wobei ein festes Element der Bahn ist)


Fortführung des Beispiels

Wir kehren nun zum oben begonnenen Beispiel zurück. Zu bestimmen ist also die Anzahl der Fixpunkte, die die Permutationen der auf der Menge haben:



Diese Anzahlen bestimmt man, indem man sich überlegt, dass man beispielsweise für die Permutation die Farben jeweils für den Punkt und die zwei Punkte festlegen kann und dass dafür jeweils zwei Farben zur Verfügung stehen.

Das heißt, nach dem Burnside'schen Fixpunktlemma, dass es Bahnen der Operation bzw. Färbungen des Dreiecks mit zwei Farben gibt.

Dieses Verfahren kann man auf beliebige endliche Mengen und Gruppen erweitern. Die Festlegung, welche Färbungen man als "gleich" ansehen möchte, bleibt einem durch die Wahl der operierenden Gruppe freigestellt.

Vereinfachung des vorgestellten Verfahrens

Wie wir bereits gesehen haben, operiert eine Gruppe auf sich selbst durch Konjugation: .
Zu einem bezeichnen wir als die Konjugiertenklasse von .

Bemerkung: Liegen und in derselben Konjugiertenklasse, so ist .

Zitat:
Beweis: Sei . Dann ist eine wohldefinierte Bijektion.


Kennt man nun also die Längen der Konjugiertenklassen von Elementen, so kann man das vorgestellte Abzählverfahren auf Vertreter der Konjugiertenklassen beschränken. Es ist dann , wobei ein Vertretersystem der Konjugiertenklassen ist und die Konjugiertenklasse des Gruppenelements bezeichnet.

Wir führen dies für das obige Beispiel aus. Diesem Artikel entnimmt man die bekannte Tatsache, dass zwei Elemente der genau dann zueinander konjugiert sind, wenn ihre Zykeltypen übereinstimmen.
Das heißt die zerfällt disjunkt in Konjugiertenklassen, die durch vertreten sind, die Längen der Konjugiertenklassen liest man aus der obigen Tabelle ab oder erschließt sie sich durch Abzählen. Sie lauten 1, 3 und 2 (in der Reihenfolge der Vertreter).

Nun müssen wir uns überlegen, wieviele Fixpunkte die Vertreter lassen, diese Information entnehmen wir ebenfalls der Tabelle oben. Multipliziert man diese Werte dann mit der Länge der Konjugiertenklasse, so erhält man das Ergebnis aus dem obigen Beispiel:


Ähnliche Beispiele lassen sich natürlich einfach konstruieren. Man kann sich beispielsweise als kleine Übungsaufgabe fragen, auf wie viele Arten man die Eckpunkte eines regelmäßigen Tetraeders im dreidimensionalen Raum einfärben kann, wenn man die darauf als Symmetriegruppe operieren lässt.
jester. Auf diesen Beitrag antworten »

Klassifikation transitiver -Mengen

In diesem Abschnitt möchten wir die transitiven -Mengen, d.h. die möglichen Bahnen einer Operation einer Gruppe , klassifizieren, wobei diese Klassifikation natürlich nur die Struktur angibt und somit bis auf sogenannte Ähnlichkeit eindeutig ist.

Definition: Seien zwei -Mengen. Eine Abbildung heißt -äquivariant, falls für alle und gilt.
Ist überdies bijektiv, dann nennt man auch eine Ähnlichkeit und und als -Mengen ähnlich.

Ist eine -Ähnlichkeit, so ist ebenfalls eine -Ähnlichkeit.

Zitat:
Beweis: Sei , sodass . Dann gilt
.


Bemerkung: Ist eine Gruppe und eine Untergruppe, so operiert auch auf der Menge der Nebenklassen durch . Die Operation ist transitiv und jeder Punktstabilisator ist konjugiert zu .

Zitat:
Beweis: Dass eine Operation vorliegt, ist offensichtlich, wenn man sich überlegt, dass die Abbildungsvorschrift wohldefiniert ist.
Die Transitivität folgt aus der Tatsache, dass die Bahn von unter der Operation von auf seinen Untergruppen ist.
Weiter ist , also für jedes .


Als nächstes werden wir nun sehen, dass zwei zueinander konjugierte Untergruppen der Gruppe zueinander ähnliche transitive -Mengen liefern. Es gilt ebenfalls die Umkehrung; sind also und zueinander ähnlich, so sind und konjugiert.

Zitat:
Beweis: Sei . Betrachte dann die Abbildung , für die die folgende Äquivalenz gilt:

mit .
Dabei zeigt die Richtung die Injektivität von , die Wohldefiniertheit.
Die Surjektivität ist klar; die -Äquivarianz rechnet man ebenfalls leicht nach.

Sei umgekehrt eine -Ähnlichkeit. Wir haben oben bereits gesehen, dass für eine Untergruppe gilt .

Ferner gilt für jedes , denn:
Sei . Dann , also und somit .
Ist , so ist , womit die Gleichheit folgt.

Nun ist für ein festes und somit erhalten wir
, also sind und zueinander konjugiert.


Als nächstes zeigen wir: Ist eine transitive -Menge, so ist ähnlich zu für ein .

Zitat:
Beweis: Betrachte für ein festes die Abbildung . Diese erfüllt




Daraus folgt wieder die Injektivität und die Wohldefiniertheit. Die Surjektivität erhalten wir sofort aus der Transitivität der Operation.

Sei nun , dann gilt , ist also -verträglich.


Zum Abschluss wollen wir beweisen, dass die Ähnlichkeitsklassen transitiver -Mengen in Bijektion stehen zu den Konjugiertenklassen von Untergruppen von .

Zitat:
Beweis: Sei die Menge der Konjugiertenklassen von Untergruppen von .
Eine Klasse bilde man ab auf (dabei sei ein Vertreter der Klasse ).
Diese Abbildung ist wohldefiniert, da wir gesehen haben, dass konjugierte Untergruppen auf diese Weise zueinander ähnliche transitive -Mengen liefern.
Da die Umkehrung dieser Aussage auch richtig ist, ist die Abbildung injektiv.

Da eine transitive -Menge zu für ein ähnlich ist, ist die Abbildung surjektiv; man kann zu jeder transitiven -Menge als Urbild die Klasse wählen, in der liegt.


Mit diesem Satz kennt man also alle Arten von Bahnen, die eine Gruppe auf einer -Menge haben kann, wenn man nur die Konjugiertenklassen von Untergruppen von kennt.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »