Matematika IV - 2. přednáška Podgrupy, homomorfismy a součiny grup Michal Bulant Masarykova univerzita Fakulta informatiky 27. 2. 2013 Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normálni' podgrupy oooo oooooo OOOO 00000 OOOOOO Obsah přednášky Q Podgrupy Q Homomorfismy Q Součiny Q Rozklady podle podgrup Q Normálni podgrupy Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normální pod| ärupy oooo oooooo OOOO ooooo oooooo • 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 knihovně PřF). Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normální f •ooo oooooo oooo ooooo oooooo Podpologrupy a podgrupy Definice Je-li (A,-) grupa (prípadne pologrupa), pak její podmnožinu 8 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 Nechi (G, o) grupa. Pak 0 7^ H c G je její podgrupa právě tehdy, když & Va,b G H : a o b e H; ® Va e H : a'1 e H. Snadno se navíc vidí, že obě podmínky v předchozí větě lze shrnout do jediné: Va, b £ H : a o b^1 £ H. Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normální pod ärupy o»oo oooooo oooo ooooo OOOOOO Příklad O Z je podgrupa aditivních grup Z,Q, M, C. Všechny podgrupy (Z, +) jsou vyčerpány množinami mZ. © (/?+•) < (/?*,•)■ O Množina /4n všech sudých permutací na n-prvkové množině je podgrupou Z„. O SZ.„(M) < GLn{R). Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normálni pod ärupy oo»o oooooo oooo ooooo OOOOOO Podgrup; 3 generován á množine DU 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 mch = <5>. • (Zg,-) není cyklická. » D2n = (r,s). Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normální f OOOO »00000 oooo ooooo oooooo Homomorfismus 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. Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normálni pod ärupy oooo o«oooo OOOO ooooo oooooo 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 e^ G G je neutrální prvek v H O 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. 0 je-li f zároveň bijekcí, pak i inverznízobrazení f:_1 je homomorfismus. O f je injektivní zobrazení právě tehdy, když f^1(en) = {sg}- Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normálni pod ärupy oooo 00*000 OOOO OOOOO OOOOOO Definice Podgrupa, která je vzorem jednotkového prvku e £ H (tj. f_1({e})) se nazývá jádro homomorfismu f a značíme ji kerf. 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). Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normálni pod| ärupy oooo ooosoo OOOO ooooo oooooo Cyklic! cé grupy ještě jednou Pro libovolný prvek a v grupě G existuje minimálni podgrupa {e = a°, a = a1, a2, s3,... }, která jej obsahuje1. 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 v 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). Z definice přímo vyplývá, že každá cyklická grupa je izomorfní bud' grupě celých čísel Z (pokud je nekonečná) nebo některé grupě zbytkových tříd (když je konečná). 1Co znamenají ty mocniny? Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normálni pod ärupy oooo oooo*o OOOO ooooo oooooo Příklad (1) Pro každou grupu permutací G = Z„ jsme definovali zobrazení sgn : (5Z„,o) —y (Z2,+) přiřazující permutaci její paritu (lichá=l, sudá=0). Jde o homomorfismus grup (5Z„,o) a (Z2,+) ■ 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, +) ->• •) (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 {2kiri; k G Z}. Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normálni pod ärupy oooo ooooo* OOOO ooooo oooooo Příklad (4) Determinant matice je zobrazením, které každé matici skalárů z K přiřazuje nějaký skalár z K (pracovali jsme s K = Z, Q, M, C). Cauchyova věta o determinantu součinu čtvercových matic det(/4 • B) = (det/4) • (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 /c-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 (Zp,-) je izomorfní aditivní grupě (Zp_i, +) (plyne z cykličnosti grupy). Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normálni pod ärupy oooo oooooo •ooo ooooo OOOOOO 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, x o y). Poznámka Rozmyslete si, že jde o grupu a že součin komutativních grup je zase komutativní! Zobrazení Pg : g x H 3 (a,x) 4 a £ g, ph : g x H 9 (a,x) 4 x é H jsou surjektivní homomorfismy (tzv. projekce) s jádry kerpG = {(eG,x); x e H} kerpH = {{a, eH)\a G G}. Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normální pod šrupy oooo OOOOOO o»oo ooooo OOOOOO Příklad (7) Grupa je izomorfní součinu Z2 x Z3. Toto lze nahlédnout bud' 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), [1]6 m- ([1]2, [2]3) [2]6^([0]2,[1]3), [3]6 m- ([1]2, [0]3) [4W([0]2,[2]3), [5]6 m. ([1]2) [1]3) (8) Dihedrální grupa D% (tj. grupa symetrií čtverce, (r, s\ŕ = 1, s2 = 1, srs = r_1) ) není izomorfní součinu Z2 x Z4, přestože mají stejný počet prvků (Qg není komutativní). Předchozí příklad (část 7) 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\, ni2, • • • , mk po dvou nesoudělná, pak (Znm.,+) ^ (Zmi,+) x (Zm2,+) x ••• x (Zm/t,+). 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 Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normálni pod| ärupy oooo oooooo ooo» ooooo OOOOOO Sestrojíme požadovaný izomorfismus f . Označme m = fli mi 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 ([al]mi> • • •> [ak] trik) ^- i^mii + ) X • • • X {%mk, +) 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 = a^ (mod m^), což se udělá malým (ale šikovným) trikem:2 Pro libovolné 1 < / < k položme n, = m/m; a protože (m/,/7/) = 1 (zde jsme využili nesoudělnost po dvou), najdeme podle Bezoutovy věty u; a v, tak, že u\m\ + 1///7,- = 1, tj. 1///7,- = 1 (mod m,-). Hledané a pak najdeme jako a = J2iaivini- 2A 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í. Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normálni pod| ärupy oooo OOOOOO OOOO •OOOO OOOOOO Uvažme grupu G a její podgrupu H. Na množině prvků grupy G definujeme relaci a ~h b jestliže b^1 ■ a G H, tj. a-1 • b G H . Je to relace ekvivalence: • a-1 • a = e G H, • je-1i b^1 ■ a = h G H, potom a-1 • b = (b^1 ■ a)-1 = h'1 G H, 9 je-li c-1 • b G H a zároveň je Ď-1 • a G H, potom c'1-a = c'1 • b-b'1- a€ H. Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normálni pod| ärupy oooo oooooo OOOO o»ooo oooooo Celá grupa G se tedy rozpadá na tzv. levé třídy rozkladu podle podgrupy H vzájemně ekvivalentních prvků. Třídu příslušející prvku a značíme a ■ H (zřejmě a G a ■ H) a skutečně platí, že a ■ H = {a ■ h; h G H}, neboť prvek b je ve stejné třídě s a, právě když jde takovýmto způsobem vyjádřit. Množinu všech levých tříd rozkladu podle podgrupy H označujeme G/H. Obdobně definujeme pravé třídy rozkladu H ■ a. Příslušná ekvivalence je: a ~ b, jestliže a • b^1 G H. Proto H\G = {H ■ a; a G G}. Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normálni pod ärupy oooo oooooo OOOO oo»oo OOOOOO Věta Pro třídy rozkladu grupy platí: O Levé a pravé třídy rozkladu podle podgrupy H c G splývají právě tehdy, když pro každé a G G, h G H platí a ■ h ■ a-1 G H. & Všechny třídy (levé i pravé) mají shodnou mohutnost jako podgrupa H. O Zobrazení a ■ H i-> H ■ a-1 zadává bijekci mezi levými a pravými třídami rozkladu G podle H. Poznámka Rozmyslete si, proč je v posledním tvrzení a a nikoliv a. Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normálni pod ärupy oooo oooooo OOOO ooo»o oooooo Důsledek Nechť G je konečná grupa s n prvky (tj. G je řádu n), H její podgrupa. Potom O Mohutnost n = \G\ je součinem mohutnosti H a mohutnosti G/H, tj. \G\ = \G/H\ ■ \H\ Q Přirozené číslo \H\ je dělitelem čísla n. O Je-li a G G prvek řádu k, pak k dělí n. O pro každé a G G je a" = e. 0 je-li mohutnost grupy G prvočíslo p , pak je G izomorfní cyklické grupě Zp. Druhému tvrzení se říkává Lagrangeova věta, předposlednímu malá Fermatova věta (nejčastěji ve speciálním případě grupy (Z£, •)). Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normálni pod ärupy OOOO OOOOOO OOOO OOOO* OOOOOO Snadnými důsledky předchozího jsou následující věty: Věta (Malá Fermatova) Pro libovolné prvočíslo p a číslo a G Z nedělitelné p platí ap- 1 = 1 (mod p). Věta (Eulerova) "* Pro libovolné m G N a každé a G Z splňující (a, m) = 1 platí 3^m) = 1 (mod m). Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normálni pod ärupy oooo oooooo OOOO ooooo •ooooo Podgrupy H, pro které platí, že a ■ h ■ a 6 H pro všechna a £ G, h 6 H, se nazývají normální podgrupy (značíme H < G) . Snadno se nahlédne platnost následujícího Podgrupa H je normální právě tehdy, když pro každé a £ G platí a ■ H = H ■ a (jinými slovy: levý rozklad G podle podgrupy H je shodný s pravým rozkladem). Důsledek • 1 < G, G < G • V komutativní grupě je každá podgrupa normální. • Je-li H podgrupa konečné grupy G, kde \ H\ = \ G\/2, pak je H normální. Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normálni pod ärupy oooo OOOOOO OOOO OOOOO o»oooo Příklad • Dihedrální grupa D2n má vždy normálni podgrupu izomorfní Z„. Levý (i pravý) rozklad podle této podgrupy je dvojprvková množina {Z„,s • Z„}. • (f2) = {'d, ľ2} je normálni podgrupa v D$. Levý rozklad podle této podgrupy je čtyřprvková množina {{id, r2},{r,r3},{s,sr2},{sr,sr3}}. Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normální pod ärupy oooo OOOOOO OOOO OOOOO oo*ooo Pro normální podgrupy je dobře definováno násobení na G/H vztahem (a • H)-{b- H) = (a • b) ■ H. Skutečně, volbou jiných reprezentantů a • h, b • H dostaneme opět stejný výsledek (a ■ h ■ b ■ h') ■ H = ((a ■ b) ■ (ZT1 -h-b)-h')-H. Věta Je-li H normálnípodgrupou G, tvoří rozklad G/H s násobením definovaným prostřednictvím reprezentantů grupu. Je-li G komutativní, je i G/H komutativní. Příklad nZ = {na; a £ Z} c Z zadává pro libovolné íiéN podgrupu Z a její faktorgrupou (až na izomorfismus) je aditivní grupa zbytkových tříd Z„ (přitom pro n = 1 jde o triviální grupu) . Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normálni pod) ärupy oooo oooooo OOOO ooooo ooo»oo Naproti tomu existují i grupy, které nemají žádné vlastní normální podgrupy, takové grupy se nazývají jednoduché (simple). Znalost těchto grup je velmi důležitá, protože z nich je v jistém smyslu složena každá konečná grupa. Mezi konečnými komutativními grupami je situace skutečně jednoduchá - prostými jsou pouze grupy Zp pro prvočíselné p (podobně i každá prostá grupa lichého řádu je nutně izomorfní Zp - důkaz tohoto faktu je ale značně netriviální3). V nekomutativním případě je situace výrazně složitější - až v roce 1982 (samozřejmě s pomocí počítačů) se podařilo završit úsilí o úplnou klasifikaci jednoduchých grup. Například alternující grupa An (tj. podgrupa sudých permutací grupy Z„) je jednoduchá pro n > 5 , z čehož (s pomocí tzv. Galoisovy teorie) plyne nemožnost existence obecných vzorců pro kořeny polynomů stupně 5 a vyššího. 3255 stran "tvrdé" matematiky Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normálni pod) ärupy OOOO OOOOOO OOOO OOOOO oooo»o Všechna jádra homomorfismů jsou normální podgrupy. Naopak, jestliže je podgrupa H c G normální, pak zobrazení (projekce na faktorgrupu) p : G —>■ G/H, 3i-> a ■ H je surjektivní homomorfismus grup s jádrem H. Skutečně, p je dobře definované, přímo z definice násobení na G/H je vidět, že to musí být homomorfismus, který je zjevně na. Je tedy vidět, že normální podgrupy jsou právě všechna jádra homomorfismů. Podgrupy Homomorfismy Součiny Rozklady podle podgrup Normální pod ärupy oooo oooooo OOOO ooooo OOOOO* Věta (první, základní) Pro libovolný homomorfismus grup f : G —» K je dobře definován také homomorfismus f : G/kerf K, f(a ■ H) = f(a), který je injektivní. Zejména dostáváme G/ ker f = f(G).