1. Druhá vnitrosemestrální práce 16.5.2014 1.1. (2b.) Určete řády všech prvků v grupách Z§, Z generátory těchto grup. Dokažte, že Zg = Z*2-Řešení. J8 ' ^12 j14 a určete Z8 1 2 3 4 5 6 7 řád 8 4 8 2 8 4 8 Zl2 1 23456789 10 11 řád 12 6 4 3 12 2 12 3 4 6 12 Generátory jsou prvky s maximálním řádem, tj. nesoudělné s 8 resp. 12 (a je jich v obou případech (p(8) — ip(12) — 4). z8x 1 3 -3 -1 ^2 1 5 -5 -1 řád 1 2 2 2 řád 1 2 2 2 13 5-5-3-1 řád 1 6 6 3 3 2 Zg a Z^2 nemají generátor, pro Z^4 je generátor 3 a 5 (jsou to vlastně primitivní kořeny modulo 14, je jich p(p(14)) — p(6) — 2). Izomorfismus Zg = Z*2 je dán přiřazením ±1 n- ±1 a ±3 n- ±5. Obě grupy jsou komutativní a mají neutrální prvek a tři prvky řádu 2, jsou tedy obě izomorfní Z2 x Z2. 1.2. (2b.) Dokažte, že předpis p zadává zobrazení, které je homomorfismem grup. Určete jeho jádro a obraz, rozhodněte o surjektivitě a injektivitě p a popište faktorgrupu A4/ im( A4, <^([a]3) = (1, 2,4) o (1, 3, 2)a o (1, 4, 2) Řešení. Předpis zadává zobrazení, protože z a = b (mod 3) plyne (1,3, 2)a — (1, 3, 2)b, a proto i (^([^3) — ip([b]3). Jedná se o homomorfismus, protože (1,2, 4)o(l,3, 2)a+bo(l,4,2) = (1,2, 4)o(l, 3,2)ao(l,4,2)o(l,2,4)o(l,3, 2)bo(l,4,2) a (1,2, 4) o (1,3, 2)° o (1,4, 2) = id. Jádro je nulové, jedna se tedy o injektivní homomorfismus. Surjektivní není, protože obrazem je identita a permutace (1,2, 4) o (1,3, 2)1o(l, 4, 2) = (2,3,4), (l,2,4)o(l,3,2)2o(l,4, 2) = (2,4,3), tj. im((p) — (2,3,4)fe, k — 0,1,2. Je to normální podgrupa v grupě sudých permutací A4. Ta je tvořena permutacemi, které jsou tvořeny právě jedním cyklem délky 3 nebo dvěmi nezávislými transpozicemi. Její řád je IA4J — ^4! — 12. Faktorgrupa A4/ im((p) má řád |A4/im(y)| — ^ — 4. Prvky faktorgrupy jsou reprezentovány právě třemi permutacemi danými součinem dvou transpozic a iden-titou, tj. jsou to třídy {id, (2, 3, 4), (2,4, 3)}, {(1, 2)o(3,4), (1, 2,4), (1, 2, 3)}, {(1, 3)o (2,4), (1,3,2), (1,3,4)}, {(1,4) o (2, 3), (1,4, 3), (1,4, 2)}. 1.3. (2b.) Určete počet obarvení vrcholů rovnostranného trojúhelníka třemi barvami, považujeme-li za stejná obarvení, která na sebe přejdou při nějaké symetrii trojúhelníka. Řešení. Grupa symetrií trojúhelníka je _D6, složená z identity, tří osových symetrií o a dvou rotací r (o ±§tt)- Množina pevných bodů identity je celá množina všech různých obarvení, tj. jS^I — \S\ — 33 — 27. Počet prvků množiny pevných bodů 2 pro osové symetrie je \SQ\ — 3 2 — 9 a pro rotace \SQ\ — 3. Počet orbit akce grupy symetrií na S, tj. náš hledaný počet odlišných obarvení, je pak _ 27 + 3-9 + 2-3 _ 60 _ 1+3+2 6 2 na součin ireducibilních prvků v 1.4. (2b.) Rozložte polynom x4 — a oborech C[x], Q[x], 1§\x\, Zs[x]. Řešení. Evidentně x4 — x2 — 2 = (x2 — 2)(x2 + 1). Rozklad nad C je (x — V2)(x + V2)(x-i)(x + i), nad IR je (x - V2)(x + V2)(x2 + 1), nad Q je (x2 - 2)(x2 + 1). V Z5 ani Z3 polynom x2 — 2 nemá kořen a je tedy ireducibilní. Stejně tak je x2 + 1 ireducibilní v Z3. V Z5 je ovšem x2 + 1 — (x — 2)(x + 2). 1.5. (2b.) Mějme lineární (8, 3) kód generovaný polynomem x5 + x4 + x2 + 1. Určete generující matici a matici parity. Dále zakódujte zprávu lila naopak určete odeslanou zprávu, jestliže jste obdrželi kódové slovo 01010010 a předpokládáte, že došlo k nejmenšímu možnému počtu chyb. Řešení. Spočítáme ' " ' + 1 2 |_^ 7 _ 4 i Odtud máme generující matici a matici parity G 1 1\ 0 1 1 i 1 0 0 1 1 i 1 0 i 0 0 0 1 0 0 v o o o Vo 1\ 1 0 1 Zakódovanou zprávu dostaneme vynásobením zaprávy maticí G, tj. lilu- 10000111. Obdržená zpráva odpovídá polynomu 01010010 y je x3 respektive x2y. Vytvořením S-polynomu získáme y(x3 — 2xy) — x(x2y + x — 2y2) — —x2. Ze soustavy pak plyne, že levá strana je nulová, a proto i x — 0 a tedy i y — 0. Vyhovuje jí tedy jediný bod (0, 0). Báze není Grôbnerova, protože x2 ^ (x3, x2y).