2.a 9.10.

1. Kongruence celých čísel a Euklidův algoritmus

Nechť a, b jsou dvě přirozená čísla. Připomeňme Euklidův algoritmus hledání největšího společného dělitele čísel a a b:

gcd(a,b) if b = 0 return a else return gcd(b, a mod b) Postupně tedy počítáme hodnoty a_{i}, kdy a_{0} = a a a_{1} = b, pro něž platí a_{i+1} =

(a_{i−1})mod a_{i}. Tedy víme, že existuje takové q_{i} ∈ N že a_{i−1} = q_{i}a_{i} + a_{i+1} a a_{i+1} < a_{i}. Algoritmus skončí, když a_{n+1} = 0, potom a_{n} = gcd(a_{0}, a_{1}).

1.1. Najděte pomocí Euklidova algoritmu

(a) gcd(4116, 2849),

(b) gcd(7^{1000} − 1, 7^{999} − 1).

(a) Mezivýsledky v běhu Euklidova algoritmu budeme stejně jako výše označovat a_{i}:

a_{0} = 4116, a_{1} = 2849, a_{2} = 4116 − 2849 = 1267, a_{3} = 2849 − 2 · 1267 = 315, a_{4} = 1267 − 4 · 315 = 7 =gcd(4116,2849), a_{5} = 315 − 45 · 7 = 0. Spočítali jsme, že největší společný dělitel čísel 4116 a 2849 je 7.

(b) Všimněme si, že 7 · (7^{999} − 1) − (7^{1000} − 1) = 6 a označíme c = gcd(7^{1000} − 1, 7^{999} − 1) a d = gcd(6, 7^{999} − 1). Protože jistě c|7^{999} − 1 a c|7^{1000} − 1 platí, že c|6 = 7 · (7^{999} − 1) − (7^{1000} − 1). Tedy c je společný dělitel čísel 6 i 7^{999} − 1, proto c|d.

Naopak číslo d dělí hodnotu 6 i 7^{999} − 1, proto dělí i číslo (7^{1000} − 1) = 7 · (7^{999} − 1) − 6, tudíž d|c. Vidíme, že místo gcd(7^{1000} − 1, 7^{999} − 1) stačí spočítat gcd(6, 7^{999} −1). Protože ovšem obecně a^{n+1} −1 = (a−1) ∑_{i=0}^{n} a^{i} a v našem případě 7^{999} − 1 = (7 − 1) ∑_{i=0}^{998} 7^{i}, vidíme, 6/7^{999} − 1, a proto gcd(7^{1000} − 1, 7^{999} − 1) = gcd(6, 7^{999} − 1) = 6. □

Na bodu (b) předchozího příkladu si lze snadno uvědomit, že obdobně funguje indukční krok důkaz Euklidova algoritmu.

1.2. Za předpkladu, že pro všechna a, b, c ∈ N platí podmínka c/a a c/b → c/NSD(a, b), dokažte, že Euklidův algoritmus pro nalezení největšího společného dělitele dvou přirozených čísel pracuje správně.

Budeme používat značení mezivýsledků Euklidova algoritmu zavedené výše. Nejprve si všimněme, že a_{n} = gcd(a_{n−1}, a_{n}), neboť a_{n}/a_{n−1} a poté dokážeme,

že gcd(a_{i}, a_{i+1} ) = gcd(a_{i−1}, a_{i}).

Položme c = NSD(a_{i−1}, a_{i}) a d = NSD(a_{i}, a_{i+1} ). Protože d/a_{i} a d/a_{i+1} , platí, že d/q · ai + a_{i+1} = a_{i−1}, tudíž d/c. Podobně nahlédneme, že c/a_{i+1} = a_{i−1} − q · ai, tedy c = d. Tím jsme ověřili, že

a_{n} = gcd(a_{n}, a_{n−1}) = ⋯ = gcd(a_{2}, a_{1}) = gcd(a_{1}, a_{0}).

□

1.3. Najděte pomocí Euklidova algoritmu celá čísla x a y, aby x bylo kladné a (a) 30x + 101y = 1,

(b) 18x + 25y = 1.

(a) Nejprve si všimněme, že číslo 101 je prvočíslo, tedy největší společný dělitel čísel 30 a 101 je zcela jistě roven jedné. Euklidův algoritmus na nalezení největšího společného dělitele čísel 30 a 101 nám tedy samozřejmě musí dát výsledek 1. Přesto ho použijeme a budeme věnovat pozornost vztahu předchozích a následujících prvků:

a_{0} = 101, a_{1} = 30, a_{2} = 101 − 3 · 30 = 11, a_{3} = 30 − 2 · 11 = 8, a_{4} = 11 − 8 = 3, a_{5} = 8 − 2 · 3 = 2, a_{6} = 3 − 2 = 1 = gcd(101, 30). Vidíme, že každé a_{i+1} je celočíselnou kombinací prvků a_{i} a a_{i−1}, budeme-li

postupně dosazovat předchozí vyjádření do následujících výrazů, dostaneme každé a_{i+1} jako celočíselnou kombinací prvků a_{0} a a_{1}:

a_{2} = 11 = 101 − 3 · 30, (to je vyjádření využívající přímo hodnot 30 a 101)

a_{3} = 8 = 30 − 2 · 11 = 30 − 2 · (101 − 3 · 30) = 7 · 30 − 2 · 101, (dosadíme jen za 11) a_{4} = 3 = 11 − 8 = (101 − 3 · 30) − (7 · 30 − 2 · 101) = 3 · 101 − 10 · 30, a_{5} = 2 = 8 − 2 · 3 = (7 · 30 − 2 · 101) − 2 · (3 · 101 − 10 · 30) = 27 · 30 − 8 · 101, a_{6} = 1 = 3 − 2 = (3 · 101 − 10 · 30) − (27 · 30 − 8 · 101) = 11 · 101 − 37 · 30. Našli jsme řešení x = −37 a y = 11, které ovšem nevyhovuje požadavku na

kladnost x. Upravíme-li rovnost

1 = 11 · 101 − 37 · 30 + c · 101 · 30 − cc · 101 · 30 = (11 + 30c) · 101 − (37 + 101c) · 30

vidíme, že řešením úlohy jsou hodnoty x = −37 − 101c a y = 11 + 30c pro každé celé c. Zvolíme-li c = −1 dostáváme vyhovující řešení x = 64 a y = −19.

(b) Protože gcd(18, 25) = 1, zaručuje nám Euklidův algoritmus existenci požadovaných čísel x, y ∈ Z. Euklidův algoritmus použijeme (podobně jako v předchozí úloze) i k jejich nalezení:

a_{0} = 25, a_{1} = 18, a_{2} = 7 = 25 − 18, a_{3} = 4 = 18 − 2 · 7 = 18 − 2 · (25 − 18) = 3 · 18 − 2 · 25, a_{4} = 3 = 7 − 4 = 25 − 18 − (3 · 18 − 2 · 25) = 3 · 25 − 4 · 18, a_{5} = gcd(25, 18) = 1 = 4 − 3 = 3 · 18 − 2 · 25 − (3 · 25 − 4 · 18) = 7 · 18 − 5 · 25. Vidíme, že x = 7 a y = −5. □

Hodnotám x a y,které jsme našli pomocí Euklidova algoritmu se obvykle říká Bezoutovy koeficienty. V následující úloze ukážeme, že lze nalezení Bezoutových koeficientů snadno formalizovat rekurentním vzorcem.

1.4. Uvažujme hodnoty a_{0} > a_{1} > ⋯ > a_{i+1} > a_{i} > … a_{n} = gcd(a_{0}, a_{1}) získané během Euklidova algoritmu, tj. a_{i−1} = q_{i}a_{i} + a_{i+1} a a_{n}|a_{n−1}. Definujme posloupnosti x_{i} a y_{i} tak, že x_{0} = y_{1} = 1, x_{1} = y_{0} = 0, a pro i ≥ 1 položme x_{i+1} = x_{i−1} − x_{i} · q_{i} a y_{i+1} = y_{i−1} − y_{i} · q_{i}. Dokažte, že a_{i} = x_{i} · a_{0} + y_{i} · a_{1} pro každé i = 0, …, n, a speciálně, že gcd(a_{0}, a_{1}) = x_{n} · a_{0} + y_{n} · a_{1}.

Platnost formule a_{i} = x_{i} · a_{0} + y_{i} · a_{1} dokážeme indukcí podle i. Pro i = 0, 1 dostáváme x_{0} · a_{0} + y_{0} · a_{1} = 1 · a_{0} + 0 · a_{1} = a_{0} a x_{1} · a_{0} + y_{1} · a_{1} =

0 · a_{0} + 1 · a_{1} = a_{1}.

Předpokládejme, že tvrzení platí pro i − 1 a i, tedy, že platí

a_{i−1} = x_{i−1} · a_{0} + y_{i−1} · a_{1} a a_{i} = x_{i} · a_{0} + y_{i} · a_{1}

a dokážeme, že tvrzení platí i pro i + 1. Dosadíme-li do (obecně platného) výrazu a_{i+1} = a_{i} · q_{i} − a_{i−1} hodnoty a_{i} a a_{i−1} z indukčního předpokladu, dostaneme

a_{i+1} = (x_{i} · a_{0} + y_{i} · a_{1}) · q_{i} − x_{i−1} · a_{0} + y_{i−1} · a_{1} =
= (x_{i−1} − x_{i} · q_{i}) · a_{0} + (y_{i−1} − y_{i} · q_{i}) · a_{1} = x_{i+1} · a_{0} + y_{i+1} · a_{1}.

Tedy a_{i+1} = x_{i+1} · a_{0} + y_{i+1} · a_{1}, což jsme měli ověřit. □

1.5. Najděte řešení rovnice 30x ≡ 1 (mod 101).

Hledáme celá x a y, aby 30x+101y = 1. Tuto úlohu jsme ovšem řešili v Příkladu 1.3, tedy 11 · 101 − 37 · 30 = 1 a 30 · (−37) ≡ 1 (mod 101), proto x = −37. □

1.6. Najděte celá čísla x a y, aby (a) gcd(891, 473) = 891x + 473y,

(b) gcd(4321, 1234) = 4321x + 1234y.

(a) Položíme a_{0} = 891 a a_{1} = 495 a počítáme stejně jako v úloze 1.3: a_{2} = 418 = 891 − 473, a_{3} = 55 = 473 − 418 = 473 − (891 − 473) = 2 · 473 − 891, a_{4} = 33 = 418 − 7 · 55 = (891 − 473) − 7 · (2 · 473 − 891) = 8 · 891 − 15 · 473, a_{5} = 22 = 55 − 33 = (2 · 473 − 891) − (8 · 891 − 15 · 473) = 17 · 473 − 9 · 891, a_{6} = 11 = 33 − 22 = (8 · 891 − 15 · 473) − (17 · 473 − 9 · 891) = 17 · 891 − 32 · 473. Spočítali jsme, že 11 = gcd(891, 473) = 17 · 891 − 32 · 473, proto tedy x = 17 a

y = −32.

(b) Tentokrát použijeme rekurentní vzorec. Nejprve ovšem opět musíme spočítat celočíselné zbytky i podíly v průběhu Euklidova algoritmu pro a_{0} = 4321 a a_{1} = 1234:

a_{2} = 619 = 4321 − 3 · 1234, tedy q_{1} = 3, a_{3} = 615 = 1234 − 619, tedy q_{2} = 1, a_{4} = 4 = 619 − 615, tedy q_{3} = 1, a_{5} = 3 = 615 − 153 · 4, tedy q_{4} = 153, a_{6} = 1 = 4 − 3, tedy q_{5} = 1, Nyní položíme (x_{0}, y_{0}) = (1, 0) a (x_{1}, y_{1}) = (0, 1) a počítáme:

x_{2} = x_{0} − q_{1}x_{1} = 1 − 3 · 0 = 1 a y_{2} = y_{0} − q_{1}y_{1} = 0 − 3 · 1 = −3,

x_{3} = x_{1} − q_{2}x_{2} = 0 − 1 · 1 = −1 a y_{3} = y_{1} − q_{2}y_{2} = 1 − 1 · (−3) = 4, x_{4} = x_{2} − q_{3}x_{3} = 1 − 1 · (−1) = 2 a y_{4} = y_{2} − q_{3}y_{3} = −3 − 1 · 4 = −7,

x_{5} = x_{3} −q_{4}x_{4} = −1−153·2 = −307 a y_{5} = y_{3} −q_{4}y_{4} = 4−153·(−7) = 1075, x_{6} = x_{4}−q_{5}x_{5} = 2−1·(−307) = 309 a y_{6} = y_{4}−q_{5}y_{5} = −7−1·1075 = −1082, Spočítali jsem, že gcd(4321, 1234) = 1 = 4321 · 309 − 1234 · 1082, tedy x = 309 a y = −1082. □

1.7. Najděte x ∈ Z splňující

(a) 1234x ≡ 1 (mod 4321),

(b) 1234x ≡ 1 (mod 4321) a x > 0

(c) 1234x ≡ 2 (mod 4321),

(a) Úlohu už jsme vyřešili v předchozím příkladu, kde jsme spočítali, že

1234 · (−1082) ≡ 1 (mod 4321),

proto řešením je například x = −1082.

(b) Snadno nahlédneme, že naší kongruenci řeší všechny hodnoty

x = 4321 · a − 1082

pro libovolné celé a, tedy zadané podmínce vyhovuje například řešení x = 4321 − 1082 = 3239.

(c) Tentokrát stačí vynássobit řešení úlohy (a) nebo (b) dvojkou, tedy například x = −2164. □

1.8. Najděte poslední cifru čísla celá čísla x a y, aby (a) 7^{777},

(b) 153^{831}.

(a) Zajímá nás hodnota (7^{777})mod 10. Počítejme:

(7^{1})mod 10 = 7, (7^{2})mod 10 = 9, (7^{3})mod 10 = (9 · 7)mod 10 = 3,

(7^{4})mod 10 = (3 · 7)mod 10 = 1.

To znamená, že

(7^{777})mod 10 = (7^{776} · 7)mod 10 = ((7^{4})^{194} · 7)mod 10 = (1^{194} · 7)mod 10 = 7.

(b) Stejně jako v případě (a) nahlédneme, že (3^{4})mod 10 = 1, proto

(153^{831})mod 10 = (3^{831})mod 10 = (3^{828} · 3^{3})mod 10 = ((3^{4})^{207} · 7)mod 10 = 7.

□

1.9. Dokažte, že je číslo 16^{15} + 29^{14} + 42^{13} dělitelné číslem 13.

Potřebujeme dokáat, že (16^{15} + 29^{14} + 42^{13}) ≡ 0 (mod 13). Proto upravujme:

(16^{15} + 29^{14} + 42^{13}) ≡ 3^{15} + 3^{14} + 3^{13} ≡ 3^{13} · (9 + 3 + 1) ≡ 3^{13} · 0 ≡ 0 (mod 13),

čímž jsme hotovi. □

1.10. Dokažte, že n^{6} − n^{2} je dělitelné číslem 60 pro každé přirozené n.

Nejprve upravíme (n^{6} − n^{2}) = (n^{2} − 1)n^{2}(n^{2} + 1) = (n − 1)n(n + 1)n(n^{2} + 1). Protože (n − 1), n, (n + 1) jsou tři po sobě jdoucí čísla, je právě jedno z nich je dělitelné třemi a spoň jedno dělitelné dvěma, proto 6|(n − 1)n(n + 1)|(n^{6} − n^{2}). Tedy

n^{6} − n^{2} ≡ n^{2}(n^{4} − 1) ≡ (n^{2} − 1)n^{2}(n^{2} + 1) ≡ (n^{2} − 1)n^{2}(n^{2} − 4) (mod 5)

a dále (n^{2} − 1)n^{2}(n^{2} − 4) ≡ n(n − 2)(n − 1)n(n + 1)(n + 2) ≡ 0 (mod 5).

Protože (n − 2), (n − 1), n, (n + 1), (n + 2) je pět po sobě jdoucích čísel, tudíž právě jedno z nich je dělitelné pěti. Tím jsme dokázali, že nejmenší společný násobek čísel 3, 4 a 5, jímž je číslo 60, dělí n^{6} − n^{2}. □

16.10.

1.11. Najděte největšího společného dělitele reálných polynomů

p = x^{4} + x^{3} + 2x^{2} + x + 1 a q = x^{3} + x^{2} + x + 1.

Dále najděte reálné polynomy a a b tak, aby gcd(p, q) = a.p + b.q.

I tentokrát můžeme podobně jako v případě počítání v celých číslech k hledání největšího společného dělitele dvou polynomů (tj. monického polynomu, který oba polynomy dělí a je největšího možného stupně) použít Euklidův algoritmus. Místo celočíselného dělení se zbytkem budeme ovšem používat dělení polynomů se zbytkem (připomeňme, že zbytek po takovém dělení musí být buď nulový nebo musí mít stupeň menší než dělitel). Není težké nahlédnout, že stejným postupem jako v úloze 1.2, lze obecně ověřit korektnost algoritmu. Počítejme:

a_{0} = x^{4} + x^{3} + 2x^{2} + x + 1,

a_{1} = x^{3} + x^{2} + x + 1,

a_{2} = x^{2} + 1 = x^{4} + x^{3} + 2x^{2} + x + 1 − x.(x^{3} + x^{2} + x + 1),

a_{3} = 0 = x^{3} + x^{2} + x + 1 − (x + 1)(x^{2} + 1).

Největším společným dělitelem polynomů x^{4} + x^{3} + 2x^{2} + x + 1 a x^{3} + x^{2} + x + 1 je polynom x^{2} + 1. Rozšířený Euklidův algoritmus má tentokrát jediný krok, tedy hledané polynomy jsou a = 1 a b = −x. □

1.12. Najděte polynomy a, b ∈ R[x] tak, aby 1 = a · (x^{3} + 2) + b · (x^{2} + 1).

Opět využijme rozšířeného Euklidova algoritmu na polynomy a_{0} = x^{3} + 2 a a_{1} = x^{2} + 1:

a_{2} = −x + 2 = x^{3} + 2 − x · (x^{2} + 1),

a_{3} = 5 = x^{2} + 1 + (x + 2) · (−x + 2) = (x + 2) · (x^{3} + 2) + (−x^{2} − 2x + 1) · (x^{2} + 1), Vydělením číslem 5 dostáváme 1 = \frac{1}{5}(x+2)·(x^{3} +2)+ \frac{1}{5}(−x^{2} −2x+1)·(x^{2} +1).

Spočítali jsme, že a = \frac{x+2}{5} a b = \frac{−x^{2} −2x+1}{5} . □

2. Řešení soustav lineárních rovnic

2.1. Najděte reálné rešení soustavy rovnic:

\begin{aligned}x & + & 2y & + & z & = & 1 \\ −2x & + & y & + & 2z & = & 2 \\ x & + & 3y & − & z & = & 0 \end{aligned}

Nejprve si soustavu zapíšeme do rozšířené matice (stejně jako v sekci 2.3.2 na přednášce) a poté ji pomocí přičtení vhodného násobku jedné rovnice k rovnici druhé upravíme (na střední škole se tento způsob upravování obvykle nazývá ţsčítací metoda”), vše si budeme zapisovat pomocí maticového zápisu. Připomeňme, že soustava rovnic na levo od symbolu ∼ má stejnou množinu řešeni jako soustava rovnic napravo od něj:

(\begin{matrix}1 & 2 & 1 & |1 \\ −2 & 1 & 2 & |2 \\ 1 & 3 & −1 & |0 \end{matrix}) ∼ (\begin{matrix}1 & 2 & 1 & | & 1 \\ 0 & 5 & 4 & | & 4 \\ 0 & 1 & −2 & | & −1 \end{matrix}) ∼ (\begin{matrix}1 & 2 & 1 & | & 1 \\ 0 & 1 & −2 & | & −1 \\ 0 & 5 & 4 & | & 4 \end{matrix}) ∼

Druhý řádek první upravené matice, který odpovídá rovnici 5y+4z = 4, jsme dostali přičtením dvojnásobku rovnice x + 2y + z = 1 k rovnici −2x + y + 2z = 2 (tedy přičtením dvojnásobku řádku (1 2 1|1) k řádku (−2 1 2|2)) a podobně třetí řádek vznikl z původního třetího řádku odečtením prvního. V dalším kroku jsme jen přehodili řádky (tedy rovnice), pokračujme v úpravách dále:

∼ (\begin{matrix}1 & 2 & 1 & | & 1 \\ 0 & 1 & −2 & | & −1 \\ 0 & 0 & 14 & | & 9 \end{matrix}) ∼ (\begin{matrix}1 & 2 & 1 & | & 1 \\ 0 & 1 & −2 & | & −1 \\ 0 & 0 & 1 & | & \frac{9}{14} \end{matrix}) ∼

∼ (\begin{matrix}1 & 2 & 1 & | & 1 \\ 0 & 1 & 0 & | & \frac{4}{14} \\ 0 & 0 & 1 & | & \frac{9}{14} \end{matrix} ) ∼ (\begin{matrix}1 & 0 & 0 & | & −\frac{3}{14} \\ 0 & 1 & 0 & | & \frac{2}{7} \\ 0 & 0 & 1 & | & \frac{9}{14} \end{matrix} ) .

Odečtením pětinásobku druhého řádku od třetího už jsme mohli skončit a poté využít zpětné substituce, ale uvědomme si, že můžeme k výsledku dospět i v maticovém zápisu, tj. můžeme levou stranu matice upravit až na jednotkovou matici. To znamená, že ve sloupci vpravo máme postupně jednoznačně nalezené hodnoty x = −\frac{3}{14} , y = \frac{2}{7} a z = \frac{9}{14} . □

2.2. Najděte všechna reálná rešení soustavy rovnic:

\begin{aligned}x & + & 2y & + & z & = & 1 \\ −2x & + & y & + & 2z & = & 2 \end{aligned}

Znovu si soustavu zapíšeme do matice a poté ji pomocí přičtení vhodného násobku jedné rovnice k rovnici druhé upravíme stejně jako v úloze 1.1:

(\begin{matrix}1 & 2 & 1 & |1 \\ −2 & 1 & 2 & |2 \end{matrix}) ∼ (\begin{matrix}1 & 2 & 1 & |1 \\ 0 & 5 & 4 & |4 \end{matrix}) ,

Snadno si uvědomíme, že dosadíme-li za z libovolnou hodnotu, pak jednoznačně dopočítáme y a x. Položíme-li například z = 0, pak z rovnice 5y+4·0 = 4 dostáváme, že y = \frac{4}{5} a z rovnice x + 2 · \frac{4}{5} + 0 = 1 spočítáme, že x = −\frac{3}{5}. Našli jsme tedy jedno řešení dané soustavy, které můžeme zapsat do trojice (x, y, z)^{T} = (−\frac{3}{5}, \frac{4}{5}, 0)^{T}. Podobně jsme jiné řešení mohli dostat po volbě z = 1 a jednoznačném dopočítání y = x = 0.

Nzní si uvědomme geometrický význam řešení dané soustavy: každou z rovnic chápeme jako rovinu v R^{3} (tvořenou všemi trojicemi (x, y, z), které rovnici řeší) a množina řešení celé soustavy je průnik těchto dvou rovin. Všimneme-li si navíc, že roviny zjevně nejsou rovnoběžné, musí množinu všech řešení tvořit přímka, jejíž jeden bod (−\frac{3}{5}, \frac{4}{5}, 0) už jsme našli a jejíž směr je dán vektorem (3, −4, 5) (jde právě o netriviální řešení soustav rovnic se stejnými levými a nulovými pravými stranami). Z geometrického náhledu tedy vidíme, že množin všechna řešení je přímka tvaru \{(−\frac{3}{5} + 3t, \frac{4}{5} − 4t, 5t)^{T} | t ∈ R\} □

Připomeňme, že Věta 2.14 z přednášky dokazuje negeometricou argumentací, že jsme v předchozí úloze našli všechna řešení soustavy. Zjevnou výhodou analytického důkazu je to, že se nemusíme omezovat jen na rovnice o dvou či třech neznámých.

2.3. Najděte všechna reálná rešení soustavy rovnic:

x_{1} + x_{2} − x_{4} = 1
x_{2} + x_{3} + x_{4} = 3
− x_{3} + 2x_{4} = 0
x_{3} + 3x_{4} = 5

Soustavu si opět můžeme zapsat do matice a poté ji (jedinou elementární řádkovou úpravou) upravíme na odstupňovanou matici:

(\begin{matrix}1 & 1 & 0 & −1 & |1 \\ 0 & 1 & 1 & 1 & |3 \\ 0 & 0 & −1 & 2 & |0 \\ 0 & 0 & 1 & 3 & |5 \end{matrix}) ∼ (\begin{matrix}1 & 1 & 0 & −1 & |1 \\ 0 & 1 & 1 & 1 & |3 \\ 0 & 0 & −1 & 2 & |0 \\ 0 & 0 & 0 & 5 & |5 \end{matrix})

Nyní už snadno jednoznačně dopočítáme neznámé zpětnou substitucí. Z posledního řádku 5x_{4} = 5 dostáváme, že x_{4} = 1, z předposledního řádku −x_{3}+2x_{4} = 0 vidíme, že −x_{3} +2 = 0, tedy x_{3} = 2. Dále z druhé rovnice x_{2} +x_{3} +x_{4} = 3 obdržíme x_{2} = 0 a konečně z rovnice x_{1} + x_{2} − x_{4} = 1 dostaneme x_{1} = 2. Vidíme, že existuje jediné řešení soustavy (x_{1}, x_{2}, x_{3}, x_{4}) = (2, 0, 2, 1). □

2.4. Najděte všechna racionální rešení soustavy rovnic z úlohy 2.2.

Stačí si rozmyslet, že z množiny řešení úlohy 2.2 musíme vybrat ta, která jsou ve všech složkách racionální. Není težké nahlédnout, že součin, součet i rozdíl racionálních čísel je opět racionální, proto množina M = \{(−\frac{3}{5} + 3t, \frac{4}{5} − 4t, 5t)^{T} | t ∈ Q} jistě obsahuje racionální řešení soustavy. Protože součin, součet a rozdíl nenulového racionálního a iracionálního čísla je zjevně iracionální, obsahuje vektor (−\frac{3}{5} + 3t, \frac{4}{5} − 4t, 5t)^{T} pro každé iracionální t iracionální hodnoty, tudíž množina M je právě množinou všech racionálních rešení soustavy. □

23.10.

3. Konečná tělesa

Připomeňme, na množině Z_{n} definice operací +_{n} a ·_{n} předpisem a +_{n} b = (a + b)mod n a a ·_{n} b = (a · b)mod n, kde mod n znamená zbytek po celočíselném dělení hodnotou n.

3.1. Je-li n > 1 celé číslo, dokažte, že Z_{n} spolu s operacemi +_{n} a ·_{n} splňuje axiomy (S1)–(S4), (N1), (N2), (N4), (D) a (¬T) z definice tělesa.

Z vlastností kongruencí, jednoznačnosti zbytku po celočíselném dělení a asociativity sčítání na celých číslech spočítáme, že

(a +_{n} b) +_{n} c = ((a + b)mod n + c)mod n= ((a + b) + c)mod n =
(a + (b + c))mod n= ((a + b)mod n + c)mod n = a +_{n} (b +_{n} c).

Stejnou úvahou pro násobení dostaneme

(a ·_{n} b) +_{n} c= ((a · b) · c)mod n = (a · (b · c))mod n= a ·_{n} (b ·_{n} c).

Ukázali jsme, že jsou axiomy (S1) a (N1) splněny. Platnost komutativních zákonů, tedy axiomů (S4) a (N4) plyne okamžitě z definice operací a komutativity příslušných operací na celých číslech, podobně snadno z definice operací nahlédneme, že 0+_{n}a = a a 1·_{n}a = a pro každé a ∈ Z_{n}, tedy i axiomy (S2) a (N2) platí. Dále −0 = 0 a −a = n − a pro všechna a ∈ Z_{n} \ {0}, protože (a + n − a)mod n = (n)mod n = 0. odkud dostáváme platnost axiomu (S3). Distributivitu, tedy axiom (D), ověříme stejně jako asociativitu s využitím distributivity na celých číslech:

(a +_{n} b) ·_{n} c= ((a + b) · c)mod n = (a · c + b · c)mod n= a ·_{n} c +_{n} b ·_{n} c.

Konečně axiom netriviality je zřejmý z předpokladu, že n > 1. □

3.2. Jsou-li r, s ∈ N, r > 1, s > 1 a položme n = rs. Dokažte, že Z_{n} spolu s operacemi +_{n} a ·_{n} není těleso.

Ukázali jsme, že Z_{n} splňuje všechny axiomy tělesa s výjimkou axiomu (N3). Protože víme, že v každém tělese musí podle Tvrzení 3.3(6) z přednášky platit pro a ≠ 0 a b ≠ 0, že a · b ≠ 0, stačí, abychom tuto podmínku vyvrátili. Položíme-li a = r a b = s, pak vidíme, že a ≠ 0 a b ≠ 0, ovšem a · b = (n)mod n = 0. □

Jak bylo na přednášce ukázáno ve Větě 3.4 tvoří Z_{p} pro p prvočíslo těleso (v dalším budeme u operací index _{p} obvykle vynechávat). Připomeme, že nalezení inverzního prvky je dokázáno konstruktivně pomocí Euklidova alůgoritmu:

3.3. Najděte inverzní prvek k prvku 30 v tělese Z_{101}.

Potřebujeme najít číslo x ∈ Z_{101}, které by řešilo rovnici (30 · x)mod 101 = 1, což můžeme reformulovat tak, že hledáme celá x a y, z nichž x má ležet v Z_{101}, aby 30x + 101y = 1. Tuto úlohu už jsme ovšem vyřešili v Příkladu 1.3, nyní si stačí uvědomit, že nalezené x, které neleží v požadovaném intervalu můžeme posunout pomocí vhodného násobku čísla 101. Dostaneme tedy zbytek po celočíselném dělení číslem 101, tj. 30^{−1} = (−37)mod 101 = 101 − 37 = 64, protože

1 = 11·101−37·30 = 11·101−30·101+101·30−37·30 = (11−30)·101+(101−37)·30.

Tedy jsme našli další a pro nás zajímavější řešení řešení 1 = 64·30−19·101 rovnice z 1.3.

3.4. Najděte nad tělesem Z_{101} prvky 63^{−1}, 20^{−1}, 2^{−1}, (20 · 63)^{−1} a vyřešte nad ním rovnici 20 ·_{101} x = 7.

U prvních dvou hodnot postupujme stejně jako v předchozích úvahách, tedy využijeme Euklidův algoritmus:

38 = 101 − 63,

25 = 63 − 38 = 2 · 63 − 101,

13 = 38 − 25 = 2 · 101 − 3 · 63,

12 = 25 − 13 = 5 · 63 − 3 · 101,

1 = 13 − 12 = 5 · 101 − 8 · 63.

Zjistili jsme, že 63^{−1} = (−8)mod 101 = 93.

Podobně už v prvním kroku Euklidova algoritmu zjistíme, že 1 = 101 − 5 · 20, tedy 20^{−1} = (−5)mod 101 = 96

Při určování hodnoty 2^{−1} můžeme udělat jednoduchou obecnou úvahu pro Z_{p}, kde p je liché prvočíslo, že \frac{p+1}{2} ∈ Z_{p} a že (2 · \frac{p+1}{2} )mod p = (p + 1)mod p = 1, tedy 2^{−1} = \frac{101+1}{2} = 51 v tělese Z_{101}.

Uvážíme-li, že z axiomatiky tělesa plyne (a·b)^{−1} = a^{−1}·b^{−1} a (−a)^{·}(−b) = a·b pro všechny jeho prvky a a b (zkuste podrobně dokázat!), a využijeme-li vypočítaných hodnot, pak

(20 ·_{101} 63)^{−1} = 20^{−1} ·_{101} 63^{−1} = (−5) ·_{101} (−8) = 40.

Protože obvyklý způsob upravovaní rovnic je ekvivalentní (tj. vratný) i pro rovnice nad obecným tělesem, zjišťujeme, že hledané x je tvaru x = 20^{−1} ·_{101} 7 = 96 ·_{101} 7 = 66. □

Nadále budeme sčítání a násobení v tělese Z_{p} pro prvočíslo p psát bez indexu _{p}, tj. jen + a ·.

3.5. Spočítejte v tělesech Z_{5} a Z_{7} hodnotu výrazu (−2)^{−1} · ((2 + 4) · (4 + 4)^{−1}) + 3.

Postupujeme podle definice operací na Z_{5} i Z_{7}, nejprve počítejme nad Z_{5}:

(−2)^{−1} · ((2 + 4) · (4 + 4)^{−1}) + 3 = 3^{−1} · (1 · 3^{−1}) + 3 = 2 · 2 + 3 = 2.

Podobně dostáváme nad Z_{7}:

(−2)^{−1} · ((2 + 4) · (4 + 4)^{−1}) + 3 = 5^{−1} · (6 · 1^{−1}) + 3 = 3 · 6 + 3 = 0.

□

3.6. Najděte nad tělesem Z_{2} = {0, 1} řešení soustavy rovnic:

x_{3} + x_{4} = 1
x_{1} + x_{3} + x_{4} = 0
x_{1} + x_{4} = 1
x_{1} + x_{2} + x_{3} = 1

Soustavu si i v tomto případě zapíšeme do matice a s počítáním v GF(2) ji budeme upravovat posloupností elementárních úprav:

(\begin{matrix}0 & 0 & 1 & 1 & |1 \\ 1 & 0 & 1 & 1 & |0 \\ 1 & 0 & 0 & 1 & |1 \\ 1 & 1 & 1 & 0 & |1 \end{matrix}) ∼ (\begin{matrix}1 & 0 & 0 & 1 & |1 \\ 1 & 0 & 1 & 1 & |0 \\ 0 & 0 & 1 & 1 & |1 \\ 1 & 1 & 1 & 0 & |1 \end{matrix}) ∼ (\begin{matrix}1 & 0 & 0 & 1 & |1 \\ 0 & 0 & 1 & 0 & |1 \\ 0 & 0 & 1 & 1 & |1 \\ 0 & 1 & 1 & 1 & |0 \end{matrix}) ∼

∼ (\begin{matrix}1 & 0 & 0 & 1 & |1 \\ 0 & 0 & 1 & 0 & |1 \\ 0 & 0 & 1 & 1 & |1 \\ 0 & 1 & 0 & 0 & |1 \end{matrix}) ∼ (\begin{matrix}1 & 0 & 0 & 1 & |1 \\ 0 & 0 & 1 & 0 & |1 \\ 0 & 0 & 0 & 1 & |0 \\ 0 & 1 & 0 & 0 & |1 \end{matrix}) ∼ (\begin{matrix}1 & 0 & 0 & 1 & |1 \\ 0 & 1 & 0 & 0 & |1 \\ 0 & 0 & 1 & 0 & |1 \\ 0 & 0 & 0 & 1 & |0 \end{matrix}) .

Nejprve jsme přehodili první a třetí řádek, a poté přičetli (nový) první řádek k druhému a čtvrtému. Dále jsme třetí řádek přičetli ke čtvrtému, pak druhý k třetímu a nakonec jsme zpřeházeli řádku a dostali jsme jediné řešení soustavy x_{1} = x_{2} = x_{3} = 1 a x_{4} = 0.

Poznamenejme, že jsme ke stejnému výsledku mohli dospět i jinou posloupností elementárních úprav, například standardním použitím Gaussovy eliminace. □

3.7. Najděte nad tělesem Z_{7} všechna řešení soustavy rovnic Ax = b s maticí

A = (\begin{matrix}3 & 1 & 5 & 2 \\ 3 & 2 & 4 & 6 \\ 2 & 5 & 6 & 0 \end{matrix}) a) pro b = (1, 1, 1)^{T}, b) pro b = (1, 2, 5)^{T}

Opět upravíme rozšířenou matici soustavy na odstupňovanou matici.

a)

(\begin{matrix}3 & 1 & 5 & 2 & |1 \\ 3 & 2 & 4 & 6 & |1 \\ 2 & 5 & 6 & 0 & |1 \end{matrix}) ∼ (\begin{matrix}3 & 1 & 5 & 2 & |1 \\ 0 & 1 & 6 & 4 & |0 \\ 0 & 2 & 5 & 1 & |5 \end{matrix}) ∼ (\begin{matrix}3 & 1 & 5 & 2 & |1 \\ 0 & 1 & 6 & 4 & |0 \\ 0 & 0 & 0 & 0 & |5 \end{matrix})

Protože poslední řádek představuje rovnici 0 = 5, která neplatí pro žádný vektor neznámých, je množina všech řešení soustavy prázdná.

b)

(\begin{matrix}3 & 1 & 5 & 2 & |1 \\ 3 & 2 & 4 & 6 & |2 \\ 2 & 5 & 6 & 0 & |5 \end{matrix}) ∼ (\begin{matrix}3 & 1 & 5 & 2 & |1 \\ 0 & 1 & 6 & 4 & |1 \\ 0 & 2 & 5 & 1 & |2 \end{matrix}) ∼ (\begin{matrix}3 & 1 & 5 & 2 & |1 \\ 0 & 1 & 6 & 4 & |1 \\ 0 & 0 & 0 & 0 & |0 \end{matrix})

Tentokrát řešení soustavy existuje a my snadno najdeme jedno partikulární, například (0, 1, 0, 0)^{T}. Dále spočítáme zpětnou substitucí řešení homogenní soustavy pro volbu (x_{3}, x_{4}) = (1, 0) a (x_{3}, x_{4}) = (0, 1) a opět využijeme Větu 2.14, podle níž je množina všech řešení nehomogenní soustavy Ax = b právě tvaru

\{(\begin{matrix}0 \\ 1 \\ 0 \\ 0 \end{matrix}) + r · (\begin{matrix}5 \\ 1 \\ 1 \\ 0 \end{matrix}) + s · (\begin{matrix}3 \\ 3 \\ 0 \\ 1 \end{matrix}) | r, s ∈ Z_{7}\}.

□

3.8. Najděte nad tělesem Z_{5} všechna řešení homogenní soustavy rovnic s maticí

A = (\begin{matrix}3 & 1 & 1 & 2 & 4 \\ 1 & 2 & 1 & 2 & 1 \\ 4 & 3 & 0 & 1 & 3 \end{matrix}).

Budeme standardně upravovat matici A posloupností elementárních úprav na odstupňovanou matici. Nulový vektor pravých stran, který se řádkovými úpravami nebude měnit, přitom nemusí do matice zaznamenávat:

(\begin{matrix}3 & 1 & 1 & 2 & 4 \\ 1 & 2 & 1 & 2 & 1 \\ 4 & 3 & 0 & 1 & 3 \end{matrix}) ∼ (\begin{matrix}3 & 1 & 1 & 2 & 4 \\ 0 & 0 & 4 & 3 & 3 \\ 0 & 0 & 1 & 3 & 4 \end{matrix}) ∼ (\begin{matrix}3 & 1 & 1 & 2 & 4 \\ 0 & 0 & 1 & 3 & 4 \\ 0 & 0 & 0 & 1 & 2 \end{matrix}) .

Vidíme, že bázické pozice jsou první, třetí a čtvrtá a volné proměnné jsou druhá a pátá. Využijeme Věty 2.14, v níž jsme si ve 2.kapitole přednášky uvědomili, že stačí zvolit hodnoty za volné proměnné x_{2} a x_{5} a poté ostatní proměnné jednoznačně dopočítat zpětnou substitucí. Tedy položíme nejprve (x_{2}, x_{5}) = (1, 0) a poté (x_{2}, x_{5}) = (0, 1) a postupně budeme dopočítávat řešení. Pro x_{2} = 1 a x_{5} = 0 snadno najdeme vektor (3, 1, 0, 0, 0)^{T} řešící soustavu a podobně pro volbu x_{2} = 0 a x_{5} = 1 dostáváme řešení (1, 0, 2, 3, 1)^{T}.

Spočítali jsme, že množina všech řešení homogenní soustavy rovnic s maticí A je tvaru

\{s · (\begin{matrix}3 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix}) + t · (\begin{matrix}1 \\ 0 \\ 2 \\ 3 \\ 1 \end{matrix}) | s, t ∈ Z_{5}\}.

□

30.10.

3.9. Existuje nějaký vektor pravých stran b ∈ Z_{5}^{3}, pro který neexistuje žádné řešení soustavy Ax = b, kde A je matice z úlohy 3.8?

Stačí si uvědomit, že pro každý vektor pravých stran bude mít odstupňovaná matice soustavy na levé straně v každém řádku nenulový koeficient, tedy podle Pozorování 2.3 z přednášky pro každý vektor pravých stran (a volbu hodnot volných proměnných) umíme dopočítat nějaké řešení. Tedy je soustava Ax = b řešitelná pro každý vektor b ∈ Z_{5}^{3}. □

3.10. Najděte nad tělesem Z_{5} všechna řešení soustavy rovnic Ax = (1, 2, 4)^{T}, kde A je matice z úlohy 3.8.

Protože už jsme v úloze 3.8 našli všechna řešení homogenní soustavy s maticí A, zbývá nám podle Věty 2.14 najít už jedno partikulární řešení u nehomogenní soustavy Ax = (1, 2, 4). Každé řešení potom budou právě tvaru u + w pro vhodné řešení w homogenní soustavy Postupujeme analogicky výpočtu v příkladu 3.8. Nejprve rozšířenou matici stejnými elementárními úpravami upravíme na odstupňovanou matici a poté dopočítáme řešení pro volbu x_{2} = 0 a x_{5} = 0:

(\begin{matrix}3 & 1 & 1 & 2 & 4 & |1 \\ 1 & 2 & 1 & 2 & 1 & |2 \\ 4 & 3 & 0 & 1 & 3 & |4 \end{matrix}) ∼ (\begin{matrix}3 & 1 & 1 & 2 & 4 & |1 \\ 0 & 0 & 4 & 3 & 3 & |0 \\ 0 & 0 & 1 & 3 & 4 & |1 \end{matrix}) ∼ (\begin{matrix}3 & 1 & 1 & 2 & 4 & |1 \\ 0 & 0 & 1 & 3 & 4 & |1 \\ 0 & 0 & 0 & 1 & 2 & |1 \end{matrix}) .

Soustavu tedy řeší například vektor (2, 0, 3, 1, 0). S využitím hodnot spočítaných v 3.8 dostáváme množinu všech řešení soustavy Ax = (1, 2, 4)^{T} ve tvaru

\{(\begin{matrix}2 \\ 0 \\ 3 \\ 1 \\ 0 \end{matrix}) + s · (\begin{matrix}3 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix}) + t · (\begin{matrix}1 \\ 0 \\ 2 \\ 3 \\ 1 \end{matrix}) | s, t ∈ Z_{5}\}

□

3.11. Najděte v závislosti na parametru a nad tělesem a) Q, b) Z_{5}, c) Z_{7} d) Z_{11} řešení soustavy rovnic:

\begin{aligned}x & + & y & + & 3z & = & a \\ 2x & − & ay & + & z & = & 1 \end{aligned}

□

Soustavu si nejprve napíšeme v maticovém tvaru a upravíme na odstupňovaný tvar:

(\begin{matrix}1 & 1 & 3| & a \\ 2 & −a & 1| & 1 \end{matrix}) ∼ (\begin{matrix}1 & 1 & 3 & | & a \\ 0 & −a − 2 & −5 & | & 1 − 2a \end{matrix}) ∼ (\begin{matrix}1 & 1 & 3| & a \\ 0 & a + 2 & 5| & 2a − 1 \end{matrix}) .

Protože levá strana poslední rovnice je vždy nenulová, má soustava pro všechna a řešení. musí jen rozlišit situaci, kdy a + 2 = 0, tedy a = −2 a situaci, kdy a ≠ −2.

Nechť nejprve a = −2 . Pak je y volná proměnná a řešíme soustavu s maticí:

(\begin{matrix}1 & 1 & 3 & | & −2 \\ 0 & 0 & 5 & | & −5 \end{matrix})

Položíme tedy y = 0 a dopočítáme z = −1 a x = −2 − 3 · (−1) = 1. Pro y = 1 a dopočítáme hodnoty homogenní soustavy z = 0 a x = −1, tedy množina všech řešení je tvaru {(1, 0, −1)^{T} + t(−1, 1, 0)^{T} | t ∈ T} pro těleso T, jestliže je charakteristika tělesa T různá od pěti. V případě b), kdy pracujeme s tělesem Z_{5} se nám modulo 5 druhý řádek soustavy vynuluje:

(\begin{matrix}1 & 1 & 3 & | & −2 \\ 0 & 0 & 5 & | & −5 \end{matrix}) = (\begin{matrix}1 & 1 & 3 & | & 3 \\ 0 & 0 & 0 & | & 0 \end{matrix})

Výše spočítané partikulární řešení po úpravě modulo 5 zůstává v platnosti (a bude tedy tvaru (1, 0, 4)^{T}), snadno lze ovšem také najít kanonické partikulární řešení pro nulové hodnoty obou volných proměnných (3, 0, 0)^{T}. Pri výpočtu řešení homogenní soustavy máme dvě volné proměnné x_{2} a x_{3}. Obvyklým postupem nyní najdeme nad Z_{5} dvě řešení (4, 1, 0)^{T} a (2, 0, 1)^{T} (jednočlené) homogenní soustavy, všechna řešení jsou tedy tvaru

(1, 0, 4)^{T} + t · (4, 1, 0)^{T} + s · (2, 0, 1)^{T} pro s, t ∈ Z_{5}.

Zjistili jsme , že všechna řešení tvoří pro a = −2 množina:

a)\{(\begin{matrix}1 \\ 0 \\ −1 \end{matrix}) + t (\begin{matrix}−1 \\ 1 \\ 0 \end{matrix}) | t ∈ R\}, b)\{(\begin{matrix}1 \\ 0 \\ 4 \end{matrix}) + t (\begin{matrix}4 \\ 1 \\ 0 \end{matrix}) + s (\begin{matrix}2 \\ 0 \\ 1 \end{matrix}) | s, t ∈ Z_{5}\},

c)\{(\begin{matrix}1 \\ 0 \\ 6 \end{matrix}) + t (\begin{matrix}6 \\ 1 \\ 0 \end{matrix}) | t ∈ Z_{7}\}, d)\{(\begin{matrix}1 \\ 0 \\ 10 \end{matrix}) + t (\begin{matrix}10 \\ 1 \\ 0 \end{matrix}) | t ∈ Z_{11}\}.

Nyní nechť a ≠ −2 . Potom je volná proměnná z. a řešíme soustavu s maticí:

(\begin{matrix}1 & 1 & 3| & a \\ 0 & a + 2 & 5| & 2a − 1 \end{matrix})

Položíme tedy z = 0 a dopočítáme y = \frac{2a−1}{a+2} a x = a − \frac{2a−1}{a+2} = \frac{a^{2} +1}{a+2} . Konečně pro z = 1 a dopočítáme hodnoty homogenní soustavy y = −\frac{5}{a+2} a x = −(3 − \frac{5}{a+2} ) = −\frac{3a+1}{a+2} a množina všech řešení je tvaru

\{(\frac{a^{2} +1}{a+2} ; \frac{2a−1}{a+2} ; 0 ) + t (\begin{matrix}−\frac{3a+1}{a+2} \\ −\frac{5}{a+2} \\ 1 \end{matrix} ) | t ∈ T \} = \{(\frac{a^{2} +1}{a+2} ; \frac{2a−1}{a+2} ; 0 ) + t (\begin{matrix}3a + 1 \\ 5 \\ −a − 2 \end{matrix}) | t ∈ T \}

pro těleso T, konkrétně:

a)\{(\frac{a^{2} +1}{a+2} ; \frac{2a−1}{a+2} ; 0 ) + t (\begin{matrix}3a + 1 \\ 5 \\ −a − 2 \end{matrix}) | t ∈ R\}, b)\{(\frac{a^{2} +1}{a+2} ; \frac{2a+4}{a+2} ; 0 ) + t (\begin{matrix}3a + 1 \\ 0 \\ 4a + 3 \end{matrix} ) | t ∈ Z_{5}\}

d)\{(\frac{a^{2} +1}{a+2} ; \frac{2a+6}{a+2} ; 0 ) + t (\begin{matrix}3a + 1 \\ 5 \\ 6a + 5 \end{matrix} ) | t ∈ Z_{7}\}, b) (\frac{a^{2} +1}{a+2} ; \frac{2a−1}{a+2} ; 0 ) + t (\begin{matrix}3a + 1 \\ 5 \\ 10a + 9 \end{matrix} ) | t ∈ Z_{11}\}

Závěrem poznamenejme, že symbol \frac{c}{d} je v tělese Z_{p} výraz, který je třeba dopočítat , tedy že \frac{c}{d} = c · d^{−1} (stejnětak by tomu bylo v případě například tělese racionálních čísel, kdyby c a d byly nikoli celé, nýbrže obecné racionální hodnoty). □

4. Počítání s maticemi

4.1. Uvažujme matice A = (\begin{matrix}1 & 2 \\ 3 & 5 \end{matrix}), B = (\begin{matrix}1 & 0 & −1 \\ 1 & 2 & 1 \end{matrix}) a C = (\begin{matrix}1 & 2 & 0 \\ 3 & 5 & 1 \end{matrix}) nad

tělesem R, Z_{7} a Z_{11}.

(a) Spočítejte součty B + C, C + B, B^{T} + C^{T}.

(b) Spočítejte součiny A · B, B^{T} · A^{T}, B^{T} · A, B^{T} · C a C^{T} · B.

(c) Spočítejte A · (A − B · C^{T}) + (C · B^{T} · A^{T}).

Ve všech případech úlohu vyřešíme nejprve v tělese charakteristiky 0, tedy v reálných číslech a poté, obdobně jako tomu bylo v Příkladu 3.11 výsledek pouze upravíme modulu příslušné prvočíslo.

(a) Postupujeme nejprve přímo podle definice součtu matic:

B + C = (\begin{matrix}1 & 0 & −1 \\ 1 & 2 & 1 \end{matrix}) + (\begin{matrix}1 & 2 & 0 \\ 3 & 5 & 1 \end{matrix}) = (\begin{matrix}1 + 1 & 0 + 2 & −1 + 0 \\ 1 + 3 & 2 + 5 & 1 + 1 \end{matrix} ) = (\begin{matrix}2 & 2 & −1 \\ 4 & 7 & 2 \end{matrix}) .

Na přednášce bylo ukázáno, že je sčítání matic komutativní, nemusíme samozřejmě

druhý součet počítat a přímo vidíme, že C + B = B + C = (\begin{matrix}2 & 2 & −1 \\ 4 & 7 & 2 \end{matrix}) nad R a

C+B = B+C = (\begin{matrix}2 & 2 & 6 \\ 4 & 0 & 2 \end{matrix}) nad Z_{7} a C+B = B+C = (\begin{matrix}2 & 2 & 10 \\ 4 & 7 & 2 \end{matrix}) nad Z_{11}.

Podobně bylo na přednášce ověřeno, že B^{T} +C^{T} = (B+C)^{T}, tedy nám stačí jen bez

dalšího počítání transponovat matici B+C, abychom dostali B^{T} +C^{T} = (\begin{matrix}2 & 4 \\ 2 & 7 \\ −1 & 2 \end{matrix})

nad tělesem reálných čísel,

B^{T} + C^{T} = (\begin{matrix}2 & 4 \\ 2 & 0 \\ 6 & 2 \end{matrix}) nad Z_{7}, a B^{T} + C^{T} = (\begin{matrix}2 & 4 \\ 2 & 7 \\ 10 & 2 \end{matrix}) nad Z_{11}.

(b) Opět nejprve postupujme bezprostředně podle definice, tentokrát se jedná o definici násobení matic: A · B =

(\begin{matrix}1 & 2 \\ 3 & 5 \end{matrix})·(\begin{matrix}1 & 0 & −1 \\ 1 & 2 & 1 \end{matrix}) = (\begin{matrix}1 · 1 + 2 · 1 & 1 · 0 + 2 · 2 & −1 · 1 + 2 · 1 \\ 3 · 1 + 5 · 1 & 3 · 0 + 5 · 2 & −3 · 1 + 5 · 1 \end{matrix} ) = (\begin{matrix}3 & 4 & 1 \\ 8 & 10 & 2 \end{matrix}) .

Protože bylo na přednášce ověřeno, že (A · B)^{T} = B^{T} · A^{T}, vidíme, že

B^{T} · A^{T} = (\begin{matrix}3 & 4 & 1 \\ 8 & 10 & 2 \end{matrix})^{T} = (\begin{matrix}3 & 8 \\ 4 & 10 \\ 1 & 2 \end{matrix}) .

To nám ovšem nepomůže pro výpočet B^{T} ·A, který opět provedeme podle definice:

B^{T} · A = (\begin{matrix}1 & 1 \\ 0 & 2 \\ −1 & 1 \end{matrix}) · (\begin{matrix}1 & 2 \\ 3 & 5 \end{matrix}) = (\begin{matrix}4 & 7 \\ 6 & 10 \\ 2 & 3 \end{matrix}) .

Při výpočtu součinu B^{T} · C nám pomůže rozklad matice C na dva bloky C = (A|S), kde A je matice s kterou pracujeme a S = (\begin{matrix}0 \\ 1 \end{matrix}). Výpočet nám usnadní jednak to, že jsme již spočítali součin B^{T} · A a dále pozorování, že součin B^{T} · S právě vybere z matice B^{T} druhý sloupec:

B^{T} · C = (B^{T} · A|B^{T} · S) = (\begin{matrix}1 & 1 \\ 0 & 2 \\ −1 & 1 \end{matrix}) · (\begin{matrix}1 & 2 & | & 0 \\ 3 & 5 & | & 1 \end{matrix}) = (\begin{matrix}4 & 7 & 1 \\ 6 & 10 & 2 \\ 2 & 3 & 1 \end{matrix}) .

Konečně C^{T} · B = C^{T} · (B^{T})^{T} = (B^{T} · C)^{T} = (\begin{matrix}4 & 6 & 2 \\ 7 & 10 & 3 \\ 1 & 2 & 1 \end{matrix}). Našli jsme výsledky v tělese reálných čísel a nyní je upravýme nad oběma konečnými tělesy:

A · B = (\begin{matrix}3 & 4 & 1 \\ 1 & 3 & 2 \end{matrix}) , B^{T} · A = (\begin{matrix}4 & 0 \\ 6 & 3 \\ 2 & 3 \end{matrix}) , B^{T} · C = (\begin{matrix}4 & 0 & 1 \\ 6 & 3 & 2 \\ 2 & 3 & 1 \end{matrix})

a C^{T} · B = (\begin{matrix}4 & 6 & 2 \\ 0 & 3 & 3 \\ 1 & 2 & 1 \end{matrix}) vše nad tělesem Z_{7} a

A · B = (\begin{matrix}3 & 4 & 1 \\ 8 & 10 & 2 \end{matrix}) , B^{T} · A = (\begin{matrix}4 & 7 \\ 6 & 10 \\ 2 & 3 \end{matrix}) , B^{T} · C = (\begin{matrix}4 & 7 & 1 \\ 6 & 10 & 2 \\ 2 & 3 & 1 \end{matrix})

a C^{T} · B = (\begin{matrix}4 & 6 & 2 \\ 7 & 10 & 3 \\ 1 & 2 & 1 \end{matrix}) vše nad tělesem Z_{11}.

(c) Využijeme početních pravidel a nejprve upravíme: A·(A−B·C^{T})+(C·B^{T} ·A^{T})−A = A·A−A·B·C^{T} +(A^{T})^{T} ·(B^{T})^{T} ·C^{T} −A =

= A · (A − I_{2}) − A · B · C^{T} + A · B · C^{T} = A · (A − I_{2}).

Nyní snadno dopočítáme

A · (A − I_{2}) = (\begin{matrix}1 & 2 \\ 3 & 5 \end{matrix}) · (\begin{matrix}0 & 2 \\ 3 & 4 \end{matrix}) = (\begin{matrix}6 & 10 \\ 15 & 26 \end{matrix}) nad R

A · (A − I_{2}) = (\begin{matrix}6 & 3 \\ 1 & 5 \end{matrix}) nad Z_{7}, a A · (A − I_{2}) = (\begin{matrix}6 & 10 \\ 4 & 4 \end{matrix}) nad Z_{11}.

□

4.2. Uvažujme matice A = (\begin{matrix}1 & 2 \\ 3 & 1 \end{matrix}) a B = (\begin{matrix}1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix}) nad tělesem Z_{5} a definujme

zobrazení φ : Z_{5}^{2} → Z_{5}^{2} a ψ : Z_{5}^{3} → Z_{5}^{2} předpisy φ(v) = Av a ψ(v) = Bv (a) Rozhodněte, zda je φ či ψ prosté zobrazení.

(b) Rozhodněte, zda je φ či ψ zobrazení na.

(c) Najděte všechny vektory v ∈ Z_{5}^{3}, pro něž je ψ(v) = (0, 0)^{T}

(d) Najděte všechny vektory v ∈ Z_{5}^{3}, pro něž je ψ(v) = (1, 2)^{T}

(a) Připomeňme, že je zobrazení φ prosté, jestliže φ(u) = φ(v) ⟹ u = v. Protože φ(u) = φ(v), právě když φ(u − v) = φ(u) − φ(v) = 0, lze ekvivalentně prostotu zobrazení φ vyjádřit podmínkou φ(u) = 0 ⟹ u = 0. Tedy nám stačí zjistit, zda mají soustavy rovnic Ax = (0, 0)^{T} a Bx = (0, 0)^{T} nějaké nenulové řešení. V obou případech po jediné ekvivalentní úpravě vidíme, že nenulové řešení existují, v prvním případě například φ((3, 1)^{T}) = (0, 0)^{T} = φ((0, 0)^{T}) a v druhém příkladě například ψ((4, 1, 1)^{T}) = (0, 0)^{T} = ψ((0, 0, 0)^{T}), proto zobrazení φ ani ψ není podle definice prosté.

(b) Opět se úloha redukuje na otázku řešení soustavy rovnic s danou maticí. Tentokrát se ptáme, zda pro každou pravou stranu existuje řešení. V prvním případě vidíme, že nikoli, například pro pravou stranu (1, 0)^{T} vidíme, že řešení soustavy Ax = (1, 0)^{T} neexistuje. V druhém případě nám stejná úvaha jakou jsme provedli v úloze 3.9 říká, že řešení vždy existuje. Proto φ není na, zatímco ψ je zobrazení na Z_{5}^{2}.

(c) Stačí, abychom obvyklým způsobem vyřešili homogenní soustavu rovnic s maticí

B ∼ (\begin{matrix}1 & 0 & 1 \\ 0 & 1 & 4 \end{matrix}) .

Obvyklým způsobem zjistíme, že vektor v splňuje ψ(v) = (0, 0)^{T}, právě když leží

v množině \{t · (\begin{matrix}4 \\ 1 \\ 1 \end{matrix}) | t ∈ Z_{5}\}.

(d) Tentokrát standardně řešíme soustavu rovnic tvaru Bx = (1, 2)^{T} s maticovým zápisem

(\begin{matrix}1 & 0 & 1 & | & 1 \\ 1 & 1 & 0 & | & 2 \end{matrix}) ∼ (\begin{matrix}1 & 0 & 1 & | & 1 \\ 0 & 1 & 4 & | & 1 \end{matrix}) .

Spočítáme jedno partikulární řešení (1, 1, 0)^{T} a využijeme výsledku (c), vidíme, že

v splňuje ψ(v) = (0, 0)^{T}, právě když leží v množině \{(\begin{matrix}1 \\ 1 \\ 0 \end{matrix}) + t · (\begin{matrix}4 \\ 1 \\ 1 \end{matrix}) | t ∈ Z_{5}\}. □

6.11.

4.3. Definujme zobrazení f_{A} : R^{2} → Z_{5}^{2} předpisem f_{A} (v) = Av pro reálnou matici

A = (\begin{matrix}2 & 3 \\ 3 & 4 \end{matrix}).

(a) Dokažte, že je f_{A} bijekce.

(b) Najděte matici B, pro niž platí f_{B} ∘ f_{A} = f_{A} ∘ f_{B} = Id, tedy f_{B} = f_{A}^{−1}.

(a) Připomeňme, že podle Věty 4.30, z přednášky máme dokázat, že je matice A regulární. Bod (5) zmíněné věty dokonce dává jednoduchý návod, jak zjistit, zda je čtvercová matice regulární, stačí upravit Gaussovou eliminací a zjistit, zda je či nenív odstupňovaném tvaru dané matice nulový řádek:

(\begin{matrix}2 & 3 \\ 3 & 4 \end{matrix}) ∼ (\begin{matrix}2 & 3 \\ 0 & \frac{−1}{2} \end{matrix}) .

Protože je odstupňovaný tvar matice A bez nulových řádků, jedná se podle Věty 4.30 o regulární matici, která indukuje bijektivní zobrazení f_{A} .

(b) Nejprve si uvědomme, že f_{A} ∘ f_{B}(v) = f_{A} (B · v) = A · B · v a podobně že f_{B} ∘ f_{A} (v) = B · A · v. Chceme-li, aby f_{B} = f_{A}^{−1}, musí B = A^{−1}, tedy potřebujeme najít inverzní matici k matici A. K tomu využijeme postup 4.7.2-3. z přednášky: jeli A čtvercová matice řádu n, budeme elementárními úpravami upravovat matici M rozšířenou o jednotkovou matici, tedy matici (M|I_{n}) tak, abychom dostali matici (I_{n}|N). Podaří-li se nám to, bude matice N právě inverzní maticí k matici M, protože (I_{n}|N) = (N·M|N·I_{n}) = N·(M|I_{n}), v opačném případě dokonce zjsitíme, že M nebyla regulární (to jsme ovšem už zjišťovali v bodu (a)). Upravujeme tedy řádky rozšířené matice:

(\begin{matrix}2 & 3 & |1 & 0 \\ 3 & 4 & |0 & 1 \end{matrix}) ∼ (\begin{matrix}−1 & −1 & |1 & −1 \\ 3 & 4 & |0 & 1 \end{matrix}) ∼ (\begin{matrix}−1 & −1 & |1 & −1 \\ 0 & 1 & |3 & −2 \end{matrix}) ∼

∼ (\begin{matrix}1 & 1 & | & −1 & 1 \\ 0 & 1 & | & 3 & −2 \end{matrix}) ∼ (\begin{matrix}1 & 0 & | & −4 & 3 \\ 0 & 1 & | & 3 & −2 \end{matrix}) .

Postupně jsme odčítali druhý řádek od prvního, přičítali trojnásobek prvního řádku ke druhému, vynásobili první řádek hodnotou −1 a odečetli druhý řádek od prvního,

abychom zjsitili, že B = A^{−1} = (\begin{matrix}−4 & 3 \\ 3 & −2 \end{matrix}). □

4.4. Existuje-li, najděte inverzní matici k maticím

(a) B = (\begin{matrix}1 & 2 & 1 \\ −2 & −3 & 1 \\ 2 & 4 & 3 \end{matrix}) nad tělesem racionálních čísel,

(b) C = (3 + 4i ) nad tělesem komplexních čísel,

(c) D = (\begin{matrix}1 + i & 1 \\ 2 & 3 − i \end{matrix}) nad tělesem komplexních čísel.

(d) F = (\begin{matrix}2 & 2 \\ 3 & 1 \end{matrix}) nad tělesem Z_{5},

(e) F nad tělesem Z_{7},

(f) G = (\begin{matrix}1 & 2 & 4 \\ 3 & 2 & 6 \\ 1 & 0 & 5 \end{matrix}) nad tělesem Z_{7},

(g) G^{T} nad tělesem Z_{7}

(h) H = (\begin{matrix}0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{matrix}) nad tělesem Z_{2}.

(a) Počítáme obdobně jako v předchozí úloze:

(\begin{matrix}1 & 2 & 1 & |1 & 0 & 0 \\ −2 & −3 & 1 & |0 & 1 & 0 \\ 2 & 4 & 3 & |0 & 0 & 1 \end{matrix}) ∼ (\begin{matrix}1 & 2 & 1 & | & 1 & 0 & 0 \\ 0 & 1 & 3 & | & 2 & 1 & 0 \\ 0 & 0 & 1 & | & −2 & 0 & 1 \end{matrix}) ∼

∼ (\begin{matrix}1 & 2 & 0 & | & 3 & 0 & −1 \\ 0 & 1 & 0 & | & 8 & 1 & −3 \\ 0 & 0 & 1 & | & −2 & 0 & 1 \end{matrix}) ∼ (\begin{matrix}1 & 0 & 0 & | & −13 & −2 & 5 \\ 0 & 1 & 0 & | & 8 & 1 & −3 \\ 0 & 0 & 1 & | & −2 & 0 & 1 \end{matrix}) .

Vidíme, že B^{−1} = (\begin{matrix}−13 & −2 & 5 \\ 8 & 1 & −3 \\ −2 & 0 & 1 \end{matrix}).

(b) Snadno si z definice maticového násobení uvědomíme, že máme za úkol spočítat v tělese komplexních čísel hodnotu (3 + 4i)^{−1} = \frac{1}{3+4i} . Obvyklým způsobem tedy rozšíříme zlomky komplexně sdruženou hodnotou a dostaneme

\frac{1}{3 + 4i} = \frac{1}{3 + 4i} · \frac{3 − 4i}{3 − 4i} = \frac{3 − 4i}{3^{2} + 4^{2}} = \frac{3}{25} − \frac{4}{25}i

Spočítali jsme, že C^{−1} = ((3 + 4i)^{−1} ) = (\frac{3}{25} − \frac{4}{25} i).

(c) Postupujeme jako v bodech (a) a (b) s využitím aritmetiky komplexních čísel:

(\begin{matrix}1 + i & 1 & |1 & 0 \\ 2 & 3 − i & |0 & 1 \end{matrix}) ∼ (\begin{matrix}1 + i & 1 & | & 1 & 0 \\ 0 & 2 & | & −1 + i & 1 \end{matrix}) ∼

∼ (\begin{matrix}1 & \frac{1−i}{2} & | & \frac{1−i}{2} & 0 \\ 0 & 1 & | & \frac{i−1}{2} & \frac{1}{2} \end{matrix}) ∼ (\begin{matrix}1 & 0 & | & \frac{1−2i}{2} & \frac{i−1}{4} \\ 0 & 1 & | & \frac{i−1}{2} & \frac{1}{2} \end{matrix})

Tentokrát jsme postupně upravovali: 1) (1 − i)-násobek prvního řádku jsme odečetli od druhého, 2) prvního řádek jsme vynásobili hodnotou \frac{1}{1+i} a druhý řádek hodnotou \frac{1}{2} 3) \frac{1−i}{2}-násobek druhého řádku jsme odečetli od prvního. Spočítali

jsme, že D^{−1} = (\begin{matrix}\frac{1−2i}{2} & \frac{i−1}{4} \\ \frac{i−1}{2} & \frac{1}{2} \end{matrix}) = \frac{1}{4} (\begin{matrix}2 − 4i & i − 1 \\ 2i − 2 & 2 \end{matrix}).

(d) Upravujeme řádky rozšířené matice nad tělesem Z_{5}:

(\begin{matrix}2 & 2 & |1 & 0 \\ 3 & 1 & |0 & 1 \end{matrix}) ∼ (\begin{matrix}2 & 2 & |1 & 0 \\ 0 & 3 & |1 & 1 \end{matrix}) ∼ (\begin{matrix}1 & 1 & |3 & 0 \\ 0 & 1 & |2 & 2 \end{matrix}) ∼ (\begin{matrix}1 & 0 & |1 & 3 \\ 0 & 1 & |2 & 2 \end{matrix})

Postupně jsme 1) přičetli 1. řádek ke 2. (protože −3 = 2 v Z_{5}), 2) vynásobili 1. řádek číslem 3 a 2. řádek číslem 2 (protože 2^{−1} = 3 a 3^{−1} = 2 v Z_{5}), 3) odečetli 2. řádek od 1. nebo ekvivalentně řečeno přičetli 4-násobek 2. řádku k 1. (protože −4 = 1 v Z_{5}).

Nyní vidíme, že inverzní matice k matici F existuje a že F^{−1} = (\begin{matrix}1 & 3 \\ 2 & 2 \end{matrix}) nad

tělesem Z_{5}.

(e) Upravujeme řádky stejné rozšířené matice tentokrát ovšem nad tělesem Z_{7}:

(\begin{matrix}2 & 2 & |1 & 0 \\ 3 & 1 & |0 & 1 \end{matrix}) ∼ (\begin{matrix}2 & 2 & |1 & 0 \\ 0 & 5 & |2 & 1 \end{matrix}) ∼ (\begin{matrix}2 & 0 & |3 & 1 \\ 0 & 5 & |2 & 1 \end{matrix}) ∼ (\begin{matrix}1 & 0 & |5 & 4 \\ 0 & 1 & |6 & 3 \end{matrix})

Nyní jsme 1) přičetli 2-násobek 1. řádku ke 2. (protože 2 · 2 = −3 v Z_{7}), 2) přičetli 2. řádek k 1. (protože 5 = −2 v Z_{7}) 3) vynásobili 1. řádek číslem 4 a 2. řádek číslem 3 (protože 2^{−1} = 4 a 5^{−1} = 3 v Z_{7}).

Spočítali jsme inverzní matici F^{−1} = (\begin{matrix}5 & 4 \\ 6 & 3 \end{matrix}) nad tělesem Z_{7}.

(f) Počítáme opět nad Z_{7}:

(\begin{matrix}1 & 2 & 4 & |1 & 0 & 0 \\ 3 & 2 & 6 & |0 & 1 & 0 \\ 1 & 0 & 5 & |0 & 0 & 1 \end{matrix}) ∼ (\begin{matrix}1 & 0 & 5 & |0 & 0 & 1 \\ 0 & 2 & 5 & |0 & 1 & 4 \\ 0 & 2 & 6 & |1 & 0 & 6 \end{matrix}) ∼ (\begin{matrix}1 & 0 & 0 & |2 & 5 & 5 \\ 0 & 1 & 0 & |1 & 3 & 4 \\ 0 & 0 & 1 & |1 & 6 & 2 \end{matrix}) .

Dostali jsme G^{−1} = (\begin{matrix}2 & 5 & 5 \\ 1 & 3 & 4 \\ 1 & 6 & 2 \end{matrix}).

(g) Tentokrát nemusíme nic počítat a jenom využijeme předchozí výsledek a Tvrzení 4.38(2) z přednášky, které říká

(G^{T})^{−1} = (G^{−1})^{T} = (\begin{matrix}2 & 5 & 5 \\ 1 & 3 & 4 \\ 1 & 6 & 2 \end{matrix})^{T} = (\begin{matrix}2 & 1 & 1 \\ 5 & 3 & 6 \\ 5 & 4 & 2 \end{matrix}) .

(h) Postupujeme standardně, přičemž nejprve přičteme všechny níže položené řádky k prvnímu a poté první řádek přičteme k níže položeným řádkům:

(\begin{matrix}0 & 1 & 1 & 1 & |1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & |0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & |0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & |0 & 0 & 0 & 1 \end{matrix}) ∼ (\begin{matrix}1 & 1 & 1 & 1 & |1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & |0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & |0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & |0 & 0 & 0 & 1 \end{matrix}) ∼

∼ (\begin{matrix}1 & 1 & 1 & 1 & |1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & |1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & |1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & |1 & 1 & 1 & 0 \end{matrix}) ∼ (\begin{matrix}1 & 0 & 0 & 0 & |0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & |1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & |1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & |1 & 1 & 1 & 0 \end{matrix}) .

Spočítali jsme, že H^{−1} = H = (\begin{matrix}0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{matrix}). □

4.5. Spočítejte součiny reálných matic

(a) (\begin{matrix}2 & 3 \\ 1 & 1 \end{matrix})^{−1} · (\begin{matrix}1 & 3 & 1 & −1 \\ 2 & 0 & −1 & 2 \end{matrix}), (b) (\begin{matrix}2 & 0 \\ −1 & 3 \\ 1 & 2 \end{matrix}) · (\begin{matrix}3 & 4 \\ 2 & 3 \end{matrix})^{−1}.

(a) Označme A = (\begin{matrix}2 & 3 \\ 1 & 1 \end{matrix}) a B = (\begin{matrix}1 & 3 & 1 & −1 \\ 2 & 0 & −1 & 2 \end{matrix}). Rozšíříme-li matici A o

matici B a budeme-li vzniklou matici (A|B) upravovat stejně jako v předchozích úlohách takovými elementárními úpravami, abychom vlevo obdrželi jednotkovou matici, snadno nahlédneme, že

(A|B) ∼ A^{−1} · (A|B) = (I_{2}|A^{−1}B),

Tedy vpravo dostaneme hledaný součin A^{−1}B. Počítejme:

(\begin{matrix}2 & 3 & |1 & 3 & 1 & −1 \\ 1 & 1 & |2 & 0 & −1 & 2 \end{matrix}) ∼ (\begin{matrix}1 & 1 & |2 & 0 & −1 & 2 \\ 2 & 3 & |1 & 3 & 1 & −1 \end{matrix}) ∼

∼ (\begin{matrix}1 & 1 & | & 2 & 0 & −1 & 2 \\ 0 & 1 & | & −3 & 3 & 3 & −5 \end{matrix}) ∼ (\begin{matrix}1 & 0 & | & 5 & −3 & −4 & 7 \\ 0 & 1 & | & −3 & 3 & 3 & −5 \end{matrix}) .

Spočítali jsme, že (\begin{matrix}2 & 3 \\ 1 & 1 \end{matrix})^{−1} · (\begin{matrix}1 & 3 & 1 & −1 \\ 2 & 0 & −1 & 2 \end{matrix}) = (\begin{matrix}5 & −3 & −4 & 7 \\ −3 & 3 & 3 & −5 \end{matrix}). □

(b) Označme C = (\begin{matrix}2 & 0 \\ −1 & 3 \\ 1 & 2 \end{matrix}) a D = (\begin{matrix}3 & 4 \\ 2 & 3 \end{matrix}). Využijeme-li Tvrzení 4.22(4) a

4.38(2), dostaneme (C · D^{−1})^{T} = (D^{−1})^{T} · C^{T} = (D^{T})^{−1} · C^{T}, a proto můžeme postupovat stejným způsobem jako v bodu (a), ovšem pro součin transponovaných matic v obráceném pořadí:

(\begin{matrix}3 & 2 & |2 & −1 & 1 \\ 4 & 3 & |0 & 3 & 2 \end{matrix}) ∼ (\begin{matrix}12 & 8 & |8 & −4 & 4 \\ 12 & 9 & |0 & 9 & 6 \end{matrix}) ∼ (\begin{matrix}3 & 2 & | & 2 & −1 & 1 \\ 0 & 1 & | & −8 & 13 & 2 \end{matrix}) ∼

∼ (\begin{matrix}3 & 0 & | & 18 & −27 & −3 \\ 0 & 1 & | & −8 & 13 & 2 \end{matrix}) ∼ (\begin{matrix}1 & 0 & | & 6 & −9 & −1 \\ 0 & 1 & | & −8 & 13 & 2 \end{matrix}) .

Zjistili jsme, že (D^{T})^{−1}·C^{T} = (\begin{matrix}6 & −9 & −1 \\ −8 & 13 & 2 \end{matrix}), a proto C·D^{−1} = (\begin{matrix}6 & −8 \\ −9 & 13 \\ −1 & 2 \end{matrix}). □

Připomeňme přirozenou definici k-té mocniny čtvercové matice A^{k} = \overbrace{AA … A}^{k-krát}.

4.6. Najděte čtvercovou matici A nad tělesem T řádu n splňující podmínky A^{2} = I_{n} a A ≠ I_{n}, jestliže

(a) n = 1 a T = R,

(b) n = 2 a T = R,

(c) n = 2 a T = Z_{5},

(d) n = 3 a T = R,

(e) n = 4 a T = Z_{2}.

(a) Čtvercové matice řádu 1 odpovídají prvkům těles, tedy se ptáme, kdy a^{2} = 1 a a ≠ 1 nad reálnými čísly. Okamžitě vidíme, že podmínku splňuje pouze matice (−1).

(b) V úloze nám může pomoct geometrický náhled. Uvážíme-li matici zobrazení f_{A} , hledáme taková zobrazení, která jsou sama k sobě inverzní. Ta ovšem snadno najdeme mezi symetriemi, například osová souměrnost podle osy x či y nebo souměrnost podle průsečíku os jsou zobrazení sama k sobě inverzní. Nyní stačí nahléd-

nout, že A_{x} = (\begin{matrix}1 & 0 \\ 0 & −1 \end{matrix}) je maticí souměrnosti podle osy x, A_{y} = (\begin{matrix}−1 & 0 \\ 0 & 1 \end{matrix}) je

maticí souměrnosti podle osy y a A_{o} = (\begin{matrix}−1 & 0 \\ 0 & −1 \end{matrix}) je maticí souměrnosti podle

počátku souřadnic, a že A_{x}^{2} = A_{y}^{2} = A_{o}^{2} = I_{2}.

(c) V tomto případě nám sice geometrická představa chybí, ale algebraické důvody ukazují, že předchozí příklady matic

(\begin{matrix}1 & 0 \\ 0 & −1 \end{matrix}) = (\begin{matrix}1 & 0 \\ 0 & 4 \end{matrix}) , (\begin{matrix}−1 & 0 \\ 0 & 1 \end{matrix}) = (\begin{matrix}4 & 0 \\ 0 & 1 \end{matrix}) , (\begin{matrix}−1 & 0 \\ 0 & −1 \end{matrix}) = (\begin{matrix}4 & 0 \\ 0 & 4 \end{matrix}) .

i nad tělesem Z_{5} splňují podmínku A^{2} = I_{2}. Poznamenejme ovšem, že existují i

další matice splňují A^{2} = I_{2} například matice (\begin{matrix}2 & 2 \\ 1 & 3 \end{matrix}).

(d) Tentokrát můžeme použít geometrickou úvahu z (b), abychom si uvědomili, že osové souměrnosti s maticemi

(\begin{matrix}1 & 0 & 0 \\ 0 & −1 & 0 \\ 0 & 0 & −1 \end{matrix}) , (\begin{matrix}−1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & −1 \end{matrix}) , (\begin{matrix}−1 & 0 & 0 \\ 0 & −1 & 0 \\ 0 & 0 & 1 \end{matrix}) ,

symetrie podle rovin určených dvojicí os s maticemi

(\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & −1 \end{matrix}) , (\begin{matrix}1 & 0 & 0 \\ 0 & −1 & 0 \\ 0 & 0 & 1 \end{matrix}) , (\begin{matrix}−1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) ,

stejně jako středová symetrie s maticí (\begin{matrix}−1 & 0 & 0 \\ 0 & −1 & 0 \\ 0 & 0 & −1 \end{matrix}) naši podmínku splňují.

(e) Nad tělesem Z_{2} platí, že −1 = 1, tedy úvahu z (b) využít nemůžeme. Přesto

například matice H = (\begin{matrix}0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{matrix}) z úlohy 4.4(h) podmínku H^{2} = I_{4} splňuje.

□

4.7. Najděte aspoň 4 reálné čtvercové matice A řádu 3, aby A^{2} = A a A ≠ I_{3}.

Podobně jako v předchozí úloze může využít geometrického náhledu. Uvážíme-li matici zobrazení f_{A} , hledáme geometrická zobrazení, která se dvojí aplikací nezmění. Takovou podmínku splňují jistě kolmé projekce na rovinu či přímku, matice projekcí na rovinu určenou dvojicí os jsou potom tvaru

(\begin{matrix}0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) , (\begin{matrix}1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}) , (\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{matrix}) ,

zatímco matice projekcí na osy jsou

(\begin{matrix}1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}) , (\begin{matrix}0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{matrix}) , (\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}) .

□

4.8. Mějme reálnou matici M = (\begin{matrix}2 & 0 \\ 1 & 3 \end{matrix}) řádu n > 1. Najděte příklady (nekonečně

mnoha) matic, které s M komutují.

Uvědomíme-li si, že je skalární násobení komutativní, dostaneme třídu matic

cI_{2} = (\begin{matrix}c & 0 \\ 0 & c \end{matrix} ) pro , které zřejmě komutují se všemi maticemi. D8le připomeňme,

že M · dM^{−1} = cI_{2} = dM^{−1} · M. Tedy matice dM^{−1} pro každé d ∈ R komutuje s

M, vezmem-li c = 6d snadno spočítáme, že s M komutují matice (\begin{matrix}3c & 0 \\ −c & 2c \end{matrix} ) pro

každé c ∈ R.

Dále pro každé přirozené n máme M · M^{n} = M^{n+1} = M^{n} · M a M · (M^{−1})^{n} = (M^{−1})^{n−1} = (M^{−1})^{n} · M, tedy matice M^{n} i (M^{−1})^{n} s M komutují. □

13.11.

4.9. Najděte nad tělesem Z_{7} všechny matice X splňující rovnost A·X = B, jestliže

(a) A = (\begin{matrix}5 & 5 \\ 2 & 3 \end{matrix}) , B = (\begin{matrix}1 & 2 & 5 \\ 3 & 1 & 1 \end{matrix}) , (b) A = (\begin{matrix}4 & 5 \\ 1 & 3 \end{matrix}) , B = (\begin{matrix}0 & 1 \\ 0 & 2 \end{matrix}) ,

(a) Nejprve si všimneme si, že je matice A zjevně invertovatelná, proto v případě, že nějaké řešení maticové rovnice A · X = B existuje, potom můžeme obě strany této rovnosti vynásobit zleva maticí A^{−1} a dostaneme A^{−1} · (A · X) = A^{−1} · B a tuto rovnost můžeme dále upravovat:

A^{−1} · B = A^{−1} · (A · X) = (A^{−1} · A) · X = I_{2} · X = X,

kde druhá rovnost platí díky asociativitě násobení matic, třetí rovnost plyne z definice inverzní matice a poslední rovnost dostáváme z vlastnosti jednotkové matice (tedy, že je I_{2} neutrální prvek vzhledem k násobení). Náhledli jsme, že existuje-li X, nutně musí být tvaru X = A^{−1} · B a zbývá ověřit, že matice A^{−1} · B splňuje danou podmínku. Tedy podobně jako výše upravujeme

A · (A^{−1} · B) = (A · A^{−1}) · B = I_{2} · B = B,

kde první rovnost dostáváme z asociativity násobení matic, druhou z definice inverzní matice a poslední rovnost je opět dokázanou vlastností jednotkové matice.

Nyní zbývá některým ze známých způsobů dopočítat jediné řešení, použijeme

například metodu úlohy 4.5: (\begin{matrix}5 & 5 & |1 & 2 & 5 \\ 2 & 3 & |3 & 1 & 1 \end{matrix}) ∼

∼ (\begin{matrix}5 & 5 & |1 & 2 & 5 \\ 0 & 1 & |4 & 3 & 6 \end{matrix}) ∼ (\begin{matrix}5 & 0 & |2 & 1 & 3 \\ 0 & 1 & |4 & 3 & 6 \end{matrix}) ∼ (\begin{matrix}1 & 0 & |6 & 3 & 2 \\ 0 & 1 & |4 & 3 & 6 \end{matrix}) .

Zjistili jsme, že X = A^{−1} · B = (\begin{matrix}6 & 3 & 2 \\ 4 & 3 & 6 \end{matrix}).

(b) Uvědomme si, že máme fakticky vzřešit dvě soustavy rovnic Ax_{1} = (0, 0)^{T} a Ax_{2} = (1, 2)^{T} se stejnými levými stranami. Hledaná matice X potom bude tvaru X = (x_{1}, x_{2}). Podobně jako v algoritmu pro výpočet inverzní matice můžeme soustavy zapsat do jedné matice s oběma vektory pravých stran vpravo a levé strany upravíme:

(\begin{matrix}4 & 5 & |0 & 1 \\ 1 & 3 & |0 & 2 \end{matrix}) ∼ (\begin{matrix}1 & 3 & |0 & 2 \\ 0 & 0 & |0 & 0 \end{matrix}) .

Nyní snadno obvyklým způsobem dopočítáme, že první soustavu řeší právě vektory c · (4, 1)^{T} pro všechna c ∈ Z_{7} druhou soustavu řeší právě vektory (2, 0)^{T} + d · (4, 1)^{T} pro všechna d ∈ Z_{7}. Tudíž X řešení maticové rovnice A · X = B, právě když X leží

v množině \{(x_{1}, x_{2})|∃c, d ∈ Z_{7} : x_{1} = c · (\begin{matrix}4 \\ 1 \end{matrix}) , x_{2} = (\begin{matrix}2 \\ 0 \end{matrix}) d · (\begin{matrix}4 \\ 1 \end{matrix})\} =

= \{(\begin{matrix}4c & 2 + 4d \\ c & d \end{matrix} ) | c, d ∈ Z_{7}\}.

□

4.10. Rozhodněte, pro která a z tělesa je matice A_{a} regulární a pro tato a spočítejte matici A_{a}^{−1}.

(a) A_{a} = (\begin{matrix}2 & a \\ 3 & 0 \end{matrix}) nad tělesem Z_{7},
(b) A_{a} = (\begin{matrix}1 & a \\ a & 2a − 1 \end{matrix}) nad tělesem Q,

(c) A_{a} = (\begin{matrix}a & 1 & 0 \\ 1 & 0 & a \\ 1 & 2 & a \end{matrix}) nad tělesem Z_{5}.

Budeme obvyklým způsobem počítat inverzní matice a přitom zároveň provedeme diskusi, pro která a inverzní matice existuje.

(a)

(\begin{matrix}2 & a & |1 & 0 \\ 3 & 0 & |0 & 1 \end{matrix}) ∼ (\begin{matrix}3 & 0 & |0 & 1 \\ 2 & a & |1 & 0 \end{matrix}) ∼ (\begin{matrix}1 & 0 & |0 & 5 \\ 0 & a & |1 & 4 \end{matrix})

Vidíme, že A_{a} regulární, právě když a ≠ 0 a tehdy A_{a}^{−1} = (\begin{matrix}0 & 5 \\ a^{−1} & 4a^{−1} \end{matrix})

(b) Postupujeme stejně jako v (a):

(\begin{matrix}1 & a & |1 & 0 \\ a & 2a − 1 & |0 & 1 \end{matrix}) ∼ (\begin{matrix}1 & a & | & 1 & 0 \\ 0 & 2a − 1 − a^{2} & | & −a & 1 \end{matrix})

Tentokrát je zřejmě matice A_{a} regulární, právě když 2a − 1 − a^{2} = −(a − 1)^{2} ≠ 1, tedy právě když a ≠ 1. Pro a ∈ Q \ {1} pokračujeme v úpravách:

∼ (\begin{matrix}1 & a| & 1 & 0 \\ 0 & 1| & \frac{a}{(a−1)^{2}} & \frac{−1}{(a−1)^{2}} \end{matrix} ) ∼ (\begin{matrix}1 & 0| & \frac{1−2a}{(a−1)^{2}} & \frac{a}{(a−1)^{2}} \\ 0 & 1| & \frac{a}{(a−1)^{2}} & \frac{−1}{(a−1)^{2}} \end{matrix} )

Zjistili jsme, že A_{a}^{−1} = \frac{1}{(a−1)^{2}} (\begin{matrix}1 − 2a & a \\ a & −1 \end{matrix}).

(c) Nejprve si všimněme, že pro a = 0 je poslední sloupec matice nulový, tedy matice A_{0} je singulární. Dále uvažujme jen a ∈ Z_{5} \ {0}:

(\begin{matrix}a & 1 & 0|1 & 0 & 0 \\ 1 & 0 & a|0 & 1 & 0 \\ 1 & 2 & a|0 & 0 & 1 \end{matrix}) ∼ (\begin{matrix}1 & 0 & a & |0 & 1 & 0 \\ 1 & 2 & a & |0 & 0 & 1 \\ a & 1 & 0 & |1 & 0 & 0 \end{matrix}) ∼ (\begin{matrix}1 & 0 & a & |0 & 1 & 0 \\ 0 & 2 & 0 & |0 & 4 & 1 \\ 0 & 1 & 4a^{2} & |1 & 4a & 0 \end{matrix}) ∼

∼ (\begin{matrix}1 & 0 & a & |0 & 1 & 0 \\ 0 & 1 & 0 & |0 & 2 & 3 \\ 0 & 0 & 4a^{2} & |1 & 4a + 3 & 2 \end{matrix}) ∼ (\begin{matrix}1 & 0 & 0 & | & a^{−1} & 3a^{−1} & 2a^{−1} \\ 0 & 1 & 0 & | & 0 & 2 & 3 \\ 0 & 0 & 4a^{2} & | & 1 & 4a + 3 & 2 \end{matrix}) ∼

Nyní snadno dopočítáme, že A_{a} = (\begin{matrix}a^{−1} & 3a^{−1} & 2a^{−1} \\ 0 & 2 & 3 \\ \frac{4}{a^{2}} & \frac{a+2}{a^{2}} & \frac{3}{a^{2}} \end{matrix} ) pro a ∈ Z_{5} \ \{0\}. □

Připomeňme, že Jordanova buňka je matice tvaru J_{λ} = (\begin{matrix}λ & 1 & 0 & … & 0 \\ 0 & λ & 1 & … & 0 \\ ⋮ & ⋮ & ... & ... & ⋮ \\ 0 & 0 & … & λ & 1 \\ 0 & 0 & … & 0 & λ \end{matrix}).

4.11. Je-li J_{λ} Jordanova buňka řádu n nad obecným tělesem, dokažte, že

J_{λ}^{k} = (\begin{matrix}λ^{k} & \binom{k}{1}λ^{k−1} & \binom{k}{2}λ^{k−2} & … & \binom{k}{n−1}λ^{k−n+1} \\ 0 & λ^{k} & \binom{k}{1}λ^{k−1} & … & \binom{k}{n−2}λ^{k−n+2} \\ ⋮ & ⋮ & ... & ... & ⋮ \\ 0 & 0 & … & λ^{k} & \binom{k}{1}λ^{k−1} \\ 0 & 0 & … & 0 & λ^{k} \end{matrix} ) ,

kde definitoricky položíme \binom{k}{r}λ_{i}^{k−r} = 0 pro r > k.

Postupujeme indukcí. Pro k = 1 tvrzení zřejmě platí. Předpokládejme, že vzorec platí pro k a dokažme ho pro k + 1. Budeme násobit J_{λ}^{k+1} = J_{λ} · J_{λ}^{k} =

= (\begin{matrix}λ & 1 & 0 & … & 0 \\ 0 & λ & 1 & … & 0 \\ ⋮ & ⋮ & ... & ... & ⋮ \\ 0 & 0 & … & λ & 1 \\ 0 & 0 & … & 0 & λ \end{matrix}) · (\begin{matrix}λ^{k} & \binom{k}{1}λ^{k−1} & \binom{k}{2}λ^{k−2} & … & \binom{k}{n−1}λ^{k−n+1} \\ 0 & λ^{k} & \binom{k}{1}λ^{k−1} & … & \binom{k}{n−2}λ^{k−n+2} \\ ⋮ & ⋮ & ... & ... & ⋮ \\ 0 & 0 & … & λ^{k} & \binom{k}{1}λ^{k−1} \\ 0 & 0 & … & 0 & λ^{k} \end{matrix} ) =

= (\begin{matrix}λ^{k+1} & (\binom{k}{1} + 1)λ^{k} & (\binom{k}{2} + \binom{k}{1})λ^{k−1} & … & (\binom{k}{n−1} + \binom{k}{n−2})λ^{k−n+2} \\ 0 & λ^{k+1} & (\binom{k}{1} + 1)λ^{k} & … & (\binom{k}{n−2} + \binom{k}{n−3})λ^{k−n+3} \\ ⋮ & ⋮ & ... & ... & ⋮ \\ 0 & 0 & … & λ^{k+1} & (\binom{k}{1} + 1)λ^{k} \\ 0 & 0 & … & 0 & λ^{k+1} \end{matrix} ) =

= (\begin{matrix}λ^{k+1} & \binom{k+1}{1}λ^{k} & \binom{k+1}{2}λ^{k−1} & … & \binom{k+1}{n−1}λ^{k−n+2} \\ 0 & λ^{k+1} & \binom{k+1}{1}λ^{k} & … & \binom{k+1}{n−2}λ^{k−n+3} \\ ⋮ & ⋮ & ... & ... & ⋮ \\ 0 & 0 & … & λ^{k+1} & \binom{k+1}{1}λ^{k} \\ 0 & 0 & … & 0 & λ^{k+1} \end{matrix} ) ,

kde jsme využili známého vztahu \binom{k}{r} + \binom{k}{r−1} = \binom{k+1}{r}. □

20.11.

4.12. Spočítejte A^{n} pro (a) n = 45 a A = (\begin{matrix}3 & 1 & 0 \\ 0 & 3 & 1 \\ 0 & 0 & 3 \end{matrix}) nad tělesem R,

(b) n = 45 a A = (\begin{matrix}1 & \frac{1}{3} & 0 \\ 0 & 1 & \frac{1}{3} \\ 0 & 0 & 1 \end{matrix}) nad tělesem R,

(c) n = 13 a A = (\begin{matrix}8 & 1 & 0 & 0 \\ 0 & 8 & 1 & 0 \\ 0 & 0 & 8 & 1 \\ 0 & 0 & 0 & 8 \end{matrix}) nad tělesem Z_{13}.

(a) Použijeme vzorečku odvozeného v úloze 4.11:

A^{45} = (\begin{matrix}3 & 1 & 0 \\ 0 & 3 & 1 \\ 0 & 0 & 3 \end{matrix})^{45} = (\begin{matrix}3^{45} & 45 · 3^{44} & 990 · 3^{43} \\ 0 & 3^{45} & 45 · 3^{44} \\ 0 & 0 & 3^{45} \end{matrix} )

(b) Všimněme si, že A = \frac{1}{3} · (\begin{matrix}3 & 1 & 0 \\ 0 & 3 & 1 \\ 0 & 0 & 3 \end{matrix}), proto

A^{45} = \frac{1}{3^{45}} · (\begin{matrix}3 & 1 & 0 \\ 0 & 3 & 1 \\ 0 & 0 & 3 \end{matrix})^{45} = \frac{1}{3^{45}} · (\begin{matrix}3^{45} & 45 · 3^{44} & 990 · 3^{43} \\ 0 & 3^{45} & 45 · 3^{44} \\ 0 & 0 & 3^{45} \end{matrix} ) = (\begin{matrix}1 & 15 & 110 \\ 0 & 1 & 15 \\ 0 & 0 & 1 \end{matrix}) .

(c) Uvědomíme-li si, že pro každé prvočíslo p a přirozené číslo r ≤ p je nad tělesem Z_{p} hodnota kombinačního čísla \binom{p}{r} = \frac{p!}{r!·(p−r)!} ≡ 0 (mod p) a spočítámeli 8^{13} ≡ 8 (mod 13) (Malá Fermatova věta nám dokonce obecně říká, že λ^{p} ≡ λ (mod p) pro každé λ ∈ Z_{13} \ {0}), dostáváme díky 4.11

A^{13} = (\begin{matrix}8 & 1 & 0 & 0 \\ 0 & 8 & 1 & 0 \\ 0 & 0 & 8 & 1 \\ 0 & 0 & 0 & 8 \end{matrix})^{13} = (\begin{matrix}8 & 0 & 0 & 0 \\ 0 & 8 & 0 & 0 \\ 0 & 0 & 8 & 0 \\ 0 & 0 & 0 & 8 \end{matrix}) .

□

Další úlohy

(1) Najděte největší společný dělitel a Bezoutovy koeficienty čísel (a) 972 a 1122,

(b) 42589 a 13548,

(c) 2^{22} − 1 a 2^{14} − 1,

(d) 3^{1000} − 1 a 3^{999} − 1,

(e) 3^{1000} + 1 a 3^{999} + 1.

(2) Spočítejte aspoň jedno řešení konruence (a) 63x ≡ 1 (mod 80),

(b) 63x ≡ 5 (mod 80),

(c) 63x ≡ 9 (mod 81),

(d) 64x ≡ 3 (mod 81).

(3) Najděte pro každé celé n (všechna) řešení konruence 857x ≡ n (mod 1021)

(4) Najděte všechna reálná řešení soustavy rovnic:

(a) \begin{aligned}2x & − & y & + & 2z & = & 1 \\ x & + & y & − & z & = & 1 \end{aligned} (b) \begin{aligned}x & + & y & + & z & + & u & = & 3 \\ x & + & 2y & + & 3z & + & 4u & = & 0 \\ x & + & 4y & & & & & = & 0 \end{aligned}

(5) Buď T těleso · a nechť a, b ∈ T. Jestliže a · a = b · b, dokažte z axiomatiky tělesa, že nutně a = b nebo a = −b.

(6) Spočítejte v tělese Z_{83} hodnoty 15^{−1} a (3^{−1} + 6 · 53^{−1})^{−1}.

(7) Vyřešte v tělese Z_{97} rovnici 7 · x + 3 = 51^{−1} + 17.

(8) Najděte nad tělesy Z_{5} a Z_{7} aspoň všechna soustavy rovnic:

x + y + z + u = 3
x + 2y + 3z + 4u = 0
x + 4y  = 0

(9) Existuje-li, najděte nad tělesy R, Q, C, Z_{3}, Z_{5} a Z_{7} všechna rešení soustavy

rovnic:

\begin{aligned}2x & − & y & + & 2z & = & 1 \\ x & + & y & − & z & = & 1 \end{aligned}

(10) Vyřešte v tělese Z_{7} rovnici 5 · x + 3 = 4^{−1} + 4.

(11) Najděte nad tělesy R, Z_{5} a Z_{7} všechna řešení homogenní soustavy rovnic

s maticí (\begin{matrix}2 & 0 & 1 \\ 2 & 1 & 0 \\ 3 & 3 & 1 \end{matrix}).

(12) Najděte nad tělesy Q, Z_{3} a Z_{7} všechna řešení nehomogenní soustavy rovnic

s maticí (\begin{matrix}1 & 0 & 1 & 2 & 2 & |2 \\ 2 & 0 & 2 & 1 & 1 & |0 \end{matrix}).

(13) Uvažujme matice A = (\begin{matrix}1 & 2 & 2 \\ 3 & 1 & 4 \end{matrix}) a B = (\begin{matrix}4 & 2 & 3 & 1 \\ 1 & 4 & 0 & 3 \\ 1 & 0 & 3 & 2 \end{matrix}) nad tělesy T:

Q, Z_{5}, Z_{7}, Z_{11}. Pro každé těleso uvažujme zobrazení φ_{A} : T^{3} → T^{2}, ψ_{A} : T^{2} → T^{3}, φ_{B} : T^{4} → T^{3}, ψ_{B} : T^{3} → T^{4} dané předpisy φ_{A}(v) = Av, ψ_{A}(v) = A^{T} v, φ_{B}(v) = Bv, ψ_{B}(v) = B^{T} v.

(a) Rozhodněte, která ze zobrazení φ_{A}, ψ_{A}, φ_{B}, ψ_{B}, φ_{A}φ_{B}, ψ_{B}ψ_{A} jsou prostá.

(b) Rozhodněte, která ze zobrazení φ_{A}, ψ_{A}, φ_{B}, ψ_{B}, φ_{A}φ_{B}, ψ_{B}ψ_{A} jsou na.

(c) Najděte u zobrazení φ_{A}, ψ_{A}, φ_{B}, ψ_{B}, φ_{A}φ_{B}, ψ_{B}ψ_{A} všechny vektory, které se zobrazí na nulový vektor.

(14) Pro komplexní matice A = (\begin{matrix}1 + i & 3 − i & 1 \\ 2 − i & −i & 1 + i \\ 1 & 1 + 2i & 1 − 2i \end{matrix}),

B = (\begin{matrix}1 − 3i & 2 + 3i & 1 \\ 2 + i & 1 + 2i & i \end{matrix}) a C = (\begin{matrix}1 − 4i & 3 & 0 \\ −i & i & 1 \end{matrix})

(a) spočítejte B + C, B^{T} + A · C^{T}, A · B^{T}, B · A, B^{T} · C a B · C^{T},

(b) existuje-li, najděte matici inverzní k matici A a k matici B · C^{T},

(b) dokažte, že matice B^{T} · C není regulární,

(d) existuje-li, najděte matici X splňující rovnost X · A = C.

(15) Rozhodněte, zda jsou nad tělesy Q, Z_{3}, Z_{5} a Z_{7} regulární matice A =

(\begin{matrix}1 & 2 & 1 \\ 2 & 1 & 0 \\ 2 & 1 & 2 \end{matrix}), B = (\begin{matrix}0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{matrix}), C = (\begin{matrix}1 & 2 & 1 & 2 \\ 0 & 0 & 2 & 2 \\ 1 & 2 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{matrix}) A^{T}, B^{T} a B · C.

(16) Tam, kde je to možné, najděte inverzní matice k maticím z předchozí úlohy.

(17) Spočítejte ((\begin{matrix}1 & 1 \\ 2 & 3 \end{matrix})^{−1} · (\begin{matrix}3 & 2 \\ 2 & 4 \end{matrix}) · (\begin{matrix}0 & 2 \\ 3 & 4 \end{matrix})^{−1} · (\begin{matrix}1 & 4 \\ 1 & 3 \end{matrix}))^{−1} nad tělesy R, Z_{5}

a Z_{7}.

(18) Existují-li najděte inverzní matice k maticím (\begin{matrix}11 & 12 \\ 13 & 14 \end{matrix}), (\begin{matrix}8 & 9 & 9 \\ 9 & 8 & 9 \\ 9 & 9 & 8 \end{matrix}) a

(\begin{matrix}15 & 16 & 3 \\ 9 & 0 & 5 \\ 12 & 0 & 15 \end{matrix}) nad tělesy Z_{17}, Z_{19}, Z_{53} a Z_{103}.

(19) Rozhodněte, pro která a ∈ C je matice A_{a} regulární, a pro tato a spočítejte matici A_{a}^{−1}:

(a) A_{a} = (\begin{matrix}a + 1 & a + 2 \\ a + 3 & a + 4 \end{matrix} ),

(b) A_{a} = (\begin{matrix}a − 1 & 3 \\ a + 1 & 2a \end{matrix}),

(c) A_{a} = (\begin{matrix}a & 1 & 1 \\ a & a & 0 \\ a & 0 & 0 \end{matrix}),

(d) A_{a} = (\begin{matrix}a − 1 & a & a + 2 \\ 3a & 1 & a − 1 \\ a + 1 & a − 1 & 0 \end{matrix}),

(20) Rozhodněte, pro která a ∈ Z_{7} je matice A_{a} regulární, a pro tato a spočítejte matici A_{a}^{−1}:

(a) A_{a} = (\begin{matrix}a + 1 & a + 2 \\ a + 3 & a + 4 \end{matrix} ) , (b) A_{a} = (\begin{matrix}2a & 3a \\ 4a & a + 2 \end{matrix} ) , (c) A_{a} = (\begin{matrix}a & 1 & 3 \\ a & 1 & a \\ 2a & 3a & 6 \end{matrix}) ,

(d) A_{a} = (\begin{matrix}a + 1 & a & a \\ a & a + 2 & a \\ a & a & a + 3 \end{matrix} ) , (e) A_{a} = (\begin{matrix}a + 1 & a & a & a \\ a & a + 1 & a & a \\ a & a & a + 1 & a \\ a & a & a & a + 1 \end{matrix} ) .

(21) Rozhodněte, pro která a, b, c ∈ R je matice A_{a,b,c} regulární, a pro tato a spočítejte matici A_{a,b,c}^{−1}:

(a) A_{a,b,c} = (\begin{matrix}a & b \\ c & a \end{matrix}) , (b) A_{a,b,c} = (\begin{matrix}a + b & 1 \\ c & b \end{matrix}) , (c) A_{a,b,c} = (\begin{matrix}a & b & c \\ c & a & b \\ 1 & 1 & 1 \end{matrix}) .