MB141,13.9.2023, zkouška, skupina Y
Příklad. 1A. [2 body] Uvažujme vektorový prostor IR4. Rozhodněte, které z vektorů
U! = (2,0,1,1), u2 = (1,-1, -5,-1)
patří do podprostoru P generovaného vektory
Vl = (1,1,-1,-1), v2 = (1,3,3,1), v3 = (0,1,2,3).
Ř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:
V
1
3 3
■1   1 3
1 \
-1 -5
/ 1 0 0
0 o
2 \
-2 5
7 0
i/ v°
Sloupec vektoru u\ vyčnívá za poslední schod určený levou stranou, zvýšil by tak hodnost hodnost matice, a proto v podprostoru P neleží. Naopak u2 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:
fl    0 0N
M =   0  -1 0
V°    0 \
□
Příklad. 1C. [2 body] V prostoru IR3 určete průnik roviny p : x — 3y + 2z = 1 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:
-3 -1
2 0
-3 2
1 0
0
1 o
Soustava zřejmě nemá řešení, podprostory jsou tedy rovnoběžné. Příklad. 2A. [2 body] Najděte celá čísla x, y, aby platilo
23x + 18y = 1.
□
i
2
Řešení. Čísla 23,18 jsou nesoudělná, tedy podle Bezoutovy věty má rovnice řešení. Toto řešení lze nalézt postupným dělením se zbytkem podle Eukleidova algoritmu a zpětným dosazováním:
23 = 18 + 5, 18(x + y) + 5x = 1,
18 = 3-5 + 3, 5(4x + 3y) + 3(x + y) = l,
5 = 3 + 2, 3(5x + 4y) + 2(Ax + 3y) = 1,
3 = 2 + 1, 2(9x + 7y) + (5x + Ay) = 1.
Soustava
9x + 7y = 0, 5x + 4y = 1
má řešení x = — 7, y = 9 a to je i odpověď na původní úlohu. □
Příklad. 2B. [5 bodů] a) Prolomte šifru RSA s veřejným klíčem n = 247 = 13 • 19, e = 23, tj. najděte inverzi d k e modulo 4>(n).
b) V daném kryptosystému zašifrujte zprávu M = 15 jako C = Me (mod n). Při výpočtu doporučujeme počítat C nejdřív zvlášť modulo 13 a modulo 19 a využít Eulerovy věty pro zjednodušení (zredukování) exponentu, poté dát tyto výsledky dohromady pomocí Čínské zbytkové věty.
Řešení, a) Protože 247 = 13-19, snadno určíme 4>(n) = 12-18 = 216. Kongruence 23cř = 1 (mod 216) má řešení d = 47.
b) Dostáváme 1523 = 211 = 2 • 45 = 8 • 32 = 7 (mod 13) a 1523 = (-4)5 = -4 • (—3)2 = 2 (mod 19). Z druhé kongruence 1523 = 19í+ 2, dosazením do první a vyřešením dostaneme t = 3 (mod 13), takže C = 1523 = 59 (mod 247). □
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-t) = -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. □