MB141,13.9.2023, zkouška, skupina X
Příklad. 1A. [2 body] Uvažujme vektorový prostor IR4. Rozhodněte, které z vektorů
Ul = (2,-1,2,3), u2 = (1,-3,-11,3)
patří do podprostoru P generovaného vektory
Vl = (1, -1, -1,1), v2 = (3, -5, -1,1), v3 = (0, 5,1,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:
/ 1
V
1 \
-3 -11
/ 1 0 0
3 0
-2 5
0 -2
0 0
2 \
-2 -4
5 0
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í / :
; je symetrií (zrcadlením) podle roviny
p : x\ = 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 = (1,0, 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 = (0,1, 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:
f-1  0 0N M=     0 10
\o   0 1,
□
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:
3 0
-2 3
1 0
0
Soustava zřejmě nemá řešení, podprostory jsou tedy rovnoběžné. Příklad. 2A. [2 body] Najděte celá čísla x, y, aby platilo
27x + 19y = 1.
□
i
2
Řešení. Čísla 27,19 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:
Soustava
27 =	19 + 8,	19(x + y) -	-f 8x =	1
19 =	2-8 + 3,	8(3x + 2y) + 3(x	+ y) =	1
8 =	2-3 + 2,	3(7x + by) + 2(3x -}	-2y) =	1
3 =	2 + 1,	2(10x + 7y) + (7x -}	-by) =	1
	lOx + 7y = 0,	7x + by	= 1	
má řešení x = —7, y = 10 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 = 29, tj. najděte inverzi d k e modulo 4>(n).
b) V daném kryptosystému zašifrujte zprávu M = 17 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 29cř = 1 (mod 216) má řešení d = 149.
b) Dostáváme 1729 = 45 = 4 • 32 = -3 (mod 13) a 1729 = (-2)11 = -2 • 45 = —8 • (—3)2 = 4 (mod 19). Z druhé kongruence 1729 = 19í + 4, dosazením do první a vyřešením dostaneme t = 1 (mod 13), takže C = 1729 = 23 (mod 247). □
Příklad. 3A. [2 body] Určete vzdálenost bodu A = [5, 2] od přímky p : x + 3y = 1 v 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 = (1,3). 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
(5 + ŕ) + 3(2 + 3r) = 1, jejímž řešením je t = — 1. Vzdálenost určíme jako velikost vektoru tn:
d(A,p) = \\tn\\ = \t\ ■ \\n\\ = | - 1| • Vl2 + 32 = VTÔ.
□
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) = 1/2, P (A -*B) = 1/2, P(B -+A) = 1/3,
P(B -*B) = 1/3, P (A -+ C) = 0, P(C -+A) = 1/2,
P(B -+C) = 1/3, P(C -+B) = 1/2, P(C -> C) = 0,
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
/l/2   1/3 l/2\ M = j 1/2   1/3   1/2 . \ 0    1/3 OJ
Primitivnost můžeme prověřit symbolickým umocňováním matice + 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 = (3, 3,1). Jeho vydělením číslem 3 + 3 + 1 = 7 dostaneme pravděpodobnostní vektor (3/7,3/7,1/7). Stav A tedy bude navštěvován s pravděpodobno stí 3 / 7. □