Permutační skupina - Permutation group
Algebraická struktura → Skupinová teorie Skupinová teorie |
---|
![]() |
Nekonečná dimenzionální Lieova skupina
|
v matematika, a permutační skupina je skupina G jejichž prvky jsou obměny daného soubor M a jehož skupinová operace je složení permutací v G (které jsou považovány za bijektivní funkce ze sady M pro sebe). Skupina Všechno obměny množiny M je symetrická skupina z M, často psaný jako Sym (M).[1] Termín permutační skupina tedy znamená podskupina symetrické skupiny. Li M = {1,2,...,n} pak Sym (M), symetrická skupina na n písmen je obvykle označeno Sn.
Podle Cayleyho věta, každá skupina je izomorfní do nějaké permutační skupiny.
Způsob, jakým prvky permutační skupiny permutují prvky sady, se nazývá jeho skupinová akce. Skupinové akce mají aplikace ve studiu symetrie, kombinatorika a mnoho dalších odvětví matematika, fyzika a chemie.

Základní vlastnosti a terminologie
Být a podskupina symetrické skupiny, vše, co je nezbytné pro splnění množiny permutací skupina axiomy a být permutační skupinou je, že obsahuje permutaci identity, inverzní permutaci každé permutace, kterou obsahuje, a být uzavřena pod složení jeho obměn.[2] Obecná vlastnost konečných skupin znamená, že konečná neprázdná podmnožina symetrické skupiny je opět skupinou právě tehdy, když je uzavřena v rámci operace skupiny.[3]
The stupeň skupiny permutací a konečná množina je počet prvků v sadě. The objednat skupiny (jakéhokoli typu) je počet prvků (mohutnost) ve skupině. Podle Lagrangeova věta, pořadí jakékoli konečné permutační skupiny stupňů n musí se rozdělit n! od té doby n-faktoriál je pořadí symetrické skupiny Sn.
Zápis
Protože permutace jsou bijekce množiny, mohou být reprezentovány Cauchy je dvouřádkový zápis.[4] V tomto zápisu je uveden seznam všech prvků prvku M v prvním řádku a pro každý prvek jeho obraz pod permutací pod ním ve druhém řádku. Li je obměna množiny pak,
Například konkrétní permutaci množiny {1,2,3,4,5} lze zapsat jako:
tohle znamená tamto σ splňuje σ(1)=2, σ(2)=5, σ(3)=4, σ(4) = 3 a σ(5) = 1. Prvky M nemusí se objevit v žádném zvláštním pořadí v prvním řádku. Tuto permutaci lze také zapsat jako:
Často jsou také zapsány obměny cyklická notace (cyklická forma)[5] tak to vzhledem k souboru M = {1,2,3,4}, permutace G z M s G(1) = 2, G(2) = 4, G(4) = 1 a G(3) = 3 bude zapsáno jako (1,2,4) (3), nebo častěji (1,2,4), protože 3 zůstane beze změny; jsou-li objekty označeny jednoduchými písmeny nebo číslicemi, lze také upustit od čárek a mezer a máme notaci jako (124). Permutace napsaná výše ve dvouřádkovém zápisu by byla zapsána v cyklickém zápisu jako
Složení permutací - skupinový produkt
Součin dvou permutací je definován jako jejich složení jako funkce, tak je funkce, která mapuje jakýkoli prvek X sady na . Všimněte si, že permutace zcela vpravo se nejprve použije na argument,[6][7] kvůli způsobu psaní aplikace funkcí. Někteří autoři dávají přednost levému faktoru,[8][9][10]ale za tímto účelem musí být permutace zapsány do že jo jejich argumentu, často jako horní index, takže permutace působící na prvek výsledky v obraze . S touto konvencí je produkt dán vztahem . To však dává a odlišný pravidlo pro násobení permutací. Tato konvence se běžně používá v literatuře o permutační skupině, ale tento článek používá konvenci, kde je nejprve použita permutace úplně vpravo.
Protože složení dvou bijection vždy dává další bijection, produkt dvou permutací je opět permutace. V dvouřádkovém zápisu se produkt dvou permutací získá přeuspořádáním sloupců druhé (vlevo) permutace tak, aby její první řada byla totožná s druhou řadou první (úplně vpravo) permutace. Produkt lze poté zapsat jako první řádek první permutace přes druhý řádek upravené druhé permutace. Například vzhledem k permutacím
produkt QP je:
Složení permutací, pokud jsou psány v cyklické formě, se získá juxtapozicí dvou permutací (přičemž druhá je napsána vlevo) a následným zjednodušením na disjunktní formu cyklu, je-li to žádoucí. V cyklickém zápisu by tedy výše uvedený produkt byl dán vztahem:
Od té doby složení funkce je asociativní, tak je operace produktu na permutacích: . Proto jsou produkty dvou nebo více permutací obvykle psány bez přidání závorek k vyjádření seskupení; jsou také obvykle psány bez tečky nebo jiného znaménka k označení násobení (tečky předchozího příkladu byly přidány pro zdůraznění, takže by byly jednoduše napsány jako ).
Neutrální prvek a inverze
Permutace identity, která mapuje každý prvek sady na sebe, je pro tento produkt neutrálním prvkem. Ve dvouřádkovém zápisu je identita
V cyklickém zápisu E = (1)(2)(3)...(n), který je podle konvence také označen pouze (1) nebo dokonce ().[11]
Od té doby bijekce mít inverze, tak i permutace a inverzní σ−1 z σ je opět obměna. Výslovně, kdykoli σ(X)=y jeden také má σ−1(y)=X. Ve dvouřádkovém zápisu lze inverzi získat záměnou dvou řádků (a tříděním sloupců, pokud si přejete, aby první řádek byl v daném pořadí). Například
Abychom získali inverzi jednoho cyklu, obrátíme pořadí jeho prvků. Tím pádem,
Abychom získali inverzi produktu cyklů, nejprve obrátíme pořadí cyklů a potom převezmeme inverzi každého z nich, jak je uvedeno výše. Tím pádem,
Mít asociativní produkt, prvek identity a inverze pro všechny jeho prvky, vytváří sadu všech permutací M do skupina, Sym (M); permutační skupina.
Příklady
Zvažte následující sadu G1 permutací souboru M = {1, 2, 3, 4}:
- E = (1)(2)(3)(4) = (1)
- Toto je identita, triviální permutace, která opravuje každý prvek.
- A = (1 2)(3)(4) = (1 2)
- Tato permutace zaměňuje 1 a 2 a opravuje 3 a 4.
- b = (1)(2)(3 4) = (3 4)
- Stejně jako předchozí, ale výměna 3 a 4 a oprava ostatních.
- ab = (1 2)(3 4)
- Tato permutace, která je složením předchozích dvou, si vyměňuje současně 1 s 2 a 3 se 4.
G1 tvoří skupinu, protože aa = bb = E, ba = ab, a abab = E. Tato permutační skupina je izomorfní, jako abstraktní skupina, do Kleinová skupina PROTI4.
Jako další příklad zvažte skupina symetrií čtverce. Nechte vrcholy čtverce označit 1, 2, 3 a 4 (proti směru hodinových ručiček kolem čtverce počínaje 1 v levém horním rohu). Symetrie jsou určeny obrazy vrcholů, které lze zase popsat permutacemi. Rotace o 90 ° (proti směru hodinových ručiček) kolem středu čtverce je popsána permutací (1234). Rotace o 180 ° a 270 ° jsou dány (13) (24) a (1432). Odraz kolem vodorovné čáry procházející středem je dán vztahem (12) (34) a odpovídající odraz svislé čáry je (14) (23). Odraz kolem 1,3 − úhlopříčky je (24) a odraz kolem 2,4 − úhlopříčky je (13). Jedinou zbývající symetrií je identita (1) (2) (3) (4). Tato permutační skupina je abstraktně známá jako dihedrální skupina objednávky 8.
Skupinové akce
Ve výše uvedeném příkladu skupiny symetrie čtverce permutace „popisují“ pohyb vrcholů čtverce vyvolaný skupinou symetrií. Je běžné říci, že tyto prvky skupiny „působí“ na množinu vrcholů čtverce. Tuto myšlenku lze zpřesnit formálním definováním a skupinová akce.[12]
Nechat G být skupina a M neprázdné soubor. An akce z G na M je funkce F: G × M → M takhle
- F(1, X) = X, pro všechny X v M (1 je identita (neutrální) prvek skupiny G), a
- F(G, F(h, X)) = F(gh, X), pro všechny G,h v G a všechno X v M.
Tuto poslední podmínku lze také vyjádřit slovy, že akce indukuje skupinový homomorfismus G do Sym(M).[12] Každý takový homomorfismus se nazývá a (permutační) reprezentace z G na M.
U jakékoli permutační skupiny akce, která odesílá (G, X) → G(X) se nazývá přirozená akce z G na M. Toto je akce, která se předpokládá, pokud není uvedeno jinak.[12] V příkladu skupiny symetrie čtverce je akce skupiny na množině vrcholů přirozenou akcí. Tato skupina však také vyvolává akci na množině čtyř trojúhelníků ve čtverci, které jsou: t1 = 234, t2 = 134, t3 = 124 a t4 = 123. Působí také na dvě úhlopříčky: d1 = 13 a d2 = 24.
Skupinový prvek | Akce na trojúhelníky | Akce na úhlopříčkách |
---|---|---|
(1) | (1) | (1) |
(1234) | (t1 t2 t3 t4) | (d1 d2) |
(13)(24) | (t1 t3)(t2 t4) | (1) |
(1432) | (t1 t4 t3 t2) | (d1 d2) |
(12)(34) | (t1 t2)(t3 t4) | (d1 d2) |
(14)(23) | (t1 t4)(t2 t3) | (d1 d2) |
(13) | (t1 t3) | (1) |
(24) | (t2 t4) | (1) |
Přechodná opatření
Činnost skupiny G na setu M se říká, že je tranzitivní pokud pro každé dva prvky s, t z M, existuje nějaký skupinový prvek G takhle G(s) = t. Ekvivalentně, sada M tvoří singl obíhat v rámci akce G.[13] Z příkladů výše, skupina {e, (1 2), (3 4), (1 2) (3 4)} permutací {1, 2, 3, 4} není přechodná (žádný prvek skupiny nezabere 1 až 3), ale skupina symetrií čtverce je přechodná na vrcholech.
Primitivní akce
Permutační skupina G přechodně působící na neprázdnou konečnou množinu M je pozitivní pokud existuje nějaký netriviální nastavit oddíl z M která je zachována působením G, kde "netriviální" znamená, že oddíl není oddílem do jedináček sady ani oddíl pouze s jednou částí. Jinak, pokud G je tranzitivní, ale nezachovává žádný netriviální oddíl M, skupina G je primitivní.
Například skupina symetrií čtverce je na vrcholech primitivní: pokud jsou očíslovány 1, 2, 3, 4 v cyklickém pořadí, pak oddíl {{1, 3}, {2, 4}} do protilehlých párů je chráněn každým prvkem skupiny. Na druhou stranu celá symetrická skupina na množině M je vždy pozitivní.
Cayleyho věta
Libovolná skupina G může působit sám na sebe (prvky skupiny, o nichž se uvažuje jako o množině M) v mnoha ohledech. Zejména existuje a pravidelná akce dáno (vlevo) násobením ve skupině. To znamená F(G, X) = gx pro všechny G a X v G. Pro každou pevnou G, funkce FG(X) = gx je bijection na G a tedy permutace množiny prvků G. Každý prvek G lze tímto způsobem považovat za permutaci G je izomorfní s permutační skupinou; toto je obsah Cayleyho věta.
Zvažte například skupinu G1 působící na množinu {1, 2, 3, 4} uvedenou výše. Nechť jsou prvky této skupiny označeny E, A, b a C = ab = ba. Akce G1 sám o sobě popsaný v Cayleyho teorému dává následující permutační reprezentaci:
- FE ↦ (E)(A)(b)(C)
- FA ↦ (ea)(před naším letopočtem)
- Fb ↦ (např)(ac)
- FC ↦ (ec)(ab).
Izomorfismy permutačních skupin
Li G a H jsou dvě permutační skupiny na množinách X a Y s akcemi F1 a F2 respektive, pak to říkáme G a H jsou permutace izomorfní (nebo izomorfní jako permutační skupiny) pokud existuje a bijektivní mapa λ : X → Y a a skupinový izomorfismus ψ : G → H takhle
- λ(F1(G, X)) = F2(ψ(G), λ(X)) pro všechny G v G a X v X.[14]
Li X = Y to je ekvivalentní k G a H konjugovat jako podskupiny Sym (X).[15] Zvláštní případ, kdy G = H a ψ je mapa identity dává vzniknout konceptu ekvivalentní akce skupiny.[16]
V příkladu výše uvedených symetrií čtverce je přirozená akce na množině {1,2,3,4} ekvivalentní akci na trojúhelnících. Bijekce λ mezi množinami je dán vztahem i ↦ ti. Přirozené působení skupiny G1 výše a jeho působení na sebe (pomocí multiplikace vlevo) nejsou ekvivalentní, protože přirozená akce má pevné body a druhá akce ne.
Oligomorfní skupiny
Když skupina G působí na a soubor Slze akci přirozeně rozšířit na kartézský součin Sn z S, skládající se z n- n-tice prvků S: působení prvku G na n-tuple (s1, ..., sn) darováno
- G(s1, ..., sn) = (G(s1), ..., G(sn)).
Skupina G se říká, že je oligomorfní pokud je akce zapnuta Sn má jen konečně mnoho drah pro každé kladné celé číslo n.[17][18] (Toto je automatické, pokud S je konečný, takže termín je obvykle zajímavý, když S je nekonečný.)
Zájem o oligomorfní skupiny je částečně založen na jejich aplikaci na teorie modelů, například při zvažování automorfismy v spočítatelné kategorické teorie.[19]
Dějiny
Studium skupiny původně vyrostl z pochopení permutačních skupin.[20] Permutace byli sami intenzivně studováni Lagrange v roce 1770 ve své práci o algebraických řešeních polynomiálních rovnic. Tento předmět vzkvétal a do poloviny 19. století existovala rozvinutá teorie permutačních skupin, kterou kodifikoval Camille Jordan ve své knize Traité des Substitutions et des Équations Algébriques z roku 1870. Jordanova kniha zase vycházela z papírů, které zanechaly Évariste Galois v roce 1832.
Když Cayley představil koncept abstraktní skupiny, nebylo okamžitě jasné, zda se jedná o větší sbírku objektů než známé permutační skupiny (které měly definici odlišnou od moderní). Cayley pokračoval dokázat, že oba pojmy byly ekvivalentní v Cayleyho teorém.[21]
Další klasický text obsahující několik kapitol o permutačních skupinách je Burnside je Teorie skupin konečných objednávek z roku 1911.[22] První polovina dvacátého století byla obecným obdobím ve studiu teorie grup, ale zájem o permutační skupiny byl v 50. letech oživen H. Wielandt jehož německé skripty byly přetištěny jako Skupiny konečné permutace v roce 1964.[23]
Viz také
Poznámky
- ^ Zápisy SM a SM jsou také používány.
- ^ Rotman 2006, str. 148, Definice podskupiny
- ^ Rotman 2006, str. 149, tvrzení 2.69
- ^ Wussing, Hans (2007), Genesis konceptu abstraktní skupiny: Příspěvek k historii vzniku teorie abstraktní skupiny Publikace Courier Dover, s. 94, ISBN 9780486458687,
Cauchy použil svoji permutační notaci - ve které jsou ujednání napsána pod sebou a obě jsou uzavřena v závorkách - poprvé v roce 1815.
- ^ zvláště když jsou zajímavé algebraické vlastnosti permutace.
- ^ Biggs, Norman L .; White, A. T. (1979). Permutační skupiny a kombinatorické struktury. Cambridge University Press. ISBN 0-521-22287-7.
- ^ Rotman 2006, str. 107 - všimněte si zejména poznámky pod čarou na této stránce.
- ^ Dixon a Mortimer 1996, str. 3 - viz komentář za příkladem 1.2.2
- ^ Cameron, Peter J. (1999). Permutační skupiny. Cambridge University Press. ISBN 0-521-65302-9.
- ^ Jerrum, M. (1986). Msgstr "Kompaktní zastoupení permutačních skupin". J. Algoritmy. 7 (1): 60–78. doi:10.1016/0196-6774(86)90038-6.
- ^ Rotman 2006, str. 108
- ^ A b C Dixon a Mortimer 1996, str. 5
- ^ Artin 1991, str. 177
- ^ Dixon a Mortimer 1996, str. 17
- ^ Dixon a Mortimer 1996, str. 18
- ^ Cameron 1994, str. 228
- ^ Cameron, Peter J. (1990). Oligomorfní permutační skupiny. Série přednášek London Mathematical Society. 152. Cambridge: Cambridge University Press. ISBN 0-521-38836-8. Zbl 0813.20002.
- ^ Oligomorfní permutační skupiny - předtisk Isaaca Newtonova institutu, Peter J. Cameron
- ^ Bhattacharjee, Meenaxi; Macpherson, Dugald; Möller, Rögnvaldur G .; Neumann, Peter M. (1998). Poznámky k nekonečným permutačním skupinám. Přednášky z matematiky. 1698. Berlín: Springer-Verlag. p. 83. ISBN 3-540-64965-4. Zbl 0916.20002.
- ^ Dixon a Mortimer 1996, str. 28
- ^ Cameron 1994, str. 226
- ^ Burnside, William (1955) [1911], Teorie skupin konečných objednávek (2. vyd.), Dover
- ^ Wielandt, H. (1964), Skupiny konečné permutace, Academic Press
Reference
- 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), Permutační skupiny, Postgraduální texty z matematiky 163), Springer-Verlag, ISBN 0-387-94599-7
- Rotman, Joseph J. (2006), První kurz v abstraktní algebře s aplikacemi (3. vyd.), Pearson Prentice-Hall, ISBN 0-13-186267-7
Další čtení
- Akos Seress. Algoritmy permutačních skupin. Cambridge Tracts in Mathematics, 152. Cambridge University Press, Cambridge, 2003.
- Meenaxi Bhattacharjee, Dugald Macpherson, Rögnvaldur G. Möller a Peter M. Neumann. Poznámky k nekonečným permutačním skupinám. Číslo 1698 v přednáškách z matematiky. Springer-Verlag, 1998.
- Peter J. Cameron. Permutační skupiny. LMS Student Text 45. Cambridge University Press, Cambridge, 1999.
- Peter J. Cameron. Oligomorfní permutační skupiny. Cambridge University Press, Cambridge, 1990.
externí odkazy
- „Permutační skupina“, Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]
- Alexander Hulpke. Knihovna dat GAP „Transitive Permutation Groups“.