Grupy permutací OOOOOO Grupy symetrií oooooooooooc Matematika IV - 2. přednáška Základy teorie grup Michal Bulant Masarykova univerzita Fakulta informatiky 2. 3. 2011 Grupy symetrií oooooooooooc Obsah přednášky O Grupy permutací O Grupy symetrií Grupy permutací Grupy symetrií oooooo oooooooooooc Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. a Predmetové záložky v IS MU Grupy permutací OOOOOO Doporučené zdroje Grupy symetrií oooooooooooc • Martin Panák, Jan Slovák, Drsná matematika, e-text. a Predmetové záložky v IS MU • Jiří Rosický, Algebra, PřF MU, 2002. • Peter J. Cameron. Introduction to algebra, Oxford University Press, 2001, 295 s. (Dostupné v knihovně PřF). Grupy symetrií oooooooooooc Plán přednášky Q Grupy permutací Grupy permutací •ooooo Grupy symetrií oooooooooooc Opakovaní minulé přednášky • grupoid (G, •) je množina G s binární operací • Grupy permutací •ooooo Grupy symetrií oooooooooooc Opakovaní minulé přednášky • grupoid (G, •) je množina G s binární operací • • pologrupa (G, •) je množina G s asociativní binární operací • Grupy permutací •ooooo Grupy symetrií oooooooooooc Opakovaní minulé přednášky • grupoid (G, •) je množina G s binární operací • • pologrupa (G, •) je množina G s asociativní binární operací • • monoid (G,) je pologrupa (G,) s jednotkovým (neutrálním) prvkem1 1 Raděj i než jednotka používejme jednotkový prvek - důvod uvidíme později. Někdy se tomuto prvku rovněž říká jednička, c Grupy permutací •ooooo Grupy symetrií oooooooooooc Opakovaní minulé přednášky • grupoid (G, •) je množina G s binární operací • • pologrupa (G, •) je množina G s asociativní binární operací • • monoid (G,) je pologrupa (G,) s jednotkovým (neutrálním) prvkem1 • grupa (G, •) je monoid, ve kterém má každý prvek inverzi 1 Raděj i než jednotka používejme jednotkový prvek - důvod uvidíme později. Někdy se tomuto prvku rovněž říká jednička, c Grupy permutací •ooooo Grupy symetrií oooooooooooc Opakovaní minulé přednášky • grupoid (G, •) je množina G s binární operací • • pologrupa (G, •) je množina G s asociativní binární operací • • monoid (G,) je pologrupa (G,) s jednotkovým (neutrálním) prvkem1 • grupa (G, •) je monoid, ve kterém má každý prvek inverzi • komutativní grupa (grupoid, pologrupa, monoid apod.), je taková grupa (grupoid, ...), že operace • je komutativní. Často se v prípade komutativních grup setkáte rovněž s pojmem abelovská grupa. 1 Raděj i než jednotka používejme jednotkový prvek - důvod uvidíme později. Někdy se tomuto prvku rovněž říká jednička, c Grupy permutací o«oooo Grupy symetrií oooooooooooc Permutace - opakování • Množina bijekcí na množině M (konečné nebo nekonečné) tvoří spolu s operací skladaní zobrazení grupu, tzv. grupu permutací. • Je-li M konečná n prvková množina, pak tuto grupu značíme obvykle Sn nebo Z„, a platí |Z„| = n!. • Každou permutaci lze zapsat jako součin nezávislých cyklů a jako součin (obecně nikoliv nezávislých) transpozic (cykly délky 2). • Každá permutace má jednoznačně přiřazenou sudou nebo lichou paritu (podle počtu transpozic na něž se rozkládá nebo též podle počtu tzv. inverzí). Grupy permutací oo«ooo Grupy symetrií oooooooooooc Rozklad na nezávislé cykly Každá permutace a rozkládá množinu M na disjunktní sjednocení maximálních invariantních podmnožin Mx, které dostaneme tak, že postupně vybíráme dosud nezpracované prvky x G M a do třídy rozkladu Mx přidáváme všechny akce iterací uk(x), k = 1, 2,..., dokud není ak(x) = x. Grupy permutací oo«ooo Grupy symetrií oooooooooooc Rozklad na nezávislé cykly Každá permutace a rozkládá množinu M na disjunktní sjednocení maximálních invariantních podmnožin Mx, které dostaneme tak, že postupně vybíráme dosud nezpracované prvky x G M a do třídy rozkladu Mx přidáváme všechny akce iterací uk(x), k = 1, 2,..., dokud není ak(x) = x. Každou permutaci tak dostáváme jako složení jednodušších permutací, tzv. cyklů, které se chovají jako identická permutace vně Mx a tak jako a na Mx. Grupy permutací oo«ooo Grupy symetrií oooooooooooc Rozklad na nezávislé cykly Každá permutace a rozkládá množinu M na disjunktní sjednocení maximálních invariantních podmnožin Mx, které dostaneme tak, že postupně vybíráme dosud nezpracované prvky x G M a do třídy rozkladu Mx přidáváme všechny akce iterací uk(x), k = 1, 2,..., dokud není ak(x) = x. Každou permutaci tak dostáváme jako složení jednodušších permutací, tzv. cyklů, které se chovají jako identická permutace vně Mx a tak jako a na Mx. Pokud přitom očíslujeme prvky v Mx jako pořadí (1, 2,..., \MX\) tak aby / odpovídalo každou permutaci napsat jako složení transpozic sousedních prvků. To, jestli potřebujeme sudý nebo lichý počet permutací, je na našich volbách nezávislé. Grupy permutací ooo«oo Grupy symetrií oooooooooooc Nejjednodušší cykly jsou jednoprvkové pevné body permutace a. Dvouprvkové (x, každou permutaci napsat jako složení transpozic sousedních prvků. To, jestli potřebujeme sudý nebo lichý počet permutací, je na našich volbách nezávislé. Máme proto dobře definováno zobrazení sgn : Zm —> Z2 = {±1}, tzv. paritu permutace. Dokázali jsme si znovu tvrzení, která jsme již využívali při studiu determinantů: Grupy permutací oooo»o Grupy symetrií oooooooooooc Věta Každá permutace konečné množiny je složením cyklů. Cyklus délky £ lze vyjádřit jako složení £ — 1 transpozic. Parita cyklu délky £ je (—l)^-1. Parita složení permutací je součinem parit jednotlivých permutací, tzn. že zobrazení sgn převádí složení permutací a o t na součin sgn a ■ sgn r v komutativní grupě Z2 (nebo jinak vyjádřeno, v grupě {1,-1} s obvyklým násobením. Grupy permutací 00000« Grupy symetrií oooooooooooc Příklad Jsou dány permutace f, g, h e 5ľg předpisem /l 2345678 9\ V6 45237198/ (1 2345678 9\ . r *=\,2 6 5 1 9 7 8 3 4J' h = f ° Q Napište permutace f,g a /7 jako součin (tj. složení) navzájem nezávislých cyklů. Q Určete paritu permutací f,g a /7. O Spočtěte permutaci f2011 o g2011 a napište ji jako součin navzájem nezávislých cyklů. O Určete počet inverzí permutace f. Grupy permutací OOOOOO Plán přednášky Grupy symetrií oooooooooooc Q Grupy symetrií Grupy permutací OOOOOO Grupy symetrií •ooooooooooc Uvažme ohraničený rovinný obrazec, např. rovnostranný trojúhelník. Ptáme se, jak moc jsou symetrické? 1 Grupy permutací OOOOOO Grupy symetrií •ooooooooooc Uvažme ohraničený rovinný obrazec, např. rovnostranný trojúhelník. Ptáme se, jak moc jsou symetrické? Tzn. vůči kterým trasformacím (zachovávajícím velikost) jsou invariantní? Všechny symetrie pevně zvoleného útvaru budou vždy tvořit grupu (většinou pouze s jediným prvkem, identickým zobrazením). Grupy permutací Grupy symetrií oooooo o«oooooooooc Symetrie rovnostranného trojúhelníku Symetrií nacházíme několik: můžeme rotovat o 7r/3 nebo můžeme zrcadlit vůči osám stran. Grupy permutací OOOOOO Symetrie rovnostranného trojúhelníku Grupy symetrií o«oooooooooc Symetrií nacházíme několik: můžeme rotovat o tt/3 nebo můžeme zrcadlit vůči osám stran. Abychom dostali celou grupu, musíme přidat všechna složení takovýchto transformací. Víme z dřívějška, že složení dvou zrcadlení je vždy otočením. Složení takových zrcadlení v opačném pořadí dá otočení o stejný úhel, ale s opačnou orientací. V našem případě tedy zrcadlení kolem dvou různých os vygenerují postupnou opakovanou aplikací všechny symetrie, který bude dohromady šest. Grupy permutací OOOOOO Grupy symetrií OO0OOOOOOOOC Jestliže si umístíme trojúhelník v souřadnicích jako na obrázku, bude našich šest transformací zadáno maticemi Sestavením tabulky pro násobení, tak jak jsme ji udělali pro grupu permutací Z 3 obdržíme právě stejný výsledek. Grupy permutac OOOOOO Grupy symetrií ooo«oooooooc a b c d e f a b c d e f b c a e f d c a b f d e d f e a c b e d f b a c f e d c b a Grupy permutací Grupy symetrií oooooo oooo»ooooooc Dihedrální grupy Obdobně umíme nacházet grupy symetrií s k různými rotacemi a k zrcadleními. Stačí si k tomu vzít pravidelný /c-úhelník. Takové grupy symetrií se často označují jako grupy Dik a říká se jim dihedrální grupy řádu 2k (někdy též např D(k)). Grupy permutací OOOOOO Dihedrální grupy Grupy symetrií oooo»ooooooc Obdobně umíme nacházet grupy symetrií s k různými rotacemi a k zrcadleními. Stačí si k tomu vzít pravidelný /c-úhelník. Takové grupy symetrií se často označují jako grupy Dik a říká se jim dihedrální grupy řádu 2k (někdy též např D(k)). Tyto grupy jsou nekomutativní pro všechny k > 3. Grupy permutací Grupy symetrií oooooo ooooo«oooooc Cyklické grupy Stejně tak lze snadno najít obrazce, které mají pouze rotační symetrie a jde tedy o komutativní grupy, které se v chemii značí jako Ck- Říkáme jim cyklické grupy řádu k. K tomu postačí např. uvažovat pravidelný mnohoúhelník, u kterého nesymetricky ale pořád stejně pozměníme chování hran. Grupy permutací OOOOOO Grupy symetrií oooooo«ooooc Příklad • grupa symetrií čtverce D% má 8 prvků (4 osové symetrie, 3 netriviální rotace a identita) a lze ji chápat jako podgrupu Z4 (kam se zobrazují vrcholy?) • grupa symetrií čtyřstěnu je celá Z4, pokud symetrie omezíme pouze na ty, které zachovávají orientaci, dostaneme podgrupu A4 < Z4 sudých permutací. Grupy permutací Grupy symetrií oooooo ooooooo«oooc Klasifikace symetrií Věta Nechi je M ohraničená množina v rovině R2. Pak grupa jejich symetrií je buď triviálni nebo jedna z grup Ck, D^k, s k > 1. Grupy permutací OOOOOO Grupy symetrií oooooooo«ooc Podpologrupy a podgrupy Definice Je-li (A, •) grupa (prípadne pologrupa), pak její podmnožinu B c A, která je uzavřená vůči zúžení operace • a zároveň je spolu s touto operací grupou (resp. pologrupou) , nazýváme podgrupa (resp. podpologrupa) v (A, •). Grupy permutací OOOOOO Grupy symetrií oooooooo«ooc Podpologrupy a podgrupy Definice Je-li (A, •) grupa (prípadne pologrupa), pak její podmnožinu B c A, která je uzavřená vůči zúžení operace • a zároveň je spolu s touto operací grupou (resp. pologrupou) , nazýváme podgrupa (resp. podpologrupa) v (A, •). Věta Necht (G, o) grupa. Pak 0 ^ H c G je její podgrupa právě tehdy, když O Va, b G H : a o b G H; Q Va G W : a"1 G W. Grupy permutací OOOOOO Grupy symetrií oooooooo«ooc Podpologrupy a podgrupy Definice Je-li (A, •) grupa (prípadne pologrupa), pak její podmnožinu B c A, která je uzavřená vůči zúžení operace • a zároveň je spolu s touto operací grupou (resp. pologrupou) , nazýváme podgrupa (resp. podpologrupa) v (A, •). Věta Necht (G, o) grupa. Pak 0 ^ H c G je její podgrupa právě tehdy, když O y a, b G H : a o b G H; q Va G H : a-1 G H._ Snadno se navíc vidí, že obě podmínky v předchozí větě lze shrnout do jediné: Va, b G H : a o b'1 G H. Grupy permutací OOOOOO Grupy symetrií ooooooooo»oc Příklad ©Zje podgrupa aditivních grup Z,Q, R, C. O Všechny podgrupy (Z, +) jsou vyčerpány množinami mZ. ô (/?+,•)<(/?*,•)■ O Množina An všech sudých permutací na n-prvkové množině je podgrupou Zn. Q SLn(R) < GLn{R). Grupy permutací Grupy symetrií oooooo oooooooooo«c Podgrupa generovaná množinou Jsou-li K, L podgrupy grupy G, je zřejmě i jejich průnik (nikoliv ovšem sjednocení!) podgrupou G. Totéž zřejmě dokonce platí i libovolný (třeba nekonečný) systém podmnožin. Grupy permutací OOOOOO Grupy symetrií oooooooooo«c Podgrupa generovaná množinou Jsou-li K, L podgrupy grupy G, je zřejmě i jejich průnik (nikoliv ovšem sjednocení!) podgrupou G. Totéž zřejmě dokonce platí i pro libovolný (třeba nekonečný) systém podmnožin. Odtud plyne následující definice: Definice Je-li M libovolná podmnožina grupy G, pak (M}= f) H M. • Podobně (Zs, +) = (1) = (3) = (5) = (7). Grupy permutací OOOOOO Grupy symetrií ooooooooooo* Příklad • Z = (1). • V (Zm,+) je Zm = <[l]m)- • Podobně (Zs, +) = (1) = (3) = (5) = (7). . (Z7V) = (3) = (5) Grupy permutací OOOOOO Grupy symetrií ooooooooooo* Příklad • Z = (1). • V (Zm,+) je Zm = ([l]m). • Podobně (Z8, +) = (1) = (3) = (5) = (7). • (Z7V) = (3) = (5). • (Zg,*) není cyklická. Grupy permutací OOOOOO Grupy symetrií ooooooooooo* Příklad • Z = (1). • V (Zm,+) je Zm = ([l]m). • Podobně (Z8, +) = (1) = (3) = (5) = (7). • (Z7V) = (3) = (5). • (Zg,) není cyklická. • D2n = (r, s). Grupy permutací OOOOOO Homomorfismus Grupy symetrií oooooooooooc Definice Zobrazení f : (G, •) —> (H, o) mezi dvěmi grupami (G, •) a (H, o) se nazýva homomorfismus grup, jestliže respektuje násobení, tj. pro všechny prvky a, b G G platí f {a- b) = f{a)of{b). Povšimněme si, že násobení vlevo je uvnitř grupy G předtím, než zobrazujeme, zatímco vpravo jde o násobení v H poté, co zobrazujeme. Grupy permutací OOOOOO Grupy symetrií oooooooooooc Přímo z definice se snadno ověří následující vlastnosti homomorfismů: Věta Pro každý homomorfismus f : G —> H grup platí O obraz neutrálního prvku ec £ G je neutrální prvek v H Grupy permutací OOOOOO Grupy symetrií oooooooooooc Přímo z definice se snadno ověří následující vlastnosti homomorfismů: Věta Pro každý homomorfismus f : G —> H grup platí O obraz neutrálního prvku ec £ G je neutrální prvek v H q obraz inverze k prvku je inverzí obrazu, tj. f (a-1) = f (a) Grupy permutac OOOOOO Grupy symetrií oooooooooooc Přímo z definice se snadno ověří následující vlastnosti homomorfismů: Věta ^ Pro každý homomorfismus f : G —> H grup platí O obraz neutrálního prvku ec £ G je neutrální prvek v H O obraz inverze k prvku je inverzí obrazu, tj. f (a-1) = f(a)-1. O obraz podgrupy K < G je podgrupa f(K) < H. Grupy permutací OOOOOO Grupy symetrií oooooooooooc Přímo z definice se snadno ověří následující vlastnosti homomorfismů: Věta Pro každý homomorfismus f : G —> H grup platí O obraz neutrálního prvku ec £ G je neutrální prvek v H q obraz inverze k prvku je inverzí obrazu, tj. f (a-1) = f (a) q obraz podgrupy K < G je podgrupa f(K) < H. q vzorem f_1(K") < G podgrupy K < H je podgrupa. Grupy permutací OOOOOO Grupy symetrií oooooooooooc Přímo z definice se snadno ověří následující vlastnosti homomorfismů: Věta Pro každý homomorfismus f : G —> H grup platí O obraz neutrálního prvku ec £ G je neutrální prvek v H q obraz inverze k prvku je inverzí obrazu, tj. f (a-1) = f (a) q obraz podgrupy K < G je podgrupa f(K) < H. q vzorem f_1(K") < G podgrupy K < H je podgrupa. q je-li f zároveň bijekcí, pak i inverznízobrazení f"_1 je homomorfismus. Grupy permutací OOOOOO Grupy symetrií oooooooooooc Přímo z definice se snadno ověří následující vlastnosti homomorfismů: Věta Pro každý homomorfismus f : G —> H grup platí O obraz neutrálního prvku ec £ G je neutrální prvek v H q obraz inverze k prvku je inverzí obrazu, tj. f (a-1) = f (a)-1 q obraz podgrupy K < G je podgrupa f(K) < H. q vzorem f_1(K") < G podgrupy K < H je podgrupa. q je-li f zároveň bijekcí, pak i inverznízobrazení f"_1 je homomorfismus. q f je injektivní zobrazení právě tehdy když f~1{ej-i) = {ec}- Grupy permutací OOOOOO Grupy symetrií oooooooooooc Definice Podgrupa, která je vzorem jednotkového prvku e e H (tj. f_1(e)) se nazývá jádro homomorfismu f a značíme ji ker f. Bijektivní homomorfismus grup G a H nazýváme izomorfismus (a značíme G H). Poznámka Podobně jako v teorii grafů jsou i v algebře izomorfní objekty nerozlišitelné. Grupy permutací OOOOOO Grupy symetrií oooooooooooc Definice Podgrupa, která je vzorem jednotkového prvku e e H (tj. f_1(e)) se nazývá jádro homomorfismu f a značíme ji ker f. Bijektivní homomorfismus grup G a H nazýváme izomorfismus (a značíme G H). Poznámka Podobně jako v teorii grafů jsou i v algebře izomorfní objekty nerozlišitelné. Z předchozích tvrzení okamžitě vyplývá, že homomorfismus f : G —> H s triviálním jádrem je izomorfismem G na obraz f{G). Grupy permutací Grupy symetrií oooooo oooooooooooc Cyklické grupy ještě jednou Pro libovolný prvek a v grupě G existuje minimálni podgrupa {e = a°,a = a1, a2, a3,... }, která jej obsahuje2. Je zjevné, že je tato podgrupa komutativní, a pokud je celá grupa G konečná, nutně musí jednou nastat případ ak = e. 2Co znamenají ty mocniny? Grupy permutací Grupy symetrií oooooo oooooooooooc Cyklické grupy ještě jednou Pro libovolný prvek a v grupě G existuje minimálni podgrupa {e = a°,a = a1, a2, a3,... }, která jej obsahuje2. Je zjevné, že je tato podgrupa komutativní, a pokud je celá grupa G konečná, nutně musí jednou nastat případ ak = e. Nejmenší k s touto vlastností nazýváme řád prvku a y G. Grupa G je cyklická, je-li celé G generované nějakým svým prvkem a výše uvedeným způsobem. 2Co znamenají ty mocniny? Grupy permutací Grupy symetrií oooooo oooooooooooc Cyklické grupy ještě jednou Pro libovolný prvek a v grupě G existuje minimálni podgrupa {e = a°,a = a1, a2, a3,... }, která jej obsahuje2. Je zjevné, že je tato podgrupa komutativní, a pokud je celá grupa G konečná, nutně musí jednou nastat případ ak = e. Nejmenší k s touto vlastností nazýváme řád prvku a y G. Grupa G je cyklická, je-li celé G generované nějakým svým prvkem a výše uvedeným způsobem. Zjistit pro konkrétní cyklickou grupu generátor je obecně obtížný problém. I při znalosti generátoru g G G je ale obecně velkým problémem zjistit pro dané a G G číslo k, pro které gk = a (tzv. problém diskrétního logaritmu je základem mnoha kryptografických protokolů - EIGamal, Diffie-Hellman, DSA). 2Co znamenají ty mocniny? Grupy permutací Grupy symetrií oooooo oooooooooooc Cyklické grupy ještě jednou Pro libovolný prvek a v grupě G existuje minimálni podgrupa {e = a°,a = a1, a2, a3,... }, která jej obsahuje2. Je zjevné, že je tato podgrupa komutativní, a pokud je celá grupa G konečná, nutně musí jednou nastat případ ak = e. Nejmenší k s touto vlastností nazýváme řád prvku a y G. Grupa G je cyklická, je-li celé G generované nějakým svým prvkem a výše uvedeným způsobem. Zjistit pro konkrétní cyklickou grupu generátor je obecně obtížný problém. I při znalosti generátoru g G G je ale obecně velkým problémem zjistit pro dané a e G číslo k, pro které gk = a (tzv. problém diskrétního logaritmu je základem mnoha kryptografických protokolů - EIGamal, Diffie-Hellman, DSA). Z definice přímo vyplývá, že každá cyklická grupa je izomorfní buď grupě celých čísel Z (pokud je nekonečná) nebo některé grupě zbytkových tříd (když je konečná). 2Co znamenají ty mocniny? Grupy permutací OOOOOO Grupy symetrií oooooooooooc Příklad (1) Pro každou grupu permutací G = Z„ jsme definovali zobrazení sgn : (Tn,°) —> (^2,+) přiřazující permutaci její paritu (lichá=l, sudá=0). Jde o homomorfismus grup (£n,°) a (^2, +) ■ Jádrem tohoto homomorfismu jsou permutace se sudou paritou (tj. tzv. alterrnující grupa An). Grupy permutací OOOOOO Grupy symetrií oooooooooooc Příklad (1) Pro každou grupu permutací G = Z„ jsme definovali zobrazení sgn : (Tn,°) —> (^2,+) přiřazující permutaci její paritu (lichá=l, sudá=0). Jde o homomorfismus grup (£n,°) a (^2, +) ■ Jádrem tohoto homomorfismu jsou permutace se sudou paritou (tj. tzv. alterrnující grupa An). (2) Grupa symetrií rovnostranného trojúhelníka D§ je izomorfní s grupou permutací Z3. Stačí zvolit realizaci Z3 tak, že za množinu tří prvků pro permutace vezmeme vrcholy trojúhelníka a jednotlivým symetriím přiřadíme permutace těchto vrcholů, které vyvolají. Grupy permutací OOOOOO Grupy symetrií oooooooooooc Příklad (1) Pro každou grupu permutací G = Z„ jsme definovali zobrazení sgn : (Tn,°) —> (^2,+) přiřazující permutaci její paritu (lichá=l, sudá=0). Jde o homomorfismus grup (£n,°) a (^2, +) ■ Jádrem tohoto homomorfismu jsou permutace se sudou paritou (tj. tzv. alterrnující grupa An). (2) Grupa symetrií rovnostranného trojúhelníka D§ je izomorfní s grupou permutací Z3. Stačí zvolit realizaci Z 3 tak, že za množinu tří prvků pro permutace vezmeme vrcholy trojúhelníka a jednotlivým symetriím přiřadíme permutace těchto vrcholů, které vyvolají. (3) Zobrazení exp : R —>• R+ (nebo C ->■ C \ {0}) je homomorfismus aditivní grupy reálných nebo komplexních čísel na multiplikativní grupu kladných reálných čísel, resp. na multiplikativní grupu všech nenulových komplexních čísel. V případě reálných čísel jde o izomorfismus (co je jeho inverzí?). Pro komplexní čísla dostáváme netriviální jádro {2/on; k G Z}. Grupy permutací OOOOOO Grupy symetrií oooooooooooc Příklad (4) Determinant matice je zobrazením, které každé matici skalám z K přiřazuje nějaký skalár z K (pracovali jsme s K = Z, Q, R, C). Cauchyova věta o determinantu součinu čtvercových matic det(A ■ B) = (det A) • (det B) je tvrzením, že pro grupu G = GL(n,K) invertibilních matic je det : G —> K \ {0} multiplikativním homomorfismem grup. □ S - ■ M Grupy permutací OOOOOO Grupy symetrií oooooooooooc Příklad (4) Determinant matice je zobrazením, které každé matici skalám z K přiřazuje nějaký skalár z K (pracovali jsme s K = Z, Q, R, C). Cauchyova věta o determinantu součinu čtvercových matic det(A ■ B) = (det A) • (det B) je tvrzením, že pro grupu G = GL(n,K) invertibilních matic je det : G —> K \ {0} multiplikativním homomorfismem grup. (5) Grupy zbytkových tříd (Z^, +) jsou izomorfní grupám komplexních /(-tých odmocnin z jedničky, což jsou zároveň izomorfní obrazy konečných grup otočení v rovině o celé násobky úhlu ^. (6) Multiplikativní grupa invertibilních zbytkových tříd (Zpv) je izomorfní aditivní grupě (Zp_i, +) (plyne z cykličnosti grupy -později snad dokážeme). Grupy permutací Grupy symetrií oooooo oooooooooooc (Přímý) součin grup Definice Pro každé dvě grupy (G, •), (H,o) definujeme součin grup (G x H, *) takto: Jako množina je G x H skutečně (kartézský) součin, na kterém definujeme grupové násobení po složkách, tj. (a,x) * (b,y) = (a- b,xoy). Poznámka Rozmyslete si, že jde o grupu a že součin komutativních grup je zase komutativní! Grupy permutací Grupy symetrií oooooo oooooooooooc (Přímý) součin grup Definice Pro každé dvě grupy (G, •), (H,o) definujeme součin grup (G x H, *) takto: Jako množina je G x H skutečně (kartézský) součin, na kterém definujeme grupové násobení po složkách, tj. (a,x) * (b,y) = (a- b,xoy). Poznámka Rozmyslete si, že jde o grupu a že součin komutativních grup je zase komutativní! Zobrazení po : G x H 3 (a, x) h> a e G, pn : G x H 3 (a, x) h> x g H jsou surjektivní homomorfismy (tzv. projekce) s jádry kerpc = {(ec,x); x g H} kerpH = {(a, en); a g G}. Grupy permutací OOOOOO Grupy symetrií oooooooooooc Příklad (7) Grupa je izomorfní součinu Z2 x Z3. Toto lze nahlédnout buď geometrickou úvahou (prostřednictvím grup symetrií v rovině) nebo přímou konstrukcí izomorfismu. Grupy permutací OOOOOO Grupy symetrií oooooooooooc Příklad (7) Grupa je izomorfní součinu Z2 x Z3. Toto lze nahlédnout buď geometrickou úvahou (prostřednictvím grup symetrií v rovině) nebo přímou konstrukcí izomorfismu. V aditivní notaci vypadá izomorfismus takto: [0W([0]2,[0]3), [iW([i]2, [2]3) [2W([0]2,[1]3), [3W([1]2, [0]3) [4]6^([0]2,[2]3), [5W([1]2, [1]3) Grupy permutací OOOOOO Grupy symetrií oooooooooooc Příklad (7) Grupa je izomorfní součinu Z2 x Z3. Toto lze nahlédnout buď geometrickou úvahou (prostřednictvím grup symetrií v rovině) nebo přímou konstrukcí izomorfismu. V aditivní notaci vypadá izomorfismus takto: [0W([0]2,[0]3), [l]e m> ([1]2, [2]3) [2]6^([0]2,[1]3), [3]6 m> ([1]2, [0]3) [4]6^([0]2,[2]3), [5]6 ^ ([1]2> [1]3) (8) Dihedrální grupa Dg (tj. grupa symetrií čtverce, (r, s\ŕ = l,s2 = l,srs = r-1} ) není izomorfní součinu Z2 x Z4, přestože mají stejný počet prvků (Dg není komutativní). □ s - ■ M Grupy permutac OOOOOO Grupy symetrií oooooooooooc Čínska zbytková věta (Chinese remainder theorem) Předchozí příklad je speciálním případem tzv. Čínské zbytkové věty. Jsou-li k, m nesoudělná, pak (Zkm,+)^(Zk,+)x(Zm,+). Grupy permutací Grupy symetrií oooooo oooooooooooc Čínská zbytková věta (Chinese remainder theorem) Předchozí příklad je speciálním případem tzv. Čínské zbytkové věty. Věta * Jsou-li k, m nesoudělná, pak (Zkm,+)^(Zk,+)x(Zm,+). a obecněji Věta Jsou-li m\, ítt2, • • • , m k po dvou nesoudělná, pak (ZUm., +) (Zmi, +) x (Zm2, +) x • • • x (Zmk, +). Tento izomorfismus se často s výhodou využívá k reprezentaci velkých čísel při distribuovaných výpočtech pracujících s dělitelností, kdy na každém počítači stačí pracovat s jedním (relativně malým) modulem. Grupy permutací OOOOOO Grupy symetrií oooooooooooc Důkaz CRT: Sestrojíme požadovaný izomorfismus f . Označme m = Y[; m, a pro libovolné [a]m G Zm položme f([a]m) = ([a]mi,..., [a]mJ. Snadno se ověří, že jde o injektivní homomorfismus (co je jádrem?). 3A nešlo by to ještě šikovněji? Pokud nám stačí existence izomorfismu, tak stačí využít toho, že injektivní zobrazení mezi množinami o stejném počtu prvků je automaticky bijekcí. Grupy permutací Grupy symetrií oooooo oooooooooooc Důkaz CRT: Sestrojíme požadovaný izomorfismus f . Označme m = Y[; m, a pro libovolné [a]m G Zm položme f([a]m) = ([a]mi,..., [a]mJ. Snadno se ověří, že jde o injektivní homomorfismus (co je jádrem?). Zbývá dokázat, že jde i o surjekci, tedy, že libovolný prvek ([ai]mi,..., [ak]mk) G (Zmi, +) x • • • x (Zmk, +) je obrazem nějakého a G Zm. To je ale totéž jako najít a G Z takové, že a = ai (mod mi),..., a = ak (mod mk), což se udělá malým (ale šikovným) trikem:3 3A nešlo by to ještě šikovněji? Pokud nám stačí existence izomorfismu, tak stačí využít toho, že injektivní zobrazení mezi množinami o stejném počtu prvků je automaticky bijekcí. Grupy permutací Grupy symetrií oooooo oooooooooooc Důkaz CRT: Sestrojíme požadovaný izomorfismus f . Označme m = Y[; m, a pro libovolné [a]m G Zm položme f([a]m) = ([a]mi,..., [a]mJ. Snadno se ověří, že jde o injektivní homomorfismus (co je jádrem?). Zbývá dokázat, že jde i o surjekci, tedy, že libovolný prvek ([ai]mi,..., [ak]mk) G (Zmi, +) x • • • x (Zmk, +) je obrazem nějakého a G Zm. To je ale totéž jako najít a G Z takové, že a = ai (mod m\),..., a = ak (mod m^), což se udělá malým (ale šikovným) trikem:3 Pro libovolné 1 < / < k položme n; = m/rtij a protože (m,-, n,-) = 1 (zde jsme využili nesoudělnost po dvou), najdeme podle Bezoutovy věty u\ a v, tak, že Ujirij + Vjtij = 1, tj. Vjtij = 1 (mod mi). 3A nešlo by to ještě šikovněji? Pokud nám stačí existence izomorfismu, tak stačí využít toho, že injektivní zobrazení mezi množinami o stejném počtu prvků je automaticky bijekcí. Grupy permutací OOOOOO Grupy symetrií oooooooooooc Důkaz CRT: Sestrojíme požadovaný izomorfismus f . Označme m = Y[; m, a pro libovolné [a]m g Zm položme f([a]m) = ([a]mi,..., [a]mJ. Snadno se ověří, že jde o injektivní homomorfismus (co je jádrem?). Zbývá dokázat, že jde i o surjekci, tedy, že libovolný prvek ([ai]mi,..., [ak]mk) g (Zmi, +) x • • • x (Zmk, +) je obrazem nějakého a g Zm. To je ale totéž jako najít a g Z takové, že a = ai (mod m\),..., a = ak (mod rrik), což se udělá malým (ale šikovným) trikem:3 Pro libovolné 1 < / < k položme n; = m/rtij a protože (m,-, n,-) = 1 (zde jsme využili nesoudělnost po dvou), najdeme podle Bezoutovy věty u\ a v, tak, že Ujirij + Vjtij = 1, tj. Vjtij = 1 (mod mi). Hledané a pak najdeme jako a = Y,iaivini- 3A nešlo by to ještě šikovněji? Pokud nám stačí existence izomorfismu, tak stačí využít toho, že injektivní zobrazení mezi množinami o stejném počtu prvků je automaticky bijekcí.