Permutationsgrupp

I matematik är en permutationsgrupp en grupp G vars element är permutationer av en given mängd M och vars gruppoperation är sammansättningen av permutationer i G (som är tänkta som bijektiva funktioner från mängden M till sig själv). Gruppen av alla permutationer av en mängd M är den symmetriska gruppen av M , ofta skriven som Sym( M ). Termen permutationsgrupp betyder alltså en undergrupp av den symmetriska gruppen. Om M = {1, 2, ..., n } så betecknas Sym( M ) vanligtvis med S _n , och kan kallas den symmetriska gruppen på n bokstäver .

Enligt Cayleys teorem är varje grupp isomorf till någon permutationsgrupp.

Det sätt på vilket elementen i en permutationsgrupp permuterar elementen i mängden kallas dess grupphandling . Gruppåtgärder har tillämpningar inom studiet av symmetrier , kombinatorik och många andra grenar av matematik , fysik och kemi.

Det populära pusslet Rubiks kub som uppfanns 1974 av Ernő Rubik har använts som en illustration av permutationsgrupper. Varje rotation av ett lager av kuben resulterar i en permutation av ytfärgerna och är en medlem av gruppen. Permutationsgruppen i kuben kallas Rubiks kubgrupp .

Grundläggande egenskaper och terminologi

Eftersom det är en undergrupp till en symmetrisk grupp, är allt som krävs för att en uppsättning permutationer ska tillfredsställa gruppens axiom och vara en permutationsgrupp att den innehåller identitetspermutationen, den omvända permutationen av varje permutation den innehåller, och är stängd under sammansättning av dess permutationer. En allmän egenskap hos ändliga grupper innebär att en ändlig icke-tom delmängd av en symmetrisk grupp återigen är en grupp om och endast om den stängs under gruppoperationen.

Graden av en grupp av permutationer av en ändlig mängd är antalet element i mängden . Ordningen för en grupp (av vilken typ som helst) är antalet element (kardinalitet) i gruppen . Enligt Lagranges teorem måste ordningen för varje ändlig permutationsgrupp av grad n dela n ! eftersom n - faktor är ordningen för den symmetriska gruppen S _n .

Notation

Huvudartikel: Permutation § Notationer

Eftersom permutationer är bijektioner av en mängd, kan de representeras av Cauchys tvåradiga notation . Denna notation listar vart och ett av elementen i M i den första raden, och för varje element, dess bild under permutationen under den i den andra raden. Om $\sigma$ är en permutation av mängden $M=\{x_{1},x_{2},\ldots ,x_{ n}\}$ sedan,

$\sigma ={\begin{pmatrix}x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\sigma (x_{1})&\sigma (x_{2}) &\sigma (x_{3})&\cdots &\sigma (x_{n})\end{pmatrix}}.$

Till exempel kan en viss permutation av mängden {1, 2, 3, 4, 5} skrivas som

$\sigma ={\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}};$

detta betyder att σ uppfyller σ (1) = 2, σ (2) = 5, σ (3) = 4, σ (4) = 3 och σ (5) = 1. Elementen i M behöver inte förekomma i någon specialordning i första raden, så samma permutation kan också skrivas som

$\sigma ={\begin{pmatrix}3&2&5&1&4\\4&5&1&2&3\end{pmatrix}}.$

Permutationer skrivs också ofta i cykelnotation ( cyklisk form ) så att givet mängden M = {1, 2, 3, 4}, en permutation g av M med g (1) = 2, g (2) = 4, g (4) = 1 och g (3) = 3 kommer att skrivas som (1, 2, 4)(3), eller mer vanligt, (1, 2, 4) eftersom 3 lämnas oförändrad; om objekten betecknas med enstaka bokstäver eller siffror kan kommatecken och mellanslag också undvaras, och vi har en notation som (124). Permutationen skriven ovan i 2-rads notation skulle skrivas i cykelnotation som $\sigma =(125)(34).$

Sammansättning av permutationer – gruppprodukten

Produkten av två permutationer definieras som deras sammansättning som funktioner, så $\sigma \cdot \pi$ är funktionen som mappar ett element x i mängden till $\ sigma (\pi (x))$ . Observera att permutationen längst till höger tillämpas på argumentet först, på grund av hur funktionssammansättningen skrivs. Vissa författare föredrar att faktorn längst till vänster agerar först, men för det ändamålet måste permutationer skrivas till höger om deras argument, ofta som en upphöjd skrift , så permutationen $\sigma$ som verkar på elementet $x$ resulterar i i bilden $x^{\sigma }$ . Med denna konvention ges produkten av $x^{\sigma \cdot \pi }=(x^{\sigma })^{\pi }$ . Detta ger dock en annan regel för att multiplicera permutationer. Denna konvention används ofta i permutationsgrupplitteraturen, men den här artikeln använder konventionen där permutationen längst till höger tillämpas först.

Eftersom sammansättningen av två bijektioner alltid ger en annan bijektion, är produkten av två permutationer återigen en permutation. I tvåradsnotation erhålls produkten av två permutationer genom att omarrangera kolumnerna i den andra (längst till vänster) permutationen så att dess första rad är identisk med den andra raden i den första (längst till höger) permutationen. Produkten kan sedan skrivas som den första raden i den första permutationen över den andra raden i den modifierade andra permutationen. Till exempel, med tanke på permutationerna,

$1&3&5\end{pmatrix} }\quad {\text{ och }}\quad Q={\begin{pmatrix}1&2&3&4&5\\5&4&3&2&1\end{pmatrix}},}$

produkten QP är:

$QP={\begin{pmatrix}1&2&3&4&5\\5&4&3&2&1\end{pmatrix}}{\begin{pmatrix}1&2&3&4&5\\\2&4&1&3&5\end{pmatrix}}={\begin{pmatrix}}={\begin{pmatrix}2&5&3&1&32&5&3&32 {pmatrix}}{\begin{pmatrix}1&2&3&4&5\\2&4&1&3&5\end{pmatrix}}={\begin{pmatrix}1&2&3&4&5\\4&2&5&3&1\end{pmatrix}}.$

Sammansättningen av permutationer, när de är skrivna i cykelnotation, erhålls genom att placera de två permutationerna (med den andra skrivna till vänster) och sedan förenkla till en disjunkt cykelform om så önskas. Således skulle ovanstående produkt ges av:

$Q\cdot P=(15)(24)\cdot (1243)=(1435).$

Eftersom funktionssammansättning är associativ , så är även produktoperationen på permutationer: $(\sigma \cdot \pi )\cdot \rho =\sigma \cdot ( \pi \cdot \rho )$ . Därför skrivs produkter av två eller flera permutationer vanligtvis utan att lägga till parenteser för att uttrycka gruppering; de skrivs också vanligtvis utan en punkt eller annat tecken för att indikera multiplikation (prickarna i föregående exempel lades till för att betona, så skulle helt enkelt skrivas som ${\displaystyle \sigma \pi \rho } )$ .

Neutralt element och inverser

Identitetspermutationen, som mappar varje element i uppsättningen till sig själv, är det neutrala elementet för denna produkt. I tvåradsnotation är identiteten

${\begin{pmatrix}1&2&3&\cdots &n\\1&2&3&\cdots &n\end{pmatrix}}.$

I cykelnotation är e = (1)(2)(3)...( n ) som enligt konventionen också betecknas med bara (1) eller till och med ().

Eftersom bijektioner har inverser , har även permutationer, och den inversa σ ⁻¹ av σ är återigen en permutation. Explicit, när σ ( x )= y har man också σ ⁻¹ ( y )= x . I tvåradsnotation kan inversen erhållas genom att byta ut de två raderna (och sortera kolumnerna om man vill att den första raden ska vara i en given ordning). Till exempel

${\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}^{-1}={\begin{pmatrix}2&5&4&3&1\\1&2&3&4&5\end{pmatrix}\end{pmatrix}\{\begin{pmatrix&4&5} \5&1&4&3&2\end{pmatrix}}.$

För att erhålla inversen av en enskild cykel, vänder vi om ordningen på dess element. Således,

$(125)^{-1}=(521)=(152).$

För att erhålla inversen av en produkt av cykler, vänder vi först om ordningen på cyklerna, och sedan tar vi inversen av varje enligt ovan. Således,

$[(125)(34)]^{-1}=(34)^{-1}(125)^{-1}=(43)(521)=(34)(152).$

Att ha en associativ produkt, ett identitetselement och inverser för alla dess element, gör uppsättningen av alla permutationer av M till en grupp , Sym( M ); en permutationsgrupp.

Exempel

Betrakta följande uppsättning G ₁ av permutationer av mängden M = {1, 2, 3, 4}:

• e = (1)(2)(3)(4) = (1)
  • Detta är identiteten, den triviala permutationen som fixar varje element.
• a = (1 2)(3)(4) = (1 2)
  • Denna permutation växlar 1 och 2 och fixar 3 och 4.
• b = (1)(2)(3 4) = (3 4)
  • Som den föregående, men byter ut 3 och 4 och fixar de andra.
• ab = (1 2)(3 4)
  • Denna permutation, som är sammansättningen av de två föregående, byter samtidigt 1 mot 2 och 3 mot 4.

G ₁ bildar en grupp, eftersom aa = bb = e , ba = ab och abab = e . Denna permutationsgrupp är, som en abstrakt grupp , Klein _- gruppen V4 .

Som ett annat exempel betrakta gruppen av symmetrier i en kvadrat . Låt hörnen på en kvadrat vara märkta 1, 2, 3 och 4 (moturs runt kvadraten som börjar med 1 i det övre vänstra hörnet). Symmetrierna bestäms av bilderna av hörnen, som i sin tur kan beskrivas med permutationer. Rotationen med 90° (moturs) kring kvadratens centrum beskrivs av permutationen (1234). 180° och 270° rotationerna ges av (13)(24) respektive (1432). Reflexionen kring den horisontella linjen genom mitten ges av (12)(34) och motsvarande vertikallinjereflektion är (14)(23). Reflexionen kring 1,3−diagonalen är (24) och reflektionen kring 2,4−diagonalen är (13). Den enda kvarvarande symmetrin är identiteten (1)(2)(3)(4). Denna permutationsgrupp är känd, som en abstrakt grupp, som den dihedriska gruppen av ordning 8.

Gruppåtgärder

Huvudartikel: Group action (matematik)

I exemplet ovan av symmetrigruppen för en kvadrat "beskriver" permutationerna rörelsen av kvadratens hörn som induceras av gruppen av symmetrier. Det är vanligt att säga att dessa gruppelement "verkar" på kvadratens hörn. Denna idé kan göras exakt genom att formellt definiera en gruppåtgärd .

Låt G vara en grupp och M en icke-tom mängd . En åtgärd av G på M är en funktion f : G × M → M så att

• f (1, x ) = x , för alla x i M (1 är identitetselementet ( neutralt) i gruppen G ), och
• f ( g , f ( h , x )) = f ( gh , x ), för alla g , h i G och alla x i M .

Detta par av villkor kan också uttryckas som att åtgärden inducerar en grupphomomorfism från G till Sym ( M ). Varje sådan homomorfism kallas en (permutations) representation av G på M .

kallas åtgärden som sänder ( g , x ) → g ( x ) den naturliga verkan av G på M . Detta är den åtgärd som antas om inte annat anges. I exemplet med kvadratens symmetrigrupp är gruppens verkan på uppsättningen av hörn den naturliga verkan. Men denna grupp inducerar också en verkan på mängden av fyra trianglar i kvadraten, vilka är: t ₁ = 234, t ₂ = 134, t ₃ = 124 och t ₄ = 123. Den verkar också på de två diagonalerna: d ₁ = 13 och d ₂ = 24.

Gruppelement	Action på trianglar	Åtgärd på diagonaler
(1)	(1)	(1)
(1234)	( t 1 t 2 t 3 t 4 )	( d 1 d 2 )
(13)(24)	( t 1 t 3 )( t 2 t 4 )	(1)
(1432)	( t 1 t 4 t 3 t 2 )	( d 1 d 2 )
(12)(34)	( t 1 t 2 )( t 3 t 4 )	( d 1 d 2 )
(14)(23)	( t 1 t 4 )( t 2 t 3 )	( d 1 d 2 )
(13)	( t 1 t 3 )	(1)
(24)	( t 2 t 4 )	(1)

Transitiva handlingar

Verkan av en grupp G på en mängd M sägs vara transitiv om det för vartannat element s , t i M finns något gruppelement g så att g ( s ) = t . På motsvarande sätt bildar mängden M en enda bana under inverkan av G . Av exemplen ovan är gruppen {e, (1 2), (3 4), (1 2)(3 4)} av permutationer av {1, 2, 3, 4} inte transitiv (inget gruppelement tar 1 till 3) men gruppen av symmetrier i en kvadrat är transitiv på hörnen.

Primitiva handlingar

Huvudartikel: Primitiv permutationsgrupp

En permutationsgrupp G som verkar transitivt på en icke-tom finit mängd M är imprimitiv om det finns någon icke-trivial uppsättningspartition av M som bevaras av åtgärden av G , där "icke-trivial" betyder att partitionen inte är partitionen i singleton-uppsättningar inte heller partitionen med bara en del. Annars, om G är transitiv men inte bevarar någon icke-trivial partition av M , är gruppen G primitiv .

Till exempel är gruppen av symmetrier för en kvadrat imprimitiva på hörnen: om de är numrerade 1, 2, 3, 4 i cyklisk ordning, då partitionen {{1, 3}, {2, 4}} i motsatta par bevaras av varje gruppelement. Å andra sidan är den fullständiga symmetriska gruppen på en mängd M alltid primitiv.

Cayleys teorem

Huvudartikel: Cayleys teorem

Vilken grupp G som helst kan agera på sig själv (de element i gruppen som betraktas som mängden M ) på många sätt. I synnerhet finns det en regelbunden åtgärd som ges av (vänster) multiplikation i gruppen. Det vill säga f ( g , x ) = gx för alla g och x i G . För varje fast g är funktionen f _g ( x ) = gx en bijektion på G och därför en permutation av mängden element i G . Varje element i G kan ses som en permutation på detta sätt och så är G isomorft till en permutationsgrupp; detta är innehållet i Cayleys teorem .

Tänk till exempel att gruppen G ₁ agerar på uppsättningen {1, 2, 3, 4} ovan. Låt elementen i denna grupp betecknas med e , a , b och c = ab = ba . Verkan av G ₁ på sig själv som beskrivs i Cayleys teorem ger följande permutationsrepresentation:

f _e ↦ ( e )( a )( b )( c )

f _a ↦ ( ea )( bc )

f _b ↦ ( eb )( ac )

f _c ↦ ( ec )( ab ).

Isomorfismer av permutationsgrupper

Om G och H är två permutationsgrupper på mängderna X och Y med åtgärder f ₁ respektive f ₂ , så säger vi att G och H är permutationsisomorfa (eller isomorfa som permutationsgrupper ) om det finns en bijektiv karta λ : X → Y och en gruppisomorfism ψ : G → H sådan att

λ ( f ₁ ( g , x )) = f ₂ ( ψ ( g ), λ ( x )) för alla g i G och x i X .

Om X = Y är detta ekvivalent med att G och H är konjugerade som undergrupper av Sym( X ). Specialfallet där G = H och ψ är identitetskartan ger upphov till begreppet ekvivalenta handlingar för en grupp.

I exemplet med symmetrierna för en kvadrat som ges ovan är den naturliga verkan på mängden {1,2,3,4} ekvivalent med verkan på trianglarna. Bijektionen λ mellan mängderna ges av i ↦ t _i . Den naturliga verkan av grupp G ₁ ovan och dess verkan på sig själv (via vänster multiplikation) är inte ekvivalenta eftersom den naturliga verkan har fixpunkter och den andra åtgärden inte har det.

Oligomorfa grupper

När en grupp G verkar på en mängd S , kan åtgärden utvidgas naturligt till den kartesiska produkten S ⁿ av S , bestående av n -tuplar av element av S : verkan av ett element g på n -tupeln ( s ₁ , ..., s _n ) ges av

g ( sl , ..., _sn ) = ( g ( sl ₎ , ..., g ( sn ) _{) .}

Gruppen G sägs vara oligomorf om verkan på S ⁿ bara har ändligt många banor för varje positivt heltal n . (Detta är automatiskt om S är ändligt, så termen är vanligtvis av intresse när S är oändlig.)

Intresset för oligomorfa grupper är delvis baserat på deras tillämpning på modellteori , till exempel när man överväger automorfismer i uträkneligt kategoriska teorier .

Historia

Huvudartikel: Historia om gruppteori

Studiet av grupper växte ursprungligen ur en förståelse av permutationsgrupper. Permutationer hade själva studerats intensivt av Lagrange 1770 i hans arbete med de algebraiska lösningarna av polynomekvationer. Detta ämne blomstrade och i mitten av 1800-talet fanns det en välutvecklad teori om permutationsgrupper, kodifierad av Camille Jordan i hans bok Traité des Substitutions et des Équations Algébriques från 1870. Jordans bok baserades i sin tur på de papper som fanns kvar. av Évariste Galois 1832.

När Cayley introducerade begreppet en abstrakt grupp var det inte omedelbart klart om detta var en större samling objekt än de kända permutationsgrupperna (som hade en annan definition än den moderna). Cayley fortsatte med att bevisa att de två begreppen var likvärdiga i Cayleys teorem.

En annan klassisk text som innehåller flera kapitel om permutationsgrupper är Burnsides Theory of Groups of Finite Order från 1911. Första hälften av 1900-talet var en träda i studien av gruppteori i allmänhet, men intresset för permutationsgrupper återupplivades i 1950-talet av H. Wielandt vars tyska föreläsningsanteckningar trycktes om som Finite Permutation Groups 1964.

Se även

• 2-transitiv grupp
• Rang 3 permutationsgrupp
• Mathieu-gruppen

Anteckningar

•   Artin, Michael (1991), Algebra , Prentice-Hall, ISBN 0-13-004763-5
•   Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms , Cambridge University Press, ISBN 0-521-45761-0
•   Dixon, John D.; Mortimer, Brian (1996), Permutation Groups , Graduate Texts in Mathematics 163), Springer-Verlag, ISBN 0-387-94599-7
•   Rotman, Joseph J. (2006), A First Course in Abstract Algebra with Applications (3:e upplagan), Pearson Prentice-Hall, ISBN 0-13-186267-7

Vidare läsning

• Akos Seress. Algoritmer för permutationsgrupp . Cambridge Tracts in Mathematics, 152. Cambridge University Press, Cambridge, 2003.
• Meenaxi Bhattacharjee, Dugald Macpherson, Rögnvaldur G. Möller och Peter M. Neumann. Anteckningar om oändliga permutationsgrupper . Nummer 1698 i föreläsningsanteckningar i matematik. Springer-Verlag, 1998.
• Peter J. Cameron . Permutationsgrupper . LMS Student Text 45. Cambridge University Press, Cambridge, 1999.
• Peter J. Cameron. Oligomorfa permutationsgrupper . Cambridge University Press, Cambridge, 1990.

externa länkar

• "Permutation group" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Alexander Hulpke. GAP-databibliotek "Transitive Permutation Groups" .