Matematika IV - 3. přednáška Homomorfismy a součiny grup Michal Bulant Masarykova univerzita Fakulta informatiky 6. 3. 2013 Homomorfismy Součiny oooooo oooo Obsah přednášky Q Homomorfismy Q Součiny Homomorfismy oooooo Dop Součiny oooo • 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). Homomorfismy •ooooo Horn Součiny oooo Definice Zobrazení f : (G, •) —> (H, o) mezi dvěmi grupami (G, •) a (/7, o) se nazývá 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. Homomorfismy o»oooo Součiny oooo 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}- Homomorfismy oo»ooo Součiny oooo 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). Homomorfismy Součiny ooo#oo oooo Cyklické grupy ještě jednou Pro libovolný prvek a v grupě G existuje minimální podgrupa {e = a°, a = a1, a2, a3,... }, 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? Homomorfismy oooo»o Součiny oooo 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}. Homomorfismy 00000» Součiny oooo 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 sK = Z,Q,l, 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). Homomorfismy Součiny oooooo »ooo (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í 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}. Homomorfismy oooooo Součiny o»oo Prí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), [1]6 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 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ů (D% není komutativní). Homomorfismy oooooo Součiny oo»o Číns 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 Homomorfismy Součiny oooooo ooo» Důkaz CRT: 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í.