Permutationsgruppe – Wikipedia

Gruppe, deren Operation die Zusammensetzung von Permutationen ist

In der Mathematik a Permutationsgruppe ist eine Gruppe G deren Elemente sind Permutationen einer gegebenen Menge M. und dessen Gruppenoperation die Zusammensetzung von Permutationen in ist G (die als bijektive Funktionen aus der Menge gedacht sind M. zu sich selbst). Die Gruppe von alles Permutationen einer Menge M. ist die symmetrische Gruppe von M., oft geschrieben als Sym (M.).[1] Der Begriff Permutationsgruppe bedeutet also eine Untergruppe der symmetrischen Gruppe. Wenn M. = {1,2, …,n}} dann Sym (M.), das symmetrische Gruppe auf n Buchstaben wird normalerweise mit S bezeichnetn.

Nach dem Satz von Cayley ist jede Gruppe zu einer Permutationsgruppe isomorph.

Die Art und Weise, wie die Elemente einer Permutationsgruppe die Elemente der Menge permutieren, wird als Gruppenaktion bezeichnet. Gruppenaktionen finden Anwendung in der Erforschung von Symmetrien, Kombinatorik und vielen anderen Zweigen der Mathematik, Physik und Chemie.

Das beliebte Puzzle Rubik’s Cube, das 1974 von Ernő Rubik erfunden wurde, wurde zur Veranschaulichung von Permutationsgruppen verwendet. Jede Drehung einer Schicht des Würfels führt zu einer Permutation der Oberflächenfarben und ist Mitglied der Gruppe. Die Permutationsgruppe des Würfels wird als Rubik-Würfelgruppe bezeichnet.

Grundlegende Eigenschaften und Terminologie[edit]

Als Untergruppe einer symmetrischen Gruppe ist alles, was für eine Reihe von Permutationen erforderlich ist, um die Gruppenaxiome zu erfüllen und eine Permutationsgruppe zu sein, dass sie die Identitätspermutation, die inverse Permutation jeder darin enthaltenen Permutation enthält und unter Zusammensetzung von geschlossen wird seine Permutationen.[2] Eine allgemeine Eigenschaft endlicher Gruppen impliziert, dass eine endliche nicht leere Teilmenge einer symmetrischen Gruppe genau dann wieder eine Gruppe ist, wenn sie unter der Gruppenoperation geschlossen wird.[3]

Das Grad einer Gruppe von Permutationen einer endlichen Menge ist die Anzahl der Elemente in der Menge. Das bestellen einer Gruppe (eines beliebigen Typs) ist die Anzahl der Elemente (Kardinalität) in der Gruppe. Nach dem Satz von Lagrange die Reihenfolge jeder endlichen Permutationsgradgruppe n muss teilen n! schon seit n-Faktor ist die Reihenfolge der symmetrischen Gruppe S.n.

Notation[edit]

Da Permutationen Bijektionen einer Menge sind, können sie durch Cauchys dargestellt werden zweizeilige Notation.[4] Diese Notation listet jedes der Elemente von auf M. in der ersten Zeile und für jedes Element sein Bild unter der Permutation darunter in der zweiten Zeile. Wenn

σ{ displaystyle sigma}

ist eine Permutation der Menge

M.={x1,x2,,xn}}{ displaystyle M = {x_ {1}, x_ {2}, ldots, x_ {n} }}

dann,

Zum Beispiel kann eine bestimmte Permutation der Menge {1,2,3,4,5} wie folgt geschrieben werden:

das bedeutet, dass σ befriedigt σ(1) = 2, σ(2) = 5, σ(3) = 4, σ(4) = 3 und σ(5) = 1. Die Elemente von M. muss nicht in einer speziellen Reihenfolge in der ersten Zeile erscheinen. Diese Permutation könnte auch geschrieben werden als:

Permutationen werden auch oft in zyklischer Notation geschrieben (zyklische Form)[5] so dass angesichts des Satzes M. = {1,2,3,4}, eine Permutation G von M. mit G(1) = 2, G(2) = 4, G(4) = 1 und G(3) = 3 wird als (1,2,4) (3) oder häufiger als (1,2,4) geschrieben, da 3 unverändert bleibt; Wenn die Objekte durch einzelne Buchstaben oder Ziffern gekennzeichnet sind, können auch auf Kommas und Leerzeichen verzichtet werden, und wir haben eine Notation wie (124). Die oben in 2-Zeilen-Notation geschriebene Permutation würde in zyklischer Notation als geschrieben

σ=((125)((34).{ displaystyle sigma = (125) (34).}

Zusammensetzung der Permutationen – das Gruppenprodukt[edit]

Das Produkt zweier Permutationen ist definiert als ihre Zusammensetzung als Funktionen, also

σπ{ displaystyle sigma cdot pi}

ist die Funktion, die ein beliebiges Element abbildet x des Satzes auf

σ((π((x)){ displaystyle sigma ( pi (x))}

. Beachten Sie, dass die Permutation ganz rechts zuerst auf das Argument angewendet wird.[6][7] aufgrund der Art und Weise, wie die Funktionsanwendung geschrieben wird. Einige Autoren bevorzugen den Faktor ganz links, der zuerst wirkt.
[8][9][10]

aber zu diesem Zweck müssen Permutationen in die geschrieben werden richtig von ihrer Argumentation, oft als hochgestellt, also die Permutation

σ{ displaystyle sigma}

auf das Element einwirken

x{ displaystyle x}

ergibt das Bild

xσ{ displaystyle x ^ { sigma}}

. Mit dieser Konvention ist das Produkt gegeben durch

xσπ=((xσ)π{ displaystyle x ^ { sigma cdot pi} = (x ^ { sigma}) ^ { pi}}

. Dies ergibt jedoch eine anders Regel zum Multiplizieren von Permutationen. Diese Konvention wird häufig in der Literatur zu Permutationsgruppen verwendet. In diesem Artikel wird jedoch die Konvention verwendet, bei der die Permutation ganz rechts zuerst angewendet wird.

Da die Zusammensetzung zweier Bijektionen immer eine andere Bijektion ergibt, ist das Produkt zweier Permutationen wieder eine Permutation. In der zweizeiligen Notation wird das Produkt zweier Permutationen erhalten, indem die Spalten der zweiten (ganz links) Permutation so angeordnet werden, dass ihre erste Zeile mit der zweiten Zeile der ersten (ganz rechts) Permutation identisch ist. Das Produkt kann dann als erste Zeile der ersten Permutation über die zweite Zeile der modifizierten zweiten Permutation geschrieben werden. Zum Beispiel angesichts der Permutationen,

das Produkt QP ist:

Die Zusammensetzung der Permutationen, wenn sie in zyklischer Form geschrieben sind, wird erhalten, indem die beiden Permutationen nebeneinander gestellt werden (wobei die zweite links geschrieben wird) und dann, falls gewünscht, zu einer disjunkten Zyklusform vereinfacht werden. In zyklischer Notation wäre das obige Produkt also gegeben durch:

Da die Funktionszusammensetzung assoziativ ist, gilt dies auch für die Produktoperation bei Permutationen:

((σπ)ρ=σ((πρ){ displaystyle ( sigma cdot pi) cdot rho = sigma cdot ( pi cdot rho)}

. Daher werden Produkte mit zwei oder mehr Permutationen normalerweise geschrieben, ohne Klammern hinzuzufügen, um die Gruppierung auszudrücken. Sie werden normalerweise auch ohne Punkt oder anderes Zeichen geschrieben, um die Multiplikation anzuzeigen (die Punkte des vorherigen Beispiels wurden zur Hervorhebung hinzugefügt, würden also einfach als geschrieben

σπρ{ displaystyle sigma pi rho}

).

Neutrales Element und invers[edit]

Die Identitätspermutation, die jedes Element der Menge auf sich selbst abbildet, ist das neutrale Element für dieses Produkt. In zweizeiliger Notation ist die Identität

In zyklischer Notation e = (1) (2) (3) … (n), die gemäß Konvention auch nur mit (1) oder sogar () bezeichnet wird.[11]

Da Bijektionen invers sind, sind es auch Permutationen und umgekehrt σ−1 von σ ist wieder eine Permutation. Ausdrücklich, wann immer σ((x) =y man hat auch σ−1((y) =x. In zweizeiliger Notation kann die Umkehrung erhalten werden, indem die beiden Zeilen vertauscht werden (und die Spalten sortiert werden, wenn die erste Zeile in einer bestimmten Reihenfolge angezeigt werden soll). Zum Beispiel

Um die Umkehrung eines einzelnen Zyklus zu erhalten, kehren wir die Reihenfolge seiner Elemente um. So,

Um die Umkehrung eines Produktes von Zyklen zu erhalten, kehren wir zuerst die Reihenfolge der Zyklen um und nehmen dann die Umkehrung von jedem wie oben. So,

Ein assoziatives Produkt, ein Identitätselement und Inversen für alle seine Elemente zu haben, macht die Menge aller Permutationen von M. in eine Gruppe, Sym (M.); eine Permutationsgruppe.

Beispiele[edit]

Betrachten Sie den folgenden Satz G1 von Permutationen der Menge M. = {1, 2, 3, 4}:

  • e = (1) (2) (3) (4) = (1)
    • Dies ist die Identität, die triviale Permutation, die jedes Element fixiert.
  • ein = (1 2) (3) (4) = (1 2)
    • Diese Permutation vertauscht 1 und 2 und behebt 3 und 4.
  • b = (1) (2) (3 4) = (3 4)
    • Wie der vorherige, aber 3 und 4 austauschen und die anderen reparieren.
  • ab = (1 2) (3 4)
    • Diese Permutation, die die Zusammensetzung der beiden vorhergehenden ist, tauscht gleichzeitig 1 mit 2 und 3 mit 4 aus.

G1 bildet eine Gruppe, da aa = bb = e, ba = ab, und abab = e. Diese Permutationsgruppe ist als abstrakte Gruppe zur Klein-Gruppe isomorph V.4.

Betrachten Sie als weiteres Beispiel die Symmetriegruppe eines Quadrats. Die Eckpunkte eines Quadrats sollen mit 1, 2, 3 und 4 gekennzeichnet sein (gegen den Uhrzeigersinn um das Quadrat herum, beginnend mit 1 in der oberen linken Ecke). Die Symmetrien werden durch die Bilder der Eckpunkte bestimmt, die wiederum durch Permutationen beschrieben werden können. Die Drehung um 90 ° (gegen den Uhrzeigersinn) um die Mitte des Quadrats wird durch die Permutation (1234) beschrieben. Die 180 ° – und 270 ° -Drehungen sind durch (13) (24) bzw. (1432) gegeben. Die Reflexion um die horizontale Linie durch die Mitte ist durch (12) (34) gegeben und die entsprechende vertikale Linienreflexion ist (14) (23). Die Reflexion um die 1,3-Diagonale ist (24) und die Reflexion um die 2,4-Diagonale ist (13). Die einzige verbleibende Symmetrie ist die Identität (1) (2) (3) (4). Diese Permutationsgruppe ist abstrakt als Diedergruppe der Ordnung 8 bekannt.

Gruppenaktionen[edit]

In dem obigen Beispiel der Symmetriegruppe eines Quadrats „beschreiben“ die Permutationen die Bewegung der Eckpunkte des Quadrats, die durch die Gruppe der Symmetrien induziert wird. Es ist üblich zu sagen, dass diese Gruppenelemente auf die Menge der Eckpunkte des Quadrats „einwirken“. Diese Idee kann präzisiert werden, indem a formal definiert wird Gruppenaktion.[12]

Lassen G eine Gruppe sein und M. ein nicht leerer Satz. Ein Aktion von G auf M. ist eine Funktion f:: G × M.M. so dass

  • f(1, x) = x, für alle x im M. (1 ist das Identitätselement (neutral) der Gruppe G), und
  • f((G, f((h, x)) = f((gh, x), für alle G,h im G und alles x im M..

Diese letzte Bedingung kann auch so ausgedrückt werden, dass die Aktion einen Gruppenhomomorphismus aus induziert G in Sym((M.).[12] Ein solcher Homomorphismus wird a genannt (Permutations-) Darstellung von G auf M..

Für jede Permutationsgruppe die Aktion, die sendet (G, x) → G((x) heißt das natürliche Handlung von G auf M.. Dies ist die Aktion, die angenommen wird, sofern nicht anders angegeben.[12] Im Beispiel der Symmetriegruppe des Quadrats ist die Aktion der Gruppe auf die Menge der Eckpunkte die natürliche Aktion. Diese Gruppe induziert jedoch auch eine Aktion für die Menge der vier Dreiecke im Quadrat, die: t1 = 234, t2 = 134, t3 = 124 und t4 = 123. Es wirkt auch auf die beiden Diagonalen: d1 = 13 und d2 = 24.

Gruppenelement Aktion auf Dreiecken Aktion auf Diagonalen
(1) (1) (1)
(1234) ((t1t2t3t4) ((d1d2)
(13) (24) ((t1t3) (t2t4) (1)
(1432) ((t1t4t3t2) ((d1d2)
(12) (34) ((t1t2) (t3t4) ((d1d2)
(14) (23) ((t1t4) (t2t3) ((d1d2)
(13) ((t1t3) (1)
(24) ((t2t4) (1)

Transitive Aktionen[edit]

Die Aktion einer Gruppe G am Set M. wird gesagt, dass transitiv wenn für jeweils zwei Elemente s, t von M.gibt es ein Gruppenelement G so dass G((s) = t. Gleichermaßen das Set M. bildet eine einzelne Umlaufbahn unter der Wirkung von G.[13] Von den obigen Beispielen ist die Gruppe {e, (1 2), (3 4), (1 2) (3 4)} von Permutationen von {1, 2, 3, 4} nicht transitiv (kein Gruppenelement nimmt 1 bis 3) aber die Symmetriegruppe eines Quadrats ist auf den Eckpunkten transitiv.

Primitive Handlungen[edit]

Eine Permutationsgruppe G transitiv auf eine nicht leere endliche Menge einwirken M. ist imprimitiv wenn es eine nichttriviale Set-Partition von gibt M. das wird durch die Aktion von erhalten G, wobei „nicht trivial“ bedeutet, dass die Partition weder die Partition in Singleton-Sets noch die Partition mit nur einem Teil ist. Ansonsten wenn G ist transitiv, bewahrt jedoch keine nichttriviale Partition von M., die Gruppe G ist Primitive.

Zum Beispiel ist die Symmetriegruppe eines Quadrats auf den Eckpunkten primitiv: Wenn sie in zyklischer Reihenfolge mit 1, 2, 3, 4 nummeriert sind, wird die Partition {{1, 3}, {2, 4}} in entgegengesetzte Paare unterteilt wird von jedem Gruppenelement beibehalten. Auf der anderen Seite die volle symmetrische Gruppe auf einer Menge M. ist immer imprimitiv.

Cayleys Satz[edit]

Jede Gruppe G kann auf sich selbst einwirken (die Elemente der Gruppe werden als Menge betrachtet M.) auf viele Arten. Insbesondere gibt es eine regelmäßige Aktion, die durch (linke) Multiplikation in der Gruppe gegeben ist. Das ist, f((G, x) = gx für alle G und x im G. Für jeden festen G, die Funktion fG((x) = gx ist eine Bijektion auf G und daher eine Permutation der Menge von Elementen von G. Jedes Element von G kann auf diese Weise und so als Permutation betrachtet werden G ist isomorph zu einer Permutationsgruppe; Dies ist der Inhalt von Cayleys Theorem.

Betrachten Sie zum Beispiel die Gruppe G1 auf das oben angegebene Set {1, 2, 3, 4} einwirken. Die Elemente dieser Gruppe seien mit bezeichnet e, ein, b und c = ab = ba. Die Aktion von G1 an sich, die im Satz von Cayley beschrieben ist, ergibt die folgende Permutationsdarstellung:

fe ↦ (e) (ein) (b) (c)
fein ↦ (ea) (bc)
fb ↦ (eb) (ac)
fc ↦ (ec) (ab).

Isomorphismen von Permutationsgruppen[edit]

Wenn G und H. sind zwei Permutationsgruppen auf Mengen X. und Y. mit Aktionen f1 und f2 jeweils sagen wir das dann G und H. sind Permutation isomorph (oder isomorph als Permutationsgruppen) wenn es eine bijektive Karte gibt λ :: X.Y. und ein Gruppenisomorphismus ψ :: GH. so dass

λ((f1((G, x)) = f2((ψ((G), λ((x)) für alle G im G und x im X..[14]

Wenn X. = Y. das ist äquivalent zu G und H. als Untergruppen von Sym konjugiert sein (X.).[15] Der Sonderfall wo G = H. und ψ Ist die Identitätskarte entsteht das Konzept von äquivalente Aktionen einer Gruppe.[16]

Im oben angegebenen Beispiel für die Symmetrien eines Quadrats entspricht die natürliche Wirkung auf die Menge {1,2,3,4} der Wirkung auf die Dreiecke. Die Bijektion λ zwischen den Sätzen ist gegeben durch ichtich. Die natürliche Wirkung der Gruppe G1 oben und seine Wirkung auf sich selbst (über die linke Multiplikation) sind nicht äquivalent, da die natürliche Handlung feste Punkte hat und die zweite Handlung nicht.

Oligomorphe Gruppen[edit]

Wenn eine Gruppe G wirkt auf ein Set S.kann die Wirkung natürlich auf das kartesische Produkt ausgedehnt werden S.n von S., bestehend aus n-Tupel von Elementen von S.: die Aktion eines Elements G auf der n-Tupel (s1, …, sn) ist gegeben durch

G((s1, …, sn) = (G((s1), …, G((sn)).

Die Gruppe G wird gesagt, dass oligomorph wenn die Aktion auf S.n hat nur endlich viele Bahnen für jede positive ganze Zahl n.[17][18] (Dies ist automatisch, wenn S. ist endlich, daher ist der Begriff typischerweise von Interesse, wenn S. ist unendlich.)

Das Interesse an oligomorphen Gruppen beruht teilweise auf ihrer Anwendung auf die Modelltheorie, beispielsweise wenn Automorphismen in zählbar kategorialen Theorien betrachtet werden.[19]

Geschichte[edit]

Das Studium von Gruppen entstand ursprünglich aus dem Verständnis von Permutationsgruppen.[20]Die Permutationen selbst wurden 1770 von Lagrange in seiner Arbeit über die algebraischen Lösungen von Polynomgleichungen intensiv untersucht. Dieses Thema blühte auf und Mitte des 19. Jahrhunderts existierte eine gut entwickelte Theorie der Permutationsgruppen, die Camille Jordan in seinem Buch kodifizierte Traité des Substitutions et des Équations Algébriques von 1870. Jordans Buch basierte wiederum auf den Papieren, die Évariste Galois 1832 hinterlassen hatte.

Als Cayley das Konzept einer abstrakten Gruppe einführte, war nicht sofort klar, ob es sich um eine größere Sammlung von Objekten handelte als die bekannten Permutationsgruppen (die eine andere Definition hatten als die moderne). Cayley fuhr fort zu beweisen, dass die beiden Konzepte im Satz von Cayley gleichwertig waren.[21]

Ein anderer klassischer Text, der mehrere Kapitel über Permutationsgruppen enthält, ist der von Burnside Theorie der Gruppen endlicher Ordnung von 1911.[22] Die erste Hälfte des 20. Jahrhunderts war eine Brachezeit für das Studium der Gruppentheorie im Allgemeinen, aber das Interesse an Permutationsgruppen wurde in den 1950er Jahren von H. Wielandt wiederbelebt, dessen deutsche Vorlesungsunterlagen als nachgedruckt wurden Endliche Permutationsgruppen im Jahr 1964.[23]

Siehe auch[edit]

  1. ^ Die Notationen S.M. und S.M. werden auch verwendet.
  2. ^ Rotman 2006, p. 148, Definition der Untergruppe
  3. ^ Rotman 2006, p. 149, Satz 2.69
  4. ^ Wussing, Hans (2007), Die Entstehung des abstrakten Gruppenkonzepts: Ein Beitrag zur Entstehungsgeschichte der abstrakten Gruppentheorie, Courier Dover Publications, p. 94, ISBN 9780486458687, Cauchy verwendete 1815 zum ersten Mal seine Permutationsnotation, in der die Arrangements untereinander geschrieben und beide in Klammern eingeschlossen sind.
  5. ^ insbesondere wenn die algebraischen Eigenschaften der Permutation von Interesse sind.
  6. ^
    Biggs, Norman L.; White, AT (1979). Permutationsgruppen und kombinatorische Strukturen. Cambridge University Press. ISBN 0-521-22287-7.
  7. ^ Rotman 2006, p. 107 – Beachten Sie insbesondere die Fußnote auf dieser Seite.
  8. ^

    Dixon & Mortimer 1996, p. 3 – siehe den Kommentar nach Beispiel 1.2.2

  9. ^
    Cameron, Peter J. (1999). Permutationsgruppen. Cambridge University Press. ISBN 0-521-65302-9.
  10. ^
    Jerrum, M. (1986). „Eine kompakte Darstellung von Permutationsgruppen“. J. Algorithmen. 7 (1): 60–78. doi:10.1016 / 0196-6774 (86) 90038-6.
  11. ^ Rotman 2006, p. 108
  12. ^ ein b c Dixon & Mortimer 1996, p. 5
  13. ^ Artin 1991, p. 177
  14. ^ Dixon & Mortimer 1996, p. 17
  15. ^ Dixon & Mortimer 1996, p. 18
  16. ^ Cameron 1994, p. 228
  17. ^ Cameron, Peter J. (1990). Oligomorphe Permutationsgruppen. Vorlesungsreihe der London Mathematical Society. 152. Cambridge: Cambridge University Press. ISBN 0-521-38836-8. Zbl 0813.20002.
  18. ^ Oligomorphe Permutationsgruppen – Preprint des Isaac Newton Institute, Peter J. Cameron
  19. ^ Bhattacharjee, Meenaxi; Macpherson, Dugald; Möller, Rögnvaldur G.; Neumann, Peter M. (1998). Hinweise zu unendlichen Permutationsgruppen. Vorlesungsunterlagen in Mathematik. 1698. Berlin: Springer-Verlag. p. 83. ISBN 3-540-64965-4. Zbl 0916.20002.
  20. ^ Dixon & Mortimer 1996, p. 28
  21. ^ Cameron 1994, p. 226
  22. ^ Burnside, William (1955) [1911], Theorie der Gruppen endlicher Ordnung (2. Aufl.), Dover
  23. ^ Wielandt, H. (1964), Endliche Permutationsgruppen, Akademische Presse

Verweise[edit]

  • Artin, Michael (1991), Algebra, Prentice-Hall, ISBN 0-13-004763-5
  • Cameron, Peter J. (1994), Kombinatorik: Themen, Techniken, Algorithmen, Cambridge University Press, ISBN 0-521-45761-0
  • Dixon, John D.; Mortimer, Brian (1996), Permutationsgruppen, Graduate Texts in Mathematics 163), Springer-Verlag, ISBN 0-387-94599-7
  • Rotman, Joseph J. (2006), Ein erster Kurs in abstrakter Algebra mit Anwendungen (3. Aufl.), Pearson Prentice-Hall, ISBN 0-13-186267-7

Weiterführende Literatur[edit]

  • Akos Seress. Permutationsgruppenalgorithmen. Cambridge Tracts in Mathematics, 152. Cambridge University Press, Cambridge, 2003.
  • Meenaxi Bhattacharjee, Dugald Macpherson, Rögnvaldur G. Möller und Peter M. Neumann. Hinweise zu unendlichen Permutationsgruppen. Nummer 1698 in Lecture Notes in Mathematics. Springer-Verlag, 1998.
  • Peter J. Cameron. Permutationsgruppen. LMS Student Text 45. Cambridge University Press, Cambridge, 1999.
  • Peter J. Cameron. Oligomorphe Permutationsgruppen. Cambridge University Press, Cambridge, 1990.

Externe Links[edit]