oooooooooooo
Matematika IV - 2. přednáška Základy teorie grup
Michal Bulant
Masarykova univerzita Fakulta informatiky
25. 2. 2008
Q Grupy - homomorfismy a součiny
oooooooooooo
Doporuč
•  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).
•  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 případě komutativních grup setkáte rovněž s pojmem abelovská grupa.
Poznámka k nejednoznačnosti terminologie.
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.
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ácí 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, svazy, 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
oo«ooooooooo
Podpologrupy a podgrup;
Je-li (A, •) grupa (případně 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, •).
Definice
Zobrazení f : (G, ■) —>■ (H, o) mezi dvěmi grupami (G, •) a (/-/, o) se nazývá homomorfismus grup, jestliže respektuje násobení, tj. pro všechny prvky a, b G G platí
f(ab) = 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.
ooo«oooooooo
Přímo z definice se snadno ověří následující vlastnosti homomorfismů:
Pro každý homomorfismus f : G —> H grup platí O obraz jednotky e^eG je jednotka v H Q obraz inverze k prvku je inverzí obrazu, tj. f (a-1) = f (a)-1 Q obraz podgrupy K C G je podgrupa f (K) C H. Q  vzorem f ~1(K) C G podgrupy K C H je podgrupa. O 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 - homomorti:
oooo»ooooooo
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).
ooooo«oooooo
Příklad
(1)  Pro každou grupu permutací G = E„ jsme definovali zobrazení sgn : (E„, o) —> (Z2,+) přiřazující permutaci její paritu (lichá=l, sudá=0). Jde o homomorfismus grup (E„, o) a (Z2, +) • Jádrem tohoto homomorfismu jsou permutace se sudou paritou.
(2)  Grupa symetrií rovnostranného trojúhelníka Dq je izomorfní s grupou permutací E3. Stačí zvolit realizaci E3 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 kit i; k G Z}.
oooooo»ooooo
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 IK = 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 /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 (Z*,-) je izomorfní aditivní grupě (Zp_i, +) (plyne z cykličnosti grupy -později snad dokážeme).
ooooooo«oooo
(Přímý) součin
Definice
Pro každé dvě grupy (G, •), (H,o) definujeme součin grup (G x /-/, *) 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 B (a, x) i—s- a € G, pn : G x H 3 (a, x) *-» x e H
jsou surjektivní homomorfismy (tzv. projekce) s jádry
ker pG = {(ec,x); x e H}     ker p h = {(a, en); a G G}.
OOOOOOOO0OOO
Příklad
(7)  Grupa Zß 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), [1W ([1]2, [2]3) [2]6^([0]2,[1]3), [3]6 ^ ([1]2> [0]3) [4]e-([0]2,[2]3), [5]6 ~ ([1]2, [1]3)
(8)  Dihedrální grupa Ds (tj. grupa symetrií čtverce,
(r, s\r = l,s2 = l,srs = r_1) ) není izomorfní součinu Z2 x Z4, přestože mají stejný počet prvků (Dg není komutativní).
Grupy - homomortismy a součiny ooooooooo«oo		
Čínská 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 (Zfan,+)^(Zfc,+)x(Z„1,+).	
	a obecněji	
	Jsou-li mi, AT72, • • • , m k po dvou nesoudělná, pak (Znm;, +) *ž (Zmi, +) x (Zm2, +) x • • • x (Zmfc, +).	
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.
Sestrojíme požadovaný izomorfismus f . Označme m = JT(- 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
(Nim,- • •, [3k]mk) e (Zmi, +) x • • • x {1mk, +)
je obrazem nějakého a G Zm. To je ale totéž jako najít a G Z takové, že a = a\ (mod mi),.. .a = a^ (mod m/J, což se udělá malým (ale šikovným) trikem:2
Pro libovolné 1 < i < k položme n; = m/m; a protože (m,-, n,-) = 1 (zde jsme využili nesoudělnost po dvou), najdeme podle Bezoutovy věty Uj a v-, tak, že u;m; + i//n,- = 1, tj. vjn; = 1 (mod m,-). Hledané a pak najdeme jako
a = V'a / ví n;.
2A nešlo by to ještě šikovněji? Pokud nám stačí existence izomorfismu, tak
staří \/vii7Ít toho   7P iniektivní 7nhra7pní mp7Í  mnnľinami o steinern nnřtii
Libovolný prvek a v grupě G je obsažen v minimální podgrupě
{e = a°,a = a1, a2, a3,... }, která jej obsahuje3.
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 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 Z^ (když je konečná).
3Co znamenají ty mocniny?