MB141, 23.5.2023, zkouška, skupina X
Příklad. 1A. [2 body] Uvažujme vektorový prostor IR4. Rozhodněte, které z vektorů
Ul = (1,3,-3,-11), u2 = (2,3,-1,2)
patří do podprostoru P generovaného vektory
Vl = (1,1, -1, -1), v2 = (3,1, -5, -1), v3 = (0, 3, 5,1).
Řešení. Vektory vi,v2, v% naskládáme jako sloupce nalevo do maticového schématu. Kdybychom testovali jeden vektor, zařadili bychom ho napravo a zjišťovali, zda navyšuje hodnost matice, či ekvivalentně, zda má odpovídající soustava rovnic řešení. Úpravy na schodový tvar by se ovšem prováděly pro oba vektory ui,u2 stejně, můžeme si tedy postup racionalizovat a vyřešit jediným schématem, kde vypíšeme vpravo oba vektory:
/ 1
V
3 0	1	2			( 1	3	0	1	2\
1 3	3	3			0	-2	3	2	1
-5 5	-3	-1		r^j • • • r^j	0	0	2	-4	0
-1 1	-11	2	/			0	0	0	
Sloupec vektoru u2 vyčnívá za poslední schod určený levou stranou, zvýšil by tak hodnost hodnost matice, a proto v podprostoru P neleží. Naopak u\ se do tohoto posledního schodu vejde, tj. je nutně lineární kombinací vektorů i>i, i>2, ^3 a patří tedy do P. □
Příklad. 1B. [2 body] Nechť zobrazení / : IR3 —> IR3 je symetrií (zrcadlením) podle roviny p : x2 = 0. Najděte matici M takovou, že v souřadnicích standardní báze je f{x) = Mx.
Řešení. Normálovým vektorem roviny p je, n = (0,1, 0). Ten se při zrcedlení zobrazí na opačný vektor: f{n) = —n. V rovině p leží mimo jiné další dva vektory standardní báze u = (1, 0, 0) a v = (0, 0,1) a ty zůstávají při zrcadlení na místě: f{u) = u, f (v) = v. Protože známe obrazy všech vektorů standardní báze, jejich prostým poskládáním do sloupců dostáváme ihned matici M:
íl    0 0N
M =   0  -1 0
V°    0 \
□
Příklad. 1C. [2 body] V prostoru IR3 určete průnik roviny p : x — 2y + 3z = 2 a přímky p : x + y = —l,y — z = —1. Jaká je jejich vzájemná poloha?
Řešení. Body průniku musí současně vyhovovat všem rovnicím, budeme je tedy řešit jako soustavu lineárních rovnic:
0
Soustava má zřejmě nekonečně mnoho řešení (s jedním parametrem), průnikem je tak celá přímka p a platí pCp. □
Příklad. 2A. [2 body] Určete zbytek po dělení čísla 5^ jedenácti.
2
Řešení. Podle malé Fermatovy věty platí 510 = 1 (mod 11), čehož využijeme ke snížení exponentu 55 na jeho zbytek po dělení deseti. Platí 55 = 5 • (52)2 = 5 (mod 10), proto 555 = 55 = 5 • (52)2 = 5 • 32 = 1 (mod 11). Zbytek po dělení čísla 555 jedenácti je 1. □
Příklad. 2B. [5 bodů] Alice a Bob používají pro šifrovanou komunikaci protokol ElGamal. Veřejnými informacemi jsou modul 13 a primitivní kořen g = 7.
a) Ověřte, že g je skutečně primitivní kořen.
b) Útočnici Evě se podařilo vyzvědět společný soukromý klíč gab = 6, z nějž díky výpočtům v části a) zvládla určit exponent ab = ?, a také Bobův soukromý klíč 6 = 5. Pomozte Evě dokončit rozbití šifry a určete Alicin soukromý klíč a.
Řešení, a) Číslo g je primitivním kořenem, pokud 0(13) = 12 je nejmenší přirozený exponent x, pro nějž je gx = 1 (mod 13). Protože 12 = 22 • 3, stačí prověřit mocniny g pro maximální dělitele 12, což jsou 4 a 6. (Pokud g4 ^ 1 a ge ^ 1, pak gx = 1 až pro x = 12.) Dostáváme (vše v modulu 13):
72 = 49 = -3,
74 = (-3)2 = -4^1,
76 = (-3)3 = -4- (-3) = -1^1,
tedy g = 7 je primitivní.
b) Potřebujeme s co nejmenší námahou zjistit exponent ab ze znalosti společného klíče gab = 6, odkud se znalostí b už snadno určíme a. Ve výpočtech z a) jsme zjistili, že 71 = 7 a 76 = —1, z čehož plyne 77 = 71+6 = 7 • (—1) = —7 = 6. To znamená, že ab = 5a = 7 (mod 12) a tedy a = 11 (mod 12). □
Příklad. 3A. [2 body] Určete vzdálenost bodu A = [3, 2] od přímky p : 2x — y = —lv rovině IR2.
Řešení. Vzdálenost se bude realizovat ve směru kolmém na přímku, tedy ve směru normálového vektoru n = (2,-1). Pata kolmice B na přímce p je tedy tvaru A + tn pro vhodné t a současně splňuje rovnici přímky. Dosazením tohoto parametrického vyjádření dostaneme rovnici
2(3 + 2t) - (2-r) = -1, jejímž řešením je t = — 1. Vzdálenost určíme jako velikost vektoru tn:
d(A,p) = \\tn\\ = \t\ ■ \\n\\ = | - 1| • ^22 + (-1)2 =
□
Příklad. 3B. [5 bodů] Uvažujeme třístavový Markovův řetězec se stavy A, B,C a pravděpodobnostmi přechodů
P (A -+A)=0, P (A -*B) = 1/2, P(B -+A) = 1/3,
P(B -*B) = 1/3, P (A -*C) = 1/2, P(C -+A) = 0,
P(B -+C) = 1/3, P(C -+B) = 1/2, P(C -+C) = 1/2,
a) Sestavte přechodovou pravděpodobnostní matici M a ověřte, že je primitivní, tj. že nějaká mocnina Mk má všechny členy kladné.
3
b) Určete pravděpodobnost, s jakou se bude po dostatečně dlouhé době systém dostávat do stavu A.
Řešení, a) Matici sestavujeme tak, aby vstupní stavy odpovídaly sloupcům a výstupní stavy řádkům. Při dodržení abecedního pořadí stavů dostaneme matici
/ 0    1/3    0 \
M = j 1/2   1/3   1/2 . \l/2   1/3 1/2/
Primitivnost můžeme prověřit symbolickým umocňováním matice ^ + + + j, přičemž zjistíme, že již M2 je pozitivní.
b) Hledáme vlastní vektor pro vlastní číslo 1, tj. řešíme homogenní soustavu (M — E)x = 0. Netriviálním řešením je například vektor x = (1, 3, 3). Jeho vydělením číslem 1 + 3 + 3 = 7 dostaneme pravděpodobnostní vektor (1/7,3/7,3/7). Stav A tedy bude navštěvován s pravděpodobností 1/7. □