Grupa permutací, grupa zbytkových tříd
Petr Pupík
1.3.2010
«□►    < o ►    < -= ►    4 -= ►       ■=       ^}C\(y
Co nás dnes čeká
O Grupa permutací
Grupa symetrií
Kongruence
O Grupa zbytkových tříd
Podgrupy
«   □   ►   <S>   4
Opakování
O Množina všech bijektivních zobrazení na konečné množině M tvoří spolu s operací skládání zobrazení grupu, které říkáme grupa permutací.
Q Je-li \M\ = n, značíme grupu permutací symbolem En, nebo §„.
O Platí, že |En| = n\.
O Každou neidentickou permutaci můžeme napsat jako součin nezávislých cyklů.
O Cyklus délky 2 nazýváme transpozice.
Q Každou permutaci můžeme napsat jako součin transpozic (cyklus délky k můžeme napsat jako součin k - 1 transpozic)
Opakování
Příklad
Uvažme permutace a,p eT7. Rozložte permutace a, p na součin nezávislých cyklů. Určete <t, p, po a■. Rozložte permutaci <r na součin transpozic.
12   3    4   5    6    7 3    4    15    7   2    6
> P
12    3   4    5    6    7 14    6    7   3   5    2
4   □   ►   4 r3>   ►   •<
Parita permutace
Definice
Řekneme, že cyklus délky k má paritu (-1
\k-1
•  Parita složení permutací je součinem parit jednotlivých permutací.
•  Permutace parity 1 se nazývá sudá, permutace parity -1 se nazývá lichá
•  Rozložíme-li permutaci na součin transpozic, z jejich počtu ihned můžeme určit paritu dané permutace.
•  Permutace a z předchozího příkladu je lichá.
Parita permutace
Paritu permutace můžeme stanovit i jiným způsobem.
Definice
Nechť je dána permutace n e Tn. Nechť i, j e {1,2,..., n}. Je-li pro / < j v permutace ir(i) > ir(j), řekneme, že dvojice (7r(/), ir(j)) tvoří v permutaci ty inverzi.
Permutace -k e Hn je sudá právě tehdy když počet inverzí permutace n je sudé číslo.
9 Zadáme-li si danou permutaci pomocí „grafu s šipkami", dostáváme počet invrezí jako počet křížení šipek.
• Permutace a z našeho příkladu má 5 inverzí.
Umocňování permutací, iverzní relace
Mocnina dané permutace a inverzní permutace k dané permutaci se snadno určí z rozkladu permutace na nezávislé cykly.
Umocníme-li cyklus délky k na k-tou (tj. složíme daný cyklus k-krát), dostaneme identitu.
•  Určeme si osmou mocninu permutace a z našeho příkladu.
•  Inverzní relace se stanoví snadno přímo ze zadání nebo z rozkladu na nezávislé cykly. Ty totiž stačí „číst odzadu".
Shodná zobrazení nechávající daný útvar na místě
Již na střední škole jste se jistě setkali se skládáním shodných zobrazení. Například zobrazíme-li libovolný útvar v osové souměrnosti podle osy o a výsledek opět zobrazíme v této osové souměrnosti, dostaneme původní útvar. Složením dvou osových souměrností s osami rovnoběžnými je posunutí a tak dále.
V mineralogii jste se jistě také setkali s krystalickými soustavami. Uvažovali jste zde jednotlivé soustavy a jejich symetrie.
< □ ► < s ► <
Shodná zobrazení nechávající daný útvar na místě
Uvažujme nyní množinu zobrazení, která nechávají daný útvar sám na sobě. U čtverce tak dostáváme:
O Identita
Q Dvě osové souměrnosti, jejichž osy procházejí středy protějších stran
O Dvě osové souměrnosti takové, že úhlopříčky leží na osách těchto souměrností
O Otočení (Rotace) o 90°, 180°, 270°. Uvědomme si, že složením libovolných dvou z těchto zobrazení dostaneme opět zobrazení, které nechá čtverec sám na sobě. Očíslujeme-li si vrcholy čtverce čísly 1,2,3,4, dokážeme libovolné zobrazení zadat jako permutaci dané čtyřprvkové množiny. Dostáváme tak podmnožinu grupy TA. Ta je zřejmě grupoidem, asociativita je zděděna z grupy 5Z4. Naše množina obsahuje neutrální prvek (identitu). Snadno se nahlédne, že také ke každému zobrazení existuje zobrazení inverzní, které také převádí čtverec sám na sebe. Dostali jsme tak uvnitř grupy 5Z4 další grupu (podgrupu grupy E4).
Grupy symetrií
Zobecníme-li naše úvahy pro libovolný pravidelný n-úhelník, dostáváme grupu symetrií, která bude obsahovat n osových souměrností a n rotací. Tuto grupu nazýváme dihedrální grupa a značíme D2n (v některých publikacích se značí Dn).
Příklad
Určete, jak vypadá grupa symetrií rovnostranného trojúhelníka.
K zamyslení
Zkuste si sami určit, jak vypadá grupa symetrií pravidelného čtyřstěnu, grupa symetrií krychle.
Grupy symetrií
Nemusíme libovolné útvary
e uvažovat pouze pravidelné n-úhelníky, ale prakticky
úh/arw
<□►  <g>  * = >  < -e ►
•f) <\(y
Kongruence
Dalším příkladem konečných (tentokrát komutativních) grup jsou grupy zbytkových tříd. Než si však řekneme, jak tyto grupy vypadají, musíme si říci něco o kongruencích.
Definice
Nechť a, b e Z, m e N. Řekneme, že a e dávají stejný zbytek po dělení číslem m.
b   (mod m), jestliže a, b
Kongruence
D	
Necht a, b O a= b Q m\(a-Q 3k eZ	g Z, m g N. Následující podmínky jsou ekvivalentní: (mod m) b) : a= b+ mk
Necht a, b, c, d g Z, me N, a= b   (moóm),c=d   (mod m) Potom platí, že
Oa + c = b + d   (mod m)
Q a- c = b- d   (mod m)
«□► < gi ► 4 ^ ► < .e ►
Kongruence
Věta (Bezoutova)
Nechť a, b e Z. Potom existují celá čísla x, y taková, že ax + by = (a, b).
Důkaz plyne z Euklidova algoritmu.
Věta (Malá Fermatova)
Nechť a, m e N, (a, p) = 1. Potom platí, že
a°~1 = 1(mod p).
Několik způsobů důkazů.
Zbytkové třídy
Relace kongruence je na množině celých čísel relací ekvivalence. Můžeme tedy uvážit rozklad příslušný této ekvivalenci. Dostáváme tak množinu tříd, kterým říkáme zbytkové třídy modulo m. Nyní budeme chtít na množině zbytkových tříd definovat nové operace sčítání a násobení. Položme
[a]m + [b]m = [a+b]m
[a]m ■ [b]m = [a ■ b]m
Uvědomme si, že tato definice je korektní.
• Označme množinu všech zbytkových tříd modulo m symbolem Zm. V anglické literatuře můžete najít označení Z/mZ. Toto označení si vysvětlíme později.
Grupa zbytkových tříd
n, +) tvoří komutativní grupu.
n, •) tvoří komutativní pologrupu s neutrálním prvkem.
4u*4í3>4  =  >1  =  t        ^       fJQ.O
Grupa invertibilních prvků
Nechť G je pologrupa s neutrálním prvkem. Označme G* všech prvků, které mají v G inverzi.
množinu
Eulerova funkce
Pokusme se nyní určit, ke kterým prvkům existuje v pologrupe (Zm, inverzní prvek a kolik prvků bude mít výsledná grupa.
Definice
Funkce y, která přiřadí přirozenému číslu m počet přirozených čísel, která jsou menší nebo rovna m a jsou s m nesoudělná, se nazývá eulerova funkce.
• ¥>(1)=1	
• <P{P) = P - 1	
• ^(p°) = (p-1)p°-1	
• Pro libovolná m, n e N, (m, n) =	= 1, platí, že
ip(m- n) = ip{m) ■ y(n).	
• ^•..pH = (Pi-1)Pľ1-1-	••(Pfc-1)Př*"1
Grupa zbytkových tříd
Nechť a, b jsou celá čísla, m přirozené. Potom existuje celé číslo x takové, že ax = b   (mod m) právě tehdy, když (a, m)\b.
Důsledek
Grupa i
mácp(m) prvků.
•  Určete, kolik prvků má grupa (Z£, •), (Z£4,
•  Určete inverzi k prvku [5]17 v grupě (Z^, •)
«□► < gi ► <.= ► <.= ►
D                                                           li	
Nechť (G, *) je grupa,	0 7^ /-/ c G. Potom /-/ y'e podgrupa grupy G
právě tehdy, když	
O Va, Ď G H : a  Ď G	H
O Va g AV : a-1 g AV	
Podgrupy
O Z je podgrupa grup Z, Q, R, C.
O Každá podgrupa Z je tvaru mZ = {ma | a g Z}.
Q R+ je podgrupa grupy R*.
O <S£n(R) je podgrupa grupy gc„{R).
O D2n je podgrupa grupy E„.
O Množina /An všech sudých permutací tvoří podgrupu Tn.
* □ ► <s> <
Podgrupy
Nechť G je grupa, K, L její podgrupy. Potom K n L je podgrupa grupy K.
Definice
Nechť M c G, potom množinu
(M)=    n    h
podgrupy h,mch nazýváme podgrupa generovaná množinou M.
4u*4í3>4  =  >1  =  t        ^       -00*0
Cyklické grupy
Nechť G je grupa, K, L její podgrupy, a e G. Potom O {KuL) = {k-l\keKJeL} Q (a) = {an\ne Z}.
Definice
Řekneme, že grupa G je cyklická, jestliže je generovaná nějakým svým prvkem.
«□► < gi ► 4 ^ ► < .e ►
Cyklické grupy
Z=(1)
,)■
D«
:([1]
(/90°,O) <[3]7>
4   □   ►   <3   ►   <