Cím: Permutációcsoportok
Szerző(k):  Pelikán József 
Füzet: 1991/április, 145 - 148. oldal  PDF file
Témakör(ök): Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Permutációcsoportok*


 

Definiáljuk először a permutáció fogalmát:
D.: A permutáció egy halmaz önmagára való kölcsönösen egyértelmű leképezése. A továbbiakban mi az {1, 2, .. . , n} halmaz permutációival foglalkozunk. A fenti definíció szemléletes jelentése, hogy egy permutáció az 1, 2, ... , n számok valamilyen sorrendje. Egy π1 permutáció természetes jelölése a következő:
 

π1=(123...na1a2a3...an),ahol{a1,a2,...,an}={1,2,...,n}.
 


Nyilvánvaló, hogy egy n elemű halmaz permutációinak száma n! Mindez önmagában elég semmitmondó, ezért vezessünk be egy permutációk közötti műveletet. Kézenfekvőnek tűnik a
 

π1=(12...na1a2...an)és aπ2=(12...nb1b2...bn)
permutációk π1π2 szorzatát a következőképpen definiálni: az 1in- re alkalmazzuk π1-et, majd az így nyert ai számra π2-t. Könnyen látható, hogy π1π2 is egy permutáció, tehát a permutációk halmaza zárt erre a műveletre nézve. A szorzás további tulajdonságai is könnyen ellenőrizhetők.
1. Asszociatív: (π1π2)π3=π1(π2π3).
2. Az ϵ=(12...n12...n) permutációt egységelemnek véve minden π-re πϵ=ϵπ=π.
3. Minden π1-re létezik pontosan egy olyan π2, hogy π1π2=π2π1=ϵ. π2=π1-1, a π1 permutáció inverze.
4. Nem kommutativ. Ezt egy példával igazoljuk:
 

(123213)(123132)(123132)(123213),

hiszen
 

(123213)(123132)=(123312),

míg
 

(123132)(123213)=(123231).

 

Tetszőleges n-re pedig a következő példát készíthetjük ezek alapján (n3):
 

π1=(123456...n213456...n)  ésπ2=(123456...n132456...n).

Az első három tulajdonság és a zártság alapján kimondhatjuk, hogy a permutációk az itt definiált szorzásra nézve csoportot alkotnak. Ezt Sn-nel jelöljük és n-ed-fokú szimmetrikus csoportnak nevezzük.
Sn-en belül a következő módon megkülönböztetünk páros és páratlan permutációkat: tekintsük a
 

1i<jn(j-i)


szorzatot. Alkalmazzuk a π permutációt minden tényezőn belül minden tagra. Így a
 

1i<jn(aj-ai)

 


szorzatot kapjuk, amelynek abszolút értéke nyilván megegyezik az előbbi szorzat abszolút értékével. A π permutációt párosnak mondjuk, ha a szorzat előjele megmarad, és páratlannak, ha a szorzat előjele megváltozik. Vegyük észre, hogy a permutációknak pontosan a fele páros, és a fele páratlan (n2) esetén. Tekintsük ugyanis a következő kölcsönösen egyértelmű megfeleltetést a páros és páratlan permutációk között: a π páratlan permutáció segítségével rendeljük a σ permutációhoz a σπ permutációt. Nyilvánvaló, hogyσ és σπ közül pontosan egy páros, és egy páratlan. Paritás szempontjából vizsgálva a szorzást, a következőket állapíthatjuk meg:

párospáros=párospáratlanpáros=páratlanpárospáratlan =páratlanpáratlanpáratlan=páros

Azonnal következik, hogy a páros permutációk halmaza a szorzásra nézve zárt, így az n!/2 db páros permutáció Sn egy részcsoportját alkotja. Ennek neve n-edfokú alternáló csoport, jelölése An.
 

*

 

Térjünk vissza a permutációk jelöléséhez. Az eddigi π=
(123...na1a2a3...an)


jelölésnél célszerűbb az úgynevezett "ciklusos'' jelölésmód: írjuk az első helyre az 1-et, majd az (i + 1)-dik helyre rendre azt a számot, amelyet a permutáció az i-dik helyen álló számhoz rendel, kivéve, ha visszajutottunk az 1-hez; ekkor zárjuk be a ciklust, és nyissunk újat a legkisebb eddig nem szereplő elemmel. Ezt addig végezzük, amíg az összes elem sorra nem kerül. Például:
 

(12345675412763)=(1573)(24)(6)

 

(Megjegyzés: Mivel minden elemnek pontosan egy "őse'' és egy "képe'' van, egy ciklus csak az első eleméhez záródhat vissza.) Ilyen jelölésmóddal a szorzás gyorsabbá és átláthatóbbá válik.
 

D.: Az olyan permutációkat, amelyek ciklusos jelölésében egy kéttagú ciklus van, a többi ciklus pedig egytagú, transzpozícióknak nevezzük. Egy transzpozició tehát két elem cseréje a továbbiak helybenhagyásával.
Ha a kéttagú ciklus két szomszédos egészből áll, szomszédos transzpozícióról beszélünk.
1.T.: Minden permutáció előáll transzpozíciók szorzataként.
Bizonyítás. A permutációk ciklusos írásmódjából következik, hogy a tételt elég egyetlen ciklusra belátni. Valóban:
 

(a1a2a3...ak)=(a1a2)(a1a3)(a1a4)...(a1ak).

 

2.T.: Minden permutáció előáll szomszédos transzpozíciók szorzataként.
Bizonyítás. Az előzőekből adódik, hogy elég a tételt transzpozíciókra belátni:
(a,a+i)=(a+i,a)=
=(a,a+1)(a+1,a+2)...(a+i-1,a+i)(a+i-1,a+i-2)(a+i-2,a+i-3)...(a+1,a).

3.T.: Minden permutáció előáll az (12) és az (12...n) permutációkból a szorzás műveletével. Ennek bizonyítása megtalálható a KöMaL 1990/7. 303. oldalán az F.2768. feladat megoldása során.
4.T.: Egy permutáció hatványaként nem állhat elő minden permutáció.
Bizonyítás. Mivel πkπl=πlπk=πl+k , egy permutáció hatványai kommutatív csoportot alkotnak; márpedig Sn(n3-ra) nem kommutatív.
A továbbiakban szükségünk lesz egy új fogalomra.
D.: π és σ konjugáltak egy H halmazban, ha létezik olyan ϱ, melyre ϱH és ϱ-1πϱ=σ.
5.T.: Ha H részcsoport, akkor a konjugáltság ekvivalencia-reláció:
1. reflexív:         ϵ-1πϵ=π;
2. szimmetrikus:        ha ϱ-1πϱ=σ,akkorϱσϱ-1=π;
3. tranzitív: ha ϱ1-1π1ϱ1=π2 és ϱ2-1π2ϱ2=π3, akkor (ϱ1ϱ2)-1π1(ϱ1ϱ2)=π3.
E tétel alapján Sn elemei diszjunkt konjugáltosztályokba rendeződnek. (Ez egyébként minden csoportra igaz.)
Felmerül a kérdés, hogy két, ciklusszerkezetével megadott permutáció mikor konjugált Sn-ben.
Legyen
π1=(a11a12...a1k1)(a21a22...a2k2)...(al1al2...alkl)

és
π2=(b11b12...b1m1)(b21b22...b2m2)...(bp1bp2...bpmp),


ahol  k1k2...kl és m1m2...mp. A π1-nek és π2-nek pontosan akkor egyezik meg a ciklusszerkezete, ha l=p és  m1=k1,m2=k2,...,mp=kl.
6.T.:  Két permutáció pontosan akkor konjugált Sn -ben, ha azonos a ciklusszerkezetük.
Bizonyítás.
1.Ha π1 és π2 konjugáltak, azaz ϱ-1π1ϱ=π2 valamilyen ϱ-ra, akkor ciklusszerkezetük megegyezik.
Írjuk fel ϱ-1-et transzpozíciók szorzataként: ϱ-1=(i1j1)(i2j2)...(ikjk). Ekkor ϱ=(ikjk)(ik-1jk-1)...(i1j1) A szorzás asszociativitása miatt elég bizonyítani, hogy π1 és (igjg)π1(igjg) ciklusszerkezete megegyezik. Ellenőrizhető, hogy ez a művelet nem csinál mást, mint az ig és a jg elemeket fölcseréli π1-ben. Így a ciklusszerkezetet nem változtatja meg.
2. Ha π1 és π2 ciklusszerkezete ugyanaz, akkor konjugáltak. A bizonyítás első részében használt elemfelcserélésekkel a π1 nyilvánvalóan átvihető π2-be. A konjugáltság a csoportelméletben mélyebb fogalmakkal van kapcsolatban:
D.: Egy H csoport olyan G részcsoportját, amely minden elemének H-beli konjugáltjait is tartalmazza, a H normális részcsoportjának vagy normálosztójának nevezzük. Minden csoportnak van két trivális normálosztója: az egységelem és maga az egész csoport.
D.: Az olyan csoportokat, amelyeknek a két triviális normálosztón kívül nincs más normálosztójuk, egyszerű csoportoknak nevezzük.
Az egyszerű csoportok a prímszámokhoz hasonló szerepet játszanak a csoportok szerkezetében. Bizonyítható, hogy An (n5 esetén)  egyszerű csoport, és ezzel van kapcsolatban az, hogy ötöd- és ennél magasabb fokú egyenletekre nincs általános megoldóképlet. (A5 a legkisebb egyszerű csoport.)
 
 

1. ábra
 

Érdekességként megadjuk a második legkisebb egyszerű csoportot: Vegyük a legkisebb, 7 pontból álló véges projektív síkot (1.ábra). Ezen 7 pont egyenestartó permutációi egyszerű csoportot alkotnak. (A kör is egyenesnek számít.)
 
Érdemes gondolkodni a következő egyszerűbb és nehezebb feladatokon:
1. Minden transzpozíció páratlan permutáció.
2. A buborékrendezés felhasználásával bizonyítsuk az 1. tételt!
3. Bizonyítsuk be a 3. tételt!
4. Mutassuk meg, hogy a kocka mozgáscsoportja izomorf S4-gyel!
*5. A dodekaéder mozgáscsoportja izomorf A5-tel!
**6. An egyszerű csoport, ha n5.
****7. An konjugáltosztályainak a száma nagyobb, mint Sn konjugáltosztályai számának a fele (n3-ra).

*A fenti előadás az Ifjúsági Matematikai Kör  Téli Ankétján hangzott el. (Lejegyezték: Kőszegi Botond és Matolcsi Máté, a Budapesti Fazekas Mihály Gimn. III. osztályos tanulói.)