Matematika IV - 1. přednáška Základy teorie grup smetni 50 Michal Bulant Masarykova univerzita Fakulta informatiky 20. 2. 2013 Motivačn í úvod Grupy Grupy permutací Grupy symeti 0 oooo oooooo ooooooo Ql Motivační úvod Q Grupy Grupy permutací Q Grupy symetrií Motivační úvod 0 Grupy oooo Grupy permutací oooooo Grupy symetrií ooooooo • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Předmětové 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 knihovne PřF). • P. Horák, Základy matematiky, http://www.math.muni.cz/~horak/09p_zm_skripta.pdf Motivační úvod Grupy Grupy permutací Grupy symetrií • oooo oooooo ooooooo Chceme abstraktně pracovat s objekty a se situacemi, ve kterých je možné rovnice a • x = b vždy jednoznačně řešit (tak jako u lineárních rovnic jsou objekty a a b dány, zatímco x hledáme). Jde o tzv. teorii grup. Všimněme si, že zatím nic nevíme o povaze objektů, ani co znamená ta "tečka" v rovnici. Motivační úvod 0 Grupy •ooo Grupy permutací oooooo Grupy symetrií ooooooo • 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. Poznámka k nejednoznačnosti terminologie (multiplikativní vs. aditivní) 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. Motivační úvod 0 Grupy 0900 Grupy permutací oooooo Grupy symetrií ooooooo Bystří studenti algebry si brzy povšimnou, že se mnohé pojmy a důkazy opakují pro různé situace. Skutečně se ukazuje, že základní pojmy a tvrzení je možné zavést a dokázat obecně pomocí univerzální algebry (příp. ještě obecněji v tzv. teorii kategorií). Pro informatiky, kteří mají za sebou funkcionální programování (příp. práci s objekty, metodami, šablonami apod.), by to možná mohl být přirozený postup, my však na to bohužel nemáme dostatek času. Pro všechny struktury (pologrupy, grupy, okruhy, tělesa, vektorové prostory, svazy, moduly atd.) lze definovat několik základních pojmů analogickým způsobem: • podstruktury • homomorfismy mezi strukturami stejného typu • součiny struktur téhož typu Motivačn úvod Grupy Grupy permutací Grupy symetrií 0 oo»o oooooo ooooooo Příklad Q Přirozená čísla (s nulou) No = {0,1,2,...}, spolu s kteroukoliv z operací sčítání a násobení jsou asociativní a komutativní pologrupa s jednotkovým prvkem, neexistují v ní ale inverzní prvky. O Celá čísla Z = {..., —2, —1, 0,1, 2,... } tvoří grupoid vůči kterékoliv z operací sčítání, odčítání, násobení. Jsou dokonce komutativní grupou vzhledem ke sčítání, jsou však jen komutativní pologrupou vůči násobení (neexistují inverze k prvkům a ^ ±1). Operace odčítání není ani asociativní (např. (5 - 3) - 2 = 0 ^ 5 - (3 - 2) = 4). Všimněte si také, že pro odečítání je nula pravý neutrální prvek, ne však levý. Dokonce v tomto případě levý neutrální prvek neexistuje. O Racionální čísla Q jsou komutativní grupou vzhledem ke sčítání (celá čísla spolu se sčítáním jsou jejich podgrupou) a nenulová racionální čísla jsou kom. grupou vůči násobení. Motivační úvod 0 Grupy ooo» Grupy permutací oooooo Grupy symetrií ooooooo Příklad (pokračovaní) O Pro k G N, množina všech /c-tých odmocnin z jedničky, tj. množina {z G C; zk = 1} je konečná grupa vůči násobení komplexních čísel. Např. pro k = 2 dostaneme grupu {—1,1} se dvěma prvky, které jsou oba samy sobě inverzí, zatímco pro k = 4 dostáváme grupu G = {1, /', —1, —/'}. O Množina Mat„ všech čtvercových matic je (nekomutativní) pologrupa vzhledem k násobení matic a komutativní grupa vzhledem ke sčítání matic. O Množina všech lineárních zobrazení Hom(\/, V) na vektorovém prostoru je pologrupa vzhledem ke skládání zobrazení a komutativní grupa vzhledem ke sčítání zobrazení. Q V obou předchozích příkladech, podmnožina invertibilních objektů uvažované (multiplikativní) pologrupy tvoří grupu. V případě matic jde o tzv. grupu invertibilních (tj. regulárních) matic, ve druhém o grupu lineárních transformací vektorového prostoru (tj. invertibilních lineárních zobrazení). Motivační úvod 0 Grupy oooo Grupy permutací •ooooo Grupy symetrií ooooooo Zpravidla grupy a pologrupy potkáváme jako množiny zobrazení na pevně dané množině M, které jsou uzavřeny vůči skládání zobrazení. Často si ale tuto skutečnost přímo neuvědomujeme. Na každé konečné množině M, s m = \ M\ G N prvky máme k dispozici mm možných definic zobrazení (každý z m prvků můžeme zobrazit na kterýkoliv v M) a všechna taková zobrazení umíme skládat. Pokud chceme, aby existovala k zobrazení a : M —> M jeho inverze a-1, musí být a bijekcí. Složením dvou bijekcí vznikne opět bijekce a proto podmnožina Sm všech bijekcí na množině M o m prvcích je grupa. Říkáme jí grupa permutací na m prvcích. Motivační úvod 0 Grupy permutací o»oooo Grupy symetrií ooooooo Název grupa permutací přitom uvádí jinou souvislost, kdy místo bijekcí na konečné množině vnímáme permutace jako přerovnání rozlišitelných prvků. Potkávali jsme se s ní např. při studiu determinantů. V grupě permutací S3 na číslech {1,2,3} si třeba označíme jednotlivá pořadí a = (1,2, 3), Z> = (2,3,1), c = (3,l,2), c/ = (l,3,2), e = (3,2,l), f = (2,1,3). Skládání našich permutací je pak zadáno tabulkou a b c d e f a a b c d e f b b c a f d e c c a b e f d d d e f a b c e e f d c a b f f d e b c a Motivační úvod 0 Grupy permutací oo»ooo Grupy symetrií ooooooo Všimněme si podstatného rozdílu mezi permutacemi a, b a c a dalšími třemi. Ty první tři tvoří tzv. cyklus generovaný prvkem b nebo prvkem c: b2 = c, b3 = a, c2 = b, c3 = a a samy o sobě jsou tyto tři prvky komutativní podgrupou. V ní a je neutrální prvek a b s c jsou vzájemně inverzní. Je tedy tato podgrupa stejná jako je grupa Z3 zbytkových tříd celých čísel modulo 3, resp. jako grupa třetích odmocnin z jedničky z jednoho z předchozích příkladů. Další tři prvky jsou samy sobě inverzí a každý z nich je tedy společně s neutrálním prvkem a podgrupou stejnou jako je Z2. Říkáme, že b a c jsou prvky řádu 3, zatímco prvky d, e a f jsou řádu 2. Motivační úvod 0 Grupy permutací ooo»oo Grupy symetrií ooooooo Obdobně se chovají všechny grupy permutací Sm. 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í ak(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 ct'(x), pak je naše permutace prostým posunutím o jednu pozici v cyklu (tj. poslední prvek je zobrazen zpátky na první). Odtud název cyklus. Zjevně přitom tyto cykly komutují, takže je jedno, v jakém pořadí z nich permutaci a složíme. Motivační úvod 0 Grupy permutací oooo»o Grupy symetrií ooooooo Nejjednodušší cykly jsou jednoprvkové pevné body permutace a. Dvouprvkové (x, každou permutaci lze napsat jako složení transpozic. 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 : Sm —> Z2 = {±1}, tzv. paritu permutace. Dokázali jsme si znovu tvrzení, která jsme již využívali při studiu determinantů: Motivační úvod 0 Grupy permutací 00000» Grupy symetrií ooooooo Věta Každá permutace konečné množiny je složením cyklů. Cyklus délky i lze vyjádřit jako složení i — 1 transpozic. Parita cyklu délky i je (—l)^-1. Parita složení permutací je součinem parit jednotlivých z nich, tzn. že zobrazení sgn převádí složení permutací a o t na součin sgn a • sgn r v komutativní grupě Z2. Motivační úvod 0 Grupy permutací oooooo Grupy symetrií •OOOOOO 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). Motivační úvod 0 Grupy oooo Grupy permutací oooooo Grupy symetrií o»ooooo 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ých bude dohromady šest. Motivační úvod 0 Grupy permutací oooooo Grupy symetrií oo«oooo 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í S3 obdržíme právě stejný výsledek. Motivační úvod 0 Grupy oooo Grupy permutací oooooo Grupy symetrií ooo»ooo 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 D2k a říká se jim dihedrální grupy řádu 2k (někdy též např D(k)). Tyto grupy jsou nekomutativní pro všechny k > 3. Motivační úvod 0 Grupy oooo Grupy permutací oooooo Grupy symetrií oooo»oo 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 Q. Ří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. Motivační úvod 0 Grupy permutací oooooo Grupy symetrií ooooo»o Prí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 < ^4 sudých permutací. Motivační úvod 0 Grupy oooo Grupy permutací OOOOOO Grupy symetrií 000000» Věta Necht je M ohraničená množina v rovině M2. Pak grupa jejich symetrií je buď triviálni nebo jedna z grup Q, D2k, s k > 1.