ZÁKLADY MATEMATIKY I Katedra aplikované matematiky a informatiky Ekonomicko-správní fakulta MU v Brně Email: vesely@econ.muni.cz http: // math. muni. cz/ ~vesely OBSAH 1. Úvod ˇ Základy výrokového počtu. ˇ Základy teorie množin. ˇ Číselné obory. 2. Algebraické struktury ˇ Relace. ˇ Uspořádané množiny. ˇ Ekvivalence a rozklady. ˇ Základní algebraické struktury (grupoid, pologrupa, grupa, okruh, obor integrity, těleso). ˇ Homomorfizmy algebraických struktur. 3. Lineární algebra ˇ Vektorové (lineární) prostory. Lineární závislost a nezá- vislost. Báze a dimenze. ˇ Metrické a normované lineární prostory. Prostory s vnitř- ním součinem. ˇ Matice, operace s maticemi, hodnost matice. ˇ Permutace a determinant. ˇ Lineární zobrazení (lineární operátory). Ortogonální pro- jekce. ˇ Pojem inverzní a pseudoinverzní matice (operátoru). Date: 16. prosinec 2004. ˇ Systémy lineárních rovnic. Cramerovo pravidlo, elimi- nační metody. Frobeniova věta. ˇ Popis množiny všech řešení pro homogenní i nehomo- genní systémy. ˇ Transformace souřadnic a diagonalizace matic. Literatura ke studiu Základní: [KaSk] Karásek J., Skula L.: Algebra a geometrie, PC-DIR Real s.r.o., Brno 2002 (skripta VUT Brno, Fakulta strojního inženýrství) [Šik] Šik F.: Lineární algebra zaměřená na numerickou ana- lýzu, PřF MU Brno, 1998 (skripta) [Ho] Horák P.: Cvičení z algebry a teoretické aritmetiky I., PřF MU Brno, 2002 (sbírka řešených i neřešených úloh) ˇ Pracovní texty vytvořené přednášejícím, které jsou ke stažení v elektronické podobě na: https://www.econ.muni.cz/stud/verejne/verejne/predmety/ Podzim%202004/PMZMI/ Doplňující: [Mi] Minorskij V.P.: Sbírka úloh z vyšší matematiky, SNTL Praha, 1964 [FaSo] Faddejev A.K.,Sominskij J.S.: Zbierka úloh z vyššej al- gebry, ALFA Bratislava, 1968 Poznámka: V tomto textu jsou úseky látky (definice, věty, důkazy a pod.) z hlediska požadavků u zkoušky rozlišeny ve třech úrovních změnou sazby přísluš- ného klíčového slova takto: 1. Minimální znalosti: podtrženě velkými písmeny (např. VĚTA) jsou vyznačeny podstatné partie, jejichž znalost je nezbytná pro získání hodnocení alespoň D­E. 2. Průměrné znalosti: velkými písmeny (např. VĚTA), jejichž znalost nad rámec 1. je třeba pro získání hodnocení B­C. 3. Nadprůměrné znalosti: jsou vysázeny obyčejně (např. Věta). Jejich znalost nad rámec 1. a 2. je třeba k hodnocení A. U důkazů stačí vyložit podstatné myšlenky (postup) vlastními slovy. 2 1. Úvod 1.1. ZÁKLADY VÝROKOVÉHO POČTU. Teorie: [KaSk: s.7-9] Příklady: [Ho:řešené č.1; s.5-6], [Ho:neřešené §1; s.39-42] Matematické vyjadřování: ˇ Stručnost: užívání symbolů (viz přílohu C) ˇ Přesnost: definice, tvrzení, pomocné tvrzení (lemma), věta (teorém), poznámka, seznam označení: s := v nebo v =: s interpretujeme jako označení výrazu v symbo- lem s. Účelem definice je přesné vymezení významu nově zavádě- ného matematického pojmu. Účelem tvrzení, mezi něž patří lemmata i věty (důležitá tvrzení), je vyvodit z výchozích předpokladů přesné logické závěry postupnou aplikací logických pravidel. Tomuto po- stupu říkáme důkaz. Univerzální předpoklady matematic- kých teorií se nazývají axiomy: vyjadřují předem dané sku- tečnosti, které považujeme za univerzálně platné. Výroky: při užití logických pravidel vystupuje jeden ze základ- ních pojmů logiky -- pojem výroku. Výrokem rozumíme libovolné sdělení (tvrzení), o kterém má smysl říci, jestli je pravdivé nebo nepravdivé. Říkáme také, že výrok platí nebo neplatí. Logická hodnota 1 značí výrok, který je vždy pravdivý a podobně logická hodnota 0 značí výrok, který je vždy nepravdivý. Výroky v dalším budeme označovat symbolicky, například V . Pokud výrok závisí na dalších proměnných (ob- vykle opět výrocích) A, B, . . . , píšeme V (A), V (A, B) a po- dobně. 3 Výrokový počet: kalkulus s výroky, kdy pomocí logických operací v tzv. výrokových formulích konstruujeme složené výroky ze zadaných elementárních výroků vystupujících v roli ope- randů. Základní operace jsou popsány pomocí pravdivostních (0­1) tabulek, které každé kombinaci pravdivostních hodnot elementárních výroků přiřazují pravdivostní hodnotu výsled- ného složeného výroku: Operace negace: ,A A 0 1 1 0 Slovní vyjádření: A neplatí Operace implikace: A B A B 0 0 1 0 1 1 1 0 0 1 1 1 Slovní vyjádření: A implikuje B; B plyne z A; B je důsledkem A; A je postačující podmínka pro B; B je nutná podmínka pro A; jestliže platí A, pak platí B. 4 Operace ekvivalence: , A B A B 0 0 1 0 1 0 1 0 0 1 1 1 Slovní vyjádření: A je ekvivalentní s B; A je nutná a posta- čující podmínka pro B; B je nutná a postačující podmínka pro A; A platí právě když B platí; A platí tehdy a jen tehdy, když platí B. Výrok V (A, B, . . . ) 1 (vždy pravdivý) se nazývá tautolo- gie. Operace `A' neboli logický součin neboli konjunkce: &, A B A B = min(A, B) 0 0 0 0 1 0 1 0 0 1 1 1 Slovní vyjádření: platí A i B; platí A a B. Operace `NEBO' neboli logický součet neboli disjunkce: A B A B = max(A, B) 0 0 0 0 1 1 1 0 1 1 1 1 Slovní vyjádření: platí A nebo B. 5 Operace `BUĎ A NEBO': xor A B xor(A, B) 0 0 0 0 1 1 1 0 1 1 1 0 Slovní vyjádření: platí buď A nebo B. Univerzální kvantifikátor: x s vlastností U : V (x) Slovní vyjádření: pro každé x s vlastností U platí V (x). Existenční kvantifikátor: x s vlastností U : V (x) Slovní vyjádření: existuje x s vlastností U splňující V (x). VĚTA 1.1. Platí následující ekvivalence výroků: (1) A A. (2) A B B A, A B B A. (3) DeMorganova pravidla: (A B) A B , (A B) A B . (4) (A B) (A B), (A B) (B A ) . (5) (A B) (A B ) , (A B) (B A ). (6) (A B) (A B)(B A), (A B) (A B ) . (7) (A B) (A B)(B A), (A B) (A B ). (8) Asociativní zákony: A (B C) (A B) C, A (B C) (A B) C. (9) Distributivní zákony: A (B C) (A B) (A C), A (B C) (A B) (A C). (10) ( x s vlastností U : V (x)) ( x s vlastností U : V (x) ) (11) ( x s vlastností U : V (x)) ( x s vlastností U : V (x) ) Poznámka: A B := (A B) , A B := (A B) . 6 DŮKAZ. CVIČENÍD ůkazové techniky: Matematické věty většinou vyjadřují slovně implikace výroků A B (A nazýváme předpokladem věty a B tvrzením věty) nebo ekvivalence výroků A B. Přímý důkaz implikace A B: konstruujeme posloupnost pravdivých výroků: A A1, A1 A2, . . . , An-1 An, An B, tj. dokazu- jeme, že je pravdivý výrok (A A1) (A1 A2) (An-1 An) (An B). Důkaz implikace A B sporem: provádíme přímý důkaz ekvivalentní implikace B A , která pak vede ke sporu s platností předpokladu A, pokud by za jeho platnosti tvrzení B neplatilo. Důkaz ekvivalence A B: dokazujeme platnost ekvivalent- ního výroku (A B)(B A) ve dvou krocích: samostatně dokazujeme platnost obou implikací A B a B A. Důkaz platnosti následujícího výroku matematickou indukcí: n n0 : V (n), kde n, n0 jsou přirozená čísla. Nekonečný přímý důkaz tvaru V (n0) (V (n0) V (n0 + 1) V (n0 + 2), . . . ) nahradíme ověřením platnosti ekvivalentního výroku: n > n0 : (V (n0) V (n0 + 1) V (n - 1)) V (n). Důkaz tak probíhá ve dvou krocích: ˇ Počáteční krok: ověření platnosti výroku V (n0) ˇ Indukční krok: pro každé n > n0 ověříme platnost implikace (V (n0) V (n0 + 1) V (n - 1)) V (n). 7 ANGLICKÁ TERMINOLOGIE VÝROKOVÉHO POČTU definice definition tvrzení statement, proposition věta theorem poznámka remark označení notation důkaz proof axiom axiom výrok sentence, proposition pravdivý, nepravdivý true, false negace negation implikace implication A implikuje B A implies B B plyne z A B follows from A B je důsledkem A B is a consequence of A A je postačující podmínka pro B A is a sufficient condition for B B je nutná podmínka pro A B is a necessary condition for A jestliže platí A, pak platí B if A holds then B holds tvrzení platí the statement holds A je ekvivalentní s B A is equivalent with B A je nutná a postačující podmínka pro B A is a necessary and sufficient condition for B A platí právě když (tehdy a jen tehdy když) B platí A holds if and only if (iff) B holds logický součin: A logical AND logický součet: NEBO (logical) OR BUĎ . . . A NEBO logical EXCLUSIVE OR, EITHER . . . OR univerzální kvantifikátor universal quantifier pro každé x s vlastností U platí V (x) V (x) is true for all x having property U existenční kvantifikátor existential quantifier existuje x s vlastností U splňující V (x) there exists x having pro- perty U such that V (x) is true 8 1.2. ZÁKLADY TEORIE MNOŽIN. Teorie a příklady: [KaSk: s.9-25,37-43] Příklady: [Ho:řešené č.2-4,7-10; s.6-12], [Ho:neřešené kap.1§2§5; s.42-45,51-54] DEFINICE 1.2 (Naivní pojetí teorie množin: Cantor 1849­1918). Množinou rozumíme soubor libovolných objektů, které nazýváme prv- ky této množiny. Množina se nazývá konečná, resp. nekonečná, jestliže má konečně, resp. nekonečně mnoho prvků. Zapisujeme: a A, A a . . . a je prvkem A. a / A, A a . . . a není prvkem A. A := {a1, a2, . . . , an} . . . specifikace konečné množiny výčtem prvků. A := {x | x má vlastnost V} . . . specifikace množiny s prvky majícími vlastnost V, například R+ := {x | x R, x 0} značí množinu všech nezáporných reálných čísel. := {} . . . prázdná množina neobsahuje žádný prvek. Výše uvedená definice je příliš široká a vede proto k logickým para- doxům. Nejznámější je Russelův paradox: Definujeme-li M := {X | X je množina: X / X}, pak pro M mohou nastat jen dvě možnosti, obě vedoucí k logickému sporu: (1) M M, což z definice implikuje M / M, nebo (2) M / M, což z definice implikuje M M. MNOŽINOVÉ INKLUZE A = B . . . množiny A a B jsou si rovny, mají-li tytéž prvky. A = B . . . množiny A a B jsou různé, nemají-li tytéž prvky. A B, B A . . . A je podmnožinou B nebo též B je nadmnoži- nou A, jestliže každý prvek A je také prvkem B. A B, B A . . . A je vlastní podmnožinou B, jestliže A B a současně A = B, tj. kromě všech prvků z A, existuje v B ještě alespoň jeden další prvek. Příklad: N Z Q R C. 9 VĚTA 1.3. Platí A = B tehdy a jen tehdy, když A B a B A. Označení (Intervaly). Nechť a, b R jsou daná reálná čísla. Pak intervalem reálných čísel nazýváme kteroukoli z níže uvedených podmnožin v R: [a, b] := {x | x R : a x b}. . . uzavřený interval; (a, b) := {x | x R : a < x < b}. . . otevřený interval; [a, b) := {x | x R : a x < b}. . . interval zleva uzavřený a zprava otevřený; (a, b] := {x | x R : a < x b}. . . interval zleva otevřený a zprava uzavřený; (-, ) := R; (-, b) := {x | x R : x < b}; (-, b] := {x | x R : x b}; (a, ) := {x | x R : a < x}; [a, ) := {x | x R : a x}. ZOBRAZENÍ DEFINICE 1.4. Buďte A, B množiny. Pravidlo f, které každému prvku a A přiřazuje právě jeden prvek b B, se nazývá zobrazení množiny A do množiny B. Píšeme b = f(a) nebo a f(b). Prvek b se nazývá obraz a v zobrazení f. Zobrazení f se nazývá prosté nebo také injektivní, když platí: a1, a2 A, a1 = a2 f(a1) = f(a2) (nebo ekvivalentně: f(a1) = f(a2) a1 = a2). Zobrazení f se nazývá A na B nebo také surjektivní, když ke kaž- dému b B existuje a A tak, že b = f(a). Je-li f prosté zobrazení A na B, nazývá se bijekce nebo také jed- nojednoznačná korespondence mezi A a B. Bijekce A na A se nazývá permutace množiny A. Zápisy: f : A B . . . zobrazení f z A do B. f : A B . . . prosté zobrazení f z A do B. 10 f : A B . . . zobrazení f z A na B. f : A B . . . bijekce f z A na B. Dvě zobrazení f : A B a g : C D jsou stejná právě když A = C, B = D a f(x) = g(x) pro každé x A. DEFINICE 1.5. Je-li f : A B, C A, D B, pak definujeme: f(C) := {f(a) | a C} . . . obraz množiny C v zobrazení f. f|C : C B definované vztahem f|C (c) := f(c) pro každé c C nazýváme restrikcí zobrazení f na množinu C. f-1 (D) := {a | a A : f(a) D} . . . úplný vzor množiny D v zob- razení f. Je-li f bijekce A na B, pak f-1 ({f(a)}) = {a} pro každé a A a f(f-1 ({b})) = {b} pro každé b B. V takovém případě píšeme zjednodušeně f-1 (f(a)) = a a f(f-1 (b)) = b a takto získané (bijektivní) zobrazení f-1 : B A nazýváme in- verzní zobrazení k f. Zřejmě platí: f-1 (b) = a b = f(a). Zobrazení IA : A A definované vztahem IA(a) := a pro každé a A je zřejmě bijekce. Nazývá se identické zobrazení na A. Je-li B A, pak zobrazení 1B : A {0, 1} definované vztahem 1B(a) := 1 pro a B 0 pro a / B nazýváme charakteristickou funkcí pod- množiny B (v množině A). DEFINICE 1.6. Zobrazení f : I A, kde I Z, nazýváme posloupností prvků z A a zapisujeme jej ve tvaru {an}nI , kde an := f(n). Pokud I = N, resp. I = Z, píšeme také {an} n=1, resp. {an} n=-. DEFINICE 1.7. Nechť f : A B a g : B C jsou dvě zobrazení, pak zobrazení h : A C definované vztahem h(a) := g(f(a)) pro každé a A, nazýváme složením zobrazení f a g a píšeme h = gf. PŘÍKLAD 1.8. Uvažujme funkční předpis f(x) := x2 , pak f : R R není ani prosté ani surjektivní, 11 f : R R+ je surjektivní, ale není prosté, f : R+ R+ je prosté i surjektivní, tj. je bijekcí. MNOŽINOVÉ OPERACE Nechť dále Ai, i I značí nějaký systém množin indexovaný prvky i z indexové množiny I. DEFINICE 1.9 (Sjednocení množin). A B := {x | (x A) (x B)} A B C := {x | (x A) (x B) (x C)} A1 A2 An := {x | i {1, 2, . . . , n} : x Ai} ... i I Ai := {x | i I : x Ai} DEFINICE 1.10 (Průnik množin). A B := {x | (x A) (x B)} A B C := {x | (x A) (x B) (x C)} A1 A2 An := {x | i {1, 2, . . . , n} : x Ai} ... i I Ai := {x | i I : x Ai} Jestliže A B = , říkáme, že množiny A a B jsou disjunktní. DEFINICE 1.11 (Rozdíl množin). A - B := {x | (x A) (x / B)} Příklad: R - Q (resp. šířeji C - Q) . . . množina všech iracionálních čísel. 12 DEFINICE 1.12 (Doplněk (komplement) množiny). Jestliže všechny uvažované množiny jsou podmnožinami jisté pevně zvolené univerzální množiny (prostoru) X, pak množinu X - A na- zýváme doplňkem nebo také komplementem množiny A (v X) a píšeme A n ebo Ac . DEFINICE 1.13 (Symetrická diference). A ÷ B := (A - B) (B - A) DEFINICE 1.14 (Kartézský součin množin). A × B := {[a, b] | (a A) (b B)} A × B × C := {[a, b, c] | (a A) (b B) (c C)} A1 × A2 × × An := {[a1, a2, . . . , an] | i {1, 2, . . . , n} : ai Ai} ... i I Ai := XiI Ai := { | : I i I Ai, kde (i) Ai i I }, kde [a, b], [a, b, c],. . . ,[a1, a2, . . . , an] značí uspořádané dvojice, trojice atd. až n-tice: i-tou složku uspořádané n-tice lze považovat za ob- raz čísla i {1, 2, . . . , n} v nějakém zobrazení : {1, 2, . . . , n} n i=1 Ai, kde ai := (i) Ai. Odtud pramení zobecnění definice kartézského součinu na libovolný systém množin, kde každá složka koresponduje s indexem i I z libovolné indexové množiny I. Jsou-li všechny množiny v kartézském součinu identické, pak značí: A2 := A × A (kartézský čtverec množiny A), A3 := A ×A ×A, . . . , An := A × A × × A n × a obecně AI := X iI A. Zejména tedy AI := { | : I A} označuje množinu všech zobra- zeni I do A. 13 PŘÍKLAD 1.15. (1) Nechť A := {a, b, c, d} a B := {c, d, e, f}, pak A B = {a, b, c, d, e, f}, A B = {c, d}, A - B = {a, b}, B - A = {e, f} a A ÷ B = {a, b, e, f}. (2) R2 . . . koresponduje s množinou všech bodů roviny, R3 . . . s množinou všech bodů 3-rozměrného prostoru, Rn . . . s množinou všech bodů n-rozměrného prostoru a RN , resp. RZ s množinou všech posloupností reálných čísel. MNOŽINOVÉ IDENTITY VĚTA 1.16. (1) Komutativita: A B = B A (2) Asociativita: (A B) C = A (B C) = A B C (3) Obecná asociativita a komutativita: Všechna možná sjedno- cení vytvořená všemi možnými uzávorkováními posloupnosti množin A1, A2, . . . , An v libovolném pořadí jsou rovna jedi- nému prvku A1 A2 An. (4) A A = A, A = A (5) A B A C B C pro libovolné C (6) A A B pro libovolné B (7) A B = B A B Důkaz. CVIČENÍV ĚTA 1.17. (1) Komutativita: A B = B A (2) Asociativita: (A B) C = A (B C) = A B C (3) Obecná asociativita a komutativita: Všechny možné průniky vytvořené všemi možnými uzávorkováními posloupnosti mno- žin A1, A2, . . . , An v libovolném pořadí jsou rovny jedinému prvku A1 A2 An. (4) A A = A, A = (5) A B A C B C pro libovolné C 14 (6) A B A pro libovolné B (7) A B = A A B Důkaz. CVIČENÍV ĚTA 1.18 (Distributivní zákon). A (B C) = (A B) (A C) A (B C) = (A B) (A C) A (B - C) = (A B) - (A C) Důkaz. CVIČENÍV ěta 1.19 (Obecný distributivní zákon [TM1:V1.1.5 s.4]). Nechť I je indexová množina a Ji jsou indexové množiny pro každé i I. Nechť ke každé uspořádané dvojici indexů [i, j], i I, j Ji, je přiřazena množina Aij. Pak platí: i I j Ji Aij = K i I Ai(i) i I j Ji Aij = K i I Ai(i), kde K := X iI Ji. Poznámka 1.20. Distributivní zákon A (B C) = (A B) (A C) z věty 1.18 je speciálním případem 1.19 (analogicky po vzájemné záměně operací průniku a sjednocení): Jestliže provedeme přeznačení množin A11 := A, A21 := B a A22 := C a zavedeme indexové množiny I := {1, 2}, J1 := {1} a J2 := {1, 2}, pak K := J1×J2 = {[1, 1], [1, 2]}, takže dostáváme: A11 (A21 A22) = (A11 A21) (A11 A22). Výše uvedený postup můžeme zobecnit do následujícího důsledku věty 1.19. Ten ilustruje skutečnost, že obecný distributivní zákon pro 15 průniky a sjednocení funguje analogicky jako při roznásobování sou- činu součtů čísel. DŮSLEDEK 1.21. (A1 A2 A3 . . . ) (B1 B2 B3 . . . ) (C1 C2 C3 . . . ) = = [ j,k,l,... ] (Aj Bk Cl . . . ) (A1 A2 A3 . . . ) (B1 B2 B3 . . . ) (C1 C2 C3 . . . ) = = [ j,k,l,... ] (Aj Bk Cl . . . ) PŘÍKLAD 1.22 (CVIČENÍ). (A B C) (D E) (F G H) =?. LEMMA 1.23. A - B = A B , kde komplement B uvažujeme v nějaké množině obsahující A i B. VĚTA 1.24 (DeMorganova pravidla [TM1:V1.1.6 s.5]). Nechť A je množina a {Ai}iI systém množin. Pak platí: A - i I Ai = i I (A - Ai) A - i I Ai = i I (A - Ai) DŮSLEDEK 1.25. [KaSk:Věta 1.4 s.15] ( i I Ai) = i I Ai ( i I Ai) = i I Ai , kde komplementy uvažujeme v nějaké množině obsahující všechny mno- žiny Ai, i I, neboli obsahující jejich sjednocení. 16 VĚTA 1.26 (Vlastnosti symetrické diference [TM1:V1.1.8 s.6]). Platí (1) Komutativita: A ÷ B = B ÷ A (2) Asociativita: (A ÷ B) ÷ C = A ÷ (B ÷ C) (3) Distributivita s průnikem: A (B ÷ C) = (A B) ÷ (A C) (4) A ÷ A = , A ÷ = ÷ A = A DEFINICE 1.27. Nechť {An} n=1 je posloupnost množin. Pak de- finujeme: lim sup An (limes superior) jako množinu všech prvků, které leží v nekonečně mnoha množinách An a lim inf An (limes in- ferior) jako množinu všech prvků, které leží ve skoro všech mno- žinách An (tj. ve všech s výjimkou konečného počtu). Zřejmě platí lim inf An lim sup An. Platí-li lim inf An = lim sup An =: A, pravíme, že posloupnost množin {An} n=1 je konvergentní a píšeme A = lim An. VĚTA 1.28. [TM1:V1.1.7 s.6] Platí lim inf An = k =1 n =k An lim sup An = k =1 n =k An DŮSLEDEK 1.29. Monotonní posloupnost je konvergentní. Přitom (1) je-li posloupnost neklesající: A1 A2 A3 . . . , pak lim An = n=1 An =: A a píšeme An A. (2) je-li posloupnost nerostoucí: A1 A2 A3 . . . , pak lim An = n=1 An =: A a píšeme An A. 17 MOHUTNOSTI MNOŽIN A KARDINÁLNÍ ČÍSLA DEFINICE 1.30. Množiny A a B se nazývají ekvivalentní, píšeme A B, jestliže existuje bijekce A na B. Říkáme také, že A a B mají stejnou mohutnost a píšeme card A = card B. Symbol a := card A pak nazýváme mohutností nebo kardinálním číslem množiny A. Jestliže existuje injekce A do B (neboli A je ekvivalentní s nějakou podmnožinou B), píšeme card A card B. Pokud přitom A a B ne- mají stejnou mohutnost, tj. card A = card B, píšeme card A < card B. DEFINICE 1.31. Každá množina ekvivalentní s množinou všech přirozených čísel N se nazývá spočetná. DEFINICE 1.32. Nekonečná množina, která není spočetná se na- zývá nespočetná. VĚTA 1.33 ([TM1:V1.3.17 s.18] viz také dále 1.34 a 1.35). Interval [0, 1] je nespočetný. DEFINICE 1.34. Říkáme, že množina M je množina o mohut- nosti kontinua, je-li M [0, 1]. VĚTA 1.35 ([TM1:V1.3.18 s.18] viz také dále 1.59(2)). Každý netriviální interval (tj. interval obsahující více jak jeden prvek) má mohutnost kontinua. Poznámka 1.36. (1) Pro množiny, které nejsou nekonečné, udává mohutnost počet jejich prvků: card =: 0 card {a1, a2, . . . , an} =: n (2) Pro zápis mohutnosti nekonečných množin je používán symbol (čteme alef : písmeno A hebrejské abecedy): A spočetná: card A =: 0 A o mohutnosti kontinua: card A =: . (3) Pro zápis mohutnosti disjunktního sjednocení množin je používán symbol + nebo : 18 card ( i I Ai) =: i I card Ai card (A1 A2 An) =: card A1 + card A1 + + card An. (4) Pro zápis mohutnosti kartézského součinu množin je po- užíván symbol nebo : card ( X iI Ai) =: i I card Ai, resp. card (AI ) =: (card A)card I , Speciálně card (A ) =: (card A)0 =: 1, tj. množina všech zobra- zení z prázdné množiny do A se považuje za jednoprvkovou množinu obsahující tzv. prázdné zobrazení. card (A1 × A2 × × An) =: card A1 card A1 card An, resp. card (An ) =: (card A)n . VĚTA 1.37. [TM1:V1.3.2 s.14] Buď I indexová množina a {Ai}iI a {Bi}iI dva systémy množin takové, že Ai Bi pro každé i I. Pak platí: (1) X iI Ai X iI Bi (2) Jsou-li množiny Ai po dvou disjunktní a rovněž množiny Bi po dvou disjunktní, platí také i I Ai i I Bi. DŮSLEDEK 1.38. A1 B1, A2 B2 A1 × A2 B1 × B2. Jsou-li navíc jak A1, A2 tak B1, B2 disjunktní, platí navíc A1 A2 B1 B2. VĚTA 1.39. [TM1:V1.3.3 s.14] Buď dán systém množin {Ai}iI , kde množiny Ai jsou po dvou dis- junktní a Ai A pro každé i I. Pak i I Ai I × A a i I (card Ai) = card I card A. VĚTA 1.40 ([KaSk:V4.6 s.39],[TM1:1.3.24 s.21]). Nechť A2 A1 A a nechť A2 A. Pak také A1 A. Neboli card A2 card A1 card A card A1 = card A. DŮSLEDEK 1.41. Nechť A, B jsou dvě množiny, z nichž každá je ekvivalentní s podmnožinou druhé. Pak A B. Zejména tedy platí: (card A card B) (card B card A) (card A = card B). 19 Zejména tedy pro žádné dvě množiny A a B nemůže současně pla- tit card A < card B a card B < card A. Věta 1.42 (Komut. zákon pro kartézský součin [TM1:V1.3.4 s.14]). Nechť je dán systém množin {Ai}iI , ai := card Ai, a I J, kde f je bijekce J na I. Pak X iI Ai X jJ Af(j) a i I ai = j J af(j). DŮSLEDEK 1.43. (1) Je-li f permutace množiny I, pak platí X iI Ai X iI Af(i) a i I ai = i I af(i). (2) A × B B × A a card A card B = card B card A. Věta 1.44 (Asoc. zákon pro kartézský součin [TM1:V1.3.5 s.15]). Nechť je dán systém množin {Ai}iI , ai := card Ai, a I = k K Ik, kde množiny Ik jsou po dvou disjunktní. Pak platí X iI Ai X kK ( X iIk Ai), i I ai = k K ( i Ik ai). DŮSLEDEK 1.45. (1) Platí A × (B × C) (A × B) × C A × B × C, a(bc) = (ab)c = abc, kde a, b, c značí po řadě mohutnosti množin A, B, C. (2) Nechť I = k K Ik, kde Ik jsou po dvou disjunktní. Pak platí AI X kK AIk a (card A) k K card Ik = k K (card A)card Ik . Zejména AI1I2 AI1 × AI2 a card Acard I1+card I2 = card Acard I1 card Acard I2 , jsou-li I1 a I2 disjunktní. (3) Nechť M je množina, m := card M, a nechť je dán systém množin {Ai}iI , ai := card Ai. Pak platí ( X iI Ai)M X iI AM i , ( i I ai)m = i I am i . Zejména (A × B)M AM × BM , (a b)m = am bm , kde a, b jsou po řadě mohutnosti množin A, B. 20 (4) Pro libovolné množiny A, M, N a jejich mohutnosti a, m, n platí AM×N (AM )N , amn = am an . Věta 1.46 (Distr. zákony pro kartézský součin [TM1:V1.3.6 s.15]). Nechť I je indexová množina a Ji jsou indexové množiny pro každé i I. Nechť ke každé uspořádané dvojici indexů [i, j] je přiřazena množina Aij. Pak platí: XiI j Ji Aij = K XiI Ai(i) XiI j Ji Aij = K XiI Ai(i) kde K := X iI Ji. DŮSLEDEK 1.47. Platí A × (B C) = (A × B) (A × C) A × (B C) = (A × B) (A × C) VĚTA 1.48. [TM1:1.3.7 s.16] Buď M množina a B množina obsahující dva prvky. Označme P(M) množinu všech podmnožin množiny M (někdy se také značí poněkud nepřesně jako 2M ). Pak P(M) BM a card (P(M)) = 2card M . VĚTA 1.49 (Cantorova věta [KaSk:V4.14-15 s.41]). Pro každé kardinální číslo a platí 2a > a. VĚTA 1.50. [TM1:V1.3.8 s.16] Množina A je spočetná tehdy a jen tehdy, když její prvky lze očíslovat přirozenými čísly, tj. když ji lze psát ve tvaru posloupnosti: A := {a1, a2, . . . , an, . . . } = {an} n=1. PŘÍKLAD 1.51. Příklady spočetných množin: ˇ N := {1, 2, 3, . . . , n, . . . } . . . množina přirozených čísel 21 ˇ {2, 4, 6, . . . , 2n, . . . } . . . množina sudých přirozených čísel ˇ {1, 3, 5, . . . , 2n - 1, . . . } . . . množina lichých přirozených čísel ˇ {1, 4, 9, . . . , n2 , . . . } . . . množina kvadrátů přirozených čísel ˇ {1, 1 2 , 1 3 , . . . , 1 n , . . . } . . . množina převrácených hodnot přiro- zených čísel VĚTA 1.52 (Vlastnosti spočetných množin). (1) Každá nekonečná množina obsahuje (vlastní) spočetnou pod- množinu. (2) Každá nekonečná podmnožina spočetné množiny je spočetná. (3) Rozdíl spočetné množiny a konečné množiny je spočetná mno- žina (0 - n = 0 pro každé n N). (4) Sjednocení spočetné množiny a konečné množiny je spočetná množina (0 + n = 0 pro každé n N). (5) Sjednocení konečného počtu spočetných množin je spočetná množina (n 0 = 0 pro každé n N). (6) Sjednocení spočetné množiny neprázdných po dvou disjunkt- ních konečných množin je spočetná množina (0 n = 0 pro každé n N). (7) Kartézský součin konečného počtu spočetných množin je spo- četná množina (n 0 = 0 pro každé n N). Důkaz. [TM1:V1.3.9-V1.3.14 s.16-17].D ŮSLEDEK 1.53. [TM1: s.17-18] (1) Sjednocení spočetné množiny spočetných množin je spočetná množina. (2) Množina všech celých i racionálních čísel je spočetná. (3) Množina všech racionálních čísel netriviálního intervalu reál- ných čísel je spočetná. (4) Množina všech bodů v rovině (v prostoru) s racionálními sou- řadnicemi je spočetná. (5) Množina všech komplexních čísel s racionální reálnou i ima- ginární částí je spočetná. 22 (6) Množina všech polynomů s celými (racionálními) koeficienty je spočetná. (7) Množina všech algebraických čísel je spočetná (algebraic- kým číslem rozumíme reálné číslo, které je kořenem něja- kého polynomu s celočíselnými koeficienty). VĚTA 1.54. [TM1:V1.3.15 s.18] Je-li M nekonečná a A nejvýše spočetná množina (tj. konečná nebo spočetná), pak M A M (neboli M A má stejnou mohutnost jako M). DŮSLEDEK 1.55. [TM1:V1.3.24 s.20] Nechť M je spočetná množina, pak P(M) má mohutnost kontinua a platí 20 = > 0. VĚTA 1.56. [TM1:V1.3.16 s.18] Buď M nespočetná množina a A její nejvýše spočetná podmnožina. Pak M - A M. Je-li A konečná, platí tvrzení i pro spočetnou množinu M dle 1.52(3). DŮSLEDEK 1.57. Množina M je nekonečná právě když obsahuje vlastní podmnožinu stejné mohutnosti jako M. VĚTA 1.58 (Vlastnosti množin o mohutnosti kontinua). (1) Každá množina o mohutnosti kontinua obsahuje vlastní pod- množinu o mohutnosti kontinua [plyne z 1.57]. (2) Rozdíl množiny o mohutnosti kontinua a nejvýše spočetné množiny má mohutnost kontinua ( - n = - 0 = pro každé n N) [plyne z 1.56]. (3) Sjednocení množiny o mohutnosti kontinua a nejvýše spo- četné množiny je množina o mohutnosti kontinua ( + n = + 0 = pro každé n N) [plyne z 1.54]. (4) Sjednocení nejvýše spočetné množiny po dvou disjunktních množin o mohutnosti kontinua má mohutnost kontinua (n = 0 = pro každé n N) [TM1:V1.3.19-20 s.19]. 23 (5) Kartézský součin spočetně mnoha dvouprvkových množin má mohutnost kontinua ( = 20 > 0) [plyne z 1.55 a z 1.48]. (6) Množina všech posloupností přirozených čísel má mohutnost kontinua (0 0 = ) [TM1:V1.3.21 s.19]. (7) Kartézský součin nejvýše spočetně mnoha množin o mohut- nosti kontinua má mohutnost kontinua (n = 0 = pro každé n N) [TM1:V1.3.22-23 s.20]. DŮSLEDEK 1.59. (1) Sjednocení nejvýše spočetné množiny množin o mohutnosti kontinua má mohutnost kontinua [plyne z 1.58(4) užitím 1.40]. (2) Každý netriviální interval i jeho nejvýše spočetná mocnina mají mohutnost kontinua [viz 1.54, 1.56 a 1.58(4)(7)]. Zejména Rn pro každé n N i RN mají mohutnost kontinua. (3) Množina všech iracionálních čísel má mohutnost kontinua [plyne ze (2) a z 1.58(2)] . (4) Množina všech transcendentních čísel má mohutnost konti- nua (transcendentním číslem nazýváme každé reálné číslo, které není algebraické) [plyne ze 1.53(7) a z 1.58(2)]. (5) Množina všech bodů v rovině má mohutnost kontinua [plyne ze (2)]. Zejména C má také mohutnost kontinua. (6) Buď dán systém množin {Ai}iI , kde množiny Ai jsou po dvou disjunktní a každá z nich má mohutnost kontinua stejně jako indexová množina I. Pak i I Ai má rovněž mohutnost kontinua [plyne z 1.58(7) spolu s 1.39]. (7) Kartézský součin spočetně mnoha nejvýše spočetných množin o alespoň dvou prvcích má mohutnost kontinua (n0 = 0 0 = pro každé n N, n 2) [plyne z 1.58(5)(6) užitím 1.40]. 24 1.3. Číselné obory. V této kapitole shrneme základní poznatky o číselných oborech, které se nejčastěji vyskytují v matematice. MNOŽINA PŘIROZENÝCH ČÍSEL N N := {1, 2, . . . , n, . . . }. Operace: sečítání +, násobení . a z něj odvozené umocňování: nk := n × n × × n k × , k N, n0 := 1. Význačné prvky: jednotkový prvek 1 (1.n = n.1 = n n N) Mohutnost: card N = 0 dle 1.31 a 1.36(2). MNOŽINA CELÝCH ČÍSEL Z Příklady: [Ho:neřešené §3; s.45-47] Z := {. . . , -2, -1, 0, 1, 2, . . . , n, . . . } = {-n | n N} {0} N. Operace: sečítání +, odečítání -, násobení . a z něj odvozené umoc- ňování: nk := n × n × × n k × , k N, n0 := 1 pro n = 0. Význačné prvky: ˇ jednotkový prvek 1 (1.n = n.1 = n n Z) ˇ nulový prvek 0 (0 + n = n + 0 = n n Z) Mohutnost: card Z = 0 dle 1.53(2). MNOŽINA CELÝCH ČÍSEL MODULO N: ZN ZN := {0, 1, . . . , N - 1} pro každé N N. Jelikož každé celé číslo n Z lze jednoznačně vyjádřit ve tvaru n = q.N +r (q je celá část podílu a r ZN zbytek po dělení), můžeme zavést surjektivní zobrazení N : Z ZN přiřazující každému ce- lému číslu n jeho zbytek po dělení číslem N: tzv. operace modulo. Pomocí této operace zavedeme tzv. modulární aritmetiku na ZN . Operace: ˇ sečítání modulo N: a b := a + b mod N := a + b N, ˇ odečítání modulo N: a b := a - b mod N := a - b N, ˇ násobení modulo N: a b := a.b mod N := a.b N 25 a z něj odvozené umocňování modulo N: nk mod N := nk N, k N, n0 mod N := 1 pro n = 0. Význačné prvky: ˇ jednotkový prvek 1 při N > 1 (1 n = n 1 = n n ZN ) ˇ nulový prvek 0 (0 n = n 0 = n n ZN ) Mohutnost: card ZN = N dle 1.36(1). MNOŽINA RACIONÁLNÍCH ČÍSEL Q Q := {p q | p q je hodnota zlomku s čit. p a jmenov. q, p, q Z, q = 0}. Je-li q = 1, pak p q = p a tedy Z Q. Operace: sečítání +, odečítání -, dělení nenulovým číslem /, náso- bení . a z něj odvozené umocňování: rk := r × r × × r k × , k N; pro r = 0 definujeme r0 := 1 a r-k := (1/r)k . Význačné prvky: ˇ jednotkový prvek 1 (1.r = r.1 = r r Q) ˇ nulový prvek 0 (0 + r = r + 0 = r r Q) Mohutnost: card Q = 0 dle 1.53(2). MNOŽINA REÁLNÝCH ČÍSEL R R := {r | r = dk dk-1 . . . d0, d-1 d-2 . . . je desetinné vyjádření čísla r}. Tedy r = k j=- dj10j , k Z, k 0, kde dj Z10, jsou dekadické cifry vyjádření čísla r v soustavě o základu 10, tj. pro k N je dk-1 k-tá cifra před desetinnou čárkou a d-k k-tá cifra za desetinnou čár- kou. Každé reálné číslo lze vyjádřit v libovolné soustavě o základu N N, N 2, kdy r = k j=- djNj , k Z, k 0, kde dj ZN . V paměti počítačů se užívají soustavy o základu N = 2 (dvojková, binární, dyadická), kde cifry dj {0, 1}; N = 8 (osmičková, ok- talová) nebo N = 16 (šestnáctková, hexadecimální), kde cifry dj 10 obvykle nahrazujeme písmeny: 10 =: A, 11 =: B, 12 =: C, 13 =: D, 14 =: E, 15 =: F. 26 Množina R představuje zúplnění množiny Q v tom smyslu, že každé reálné číslo je 'limitou' nějaké posloupnosti racionálních čísel. Napří- klad stačí vzít useknuté desetinné rozvojek j=-m dj10j = dk dk-1 . . . d0, d-1 d-2 . . . d-m postupně s m = 1, 2, . . . místy za desetinnou čárkou, které představují racionální čísla blížící se pro m k číslu r. Operace: sečítání +, odečítání -, dělení nenulovým číslem /, náso- bení . a z něj odvozené umocňování rk := r × r × × r k × , kde r R a k N; pro r = 0 definujeme r0 := 1 a r-k := (1/r)k . Pokud r > 0, lze umocňování dále rozšířit na rs i pro reálný exponent s R, přičemž platí r-s := (1/r)s . Význačné prvky: ˇ jednotkový prvek 1 (1.r = r.1 = r r R) ˇ nulový prvek 0 (0 + r = r + 0 = r r R) Mohutnost: card R = dle 1.59(2). MNOŽINA IRACIONÁLNÍCH ČÍSEL I I := R - Q. Mohutnost: card I = dle 1.59(3). MNOŽINA ALGEBRAICKÝCH ČÍSEL A Dle 1.53(7) algebraickým číslem rozumíme každé reálné číslo a R, které je kořenem nějakého polynomu s celočíselnými koeficienty, tj. platí P(a) = 0, pro nějaký polynom P(x) = p0 + p1x + + pnxn stupně n N, kde pi Z i Z, pn = 0. Je Q A, neboť každé racionální číslo p q , q = 0, je řešením lineární rovnice q.x - p = 0. Existují však další algebraická čísla: například n m pro libovolné m, n N, n > 1, je řešením rovnice xn - m = 0. Zejména 2 je algebraické číslo, které není racionální. Mohutnost: card A = 0 dle 1.53(7). 27 MNOŽINA TRANSCENDENTNÍCH ČÍSEL T Dle 1.59(4) definujeme T := R - A R - Q = I. Nejznámějšími příklady transcendentních čísel jsou čísla e := 2.718281828459 . . . základ tzv. přirozeného logaritmu ln a := 3.1415926535897 . . . Ludolfovo číslo=délka kružnice o prů- měru 1. Mohutnost: card T = dle 1.59(4). MNOŽINA KOMPLEXNÍCH ČÍSEL C Motivací pro zavedení komplexních čísel je skutečnost, že některé po- lynomické rovnice P(x) = 0 s reálnými koeficienty nemají reálný ko- řen. Například x2 + 1 > 0 pro každé x R. Jestliže označíme speci- álním symbolem i := -1 nazývaným imaginární jednotka, pak i2 = -1 můžeme považovat za řešení odpovídající rovnice x2 + 1 = 0 (někdy místo i se používá symbol j). Zavedeme-li množinu tzv. kom- plexních čísel jako množinu formálních součtů reálných čísel s reál- nými násobky imaginární jednotky, tj. C := {a + i.b | a R, b R}, pak se dá ukázat, že uvedený problém bude odstraněn: každý poly- nom stupně n s komplexními koeficienty bude mít právě n kořenů. To odpovídá zkušenosti z reálného oboru s rovnicí x2 - 1, která má dva kořeny -1 a 1. V rozšířeném oboru komplexních čísel C pak podobně rovnice x2 + 1 má dva kořeny -i a i. Značení: Je-li c = a + i.b komplexní číslo, pak značí Re c := a . . . reálnou část c Im c := b . . . imaginární část c |c| := a2 + b2 . . . velikost (absolutní hodnotu, modul) c := arctan( b a ), 0 < 2 . . . argument c c := a - i.b . . . číslo komplexně sdružené k c (zřejmě c.c = |c|2 ). Zřejmě C {[a, b] | a R, b R} = R2 , takže každé komplexní číslo a + i.b můžeme znázornit jako bod v kartézské rovině o souřadnicích a, b. Tato rovina se pak nazývá komplexní rovina. 28 Dostáváme tak tři základní tvary pro vyjádření komplexního čísla: ˇ kartézský: c = a + i.b ˇ goniometrický: c = A(cos + i sin ), který odpovídá přechodu k polárním souřadnicím: a = A cos , b = A sin . ˇ Eulerův: c := Aei , kde ei := cos + i sin je komplexní číslo na jednotkové kružnici v komplexní rovině. R = {c C | Im c = 0} C, přičemž operace z R rozšíříme formálně na C za užití vlastnosti i2 = -1 při operacích násobení a dělení. Operace sečítání (odečítání) se provádí po složkách jako s vektory v rovině. Tyto výpočty pak formálně usnadňuje Eulerův zápis. Odtud dostáváme s uvážením 1 i = i i.i = -i: i0 = 1, i1 = i, i2 = -1, i3 = -i, i4 = 1, obecně: i4n+k = ik n, k Z. Operace (podrobněji viz přílohu A): sečítání +, odečítání -, dělení nenulovým číslem /, násobení . a z něj odvozené umocňování (resp. odmocňování) ck := c × c × × c k × , kde c C a k N; pro c = 0 lze umocňování dále rozšířit na cs i pro komplexní exponent s C, přičemž platí c-s := (1/c)s . Význačné prvky: ˇ jednotkový prvek 1 := 1 + i.0 (1.c = c.1 = c c C) ˇ nulový prvek 0 := 0 + i.0 (0 + c = c + 0 = c r R). Mohutnost: card C = dle 1.59(5). 29 ANGLICKÁ TERMINOLOGIE TEORIE MNOŽIN množina, prázdná množina set, empty set (vlastní) podmnožina, nadmnožina (proper) subset, superset zobrazení, prosté, inverzní mapping, injective, inverse surjektivní (na), bijektivní surjective (onto), bijective permutace permutation obraz, úplný vzor image, preimage (inverse image) posloupnost sequence sjednocení, průnik union, intersection (kartézský) součin, mocnina (cartesian) product, power disjunktní, po dvou disjunktní disjoint, pairwise disjoint rozdíl, symetrická diference difference, symmetric difference monotonní, konvergentní monotone, convergent mohutnost, kardinální číslo cardinality, cardinal number spočetný, nespočetný countable, uncountable mohutnost kontinua continuum power konečný, nekonečný finite, infinite množina všech podmnožin power set číslo, reálné, komplexní mumber, real, complex celé, racionální, iracionální integer, rational, irrational algebraické, transcendentní algebraic, transcendental komplexně sdružené číslo complex conjugate number 30 MATLAB logical . . . transformace čísla na logický typ: a = 0 logical(a)=true (platí), logical(0)=false (neplatí) mod . . . operace modulo: mod(n,N) = n N . i,j . . . imaginární jednotka. Logické operátory: A (negace A), A & B (konjunkce), A | B (dis- junkce), xor(A,B). . . buď a nebo. Ostatní logické operátory se z nich složí pomocí ekvivalentních logických formulí (viz 1.1). Zápisy množin: například {a1,a2,a3} nebo [a1,a2,a3] . . . řádková verze. Jako od- dělovač lze užít i středník (sloupcová verze). Množinové operace: ismember(A,B) . . . testuje příslušnost prvků z A v B unique(A) . . . odstraní z A duplicitní prvky union(A,B) . . . sjednocení množin A a B intersect(A,B) . . . průnik množin A a B setdiff(A,B) . . . rozdíl množin A a B setxor(A,B) . . . symetrická diference množin A a B Ostatní operace lze vytvořit (simulovat) pomocí vhodných složených výrazů. 31 2. Algebraické struktury Teorie a příklady: [KaSk: s.26-36,44-53] Příklady: [Ho:řešené č.5,6,11-15; s.8,9,13-16], [Ho:neřešené kap.1,§4-7,kap.2 s.47-80] MOTIVACE V reálném světě se objekty zařazované do množin často vyznačují specifickými vlastnostmi: můžeme je dávat do nejrůznějších souvis- lostí (relací) ­ např. je porovnávat, vybírat mezi nimi jisté význačné prvky se specifickou rolí, provádět různé operace, měřit velikost či vzdálenost, nebo u některých podmnožin jejich délku, plochu, objem, hmotnost apod. Nejnázornějším motivačním příkladem může sloužit v tomto směru množina reálných čísel R. Její prvky lze porovnávat (relace uspořá- dání), sečítat či násobit, roli význačných prvků hraje 0 a 1, velikost a vzdálenost měříme absolutní hodnotou, intervaly jsou specifické pod- množiny, jimž lze přiřadit délku apod. Algebraické struktury představují abstraktní konstrukci umožňující přenášet vybrané strukturní vlastnosti reálné přímky i na množiny sice s jinými prvky ale podobného charakteru. Nepřeneseme-li vlast- nosti všechny, ale jen některé, část strukturních rysů reálné přímky ztratíme, některé však zůstanou zachovány. Cílem této (ale i následu- jící) kapitoly je podat přehled nejčastěji používaných matematických struktur a jejich základních vlastností. DEFINICE 2.1. V širším smyslu (algebraickou) strukturou ro- zumíme uspořádanou dvojici (N, S), kde N = je samotná množina, tzv. nosič algebraické struktury, a S systém množin popisující její strukturu (množina relací, operací, význačných prvků, specific- kých podmnožin apod.). Jestliže například S = {+, , 1}, píšeme také (N, +, , 1) místo (N, {+, , 1}). 32 DEFINICE 2.2. Jsou-li (N1, S1) a (N2, S2) dvě algebraické struk- tury téhož typu1 a f : N1 N2 zobrazení přenášející konzistentně1 strukturu S1 do S2, pak říkáme, že zobrazení f zachovává struk- turu na (N1, S1) a f nazýváme homomorfizmem (N1, S1) do (N2, S2); píšeme f : (N1, S1) (N2, S2). Homomorfizmus (N, S) do (N, S) se nazývá endomorfizmus struktury (N, S). Bijektivní homomorfi- zmus se nazývá izomorfizmus, jestliže f-1 : (N2, S2) (N1, S1) je rovněž homomorfizmem. V takovém případě píšeme (N1, S1)( N2, S2). 2.1. RELACE A OPERACE. DEFINICE 2.3. Buďte M1, M2, . . . , Mn, n N, neprázdné mno- žiny, pak každou podmnožinu M1 × M2 × × Mn nazýváme n-ární relací mezi množinami M1, M2, . . . , Mn (pro n = 1 unární, pro n = 2 binární, pro n = 3 ternární atd.). Je-li M1 = M2 = . . . Mn =: M, pak Mn nazýváme n-ární relací na množině M. Řekneme pak, že (M, ) je množina s relací. V případě binární relace se obvykle místo [x, y] píše x y a říká se, že prvek x je v relaci s prvkem y. Podobně píšeme x y nebo x non y, jestliže tomu tak není. DEFINICE 2.4. Buďte M a M1, M2, . . . , Mn, n {0} N, ne- prázdné množiny, pak zobrazení f : M1 × M2 × × Mn M nazýváme funkcí n proměnných na M1 × M2 × × Mn. Je-li M1 = M2 = . . . Mn =: M, pak f : Mn M nazýváme n-ární operací na množině M (pro n = 0 nulární, pro n = 1 unární, pro n = 2 binární, pro n = 3 ternární atd.). Řekneme pak, že (M, f) je množina s operací. Píšeme obvykle místo f([x1, . . . , xn]) zjed- nodušeně f(x1, . . . , xn). V případě binární operace se obvykle místo y = f(x1, x2) píše y = x f y, pokud f reprezentuje vhodný operátor (např. + pro operaci sečítání). 1Přesný význam určuje každá konkrétní struktura -- viz dále 33 Poznámka 2.5. Někdy také relaci ztotožňujeme s její charakteristic- kou funkcí (viz 1.5) a v souladu s 2.4 píšeme (x1, x2, . . . , xn) = 1, resp. (x1, x2, . . . , xn) = 0, jestliže prvky xi Mi (i = 1, 2, . . . , n) jsou, resp. nejsou v relaci . Každá unární relace na M koresponduje s nějakou podmnožinou v M. Relační struktury představují základní aparát konstrukce tzv. relač- ních databázových systémů, kde jsou dle potřeby do vzájemného vztahu dávány informace uložené v databázi. Poznámka 2.6. (1) Pro danou funkci n proměnných můžeme zavést (n + 1)-ární relaci f M1 × × Mn × M takto: f (x1, . . . , xn, y) = 1 právě když y = f(x1, . . . , xn). Zřejmě f pak můžeme pova- žovat za graf funkce f. Obvykle však neděláme rozdíl mezi funkcí a jejím grafem. Z definice zobrazení naopak plyne, že daná (n+1)-ární relace M1 × × Mn × M může být grafem nejaké funkce n proměnných M1 × M2 × × Mn do M právě když má tuto vlastnost: pro každou uspořádanou n-tici x1 M1, . . . , xn Mn exis- tuje jediné y M : (x1, . . . , xn, y) = 1. Funkční hodnotou je pak právě tento prvek y. (2) Zvláštní roli hraje nulární operace na M. Podle 1.36(4) ji totiž můžeme považovat za zobrazení M M, tj. za zobra- zení, které prázdnému zobrazení přiřazuje nějaký význačný prvek z M. Opět nerozlišujeme mezi význačným prvkem a nulární operací, která jej vybrala: strukturu s jedním význač- ným prvkem pak zapisujeme například takto: (R, 1). Pokud nebude řečeno jinak, budeme nadále ve zbytku této kapitoly uvažovat algebraické struktury (M, S), kde S obsahuje pouze relace a operace. 34 DEFINICE 2.7. Binární relace na M se nazývá: a) reflexivní, když a a pro každé a M; b) areflexivní, když a a pro každé a M; c) symetrická, když a b b a pro libovolné a, b M; d) asymetrická, když a b b a pro libovolné a, b M; e) antisymetrická, když a b, b a a = b pro libovolné a, b M; f) tranzitivní, když a b, b c a c pro libovolné a, b, c M; g) atranzitivní a b, b c a c pro libovolné a, b, c M; h) antitranzitivní, když a b, b c, a c (a = b) (b = c) (a = c) pro libovolné a, b, c M; i) úplná, když pro každé a, b M platí a b nebo b a. DEFINICE 2.8. Binární operace na M se nazývá: a) asociativní, když a (b c) = (a b) c pro libovolné a, b, c M; b) komutativní, když a b = b a pro libovolné a, b M; Význačný prvek e M se nazývá neutrálním prvkem binární operace , jestliže a e = e a = a pro každé a M; Definice 2.9. Řekneme, že dvě algebraické struktury (M1, S1) a (M2, S2) jsou té- hož typu, jestliže existuje bijekce S1 na S2 přiřazující každé relaci (operaci) z S1 odpovídající relaci (operaci) v S2 téže arity. Definice 2.10. Pro dvě algebraické struktury (M1, S1) a (M2, S2) téhož typu považujeme ve smyslu definice 2.2 za homomorfizmus (M1, S1) do (M2, S2) každé zobrazení f : M1 M2 s těmito vlast- nostmi: (1) pro každou relaci 1 S1 a odpovídající relaci 2 S2 téže arity n platí: 1(x1, . . . , xn) = 1 2(f(x1), . . . , f(xn)) = 1; (2) pro každou operaci 1 S1 a odpovídající operaci 2 S2 téže arity n platí: f(1(x1, . . . , xn)) = 2(f(x1), . . . , f(xn)). 35 Zejména f zobrazí každý význačný prvek v (M1, S1) na odpovídající význačný prvek v (M2, S2). Zřejmě složení dvou homomorfizmů je opět homomorfizmus (viz též dále konec poznámky 2.61). Definice 2.11 (Přímý součin algebraických struktur). Nechť {(Mi, Si)}iI je systém algebraických struktur téhož typu: Si = {ij}jJ , kde ij je pro každé i I buď operace nebo re- lace téže arity nj. Algebraickou strukturu (M, S) nazveme přímým součinem algebraických struktur (Mi, Si), jestliže M = X iI Mi, kde S := {j}jJ obsahuje relace (operace) definované po složkách: nechť , k M pro k = 1, . . . , nj a j J, pak (1) jsou-li ij relace pro každé i I, definujeme j-tou relaci takto: j(1, . . . , nj ) = 1 právě když ij(1(i), . . . , nj (i)) = 1 pro všechna i I; (2) jsou-li ij operace pro každé i I, definujeme j-tou operaci takto: j(1, . . . , nj )(i) := ij(1(i), . . . , nj (i)) pro každé i I. Značíme také S =: X iI Si, případně (M, S) =: X iI (Mi, Si). Je-li I konečná, například I = {1, 2, . . . , q}, pak také explicitně: S =: S1 ×S2 × ×Sq a (M, S) =: (M1, S1)×(M2, S2)× ×(Mq, Sq). Definice 2.12 (Algebraické podstruktury). Nechť (M, S) a (M , S ) jsou algebraické struktury téhož typu: S = {j}jJ a S = {j }jJ , kde j a j jsou pro každé j J buď operacemi nebo relacemi téže arity nj. Řekneme, že (M , S ) je al- gebraickou podstrukturou algebraické struktury (M, S), jestliže M M a pro každé j J a x1, . . . , xnj M p latí: (1) jsou-li j a j relace, pak j (x1, . . . , xnj ) = 1 právě když j(x1, . . . , xnj ) = 1, neboli j = M nj j; (2) jsou-li j a j operace, pak x := j(x1, . . . , xnj ) M a j (x1, . . . , xnj ) = x. 36 Říkáme také, že podmnožina M M je uzavřená vzhledem ke struktuře S a píšeme (M , S ) (M, S) nebo jen M M. Zejména M m usí obsahovat všechny význačné prvky z M. Definice 2.13 (Generátory). Nechť (M, S) je algebraická struktura a G M nějaká její podmno- žina. Jestliže existuje nejmenší2 podmnožina M M obsahující G (tj. G M ) taková, že (M , S) je podstrukturou v (M, S), pak G nazýváme množinou generátorů struktury (M , S) nebo také ří- káme, že struktura (M , S) je generována svou podmnožinou G a píšeme M = S(G) (zde S vystupuje spíše v roli symbolu pro struktury téhož typu). Příklad 2.14. (N, +) je algebraická podstruktura v (Z, +) genero- vaná jednoprvkovou podmnožinou G = {1} Z. Poznámka 2.15. Binární relace či operace na konečných množinách nevelkého rozsahu lze zadat tabulkou (viz [KaSk:obr.8,15 s.26,45]). Binární relace je také možno znázornit graficky ([KaSk:obr.9 s.27]). V dalších odstavcích této kapitoly se již zaměříme na speciální případy jednoduchých struktur, které spolu s příklady budou dobře ilustrovat obecnou koncepci, kterou jsme zavedli v tomto odstavci. 2.2. USPOŘÁDANÉ MNOŽINY. DEFINICE 2.16. Binární relace na M se nazývá (částečné) uspořádání, je-li reflexivní, antisymetrická a tranzitivní. Nazývá se úplné uspořádání nebo také lineární uspořádání, je-li navíc úplná. Algebraická struktura (M, ) se pak nazývá (částečně, příp. line- árně) uspořádaná množina. Relace uspořádání se obvykle značí symbolem nebo a pod. Píšeme pak (M, ) nebo (M, ) a pod. 2(M , S) (M, S), G M (M , S) (M , S) . . . viz dále 2.20 37 PŘÍKLAD 2.17. Lineárně uspořádané množiny: (N, ), (Z, ), (Q, ) a (R, ) s obvyklým uspořádáním. Částečně uspořádané množiny, které nejsou lineárně uspořádány: (N, |), kde n|m značí, že n je dělitelem m; (P(M), ); Poznámka 2.18. Uspořádané množiny lze graficky znázornit pomocí tzv. Hasseova diagramu (viz [KaSk:obr.11,12 s.28-29]). VĚTA 2.19. [TM1:V1.2.1 s.9] Nechť je uspořádání na M. Definujme na M relaci < takto: a < b (a b) (a = b). Pak < je relace areflexivní a tranzitivní. Naopak, je-li < areflexivní a tranzitivní relace na M a definujeme-li a b (a < b) (a = b), pak je uspořádání na M. DEFINICE 2.20. Buď (M, ) uspořádaná množina. Prvek a M se nazývá nejmenší, resp. největší prvek v M, platí-li x a, resp. x a pro každé x M. Prvek a M se nazývá minimální, resp. maximální prvek v M, jestliže pro žádné x M neplatí x < a, resp. x > a. Definice 2.21. Nechť (M, ) je uspořádaná množina. Pro prvky a, b M řekneme, že b pokrývá a, jestliže a < b a neexistuje c M tak, že a < c < b. Věta 2.22. [TM1: s.9] Nechť (M, ) je konečná uspořádaná množina. Pak platí a < b existuje konečný počet prvků a = t0 < t1 < < tn = b tak, že ti pokrývá ti-1 pro každé i = 1, . . . , n. VĚTA 2.23. [KaSk:V3.1 s.28] (1) Libovolná uspořádaná množina má nejvýše jeden nejmenší a nejvýše jeden největší prvek. (2) Má-li uspořádaná množina nejmenší, resp. největší prvek, pak tento prvek je zároveň jejím jediným minimálním, resp. ma- ximálním prvkem. 38 (3) V úplně uspořádané množině existuje nejvýše jeden mini- mální, resp. maximální prvek, který je zároveň jejím nejmen- ším, resp. největším prvkem. (4) Každá konečná uspořádaná množina má alespoň jeden mini- mální a alespoň jeden maximální prvek. DEFINICE 2.24. Buď (M, ) uspořádaná množina a N M. Pr- vek a M se nazývá dolní, resp. horní závora (hranice) pod- množiny N (v M), platí-li x a, resp. x a pro každé x N. DEFINICE 2.25. Buď (M, ) uspořádaná množina a N M. Prvek a M se nazývá největší dolní závora, resp. nejmenší horní závora neboli infimum, resp. supremum množiny N (v M), platí-li: (1) a je dolní, resp. horní závora N, (2) pro každou dolní, resp. horní závoru t množiny N platí t a, resp. t a. Pak píšeme a = inf N, resp. a = sup M. DEFINICE 2.26 (srov. s 1.27 a s 1.28). Buď (M, ) uspořádaná množina a N := {an} n=1 posloupnost je- jích prvků. Pokud existuje b- k := inf{an} n=k pro každé k N i a- := supkN b- k , pak a- nazýváme limes inferior posloupnosti {an} a píšeme a- = lim inf an. Analogicky duálně: pokud existuje b+ k := sup{an} n=k pro každé k N i a+ := infkN b+ k , pak a+ nazýváme limes superior posloupnosti {an} a píšeme a+ = lim sup an. Pokud existuje a- i a+ , pak platí lim inf an lim sup an (CVIČENÍ). Platí-li rovnost, pak jejich spo- lečnou hodnotu a := a- = a+ nazýváme limitou posloupnosti {an}nN a píšeme a = lim an. Říkáme také, že posloupnost {an} n=1 konverguje k a. VĚTA 2.27. (1) Je-li posloupnost neklesající, a1 a2 a3 . . . , a existuje a := sup an, pak lim an = a a píšeme také an a. 39 (2) je-li posloupnost nerostoucí, a1 a2 a3 . . . , a existuje a := inf an, pak lim an = a a píšeme také an a. DEFINICE 2.28 (viz 2.2). Buďte (M, ) a (N, ) uspořádané množiny. Zobrazení f : M N se nazývá homomorfizmus nebo také monotonní zobrazení, jestliže pro libovolné prvky x, y M, x y, platí f(x) f(y). V souladu s 2.2 píšeme f : (M, ) (N, ). Zobrazení f se nazývá izomorfis- mus, jestliže navíc rovněž f-1 : N M je homomorfizmem, neboli pro libovolné prvky x, y M platí x y f(x) f(y). Věta 2.29 ([TM1:V1.2.4 s.10]). Buďte (M, ) a (N, ) uspořádané množiny a f : (M, ) (N, ) izomorfizmus. Nechť P M je nějaká podmnožina. Pak inf P, resp. sup P existuje v M právě když existuje inf f(P), resp. sup f(P) v N. V takovém případě platí f(inf P) = inf f(P), resp. f(sup P) = sup f(P). Důsledek 2.30. Nechť v předchozí větě P = {an} n=1 je posloup- nost. Pak lim inf an, resp. lim sup an existuje v M právě když exis- tuje lim inf f(an), resp. lim sup f(an) v N. V takovém případě platí f(lim inf an) = lim inf f(an), resp. f(lim sup an) = lim sup f(an). VĚTA 2.31 (Přímý součin uspořádaných množin ­ viz 2.11(1)). Nechť (M, ) a (N, ) jsou dvě uspořádané množiny a (M × N, ) jejich přímý součin. Buďte [m1, n1], [m2, n2] M × N dva prvky, pak [m1, n1] [m2, n2] (m1 m2) (n1 n2). Analogicky (po složkách) uspořádáme prvky přímého součinu konečně mnoha uspořá- daných množin či libovolného systému takových množin. 2.3. EKVIVALENCE A KONGRUENCE. DEFINICE 2.32. Binární relace na množině M se nazývá ekvivalencí na této mno- žině, jestliže je reflexivní, symetrická a tranzitivní. Obvykle se značí symboly , nebo a pod. Píšeme pak (M, ),(M, ) nebo (M, ) a 40 pod. Množinu všech ekvivalencí na M budeme dále značit E(M). Tato množina je uspořádána inkluzí neboli pro ekvivalence , E(M) je [xy xy]. DEFINICE 2.33. Buď M neprázdná množina. Rozkladem M na množině M rozu- míme neprázdný systém po dvou disjunktních neprázdných podmno- žin M := {Mi}iI množiny M, jejichž sjednocením je celá množina M. Prvky M se nazývají třídy tohoto rozkladu. Vybereme-li z každé třídy Mi nějaký prvek mi, pak mi se nazývá reprezentan- tem třídy Mi a množina všech reprezentantů {mi | i I} se nazývá systém reprezentantů rozkladu M. Přiřadíme-li každému prvku m M (jednoznačně určenou) třídu rozkladu m, do níž m patří, pak toto zobrazení (pruh nahoře) je surjekcí M na M a nazývá se kanonickým zobrazením rozkladu M. Jeho restrikce na systém reprezenantů je pak bijekce na M. VĚTA 2.34 ([KaSk:V3.2 s.31]). Buď M rozklad na množině M. Definujme relaci na M takto: xy existuje třída m M tak, že x m, y m. Pak je ekvivalence na M. VĚTA 2.35 ([KaSk:V3.3 s.31]). Buď ekvivalence na množině M. Pak existuje jediný rozklad Mna M takový, že pro x, y M platí xy existuje třída m M tak, že x m, y m. DEFINICE 2.36. Rozklad M příslušný k ekvivalenci na M po- psaný v předchozí větě značíme M =: M/. Označme R(M) množinu všech rozkladů na množině M. Definice 2.37. Buďte M, M R(M). Pravíme, že M je jemnější než M, neboli M je hrubší než M, když ke každé třídě m M existuje třída m M tak, že m m. Píšeme M M. Snadno nahlédneme, že je uspořádání na R(M). 41 Věta 2.38. Buď M neprázdná množina a pro libovolné E(M) položme f() := M/. Pak f je izomorfismus (E(M), ) na (R(M), ). VĚTA 2.39. Nechť M, N jsou neprázdné množiny a f : M N zob- razení. Definujme na M relaci f takto: x f y f(x) = f(y). Pak f je ekvivalence na M a třídy rozkladu M/ f jsou právě úplné vzory všech prvků z f(M), tj. M/ f = {f-1 ({n}) | n f(M)}. Zejména dostáváme bijekci (jednojednoznačnou korespondenci) mezi třídami rozkladu, jejich reprezentanty a obrazem f(M) množiny M v N. DEFINICE 2.40. Rozklad M/ f z předchozí věty se nazývá kano- nický rozklad příslušný k zobrazení f. Důsledek 2.41. Nechť M, N, P jsou neprázdné množiny a f : M N a g : N P dvě zobrazení. Označíme-li gf : M P složené zobrazení, pak f gf a tedy kanonický rozklad příslušný k f je vždy jemnější než kanonický rozklad příslušný ke složenému zobrazení gf. DEFINICE 2.42. Buď dána algebraická struktura (M, S) a nějaká ekvivalence na M. Řekneme, že je kongruencí na struktuře (M, S), jestliže pro každou n-ární operaci na M, S, platí: (1) a1 b1, . . . , an bn (a1, . . . , an) (b1, . . . , bn). Na M := M/ lze pak zavést strukturu S stejného typu jako S takto: (i) pro každou relaci S n-ární definujeme S téže arity: (a1, . . . , an) := 1 právě když pro nějaký výběr reprezentantů a1, . . . , an je (a1, . . . , an) = 1; (ii) pro každou operaci S n-ární definujeme S téže arity takto: a) n = 0: význačným prvkem je třída obsahující vý- značný prvek , b) n > 0: (a1, . . . , an) := (a1, . . . , an) pro nějaký výběr reprezentantů a1, . . . , an (dle (1) na výběru nezáleží). 42 Strukturu (M, S) pak značíme (M, S)/ a nazýváme ji faktorovou (podílovou) strukturou struktury (M, S) vzhledem ke kon- gruenci . VĚTA 2.43. Buď dána algebraická struktura (M, S) a nějaká kon- gruence na M. Pak příslušné kanonické zobrazení je homomorfi- zmus (M, S) na (M, S). Je-li naopak f : (M, S) (N, S ) nějaký homomorfizmus, pak f v příslušném kanonickém rozkladu M := M/ f je kongruence na (M, S). Přitom (f(M), S ) je podstruktura v (N, S ) izomorfní s (M, S). 2.4. STRUKTURY S JEDNOU BINÁRNÍ OPERACÍ. DEFINICE 2.44. Algebraická struktura (M, ) s jednou binární operací se nazývá grupoid. Grupoid (M, ), v němž platí aso- ciativní zákon se nazývá pologrupa. Každá pologrupa, v níž exis- tuje neutrální prvek e se nazývá monoid -- píšeme (M, , e). Je-li operace multiplikativního typu (například , ), pak hovoříme o multiplikativním grupoidu (pologrupě, monoidu). Je-li aditiv- ního typu (například +, -), hovoříme o aditivním grupoidu (po- logrupě, monoidu). Neutrální prvek e multiplikativního, resp. adi- tivního grupoidu se obvykle nazývá jeho jednotkovým, resp. nu- lovým prvkem a místo e se značí 1, resp. 0. Grupoid (pologrupa, monoid) se nazývá komutativní, jestliže operace je komutativní. PŘÍKLAD 2.45. Nechť S je množina nějakých symbolů, například 26 malých písmen abecedy spolu se znakem nahrazujícím mezeru: S = {a, b, . . . , z, }. Označme S množinu všech konečných řetězců (posloupností) znaků z S včetně prázdného řetězce, tj. S = { s 1s2 . . . sn | si S pro i = 1, . . . , n; n N} { } . Nechť (S , , ) je algebraická struktura, kde je operace skládání řetězců (konkatenace), tj. například definu- jeme 'auto ''jede':='auto jede'. Pak (S , , ) je zřejmě nekomuta- tivní monoid, jehož neutrálním prvkem je prázdný řetězec . 43 VĚTA 2.46 (Obecný asoc. zákon [AG1: s.12],[KaSk:V5.1 s.46]). Nechť (M, ) je pologrupa a a1, a2, . . . , an M. Potom všechny možné součiny vytvořené všemi možnými uzávorkováními posloupnosti {ai}n i=1 jsou rovny jednomu a témuž prvku. VĚTA 2.47 ([AG1: s.12]). Každý grupoid má nejvýše jeden neutrální prvek. DEFINICE 2.48. Nechť (M, ) je grupoid s neutrálním prvkem e. Nechť dále a M a nechť pro jisté b M platí a b = b a = e. Potom b se nazývá inverzní prvek k a a značí se a-1 . V aditivním grupoidu se obvykle nazývá prvkem opačným k a a značí se -a. DEFINICE 2.49. Nechť grupoid (M, ) má tyto vlastnosti: (1) Operace je asociativní (neboli (M, ) je pologrupa). (2) Existuje jednotkový prvek e (neboli (M, ) je dokonce mo- noid). (3) Ke každému prvku a M existuje inverzní prvek a-1 . Potom algebraická struktura (M, , e)3 se nazývá grupa: multiplika- tivní, resp. aditivní dle typu operace. Je-li operace navíc komuta- tivní, pak grupa (M, , e) se nazývá komutativní grupa nebo také abelovská grupa. VĚTA 2.50 ([AG1: s.12],[KaSk:V5.11 s.50]). Nechť (M, , e) je grupa. Potom pro každé a je a-1 určeno jedno- značně, tj. každý prvek má právě jeden inverzní prvek. PŘÍKLAD 2.51. a) Množina komplexních čísel C s obvyklými operacemi +, , - tvoří grupoidy (C, +), (C, ), (C, -). Obvyklé dělení / na mno- žině C není operace, neboť není definován např. prvek 2/0. Dělení / je ale operace na množině C všech nenulových kom- plexních čísel. (C , /) je tedy nekomutativní grupoid. Navíc 3Přesněji bychom měli psát (M, , -1 , e), neboť grupa je strukturou s jednou binární operací , jednou unární operací -1 a jedním neutrálním prvkem e. 44 (C, +, 0) je abelovská grupa, zatímco (C, , 1) je jen komuta- tivním monoidem a (C, -, 0) pouze nekomutativním grupoi- dem, neboť odečítání není ani asociativní ani komutativní. Nenulová čísla (C , , 1) však již tvoří abelovskou grupu vzhle- dem k násobení, ne tak (C , /, 1) vzhledem k dělení přestože každý prvek má inverzní (jelikož a/a = 1, je dokonce každý prvek inverzní sám k sobě). Dělení totiž není podobně jako odečítání ani asociativní ani komutativní operací. b) Analogicky jako v a) nechť +, , - mají obvyklý význam. Pak (R, +), (R, ), (R, -), (Q, +), (Q, ), (Q, -), (Z, +), (Z, ), (Z, -), jsou grupoidy s obdobnými vlastnostmi jako v a). Je-li / obvyklé dělení na množinách R = R - {0}, Q = Q - {0}, jsou (R , /), (Q , /) grupoidy. Naproti tomu / není operace na množině celých nenulových čísel, neboť např. 2/3 není celé nenulové číslo. Podobně také (ZN , , 0) je abelovská grupa, (ZN , , 1) je ko- mutativní monoid a (ZN , , 0) nekomutativní grupoid s ope- racemi sečítání , odečítání a násobení modulo N (viz 1.3). c) Operace + a jsou také operace na množině N, tedy (N, +), (N, ) jsou komutativní grupoidy. Naproti tomu - a / nejsou operace na N. d) Je-li X libovolná množina, pak průnik množin , sjednocení množin , rozdíl množin (-) a symetrická diference množin (÷) jsou operace na množině všech podmnožin 2X . Jsou tedy: (2X , ), (2X , ), (2X , -) a (2X , ÷) grupoidy. Navíc (2X , ÷, ) je abelovská grupa dle věty 1.26, kde každý prvek je opačný sám k sobě, (2X , , ) i (2X , , X) jsou pouze komutativní monoidy, zatímco (2X , -) pouze nekomutativní grupoid, ne- boť rozdíl množin není ani komutativní ani asociativní. Na- proti tomu kartézský součin × není obecně operace na mno- žině 2X . 45 e) Nechť X je libovolná neprázdná množina. Symbol XX ozna- čuje systém všech zobrazení množiny X do X. Pro f XX , g XX je složené zobrazení g f opět prvkem množiny XX . Tedy je operace na množině XX a (XX , ) je (obecně ne- komutativní) pologrupa. Označíme-li IX : X X identické zobrazení (IX (x) = x pro každé x X), pak (XX , , IX ) je dokonce monoid. Prvek f XX má inverzní prvek v mono- idu (XX , , I) právě když f je bijekce. Inverzní prvek k f je pak roven inverznímu zobrazení f-1 k zobrazení f. VĚTA 2.52 ([KaSk:V5.8 s.48]). Nechť (M, , e) je monoid. Nechť a, a1, a2, . . . , an M mají inverzní prvky v (M, ). Pak platí: (a) e-1 = e, (b) (a-1 )-1 = a, (c) (a1 a2 . . . an)-1 = a-1 n a-1 n-1 . . . a-1 1 , (d) pro b M jsou prvky x = a-1 b, y = b a-1 jediná řešení rovnic a x = b, y a = b v grupoidu (M, ). Definice 2.53. Nechť (M, ) je grupoid. Jestliže pro každou dvo- jici prvků a, b M existuje jediný prvek x tak, že a x = b, pak říkáme, že v grupoidu platí levý zákon o jednoznačném dělení (resp. odečítání v aditivním případě). Jestliže pro každou dvojici prvků a, b M existuje jediný prvek y tak, že y a = b, pak říkáme, že v grupoidu platí pravý zákon o jednoznačném dělení (resp. odečítání v aditivním případě). Věta 2.54 ([AG1: s.13-14]). Pologrupa (M, ) je grupou právě když v ní platí levý i pravý zákon o jednoznačném dělení. DEFINICE 2.55. Nechť (M, ) je grupoid. Jestliže pro každou tro- jici prvků a, x, y M platí implikace a x = a y x = y, pak říkáme, že v grupoidu platí levý zákon o krácení (resp. rušení v aditivním případě). Jestliže obdobně x a = y a x = y, pak říkáme, že v grupoidu platí pravý zákon o krácení (resp. rušení 46 v aditivním případě). Říkáme take, že v (M, ) lze krátit zleva, pří- padně zprava. VĚTA 2.56 ([KaSk:V5.13 s.51]). V každé grupě lze krátit zleva i zprava. Označení . Nechť (G, ) je pologrupa a nechť a G. Pro přirozené číslo n položíme: an := a a . . . an prvků a . Má-li grupoid (G, ) jedničku e, položíme: a0 := e. Nechť (G, ) má jedničku a prvek a nechť má inverzní prvek a-1 v grupoidu (G, ). Pak položíme: a-n := (a-1 )n := a-1 a-1 . . . a-1 n prvků a-1 . Pro takto zavedené umocňování platí známá pravidla: am an = am+n a (am )n = amn (viz [KaSk:V5.9 s.49]). V aditivním grupoidu a - b := a + (-b) a dále píšeme na místo an a -na místo a-n , takže výše uvedená pravidla pak přepíšeme takto: ma + na = (m + n)a a n(ma) = (nm)a = (mn)a. DEFINICE 2.57. Algebraickou podstrukturu grupoidu (pologrupy, monoidu, grupy) nazýváme jeho/jejím podgrupoidem (podpolo- grupou, podmonoidem, podgrupou). POZNÁMKA 2.58. Nechť (M, ) je grupoid a N M, N = . Uvažme následující vlastnosti podmnožiny N: (1) x, y N x y N (uzavřenost k binární operaci ); (2) je-li e neutrální prvek v (M, ), pak e N (uzavřenost k nulární operaci vybírající neutrální prvek); (3) je-li x N a x-1 k němu inverzní prvek v (M, ), pak x-1 N (uzavřenost k unární operaci -1 ). 47 Podle definice 2.12 je tedy a) (N, ) podgrupoidem (podpologrupou) grupoidu (pologrupy) (M, ) právě když má vlastnost (1); b) (N, , e) je podmonoidem monoidu (M, , e) právě když má vlastnosti (1) a (2); c) (N, , e) je podgrupou grupy (M, , e) právě když má vlast- nosti (1) a (3) [pak má zřejmě i vlastnost (2)]. Každý monoid (každá grupa) (M, , e) má alespoň dva podmonoidy (dvě podgrupy): (M, , e) a triviální podmonoid (podgrupu) ({e}, , e). Věta 2.59 ([AG1: s.15]). Nechť (M, , e) je grupa a N M, N = . Pak následující výroky jsou ekvivalentní: (1) (N, , e) je podgrupa v (M, , e), (2) x, y N x y-1 N, (3) x, y N x-1 y N. PŘÍKLAD 2.60. Podpologrupy: ˇ (N, +) (Z, +), ˇ množina všech bijekcí X X z příkladu 2.51e) je grupou, která je podmonoidem v (XX , , IX ). Podgrupy: ˇ (Z, +, 0) (Q, +, 0) (R, +, 0) (C, +, 0); ˇ (R+ - {0}, , 1) (R , , 1) . . . viz příklad 2.51b); ˇ Naopak (ZN , ) není ani podgrupoid v (Z, +). POZNÁMKA 2.61. Nechť (M, ) a (N, ) jsou grupoidy a f : M N zobrazení. Uvažme následující vlastnosti zobrazení f: (1) x, y M f(x y) = f(x) f(y); (2) jsou-li e, E neutrální prvky po řadě v (M, ) a (N, ), pak f(e) = E; (3) je-li a M a a-1 k němu inverzní prvek v (M, ), pak f(a-1 ) je inverzní k f(a) v (N, ), neboli f(a-1 ) = f(a)-1 . 48 Podle definice 2.10 tedy platí: a) f : (M, ) (N, ) je homomorfizmus grupoidů právě když má vlastnost (1); b) f : (M, , e) (N, , E) je homomorfizmus monoidů právě když má vlastnost (1) a (2); c) f : (M, , e) (N, , E) je grupový homomorfizmus právě když má vlastnosti (1) a (3) [pak má zřejmě i vlastnost (2)] nebo vlastnosti (1) a (2) [pak má zřejmě i vlastnost (3) uvá- žíme-li větu 2.50]; Kterýkoli z výše uvedených homomorfizmů je izomorfizmem právě když f je bijekce. Snadno se totiž ověří, že f-1 : N M je rovněž homomorfizmus z (N, ) do (M, ): f-1 (E) = f-1 (f(e)) = e, f-1 (f(a) f(b)) = f-1 (f(a b)) = a b = f-1 (f(a)) f-1 (f(b)). Tento homomorfizmus je ovšem také izomorfizmem. Poznamenejme, že obdobnou vlastnost mají nejen struktury s jednou binární operací, ale každá struktura obsahující pouze operace a žádnou relaci: každý bijektivní homomorfizmus je pak také automaticky izomorfizmem. PŘÍKLAD 2.62. (1) Nechť (S , , ) je monoid z příkladu 2.45 a d : S Z zob- razení přiřazující každému řetězci jeho délku. Pak d je homo- morfizmus nekomutativního monoidu (S , , ) do abelovské grupy (Z, +, 0). (2) Zobrazení modulo f:= N z odst. 1.3 je grupovým homomor- fizmem (Z, +, 0) na (ZN , , 0). Pak f je grupovou kongruencí příslušného kanonického rozkladu (věta 2.43) a platí: a f b právě když N je dělitelem b - a. 49 2.5. STRUKTURY SE DVĚMA BINÁRNÍMI OPERACEMI. Tyto struktury již zachycují všechny podstatné vlastnosti běžných číselných oborů. DEFINICE 2.63. Algebraická struktura (M, +, , 0) s dvěma binár- ními operacemi + (aditivní) a (multiplikativní) se nazývá okruh, jestliže jsou splněny následující podmínky: (1) (M, +, 0) je abelovská grupa; (2) (M, ) je pologrupa; (3) Pro libovolnou trojici prvků a, b, c M platí distributivní zákony: (a + b) c = a c + b c c (a + b) = c a + c b. Okruh (M, +, , 0) se nazývá okruhem s jednotkou, jestliže exis- tuje neutrální prvek 1 M takový, že (M, , 1) je monoid. Pak píšeme (M, +, , 0, 1). Okruh (M, +, , 0) se nazývá komutativní, jestliže (M, ) je komuta- titvní pologrupa. DEFINICE 2.64. Algebraickou podstrukturu okruhu nazýváme jeho podokruhem. POZNÁMKA 2.65. Nechť (M, +, , 0) je okruh a N M, N = . Podle definice 2.12 a s uvážením poznámky 2.58 tedy vidíme, že (N, +, , 0) je podokruhem v (M, +, , 0) právě když platí: (1) x, y N x + y N; (2) x, y N x y N; (3) je-li x N, pak -x N. (4) je-li 1 jednotka okruhu (M, +, , 0, 1), pak 1 N; Podle poznámky 2.58 je tedy (N, +, , 0) podokruhem okruhu (M, +, , 0, 1) právě když (N, +, 0) je podgrupou v (M, +, 0) a současně (N, ) je podpologrupou v (M, ), případně (N, , 1) je podmonoidem v (M, , 1). 50 VĚTA 2.66 ([AG1: s.16]). V každém okruhu (M, +, , 0) platí pro jeho libovolné prvky a, b, c M následující identity: (a - b) c = a c - b c c (a - b) = c a - c b a 0 = 0 a = 0. Definice 2.67. Nenulový prvek a okruhu (M, +, , 0) se nazývá dělitelem nuly to- hoto okruhu, když v M existuje b = 0 takové, že a b = 0 nebo b a = 0. Definice 2.68. Komutativní okruh s jednotkou, který nemá dělitele nuly se nazývá obor integrity. Věta 2.69 ([AG1: s.16]). V každém oboru integrity (M, +, , 0, 1) lze krátit (vzhledem ke komu- tativitě zleva i zprava) nenulovým prvkem: a, b, c M, a = 0, a b = a c b = c Důsledek 2.70. Je-li (M, +, , 0, 1) obor integrity, pak (M - {0}, ) je komutativní grupoid, v němž platí levý i pravý zákon o krácení. Definice 2.71 (Charakteristika oboru integrity). Nechť (M, +, , 0, 1) je obor integrity. Jestliže existuje přirozené číslo n tak, že n1 = 0, potom řekneme, že obor integrity (M, +, , 0, 1) má konečnou charakteristiku. Nejmenší přirozené číslo s touto vlast- ností se nazývá charakteristikou tohoto oboru integrity. V opačném případě říkáme, že obor integrity (M, +, , 0, 1) má ne- konečnou charakteristiku nebo též charakteristiku nula. Věta 2.72 ([AG1: s.17]). Nechť obor integrity (M, +, , 0, 1) má konečnou charakteristiku n, pak n je prvočíslo. 51 DEFINICE 2.73. Okruh s jednotkou (M, +, , 0, 1), v němž (M - {0}, , 1) je grupa se nazývá těleso. Je-li tato grupa komutativní, potom (M, +, , 0, 1) se nazývá komutativní těleso nebo také pole. Věta 2.74 ([AG1: s.17]). Pole je oborem integrity. Věta 2.75 ([AG1: s.17]). Každý konečný obor integrity je polem. Příklad 2.76 (viz 2.51). ˇ (N, +, , 0, 1) (Z, +, , 0, 1) (Q, +, , 0, 1) (R, +, , 0, 1) (C, +, , 0, 1) jsou do sebe vnořené obory integrity, z nichž poslední tři jsou dokonce pole nekonečné charakteristiky. ˇ (ZN , , , 0, 1) je komutativním okruhem s jednotkou, který není podokruhem žádného z výše uvedených okruhů. (ZN , , , 0, 1) je oborem integrity jen když N je prvočíslo. V takovém případě je do- konce polem dle věty 2.75. ˇ Množina všech polynomů s koeficienty například z C tvoří rovněž obor integrity vzhledem k obvyklému sečítání a násobení polynomů. ˇ (2X , ÷, , , X) je dle věty 1.26 komutativním okruhem s jednotkou X (totiž AX = A pro každou podmnožinu A X), který není obo- rem integrity, pokud X má více jak jeden prvek (pak totiž lze vždy najít dvě různé neprázdné podmnožiny s prázdným průnikem). POZNÁMKA 2.77. Nechť (M, +, , 0) a (N, , , 0) jsou okruhy (tělesa) a f : M N zobrazení. Uvážíme-li 2.61b)c), potom f je homomorfizmem těchto struktur ve smyslu 2.10 právě když jak f : (M, +, 0) (M, , 0) tak i f : (M, ) (N, ) jsou homomorfizmy, tj. právě když f má následující vlastnosti: (1) a, b M f(a + b) = f(a) f(b), (2) a, b M f(a b) = f(a) f(b), (3) f(0) = 0 a f(1) = 1, pokud oba okruhy mají jednotku. 52 Poznamenejme ještě, že ve (3) lze podmínku f(0) = 0 nahradit pod- mínkou a M f(-a) = -f(a), a v případě těles i podmínku f(1) = 1 podmínkou 0 = a M f(a-1 ) = f(a)-1 . PŘÍKLAD 2.78. Grupový homomorfizmus f:= N z příkladu 2.62(2) je i okruhovým homomorfizmem (Z, +, , 0, 1) na (ZN , , , 0, 1), při- čemž f je pak také okruhová kongruence. 53 ANGLICKÁ TERMINOLOGIE ALGEBRAICKÝCH STRUKTUR algebraická (pod)struktura algebraic (sub)structure homomorfizmus, endomorfizmus homomorphism, endomorphism izomorfizmus, relace, operace isomorphism, relation, operation nulární, unární, binární, n-ární nullary, unary, binary, n-ary význačný, neutrální singular, neutral reflexivní, symetrická, úplná reflexive, symmetric, complete antisymetrická, tranzitivní antisymmetric, transitive asociativní, komutativní associative, commutative generátor, generovaný podmnožinou generator, generated by a set přímý součin, uspořádaná množina direct product, ordered set částečně (lineárně) uspořádaná partially (linearly) ordered menší (větší) nebo roven než less (greater) than or equal to nejmenší (největší) least (greatest) minimální (maximální) minimal (maximal) dolní (horní) závora lower (upper) bound infimum (supremum) infimum (supremum) limes inferior (limes superior) inferior limit (superior limit) ekvivalence, kongruence equivalence, congruence rozklad na třídy, kanonický partition into classes, canonical faktorová struktura factor structure (pod)grupoid, (pod)pologrupa (sub)groupoid, (sub)semigroup (pod)monoid, pod(grupa) (sub)monoid, (sub)group abelovská grupa abelian group opačný (inverzní) prvek negated (inverse) element nulový (jednotkový) prvek zero, null (unit) element (levý, pravý) zákon o krácení (left, right) cancellation law zákon o jednoznačném dělení unique division law okruh, obor integrity ring, domain of integrity dělitel nuly, charakteristika divisor of zero, characteristic těleso, pole division ring, field 54 3. Lineární algebra Teorie a příklady: [KaSk: s.54-129], [Šik: s.1-131] Příklady: [Ho:řešené č.16-36; s.17-37], [Ho:neřešené kap.3-7 s.81-167] 3.1. VEKTOROVÉ PROSTORY. DEFINICE 3.1. Nechť (F, +, , 0, 1), 0 = 1 je pole (tzv. pole ska- lárů), jehož prvky budeme nazývat skaláry. Nechť (V, +, 0, SF) je algebraická struktura s jednou binární operací +, nulovým prvkem 0 a zobrazením SF : F×V V určujícím pro každý skalár F jednu unární operaci {} × V V zapisovanou ve tvaru SF(, x) =: x a nazývanou násobení skalárem. Nechť (V, +, 0) je abelovská grupa a pro každé , F a x, y V nechť platí: (L1) Distributivní zákon vzhledem k sečítání vektorů: (x + y) = x + y (L2) Distributivní zákon vzhledem k sečítání skalárů: ( + )x = x + x (L3) Asociativní zákon vzhledem k násobení skaláry: (x) = ()x (L4) 1x = x. Pak algebraická struktura (V, +, 0, SF) se nazývá vektorový (line- ární) prostor nad polem F, prvky množiny V se nazývají vektory a operace x x se nazývá násobení vektoru x skalárem . Vek- torový prostor se nazývá reálný (resp. komplexní), jestliže F = R (resp. F = C). Poznámka 3.2. (1) Jestliže nerozlišujeme mezi skalárem a odpovídající unární operací, pak v souladu s 2.1 můžeme vektorový prostor pova- žovat za algebraickou strukturu (V, LF), kde LF = {+, (-), 0} F představuje popis operací lineární struktury (symbol (-) značí unární operaci výběru opačného prvku v aditivní grupě). 55 (2) Bude-li pole skalárů zřejmé z kontextu, budeme psát též stručně L místo LF. V dalším budeme často pracovat s reálným nebo komplexním vektorovým prostorem, kde L := LR nebo L := LC. (3) Pojem vektorového prostoru lze zavést i nad nekomutativ- ním tělesem F. V takovém případě je nutno rozlišovat mezi násobením skaláry zleva a zprava a zavést tzv. levý (resp. pravý) vektorový prostor nad F. Je-li F pouze okruh s 1 = 0, pak se toto pojetí dále zobecňuje a zavádí se tzv. levý (resp. pravý) modul nad F (nebo též F-modul). VĚTA 3.3 ([Šik:V3.6 s.25]). Nechť V je vektorový prostor nad F a , , i F; x, y, xj V . Pak platí: (L5) x = 0 = 0 nebo x = 0 (L6) -x = (-x) = (-)x (L7) (x - y) = x - y (L8) ( - )x = x - x (L9) (x1 + + xn) = x1 + + xn (L10) (1 + + m)x = 1x + + mx (L11) m i=1 i n j=1 xj = m i=1 n j=1 ixj = n j=1( m i=1 i)xj PŘÍKLAD 3.4 ([Šik:Př.3.5 s.25]). (1) (F, LF) je vektorový prostor nad polem F. Vlastnosti (L1) a (L2) jsou důsledkem okruhových distributivních zákonů, (L3) plyne z asociativity okruhového násobení a (L4) rovněž platí, neboť 1 je jednotkou okruhového násobení. Zejména (R, LR), resp. (C, LC) je reálný, resp. komplexní vektorový prostor. (2) Užitím přímého součinu z definice 2.11 lze konstruovat další (vícerozměrné) vektorové prostory (n N, n > 1): (Fn , LF) := (F, LF) × × (F, LF) n × . . . n-tice skalárů z F. Zejména (Rn , LR) (resp. (Cn , LC)) je reálný (resp. komplexní) vektorový prostor n-tic reálných (resp. komplexních) čísel. V 56 těchto prostorech jsou tedy dle 2.11 všechny operace defino- vány po složkách: [x1, . . . , xn] + [y1, . . . , yn] := [x1 + y1, . . . , xn + yn] 0 := [0, . . . , 0] . . . nulový vektor -[x1, . . . , xn] := [-x1, . . . , -xn] . . . opačný vektor [x1, . . . , xn] := [x1, . . . , xn] . . . skalární násobek (3) Analogicky: (RN , LR) := X nN (R, LR) a (Cn , LC) := X nN (C, LC) jsou po řadě vektorové prostory všech reálných, resp. kom- plexních posloupností s operacemi po složkách jako ve (2). (4) Analogicky: (RI , LR) := X nI (R, LR) a (Cn , LC) := X nI (C, LC) jsou po řadě vektorové prostory všech reálných, resp. kom- plexních funkcí definovaných na množině I (tj. funkcí z I do R, resp. z I do C) opět s operacemi po složkách. Tedy defi- nujeme pro každé i I: (f + g)(i) := f(i) + g(i), (-f)(i) := -f(i), f 0 f(i) = 0 pro každé i I, (f)(i) := f(i). (5) Označme po řadě R[t], resp. C[z] množinu všech polynomů jedné proměnné t R, resp. z C s koeficienty z R, resp. z C. Pak tyto množiny tvoří vzhledem k obvyklému sečítání a ná- sobení skalárem reálný, resp. komplexní vektorový prostor, který lze ztotožnit s reálnými, resp. komplexními posloup- nostmi koeficientů (viz (3)) tvaru {a0, a1, . . . , an, 0, . . . , 0, . . . } pro libovolné n N. Omezíme-li se na pevné n, dostaneme vektorové prostory Rn[t], resp. Cn[z] všech polynomů s reál- nými, resp. komplexními koeficienty stupně nejvýše n. DEFINICE 3.5. Nechť (V, LF) je vektorový prostor, x1, . . . , xn V a 1, . . . , n F. Pokud x V lze vyjádřit ve tvaru x = 1x1 + + nxn, pak řekneme, že vektor x je lineární kombinací vektorů x1, . . . , xn. 57 3.2. VEKTOROVÉ PODPROSTORY, GENERÁTORY. DEFINICE 3.6. Algebraickou podstrukturu (definice 2.12) vektorového prostoru (V, LF) nazýváme jeho vektorovým (lineárním) podprostorem. VĚTA 3.7. Nechť (V, LF) je vektorový prostor a = W V jeho podmnožina. Pak (W, LF) je vektorovým podprostorem prostoru (V, LF) (píšeme (W, LF) (V, LF)) právě když má následující vlastnosti: (1) x, y W x + y W (uzavřenost vzhledem ke grupovému sečítání) (2) x W, F x W (uzavřenost vzhledem ke skalárnímu násobení). DŮSLEDEK 3.8. Každý vektorový podprostor (W, LF) prostoru (V, LF) je uzavřený k libovolným lineárním kombinacím svých prvků, tj. platí: xi W, i F pro i = 1, . . . , n 1x1 + + nxn W. Poznámka 3.9. V každém vektorovém prostoru (V, LF) existuje nejmenší vektorový podprostor ({0}, LF) nazývaný také nulový podprostor a největší podprostor totožný s celým prostorem (V, LF). VĚTA 3.10. Nechť {(Wi, LF)}iI je systém vektorových podprostorů prostoru (V, LF). Pak jejich průnik i I Wi je rovněž vektorový pod- prostor ve V . DEFINICE 3.11. Nechť (V, LF) je vektorový prostor a G V jeho podmnožina. Pak v souladu s definicí 2.13 nejmenší vektorový pod- prostor ve V obsahující G nazveme podprostorem generovaným množinou G nebo také lineárním obalem množiny G ve V . Značíme jej LF(G) nebo stručněji L(G). Prvky množiny G nazýváme generátory tohoto podprostoru. VĚTA 3.12. Nechť (V, LF) je vektorový prostor a G V jeho pod- množina. Pak L(G) vždy existuje a platí: 58 (1) L(G) = { W | (W, LF) (V, LF) : G W} (neboli L(G) je průnikem podprostorů ve V obsahujících G) (2) Je-li G = , pak L(G) = { n i=1 ixi | i F, xi G pro i = 1, . . . , n; n N} (neboli L(G) tvoří všechny lineární kombinace vektorů z G). Zejména L() = {0} je nulový podprostor. Poznámka 3.13. Podle 3.12(2) tedy zápis x L(G) vyjadřuje fakt, že x je nějakou lineární kombinací vektorů z množiny G. VĚTA 3.14 (Vlastnosti generátorů). Nechť (V, LF) je vektorový prostor, W jeho podprostor a M, N, G pod- množiny ve V . Pak platí: (1) 0 L(G) pro každé G V (2) M L(G) L(M) L(G) (3) M N L(M) L(N) (4) W = L(W) a zejména L(M) = L(L(M)) (5) je-li nějaký generátor lineární kombinací ostatních generá- torů, pak jej lze vynechat: x G, x L(G - {x}) L(G - {x}) = L(G). (6) každý generátor lze zaměnit za jeho nenulový skalární náso- bek: x G, 0 = F L((G - {x}) {x}) = L(G). (7) ke každému generátoru lze přičíst libovolnou lineární kombi- naci ostatních generátorů: x G, y L(G - {x}) L((G - {x}) {x + y}) = L(G). Úpravy uvedené v (5) až (7) se nazývají elementární úpravy mno- žiny generátorů. 59 3.3. ZÁVISLOST, NEZÁVISLOST, BÁZE, DIMENZE. DEFINICE 3.15. Minimální podmnožina ve V generující vektorový prostor (V, LF) se nazývá báze tohoto prostoru, neboli platí impli- kace: G báze ve V, M G systém generátorů prostoru V M = G. Zejména za bázi nulového prostoru tedy můžeme považovat prázdnou množinu. DEFINICE 3.16. Nechť (V, LF) je vektorový prostor a M := {x1, . . . , xn} V jeho nějaká neprázdná konečná podmnožina navzájem různých vektorů. Řekneme, že M je (resp. vektory x1, . . . , xn jsou) lineárně nezá- vislá(é), jestliže nulový vektor nelze vyjádřit jako netriviální lineární kombinaci těchto vektorů, tj.: i F, i = 1, . . . , n; 1x1 + + nxn = 0 1 = = n = 0. Nekonečná podmnožina ve V se nazývá lineárně nezávislá, jestliže každá její konečná podmnožina je lineárně nezávislá. Podmnožina (resp. vektory) vektorového prostoru V se nazývá (nazývají) line- árně závislá(é), jestliže není (nejsou) lineárně nezávislá(é). VĚTA 3.17. Jestliže M je lineárně nezávislá množina nějakého vek- torového prostoru, pak platí: (1) Každá neprázdná podmnožina v M je lineárně nezávislá; (2) 0 / M; (3) Je-li M =: {x1, . . . , xn} konečná, x L(M) a x = n i=1 ixi = n i=1 ixi, pak i = i pro i = 1, . . . , n. (4) Každý vektor 0 = x L(M) má až na pořadí sčítanců jediné vyjádření ve tvaru lineární kombinace s nenulovými koefici- enty a navzájem různými vektory z M. VĚTA 3.18. Neprázdná podmnožina M vektorového prostoru (V, LF) je lineárně závislá právě když existuje vektor x M, který je lineární kombinací některých dalších vektorů z M, tj. x L(M - {x}). 60 VĚTA 3.19 ([Šik:V3.18,V3.25 s.27-29]). Nechť = G V je podmnožina nenulového vektorového prostoru (V, LF). Pak následující výroky jsou ekvivalentní: (1) G je báze ve V . (2) G je maximální lineárně nezávislá podmnožina ve V . (3) G je lineárně nezávislá a generuje V , tj. L(G) = V . DŮSLEDEK 3.20 ([Šik:V3.22 s.28]). Z každé množiny generá- torů G nenulového vektorového prostoru V lze vybrat bázi prostoru V jako maximální nezávislou podmnožinu v G. Dokonce to lze udělat tak, aby obsahovala jakoukoli předem danou nezávislou podmnožinu v G. VĚTA 3.21 (Steinitzova věta o výměně, [Šik:V3.23 s.28],[AG1: s.28]). Nechť M, N jsou konečné podmnožiny vektorového prostoru (V, LF), M L(N) lineárně nezávislá. Potom v N existuje podmnožina N s těmito vlastnostmi: (1) N m á týž počet prvků jako M, (2) L((N - N ) M) = L(N). DŮSLEDEK 3.22 ([Šik:3.26 s.29]). Má-li nenulový vektorový prostor (V, LF) konečný systém generátorů, pak ve V existuje konečná báze a všechny báze mají týž (konečný) počet prvků. DEFINICE 3.23. Má-li vektorový prostor (V, LF) konečnou bázi o n prvcích. Pak (jednoznačně určené) číslo n nazýváme dimenzí tohoto prostoru a píšeme dim V = n. Prostor V pak nazýváme n-rozměr- ným (n-dimenzionálním) vektorovým prostorem nebo také ko- nečně rozměrným (konečně dimenzionálním) vektorovým pro- storem. Zejména s uvážením definice 3.15 má každý nulový prostor dimenzi 0 (jeho báze je totiž prázdná množina). Vektorový prostor V , v němž neexistuje konečný systém generátorů se nazývá nekonečně rozměrný (nekonečně dimenzionální), píšeme dim V = . 61 DŮSLEDEK 3.24 (Další důsledky Steinitzovy věty. [Šik:V3.31-2 s.30]). (1) Pro každou lineárně nezávislou množinu vektorů x1, . . . , xk vektorového prostoru V platí k dim V , přičemž každou ta- kovou množinu lze doplnit (rozšířit) na bázi prostoru V . (2) Každý vektorový prostor má bázi. (3) Pro každý lineární podprostor W vektorového prostoru V platí dim W dim V . Přitom každou bázi ve W lze rozšířit na bázi ve V . Je-li dim V < a W = V , pak dim W < dim V . (4) Nechť V je vektorový prostor, dim V = n, 0 < n < , a G jeho podmnožina. Pak následující výroky jsou ekvivalentní: (i) G je báze ve V . (ii) G je n-prvková a lineárně nezávislá. (iii) G je n-prvková a generuje V . PŘÍKLAD 3.25. Pro vektorové prostory z příkladu 3.4 platí: (1) pro každé n N: (Qn , LQ) (Rn , LQ), (Rn , LR) (Cn , LR), (Rn[t], LR) (R[t], LR), (Cn[z], LC) (C[z], LC). (2) pro každé n N: (Qn , LR) (Rn , LR), (Rn , LC) (Cn , LC), (Rn , LR) (Cn , LC), (R[z], LC) (C[z], LC), (R[z], LR) (C[z], LC). (3) {1} je báze v (F, LF) a tedy dim F = 1. Zejména dim R = dim C = 1. Podle věty 3.14(6) je bází také každá jednoprv- ková podmnožina {a}, a = 0. (4) En := {[1, 0, . . . , 0], [0, 1, . . . , 0], . . . , [0, 0, . . . , 1]} je tzv. při- rozená báze v (Fn , LF). Pro každé i = 1, . . . , n bude nadále i := [0, . . . , 1 i , . . . , 0] značit i-tý prvek této báze. Zejména tedy dim Rn = dim Cn = n. Opět podle věty 3.14(6) a s uvá- žením 3.24(4) je bází také každá podmnožina {a11, . . . , ann}, kde ai = 0 pro i = 1, . . . , n. (5) Podle 3.4(5) lze každý polynom a0 + a1t + + antn z Rn[t], resp. z Cn[t] ztotožnit s jeho vektorem n + 1 koeficientů [a0, a1, . . . , an], takže roli přirozené báze v Rn[t], resp. v Cn[t] 62 hrají homogenní polynomy t0 1, t1 , . . . , tn a platí tedy dim Rn[t] = dim Cn[t] = n + 1. (6) Pokud I je nekonečná množina, pak prostory (RI , LR) i (CI , LC) mají nekonečnou dimenzi. Zejména tedy mají nekonečnou di- menzi také prostory posloupností (RN , LR) a (CN , LC) stejně jako prostory polynomů R[t] a C[z]. 63 3.4. LINEÁRNÍ ZOBRAZENÍ. DEFINICE 3.26. Nechť (V1, LF) a (V2, LF) jsou dva vektorové prostory. Pak zobra- zení T : V1 V2, které je homomorfizmem (definice 2.10) nazý- váme lineárním zobrazením (lineárním operátorem) z vekto- rového prostoru (V1, LF) do vektorového prostoru (V2, LF) a píšeme T : (V1, LF) (V2, LF)4 . Speciálně lineární zobrazení T : (V, LF) (F, LF) se nazývá lineární funkcionál na V (viz též 3.4(1)). Lineární zobrazení se nazývá izomorfizmem vektorových prostorů (V1, LF) a (V2, LF), jestliže je bijekcí V1 na V2 (viz úvahu na konci poznámky 2.61). Je-li T pouze prosté lineární zobrazení, nazývá se izomorfní vnoření prostoru (V1, LF) do (V2, LF). Existuje-li alespoň jeden izomorfizmus (V1, LF) na (V2, LF), říkáme, že vektorové prostory (V1, LF) a (V2, LF) jsou izomorfní a píšeme (V1, LF) (V2, LF) nebo jen stručně V1 V2. Existuje-li pouze izo- morfní vnoření, píšeme (V1, LF) (V2, LF) nebo V1 V2. VĚTA 3.27. Nechť (V1, LF) a (V2, LF) jsou dva vektorové prostory. Pak zobrazení T : V1 V2 je lineární právě když má následující vlastnosti: (1) x, y V1 T(x + y) = T(x) + T(y) (vlastnost zachování grupového sečítání) (2) x V1, F T(x) = T(x) (vlastnost zachování skalárního násobení). Je-li T izomorfizmus, pak T-1 je rovněž lineární zobrazení (a tedy izomorfizmus) z (V2, LF) na (V1, LF). Zřejmě složení dvou lineárních zobrazení je rovněž lineární zobrazení. DŮSLEDEK 3.28. Každé lineární zobrazení T : (V1, LF) (V2, LF) zachovává libovolné 4místo y = T (x) píšeme stručněji také y = T x 64 lineární kombinace vektorů, tj. pro i F a xi V1, i = 1, . . . , n, platí: T(1x1 + + nxn) = 1T(x1) + + nT(xn). VĚTA 3.29. Nechť T : (V1, LF) (V2, LF) je lineární operátor, pak N(T) := {x V1 | Tx = 0} je vektorový podprostor v (V1, LF) nazý- vaný jádro (nulový podprostor) operátoru T. Podobně R(T) := {y V2 | x V1 : y = Tx} je vektorový podprostor ve (V2, LF) nazývaný obor hodnot operátoru T. DŮSLEDEK 3.30. Nechť T : (V1, LF) (V2, LF) je lineární operátor. Pak (1) T je izomorfní vnoření právě když N(T) = {0}. (2) T je izomorfizmus právě když N(T) = {0} a R(T) = V2. (3) T je izomorfní vnoření právě když obraz každé neprázdné ko- nečné množiny lineárně nezávislé ve V1 je také lineárně ne- závislá množina ve V2 s týmž počtem prvků. (4) T je izomorfizmus právě když obraz každé báze ve V1 je také báze ve V2 téže mohutnosti. DEFINICE 3.31. Nechť (V, LF) je n-rozměrný vektorový prostor a E := {e1, . . . , en} jeho báze. Definujme zobrazení []E : V Fn , které každému vektoru x V přiřazuje vektor jeho souřadnic v bázi E, tj. [x]E := [1, . . . , n] je ona dle 3.17(3) jednoznačně určená n-tice skalárů taková, že x = 1e1 + + nen. Pokud báze E ve V bude pevně dána, budeme též psát stručně [x] místo [x]E. VĚTA 3.32. Zobrazení []E : V Fn z předchozí definice je izo- morfizmus vektorového prostoru (V, LF) na (Fn , LF). DŮSLEDEK 3.33. (1) Dva konečně rozměrné vektorové prostory V1 a V2 nad týmž polem F mají stejnou dimenzi právě když (V1, LF) (V2, LF). (2) Pro dva konečně rozměrné vektorové prostory (V1, LF), (V2, LF) platí dim V1 dim V2 právě když (V1, LF) (V2, LF). 65 POZNÁMKA 3.34. Každý lineární operátor T : (V1, LF) (V2, LF), V1 = L(E1), je dle 3.28 jednoznačně určen jen svými hodnotami T(E1) = {Te}eE1 na generátorech. Je-li x V1 libovolný vektor a x = 1e1 + + nen nějaké jeho vyjádření jako lineární kombinace generátorů ei E1, i = 1, . . . , n (viz 3.13), pak totiž Tx = 1T(e1) + + nT(en) dle 3.28. Poznamenejme, že zatímco toto vyjádření nemusí být jediné možné (je tomu tak jen když E1 je báze), obraz Tx je vždy jediný bez ohledu na volbu tohoto vyjádření. DEFINICE 3.35. Nechť T : (V1, LF) (V2, LF) je lineární operátor, E1 n-prvková báze ve V1 a E2 m-prvková báze ve V2. Pak dle předchozí poznámky a s ohledem na 3.32 je T jednoznačně určen vektory souřadnic [Te]E2 pro e E1. Systém n vektorů (každý délky m) značený [T]E1,E2 := {[Te]E2 }eE1 pak nazýváme souřadnicovou reprezentací operá- toru T v bázích E1 a E2. Jsou-li obě báze pevně dány, píšeme opět stručně [T] místo [T]E1,E2 . VĚTA 3.36. Nechť T : (V1, LF) (V2, LF) je lineární operátor, V1 = L(E1). Pak platí: (1) T(E1) generuje R(T). (2) T(E1) generuje V2 právě když T je surjekce. (3) Je-li T izomorfní vnoření a E1 báze, pak T(E1) je báze v R(T). (4) Je-li T izomorfní vnoření a E1 báze, pak T(E1) je nezávislá podmnožina ve V2. (5) Je-li T izomorfizmus a E1 báze, pak T(E1) je báze ve V2. (6) Každé zobrazení f báze E1 do prostoru V2 se dá jednoznačně rozšířit na lineární operátor V1 do V2. Je-li f prosté zobra- zení do nějaké báze E2 ve V2 (resp. bijekce na E2), pak toto rozšíření je izomorfní vnoření (resp. izomorfizmus). 66 PŘÍKLAD 3.37. Uvážíme-li 3.25(5), pak zobrazení (a0 + a1t + + antn ) := [a0, a1, . . . , an] definuje izomor- fizmus z (Rn[t], LR) na (Rn+1 , LR), resp. z (Cn[z], LC) na (Cn+1 , LC). Analogicky (a0 + a1t + + antn ) := {a0, a1, . . . , an, 0, . . . } defi- nuje izomorfní vnoření z (Rn[t], LR) do (RN , LR), resp. z (Cn[t], LC) do (CN , LC). VĚTA 3.38. Nechť (V1, LF) a (V2, LF) jsou dva vektorové prostory. Nechť L(V1, V2) značí množinu všech lineárních operátorů z V1 do V2 s operacemi z LF definovanými po složkách jako v 3.4(4), tj. pro T, T1, T2 L(V1, V2) a každé x V1 klademe: (T1 + T2)(x) := T1(x) + T2(x), (-T)(x) := -T(x), T 0 T(x) = 0, (T)(x) := T(x). Pak L(V1, V2) je vektorový prostor nad F. 3.5. FAKTOR PROSTORY A PŘÍMÝ SOUČET. Věta 3.39. Nechť (V, LF) je vektorový prostor a nějaká relace ekvivalence na V a V := V/ příslušný rozklad na V . Pak relace je kongruence na (V, LF) ve smyslu definice 2.42 právě když pro x, x1, x2, x , x1 , x2 V platí implikace: (1) x1 x1 , x2 x2 x1 + x2 x1 + x2 , (2) F, x x x x . V takovém případě třída 0 V obsahující nulový prvek je vektorovým podprostorem ve V . Důsledek 3.40. Každý vektorový podprostor W vektorového prostoru (V, LF) určuje kongruenci W na V s vlastností W = 0 a naopak dle 3.39. Příslušný faktor prostor (V , LF) tvořený odpovídajícími třídami rozkladu pak značíme jako V/W a nazýváme jej faktor prostorem V modulo 67 (podle) W. Každá jeho třída obsahující vektor x je jednoznačně ur- čena podprostorem W ve tvaru x = {x + w | w W}. Místo x pak píšeme x + W. Zejména samotný podprostor W = 0 + W tvoří třídu obsahující nulový vektor 0. Přitom platí x W y y - x W. V takovém případě říkáme, že vektory x a y jsou kongruentní modulo W. Pro příslušné kanonické lineární zobrazení V V/W z věty 2.43, x x + W, pak tedy platí: (x + y) + W = (x + W) + (y + W), (-x) + W = -(x + W), 0 W, (x) + W = (x + W) pro každé F. Důsledek 3.41. Je-li T : (V1, LF) (V2, LF) lineární zobrazení a V1/ T příslušný kanonický rozklad dle definice 2.40, pak V1/ T = V1/N(T). Poznámka 3.42. Podobně každá faktor grupa V/W grupy (V, +, 0) je určena nějakou podgrupou W ve V . Stačí vlastnost (2) ve větě 3.39 nahradit vlast- ností: x x -x -x . Příkladem je grupa (ZN , , 0), která je izomorfní s faktor grupou grupy (Z, +, 0) podle podgrupy NZ := {Nk | k Z}. Píšeme pak ZN Z/NZ. Pak a NZ b b-a NZ b-a = Nk pro nějaké k Z N|(b-a), což přesně odpovídá kongruenci z příkladu 2.62(2). DEFINICE 3.43. Nechť {(Wi, LF)}iI je systém vektorových podprostorů vektorového prostoru (V, LF). Pak podprostor W := L( i I Wi) nazýváme souč- tem vektorových podprostorů Wi, i I a píšeme W = i I Wi. Jestliže navíc platí Wi L( j I,j=i Wj) = {0} pro každé i I, pak součet nazýváme přímým součtem vektorových podprostorů Wi, i I a píšeme W = i I Wi. Speciálně v případě součtu dvou, resp. konečného počtu (n 2) pod- prostorů píšeme W = W1 + W2, resp. W = W1 + + Wn. Podobně 68 v případě přímého součtu dvou5 , resp. konečného počtu (n 2) pod- prostorů píšeme W = W1 W2, resp. W = W1 Wn. Poznámka 3.44. Součet ani přímý součet podprostorů zřejmě nezávisí na pořadí a uzá- vorkování sčítanců a jsou to tedy komutativní a asociativní operace. VĚTA 3.45. Pro podprostory z předchozí definice platí: (1) W = i I Wi právě když W = {x V | x = j J xj, xj Wj, J I, card J < }. (2) W = W1 + + Wn právě když W = {x1 + + xn | xi Wi, i = 1, . . . , n}. (3) W = i I Wi právě když W = {x V | x = j J xj, xj Wj, J I, card J < }, kde vyjádření každého vektoru x W ve tvaru součtu x =j J xj je jediné až na pořadí a počet nulových sčítanců xj. (4) W = W1 Wn právě když W = {x1 + + xn | xi Wi, i = 1, . . . , n}, kde vyjádření x1 + +xn každého vektoru je až na pořadí sčítanců jediné. DŮSLEDEK 3.46. W = W1 Wn právě když W W1 × × Wn. VĚTA 3.47 ([Šik:V3.43 s.32]). Ke každému podprostoru W vektorového prostoru (V, LF) existuje (obec- ně ne jediný) podprostor W v e V tak, že V = W W a dim V = dim W +dim W . Podprostor W s e nazývá přímý doplněk W ve V . Věta 3.48 ([Šik:V3.44 s.33]). Nechť (V, LF) je vektorový prostor a V = W1 W2, pak V/W1 W2 a každá třída rozkladu V/W1 obsahuje právě jeden prvek z W2 (podobně po záměně role W1 a W2). 5dodatečná podmínka je v tomto případě tvaru W1 W2 = {0}. 69 VĚTA 3.49 ([Šik:V3.45 s.33]). Nechť (V, LF) je vektorový prostor a V = W1 W2, pak dim V = dim(W1 + W2) = dim W1 + dim W2. VĚTA 3.50 ([Šik:V3.46 s.33]). Nechť (V, LF) je vektorový prostor a W1 a W2 jeho podprostory, pak dim(W1 W2) + dim(W1 + W2) = dim W1 + dim W2. PŘÍKLAD 3.51. (1) Nechť 0 = u R2 je nějaký vektor, pak W := L({u}) = {u | R} je jednorozměrný vektorový podprostor v (R2 , LR) generovaný vektorem u. Tento podprostor je v Euklidovské rovině s pevně zvoleným počátkem reprezentován přímkou procházející tímto počátkem ve směru vektoru u. Pak roz- klad R2 /W dle 3.40 je tvořen všemi přímkami rovnoběžnými s W. (2) Nechť W1 a W2 jsou dva různé jednorozměrné vektorové pod- prostory jako v (1) reprezentované dvěma přímkami prochá- zejícími počátkem v různých směrech u1 a u2. Pak R2 = W1 W2, neboť W1 W2 = {[0, 0]} a R2 = L(W1 W2) = L({u1, u2}), neboť u1, u2 jsou zřejmě nezávislé a tudíž tvoří bázi v R2 . Dle 3.49 podle očekávání platí 2 = dim R2 = dim W1 + dim W2 = 1 + 1. (3) Nechť W1 a W2 jsou dva různé dvourozměrné podprostory v (R3 , LR) reprezentované různými rovinami procházejícími počátkem Eukleidovského prostoru R3 . Zřejmě R3 = W1+W2 a dle 3.50 platí dim(W1 W2) = dim W1 +dim W2 -dim R3 = 2 + 2 - 3 = 1. Podle očekávání je tedy průnikem těchto rovin nějaká přímka procházející počátkem a součet R3 = W1 +W2 tedy nemůže být přímým součtem. Toho lze dosáhnout jen když W1 je přímka a W2 rovina (nebo naopak), kdy dim(W1 W2) = 1 + 2 - 3 = 0, tj. W1 W2 = {[0, 0, 0]}. DEFINICE 3.52. Nechť W je vektorový podprostor vektorového prostoru (V, LF) a P : V W lineární operátor s vlastností: Px = x 70 pro každé x W. Pak P se nazývá projekční. P je zřejmě surjek- tivní a P2 = P, tj. P(Px) = Px pro každé x V (tzv. vlastnost idempotence). VĚTA 3.53. Nechť (V, LF) je vektorový prostor a V = W1 W2. De- finujme zobrazení P1 : V W1 takto: P1(x) := x1 je onen dle věty 3.45(4) jednoznačně určený prvek z vyjádření x = x1 + x2, x1 W1, x2 W2. Pak P1 je projekční operátor nazývaný operátorem rov- noběžné6 projekce na podprostor W1, přičemž N(P1) = W2 a V/ P1 = V/W2. 3.6. PROSTORY S NORMOU A SKALÁRNÍM SOUČINEM. Všude v tomto odstavci uvažujeme pouze reálné nebo komplexní vek- torové prostory, tj. F C, zpravidla F = R nebo F = C. DEFINICE 3.54. Nechť V je (reálný nebo komplexní) vektorový prostor. Normou na V rozumíme funkci7 : V R+ s těmito vlastnostmi: (N1) x + y x + y pro každé x, y V (trojúhelníková nerovnost). (N2) x = || x pro každé x V a F. (N3) Pro každé x V platí x 0, přičemž x = 0 x = 0. Vektorový prostor V pak nazýváme normovaným lineárním (vek- torovým) prostorem, zkráceně NL-prostorem a píšeme (V, LF, ). VĚTA 3.55. (Vlastnosti normy) Z axiomů (N1) až (N3) bezprostředně vyplývají některé další užitečné vlastnosti normy, například: (N4) | x - y | x y x + y pro každé x, y V. 6rozumí se rovnoběžně s podprostorem W2 7někdy také budeme psát V místo , abychom zdůraznili příslušnost normy k prostoru V . 71 PŘÍKLAD 3.56. (1) Absolutní hodnota || je normou v (F, LF). (2) Podobně pro x =: [x1, . . . , xn] Fn , n N, definuje vztah x 1 := |x1| + + |xn| tzv. 1-normu v (Fn , LF). (3) Dá se ukázat, že pro libovolné p N je rovněž x p := p | x1|p + + |xn|p tzv. p-norma v (Fn , LF). V li- mitě pro p dostaneme normu x := max(|x1|, . . . , |xn|). POZNÁMKA 3.57. Norma představuje míru pro velikost vektorů ve vektorovém prostoru. Norma x 2 z předchozího příkladu je běžně užívaná Euklidovská norma. DEFINICE 3.58. Nechť V je (reálný nebo komplexní) vektorový prostor. Skalárním (vnitřním) součinem na V rozumíme funkci8 , : V × V F s těmito vlastnostmi: (S1) x + y, z = x, z + y, z pro každé x, y, z V . (S2) x, y = x, y pro každé x, y V a F. (S3) y, x = x, y pro každé x, y V , zejména tedy x, x R. (S4) Pro každé x V platí x, x 0, přičemž x, x = 0 x = 0. Vektorový prostor V pak nazýváme lineárním (vektorovým) pro- storem s vnitřním součinem, zkráceně VS-prostorem a píšeme (V, LF, , ). VĚTA 3.59. (Vlastnosti skalárního součinu) Z axiomů (S1) až (S4) vyplývají některé další užitečné vlastnosti ska- lárního součinu, například: (S5) x, y + z = x, y + x, z pro každé x, y, z V . (S6) x, y = x, y pro každé x, y V a F. (S7) 0, x = x, 0 = 0 pro každé x V . 8někdy také budeme psát , V místo , , abychom zdůraznili příslušnost skalárního součinu k prostoru V . 72 POZNÁMKA 3.60. Je-li V reálný vektorový prostor (F = R), pak (S3) a (S6) jsou tvaru: (S3') y, x = x, y pro každé x, y V (symetrie). (S6') x, y = x, y pro každé x, y V a R. Vlastnosti (S1), (S2), (S5) a (S6'), resp. (S6), znamenají, že , je tzv. bilineární forma na V. Vlastnost (S3') znamená, že , je dokonce symetrická bilineární forma. Vzhledem k vlastnostem bilinearity můžeme dále s výhodou provádět následující úpravy (i, j F, xi, yj V ): n i =1 ixi, mj =1 jyj = ni =1 i xi, mj =1 jyj = ni =1 i mj =1 j xi, yj = = ni =1 mj =1 ij xi, yj . (3.1) VĚTA 3.61 ((Cauchy-)Schwarzova nerovnost, [KaSk:V11.5 s.105]). (S8) | x, y | x , x y, y ( S9) = x y pro každé x, y V , přičemž rovnost nastane jen v případě, že x, y jsou lineárně závislé, tj. jen když jeden z nich je skalárním násobkem dru- hého (viz větu 3.18). DŮSLEDEK 3.62. (S9) x := x , x je norma na V nazývaná normou odvoze- nou ze skalárního součinu , nebo také normou indu- kovanou skalárním součinem , . Věta 3.63. V NL-prostoru V s normou lze zavést vnitřní součin , indu- kující tuto normu dle (S9) právě když platí tzv. rovnoběžníkový zákon: (S10) x + y 2 + x - y 2 = 2( x 2 + y 2 ) pro každé x, y V . 73 PŘÍKLAD 3.64. ˇ (Cn , LC), n N, je VS-prostorem s vnitřním součinem x, y = n i=1 xiyi. ˇ (Rn , LR), n N, je VS-prostorem s vnitřním součinem x, y = n i=1 xiyi. ˇ Indukovanou normou je v obou případech euklidovská norma, neboť x, x = n i=1 xixi = n i=1|xi|2 = x 2 2. ˇ Protože každé dva nenulové reálné vektory x, y generují nejvýše dvourozměrný podprostor v (Rn , LR), který je dle 3.32 izomorfní s (R2 , LR) můžeme bez újmy na obecnosti předpokládat, že x, y R2 . Pak užitím Pythagorovy věty dostáváme ( a jsou úhly, které po řadě vektory x a y svírají s osou x): x, y = x1y1 + x2y2 = = ( x cos ) ( y cos ) + ( x sin ) ( y sin ) = = x y (cos cos + sin sin ) = = x y cos( - ). Pak := - je úhel mezi směrově orientovanými vektory x a y a můžeme psát: -1 cos := x, yx y 1, 0 , (3.2a) což poskytuje geometrickou interpretaci Schwarzovy nerovnosti. V komplexním případě je x, y obecně komplexní číslo, takže úhel můžeme zavést jen jako úhel mezi neorientovanými vektory: 0 cos := | x, y | x y 1, 0 2 , (3.2b) Skalární součin tedy prostřednictvím Schwarzovy nerovnosti umož- ňuje zavést úhlovou geometrii do libovolného abstraktního vektoro- vého prostoru se skalárním součinem dle následující definice. 74 DEFINICE 3.65. Nechť V je reálný (resp. komplexní) vektorový prostor a x, y V jeho dva nenulové vektory. Pak úhlem mezi x a y (svíraným vektory x a y) rozumíme úhel určený svým kosinem dle (3.2a) (resp. dle (3.2b)). Je-li x = 0 nebo y = 0, klademe definitoricky = 2 . ˇ Řekneme, že vektory x a y jsou ortogonální, jestliže x, y = 0 (tj. když svírají pravý úhel), píšeme x y. Zřejmě nulový vektor 0 je dle (S7) kolmý na každý vektor x V a dle (S4) je to současně jediný vektor, který je kolmý sám na sebe. ˇ Podobně podmnožiny M, N V se nazývají k sobě ortogonální, jestliže x y pro každou dvojici x M a y N. Píšeme opět M N (místo {x} N píšeme stručně x N). ˇ Řekneme, že množina M V je ortogonální, jestliže x y pro každou dvojici x, y M, x = y. Ortogonální množina M se nazývá ortonormální9 , jestliže navíc x = 1 pro každé x M. VĚTA 3.66 ([KaSk:V11.8 s.106]). Nechť E := {e1, . . . , en} je or- togonální množina VS-prostoru V . Pak platí: (a) množina {1e1, . . . , nen} je ortogonální pro libovolná čísla 1, . . . , n F, (b) pokud E neobsahuje nulové vektory, pak E lze normalizovat: množina { 1 e1 e1, . . . , 1 en en} je ortonormální. VĚTA 3.67 (Pythagorova věta, [KaSk:V11.9 s.106]). (S11) x + y 2 = x 2 + y 2 pro každé x, y V , x y. Je-li E = {e1, . . . , en}, n N, ortogonální množina vektorového pro- storu V . Pak platí (S11') e1 + e2 + + en 2 = e1 2 + e2 2 + + en 2. VĚTA 3.68. Nechť E je ortogonální množina VS-prostoru V ne- obsahující nulové prvky. Pak E je lineárně nezávislá. Zejména tedy 9Na rozdíl od ortogonální množiny nemůže dle (N3) ortonormální množina obsahovat nulové prvky. 75 každá ortonormální množina E V je lineárně nezávislá. Jestliže taková množina E generuje celý prostor V (viz 3.19(3)), nazývá se ortogonální, resp. ortonormální báze prostoru V (zkráceně OB, resp. ONB). DŮSLEDEK 3.69. Nechť E je ONB VS-prostoru V , pak každý vektor x V má jediné vyjádření ve tvaru x = e E x, e e, kde suma má nejvýše konečně mnoho nenulových sčítanců, neboť card {e E | x, e = 0} < . Je-li V konečně rozměrný a E = {e1, . . . , en}, pak x má v této bázi vektor souřadnic10 [x]E = [ x, e1 , . . . , x, en ]. DŮSLEDEK 3.70 (Souřadnicové vyjádření skalárního součinu v ONB). Nechť E je ONB VS-prostoru V , x, y V , pak skalární sou- čin lze vyjádřit ve tvaru x, y = e E x, e y, e , kde suma má nej- výše konečně mnoho nenulových sčítanců. Zejména v případě x = y platí x = e E| x, e |2. Je-li V konečně rozměrný a E = {e1, . . . , en}, pak x, y = n i=1 ii a x = n i=1|i|2, kde [x]E =: [1, . . . , n], [y]E =: [1, . . . , n], i = x, ei a i = y, ei pro i = 1, . . . , n. Věta 3.71. Nechť = M V je podmnožina VS-prostoru V . Pak množina M := {x V | x M} je vektorový podprostor ve V a platí L(M) = M . Množina M se nazývá ortogonální doplněk (komplement) množiny M ve V . POZNÁMKA 3.72. Z předchozí věty vyplývá důležitý fakt: k tomu, aby nějaký vektor x V byl kolmý na nějaký podprostor W ve V stačí, aby byl kolmý na nějakou obvykle podstatně menší množinu jeho generátorů (konečná množina, pokud dim W < ). VĚTA 3.73. Nechť {(Wi, LF)}iI je systém navzájem kolmých VS­pod- prostorů VS-prostoru (V, LF), Wi Wj pro i = j. Pak jejich součet 10viz definici 3.31 76 W := i I Wi je přímý a nazývá se ortogonální součet pod- prostorů {Wi}iI . Místo W = i I Wi v takovém případě píšeme W = i I Wi. Speciálně v případě ortogonálního součtu dvou, resp. konečného počtu (n 2) podprostorů píšeme W = W1 W2, resp. W = W1 Wn. VĚTA 3.74. Nechť (V, LF) je VS-prostor a V = W W . Pak W = W je jediný přímý doplněk ortogonální k W. V tomto případě operátor rovnoběžné projekce V na W zavedený ve větě 3.53 nazýváme operátorem ortogonální projekce a značíme jej PW . Každý vek- tor x V lze pak jednoznačně rozložit na součet x = x + x , kde x := PW x W je ortogonální projekce x na W a x W je jednoznačně určená reziduální složka vektoru x, x W. DŮSLEDEK 3.75. I - PW je operátor ortogonální projekce V na W a platí W = W. VĚTA 3.76 (Některé vlastnosti operátoru ortogonální projekce). Nechť W1 a W2 jsou vektorové podprostory VS-prostoru V a PW1 a PW2 operátory ortogonální projekce prostoru V po řadě na W1 a W2. Pak platí: (1) x W1 PW1 x = x. (2) x W 1 PW1 x = 0. (3) W2 W1 PW2 (PW1 x) = PW2 x pro každé x V. VĚTA 3.77 (Věta o ortogonální projekci). Nechť (V, LF) je VS-prostor, V = W W a x = PW x pro nějaký vektor x V . Pak x - x = infyW x - y a x je jediný prvek ve W s takovou vlastností. Je-li W = L(E), pak x = 1e1 + + nen pro vhodné11 vektory ei E a i F, i = 1, . . . , n, n N. Vektor x proto také na- zýváme nejlepší lineární aproximací x pomocí vektorů z E 11zatímco x je určen jednoznačně, jeho lineární reprezentace pomocí j a ej E je jediná jen v případě, že E je báze. 77 podle normy . Je-li E ONB ve W, pak i = x, ei = x, ei pro i = 1, . . . , n. VĚTA 3.78 (Gram-Schmidtova ortogonalizace, [KaSk:V11.11 s.107]). Nechť V je vektorový prostor se skalárním součinem , a nechť v1, . . . , vn (n N) je báze12 vektorového podprostoru W vektorového prostoru V . Položme Wk := L({v1, . . . , vk}) pro každé k N, 1 k n a definujme rekurentně vektory e1, . . . , en V takto: e1 = v1, ek = vk - PWk-1 vk = vk - k-1j =1 vk, eje j 2 ej pro každé k = 2, . . . , n. Pak L({e1, . . . , ek}) = Wk pro každé k = 1, . . . , n, přičemž vek- tory e1, . . . , ek tvoří ortogonální bázi ve Wk. Zejména tedy vektory e1, . . . , en tvoří ortogonální bázi ve W = Wn. DŮSLEDEK 3.79 ([KaSk:V11.12 s.107]). Každý VS-prostor V konečné dimenze má ortogonální i ortonormální bázi. Přitom každou jeho ortogonální množinu bez nulových prvků lze doplnit na OB ve V a každou jeho ortonormální množinu lze doplnit na ONB ve V . VĚTA 3.80. Pro každý konečně rozměrný podprostor W vektorového prostoru (V, LF) platí V = W W a tedy v takovém případě lze vždy použít větu o ortogonální projekci. Důsledek 3.81. Nechť = M V je podmnožina VS-prostoru V generující ve V podprostor L(M) konečné dimenze. Pak M = L(M). VĚTA 3.82. Nechť (V1, LF) a (V2, LF) jsou dva VS-prostory a T : V1 V2 lineární operátor. Jestliže existuje zobrazení T : V2 V1 takové, že Tx, y = x, T y platí pro každé x V1 a y V2, pak T je jediné takové a 12algoritmus lze po modifikaci užít i v případě, že v1, . . . , vn pouze generují V : v rekurzi pro ek sčítáme jen přes ta j, pro něž ej = 0; bázi pak tvoří jen nenulové vektory ej . 78 určuje lineární operátor nazývaný operátorem adjungovaným k T. Je-li V1 = V2 a T = T , pak T se nazývá samoadjungovaný operátor. Věta 3.83. Je-li T lineární operátor jako v 3.82 a dim R(T) =: n < pak T existuje a zkonstruuje se takto: (1) V R(T) vybereme nějakou n-prvkovou ortonormální bázi Ea b1, . . . , bn V1 takové, že E = {T(b1), . . . , T(bn)}. (2) Pak B := {b1, . . . , bn} je lineárně nezávislá ve V1 a tedy ge- neruje ve V1 podprostor W := L(B) rovněž dimenze n. (3) Nechť E =: {e1, . . . , en} je ONB ve W získaná Gram-Schmidt- ovou ortogonalizací báze B dle 3.78. (4) Pro každé y V2 položíme T y := n j=1 y, Tej ej. POZNÁMKA 3.84. Každý lineární operátor V1 V2 určuje vztahem Tx, y bilineární formu V1 ×V2 F (srov. 3.60), kterou lze vzhledem k linearitě T opět upravovat podle vztahů analogických k (3.1): T ni =1 ixi , mj =1 jyj = ni =1 mj =1 ij Txi, yj . (3.3) Je-li V := V1 = V2, pak zobrazení V V definované vztahem Tx, xn azýváme kvadratickou formou. Pokud navíc platí T = T , pak tato forma nabývá pouze reálných hodnot, neboť Tx, x = x, Tx ( S3) = Tx, x . Samoadjungovaný operátor T se nazývá (striktně) pozitivní, jestliže Tx, x 0 pro každé x V ( Tx, x > 0 pro každé x = 0), ne- boli když jím určená kvadratická forma nabývá pouze nezáporných hodnot (kladných hodnot pro nenulová x). Píšeme T 0 (T > 0). VĚTA 3.85 (Vlastnosti adjungovaných operátorů). Nechť (V1, LF), (V2, LF) a (V3, LF) jsou VS-prostory, T : V1 V2 a U : V2 V3 lineární operátory a T : V2 V1 a U : V3 V2 operátory k nim adjungované. Pak platí 79 (1) T je operátor adjungovaný k T , tj. platí T = T. (2) T U je operátor adjungovaný ke složenému operátoru UT : V1 V3, tj. platí (UT) = T U . (3) Identický operátor I : V1 V1 je samoadjungovaný, tj. I = I. (4) TT i T T jsou pozitivní operátory a tedy také samoadjun- gované. VĚTA 3.86 (Charakterizace operátoru ortogonální projekce). Nechť (V, LF) je VS-prostor a P surjektivní zobrazení V na nějaký jeho podprostor W. Pak následující výroky jsou ekvivalentní: (1) P = PW , tj. P je operátor ortogonální projekce V na W. (2) Pro každé x V platí x - Px W. (3) P je lineární operátor s vlastnostmi: P2 = P (tj. P je pro- jekční) a P = P (tj. P je samoadjungovaný). Důsledek 3.87. Každý operátor ortogonální projekce je pozitivní. Věta 3.88. Nechť (V1, LF), (V2, LF) jsou VS-prostory, T : V1 V2 lineární ope- rátor a T : V2 V1 operátor k němu adjungovaný. Pak platí: (1) N(T) = R(T ) a N(T ) = R(T) . (2) T = T N(T) = R(T) . (3) N(T T) = N(T) a N(TT ) = N(T ). (4) T izomorfizmus T je izomorfní vnoření. (5) Jestliže dim R(T) < nebo dim R(T ) < , pak (i) V1 = R(T ) N(T), V2 = R(T) N(T ), (ii) N(T) = R(T ), N(T ) = R(T), (iii) R(T T) = R(T ) a R(TT ) = R(T). (iv) T |R(T ) : R(T) R(T ) i T|R(T ) : R(T ) R(T) jsou izomorfizmy a tedy dim R(T) = dim R(T ) =: n. (v) dim V1 = n + dim N(T) a dim V2 = n + dim N(T ). (vi) T izomorfizmus T je izomorfizmus, (T-1 ) existuje a platí (T-1 ) = (T )-1 . 80 DEFINICE 3.89. Lineární operátor z VS-prostoru V1 do VS-prostoru V2 se nazývá unitární (ortogonální13 ), jestliže zobrazuje nějakou ONB ve V1 na ONB ve V2 o stejné mohutnosti. Každý unitární ope- rátor je dle 3.36(6) izomorfizmem, nazývá se proto také unitárním izomorfizmem prostorů V1 a V2. Jestliže existuje unitární operátor V1 na V2, pak říkáme, že prostory V1 a V2 jsou unitárně izomorfní a píšeme (V1, LF) U (V2, LF). Jestliže V1 je unitárně izomorfní pouze s nějakým podprostorem ve V2, pak pí- šeme (V1, LF) U (V2, LF) a každý unitární operátor V1 na R(V1) V2 nazýváme unitárně izomorfním vnořením V1 do V2. VĚTA 3.90 (Charakterizace unitárních operátorů). Nechť (V1, LF), (V2, LF) jsou VS-prostory a existuje ONB ve V1. Nechť dále T : V1 V2 je lineární operátor. Pak následující výroky jsou ekvivalentní: (1) T je unitární. (2) T zobrazuje každou ONB ve V1 na ONB ve V2 o stejné mo- hutnosti. (3) T je surjekce zachovávající skalární součin: Tx, Ty = x, y pro každé x, y V1. (4) T je surjekce zachovávající normu (tzv. izometrie): Tx = x pro každé x V1. (5) T existuje a platí T = T-1 . (6) T existuje a T T i TT jsou identické operátory. V takovém případě T-1 = T je rovněž unitární operátor z V2 na V1. DŮSLEDEK 3.91 (Charakterizace unitárně izomorfních vnoření). Za předpokladů předchozí věty jsou ekvivalentní následující výroky: (1') T je unitárně izomorfní vnoření. (2') T zobrazuje každou ONB ve V1 na ortonormální množinu ve V2 o stejné mohutnosti. 13Termín ortogonální se obvykle užívá v případě reálných prostorů (F = R). 81 (3') T zachovává skalární součin: Tx, Ty = x, y pro každé x, y V1. (4') T zachovává normu: Tx = x pro každé x V1. (5') T : R(T) V1 existuje a platí T = T-1 na R(T). (6') T existuje a T T je identický operátor. V takovém případě T-1 = T je unitární operátor z R(T) na V1. DŮSLEDEK 3.92. Je-li (V, LF) VS-prostor konečné dimenze n, a E jeho ONB, pak izomorfizmus []E : V Fn z věty 3.32 je dokonce unitární izomorfizmus (V, LF) na (Fn , LF). DŮSLEDEK 3.93. (1) Dva konečně rozměrné reálné (komplexní) VS-prostory V1 a V2 mají stejnou dimenzi právě když (V1, LF) U (V2, LF). (2) Pro dva konečně rozměrné reálné (komplexní) VS-prostory (V1, LF), (V2, LF) platí dim V1 dim V2 právě když (V1, LF) U (V2, LF). 82 ANGLICKÁ TERMINOLOGIE Z LINEÁRNÍ ALGEBRY skalár scalar skalární součin dot product vektor vector vektorový (lineární) prostor vector (linear) space podprostor subspace lineární kombinace linear combination lineární obal linear span (lineárně) generovaný (čím) spanned by báze basis lineárně (ne)závislý linearly (in)dependent dimenze dimension n-dimenzionální n-dimensional vícerozměrný multivariate lineární zobrazení (operátor) linear mapping (operator) vnoření embedding nulový podprostor (jádro) operátoru null space prostor hodnot operátoru range space souřadnice co-ordinates faktor prostor factor space kongruentní modulo congruent modulo (přimý) součet (direct) sum přímý doplněk direct complement projekční operátor projection operator norma norm normovaný prostor normed space vnitřní (skalární) součin inner (scalar) product prostor s vnitřním součinem inner product space bilineární forma bilinear form kvadratická forma quadratic form Pythagorova věta Pythagorean theorem rovnoběžníkový zákon parallelogram law úhel mezi angle between 83 kolmý, ortogonální perpendicular, orthogonal ortonormální orthonormal ortogonální doplněk orthogonal complement ortogonální součet orthogonal sum ortogonální projekce orthogonal projection nejlepší lineární aproximace best linear approximation ortogonalizace orthogonalization (samo)adjungovaný (self-)adjoint (striktně) pozitivní (strictly) positive unitární operátor unitary operator unitárně izomorfní unitary isomorphic 84 4. Teorie matic Teorie a příklady: [KaSk: s.63-129], [Šik: s.1-23] Příklady: [Ho:řešené č.16-36; s.17-37], [Ho:neřešené kap.4, 5 s.100-137] Teorie matic představuje formální kalkulus pro manipulaci s vektory a lineárními zobrazeními ve VS-prostoru (Fn , LF). Prostřednictvím unitárního izomorfizmu z 3.92 lze tento aparát užít i pro jakýkoli abstraktní vektorový prostor (V, LF) konečné dimenze. Numerické výpočetní prostředí MATLAB používá matice nad kom- plexními čísly (F = C) jako základní proměnné a je tedy ideálním vý- početním prostředím pro řešení úloh lineárního charakteru. Má však daleko širší záběr i nad tento lineární rámec. Název systému je odvozen z angličtiny: MATLAB=MATrix LABora- tory. Systém produkuje americká společnost MathWorks, Inc. (http://www.mathworks.com) a jejím výhradním distributorem pro Českou republiku je pražská firma Humusoft, s.r.o. (http://www.humusoft.cz). Obecně lze systém MATLAB charakte- rizovat jako maticově orientované výpočetní prostředí s vlastním pro- gramovacím jazykem vhodným pro efektivní implementaci, provádění a vizualizaci numerických výpočtů vyžadujících náročný aparát z nej- různějších oblastí matematiky. Je dostupný na všech běžných platfor- mách (WINDOWS, LINUX, UNIX, atd.) při zachování takřka sto- procentní přenositelnosti vytvořených programů a datových souborů. Vzhledem ke svému snadnému a intuitivnímu ovládání bude proto MATLAB nadále využíván k demonstracím i ve cvičeních. Cvičení v MATLABu: tmcv1, tmcv2, tmcv3, tmcv4 85 4.1. MATICE A JEJICH ZÁKLADNÍ DRUHY. DEFINICE 4.1. Nechť I a J jsou konečné lineárně uspořádané množiny (m := card I, n := card J), pak každé zobrazení A : I × J F nazýváme maticí nad F typu m/n (rozměru m × n). Pro každé i I a j J značíme hodnotu tohoto zobrazení jako aij := A(i, j) (aij F) a nazýváme prvkem matice A v i-tém řádku a j-tém sloupci nebo také (i, j)-tým prvkem matice A. Množina I, resp. J se nazývá množinou řádkových, resp. sloup- cových indexů matice A. V dalším se bez újmy na obecnosti mů- žeme omezit na standardně užívané indexové množiny I = {1, 2, . . . , m} a J = {1, 2, . . . , n}. Matici A pak zapisujeme jako podrobný výčet všech jejích prvků uspořádaný do tabulky: A = a11 a12 a1n a21 a22 a2n ... ... ... ... am1 am2 amn . (4.1) Pokud aij nepředstavují konkrétní hodnoty, vystačíme se zjednodu- šeným symbolickým zápisem A = [aij]. Speciální případy: ˇ m = n: A nazýváme čtvercovou maticí řádu m. ˇ m = 1: A nazýváme řádkovým vektorem délky n. ˇ n = 1: A nazýváme sloupcovým vektorem délky m. ˇ m = n = 1: A ztotožňujeme s jejím jediným prvkem, tj. [a] = a. ˇ m = 0: A nazýváme prázdným řád. vektorem délky n. ˇ n = 0: A nazýváme prázdným sloup. vektorem délky m. ˇ m = n = 0: A nazýváme prázdnou maticí typu 0/0. Je-li m = 0 nebo n = 0, pak A se nazývá prázdná matice14 . Píšeme A = [ ]. 14Prázdná matice koresponduje s prázdným zobrazením zavedeným v po- známce 1.36(4). 86 DEFINICE 4.2 (Submatice). Matici B =: [bkl] nazveme submaticí matice A =: [aij], jestliže existují řádkové indexy 1 i1 < i2 < < ip m a sloupcové indexy 1 j1 < j2 < < jq n tak, že bkl = aikjl pro každé k = 1, . . . , p a l = 1, . . . , q. Píšeme B = A([i1, . . . , ip], [j1, . . . , jq]). Speciální případy: ˇ p = m (vybrány všechny řádky): B =: A(:, [j1, . . . , jq]), ˇ q = n (vybrány všechny sloupce): B =: A([i1, . . . , ip], :), ˇ p = 1 (vybrán jeden řádek i := i1): B =: A(i, [j1, . . . , jq]), ˇ q = 1 (vybrán jeden sloupec j := j1): B =: A([i1, . . . , ip], j), ˇ i-tý řádek matice A: B =: A(i, :), ˇ j-tý sloupec matice A: B =: A(:, j). Poznámka 4.3. (1) Matice lze sestavovat i po blocích ve tvaru (4.1), kde aij mo- hou být nahrazeny submaticemi Aij kompatibilních rozměrů. Při sestavování matice pomocí bloků skládaných vedle sebe (pod sebe) budeme v souladu se syntaxí jazyka MATLAB v zápisech užívat jako oddělovače čárku (středník). Například matici A ze (4.1) můžeme pomocí jejích sloupců sj := A(:, j), resp. řádků ri := A(i, :) zapsat také takto: A = [s1, . . . , sn], resp. A = [r1; . . . ; rm]. (2) Ztotožníme-li řádkové, resp. sloupcové vektory délky n s prvky vektorového prostoru Fn , můžeme matici A typu m/n inter- pretovat dvojím způsobem: a) jako uspořádaný systém m řádkových vektorů z Fn , b) jako uspořádaný systém n sloupcových vektorů z Fm . Takový systém může v příslušném prostoru hrát roli systému generátorů nějakého podprostoru, jeho báze apod. Označení . Mm,n := Mm,n(F) . . . množina všech matic nad F typu m/n, ij = 1 pro i = j 0 pro i = j . . . Kroneckerův symbol . 87 x Fn . . . sloupcový vektor (pokud nebude řečeno jinak). i := [1,i; 2,i; . . . ; n,i] . . . i-tý prvek přirozené báze E dle 3.25(4). In := [i,j] . . . jednotková matice řádu n: In(i, :) = In(:, i) = i; její i-tý řádek (sloupec) je právě i. 0m,n . . . nulová matice typu m/n: všechny prvky jsou nuly. 1m,n . . . matice jedniček typu m/n: všechny prvky jsou jedničky. Eij Mm,n . . . matice, kde Eij(i, j) = 1 a ostatní prvky jsou nuly. diag(A) =: [a11, a22, . . . ] . . . hlavní diagonála matice A. [a1n, a2,n-1, a3,n-2, . . . ] . . . vedlejší diagonála matice A. Poznámka 4.4. Je-li x = [x1; . . . ; xn], pak zřejmě x = n i=1 xii a tedy složky xi jsou dle 3.31 přímo souřadnicemi x v přirozené bázi. Tudíž x = [x]E a zobrazení []E : Fn Fn je identita. DEFINICE 4.5 (Matice se speciální strukturou). Konstantní matice: A = [aij], kde aij = a i, j, neboli matice, jejíž všechny prvky jsou stejné, například 0m,n a 1m,n. Diagonální matice: D = [dij], dij = 0 pro i = j, neboli matice, která má všechny prvky mimo hlavní diagonálu nu- lové. diag(d), diag(d1, . . . , dn) . . . čtvercová diagonální matice řádu n s hlavní diagonálou d = [d1, . . . , dn]. Symetrická matice: A = [aij], aij = aji i, j, neboli matice se stejnými řádky a sloupci: A(i, :) = A(:, i) i (symetrie vzhledem k hlavní diagonále). Antisymetrická matice: A = [aij], aij = -aji i, j, neboli matice, kde řádky a sloupce mají opačné znaménko: A(i, :) = -A(:, i) i (antisymetrie vzhledem k hlavní diagonále). Jelikož aii = -aii, tak každá antisymetrická matice má nulovou hlavní diagonálu. Hermitovsky symetrická matice (F C): A = [aij], aij = aji i, j, neboli matice, kde řádky a sloupce jsou vůči sobě komplexně sdru- žené: A(i, :) = A(:, i) i (hermitovská symetrie vzhledem k hlavní diagonále). Jelikož aii = aii, tak každá hermitovsky symetrická ma- tice má na hlavní diagonále reálná čísla. 88 Je-li aij R i, j, pak hermitovská symetrie je zřejmě ekvivalentní se symetrií. Hermitovsky antisymetrická matice (F C): A = [aij], aij = -aji i, j (tj. Re aij = -Re aji a Im aij = Im aji), neboli matice, kde řádky a sloupce se liší znaménkem v reálné části: A(i, :) = -A(:, i) i (hermitovská antisymetrie vzhledem k hlavní di- agonále). Jelikož aii = -aii, tak každá hermitovsky antisymetrická matice má na hlavní diagonále ryze imaginární čísla nebo nuly. Je-li aij R i, j, pak hermitovská antisymetrie je zřejmě ekviva- lentní s antisymetrií. Horní trojúhelníková matice: U = [uij], uij = 0 pro i > j, neboli matice, která má všechny prvky pod hlavní diagonálou nulové. Dolní trojúhelníková matice: L = [lij], lij = 0 pro i < j, neboli matice, která má všechny prvky nad hlavní diagonálou nulové. Schodovitá matice: S = [sij] matice m × n, která je buď nulová nebo existují přirozená čísla k m a 1 j1 < j2 < . . . < jk n s těmito vlastnostmi: (a) siji = 0 pro 1 i k, (b) sir = 0 pro 1 i k, 1 r < ji, (c) sij = 0 pro k < i m, 1 j n. Snadno jako cvičení se dokáže následující věta. VĚTA 4.6. Nechť S je nenulová schodovitá matice jako v definici 4.5, pak S([1, . . . , k], [j1, . . . , jk]) je její horní trojúhelníková submatice s nenulovými prvky siji na hlavní diagonále. 89 4.2. ZÁKLADNÍ MATICOVÉ OPERACE. V hranaté závorce za názvem operace uvádíme její syntaxi v MATLABu. DEFINICE 4.7 (LINEÁRNÍ OPERACE). Operace sečítání matic téhož typu, výběru opačné matice a násobení matice skalárem definujeme po složkách: Sečítání [X = A + B]: X m×n = A m×n + B m×n def. X(i, j) := A(i, j) + B(i, j) i, j. Opačná matice [X = -A]: X m×n = - A m×n def. X(i, j) := -A(i, j) i, j. Násobení matice skalárem a F [X = a*A]: X m×n = a A m×n def. X(i, j) := aA(i, j) i, j. DEFINICE 4.8 (TRANSFORMACE MATICE NA VEKTOR). Operátor vec : Mmn Fmn [A(:)]: vec A m×n := [A(:, 1); A(:, 2); . . . ; A(:, n)]. Tento operátor skládá tedy sloupce matice A pod sebe do sloupcového vektoru. Věta 4.9. Stejně jako v příkladu 3.4(4) tvoří množina všech matic Mm,n opatřená výše uvedenými operacemi vektorový prostor (Mm,n, LF) s nulovou maticí 0m,n jako nulovým prvkem. Operátor vec je zřejmě lineární a dokonce izomorfizmus vektorových prostorů (Mm,n, LF) a (Fmn , LF). Uvážíme-li 3.33 a 3.25(4), pak dim Mm,n = mn, přičemž roli přirozené báze v Mm,n hraje systém matic Eij (i = 1, . . . , m; j = 1 . . . , n). DEFINICE 4.10 (TRANSPOZICE MATIC). Transponovaná matice [X = A.']: X n×m = AT m×n def. X(i, j) := A(j, i) i, j. 90 Tento operátor zaměňuje sloupce a řádky, tj.: X(i, :) = A(:, i) nebo ekvivalentně X(:, i) = A(i, :) i. Hermitovsky (konjugovaně) transponovaná matice (F C) [X = A']: X n×m = A m×n def. X(i, j) := A(j, i) i, j. Tento operátor zaměňuje řádky (resp. sloupce) za komplexně sdružené sloupce (resp. řádky): X(i, :) = A(:, i), resp. ekvivalentně X(:, i) = A(i, :) i. Transpoziční operátory mají zřejmě následující vlastnosti: VĚTA 4.11 (Vlastnosti (hermitovské) transpozice). (1) (A + B)T = AT + BT , (A + B) = A + B . (2) (aA)T = aAT , (aA) = aA a F. (3) 0 m,n = 0T m,n = 0n,m, 1 m,n = 1T m,n = 1n,m, E ij = ET ij = Eji i, j. (4) (AT )T = A, (A ) = A. (5) A reálná A = AT . (6) A je symetrická AT = A, A je hermitovsky symetrická A = A. (7) D diagonální DT = D, zejména platí I n = IT n = In. (8) A horní (dolní) trojúhelníková A i AT jsou dolní (horní) trojúhelníkové matice. (9) a(A + AT ), resp. a(A - AT ) je symetrická, resp. antisymet- rická matice pro každou čtvercovou matici A a každé a F. (10) a(A+A ), resp. a(A-A ) je hermitovsky symetrická, resp. hermitovsky antisymetrická matice pro každou čtvercovou ma- tici A a každé a R. (11) Každou čtvercovou matici A lze rozložit na její (hermitovsky) symetrickou a antisymetrickou část: A = 1 2 (A+AT )+ 1 2 (A-AT ), A = 1 2 (A+A )+ 1 2 (A-A ). 91 Poznámka 4.12. Jelikož transpozice transformuje sloupcový (řádkový) vektor na řád- kový (sloupcový), platí zejména [x1; . . . ; xn] = [x1, . . . , xn]T . V dalším budeme pro zápis sloupcových vektorů přednostně užívat tvar [x1, . . . , xn]T , který je v matematice standardní (užívání střed- níku je totiž motivováno pouze syntaxí jazyka MATLAB). DEFINICE 4.13 (MULTIPLIKATIVNÍ OPERACE). Maticové násobení [X = A * B]: X m×p = A m×n . B n×p def. X(i, j) := n k=1 A(i, k).B(k, j) i, j. Výše uvedené lze ekvivalentně vyjádřit dvojím způsobem: a) X(:, j) = n k=1 A(:, k).B(k, j) j . . . j-tý sloupec X je line- ární kombinací sloupců matice A pomocí koeficientů z j-ho sloupce matice B, nebo ekvivalentně: X(:, j) = A.B(:, j). b) X(i, :) = n k=1 A(i, k).B(k, :) i . . . i-tý řádek X je lineární kombinací řádků matice B pomocí koeficientů z i-ho řádku matice A, nebo ekvivalentně: X(i, :) = A(i, :).B. Hadamardův součin matic [X = A .* B]: X m×n = A m×n B m×n def. X(i, j) := A(i, j).B(i, j) i, j. Hadamardův součin je tedy operace součinu pro matice téhož typu zavedená po složkách podobně jako v případě sečítání. Kroneckerův (přímý) součin matic [X = kron(A,B)]: X mm ×nn = A m×n B m ×n d ef. X = [A(i, j)B] i, j. X je tedy matice sestavená z m × n bloků (submatic) A(i, j)B o rozměru m × n . Věta 4.14 (Vlastnosti multiplikativních operací). (1) Asociativita: (A.B).C = A.(B.C), (A B) C = A (B C), (A B) C = A (B C). 92 (2) Distributivita zprava: A.(B + C) = A.B + A.C, A (B + C) = A B + A C, A (B + C) = A B + A C. (3) Distributivita zleva: (A + B).C = A.C + B.C, (A + B) C = A C + B C, (A + B) C = A C + B C. (4) Komutativita: A B = B A. Maticový součin ani Kroneckerův součin nejsou obecně ko- mutativní operace. (5) Jednotkový prvek: Im.A = A.In = A, 1m,n A = A 1m,n = A, 11,1 A = A 11,1 = A, In Im = Imn. (6) (Hermitovská) transpozice součinu: (A.B)T = BT .AT , (A.B) = B .A , (A B)T = AT BT , (A B) = A B , (A B)T = AT BT , (A B) = A B . (7) Pravidlo smíšeného součinu: (A B).(C D) = A.C B.D pro matice kompatibilních rozměrů: A je m × n, C je n × p A.C je m × p, B je m × n , D je n × p B.D je m × p , Odtud: A B je (mm × nn ) a C D je (nn × pp ) , takže (A B).(C D) má rozměr (mm × pp ) , který je stejný jako rozměr matice A.C B.D. (8) Maticový součin dvou vektorů: a) součin řádkového vektoru se sloupcovým: x = [x1; . . . ; xn], y = [y1; . . . ; yn] xT y = yT x = n i=1 xiyi. b) součin sloupcového vektoru s řádkovým: x = [x1; . . . ; xm], y = [y1; . . . ; yn] xyT = [xiyj] Mm,n. (9) Skalární součiny pomocí maticového násobení (F C): x = [x1; . . . ; xn], y = [y1; . . . ; yn] y x = n i=1 xiyi = x, y , X = [xij] Mn,p, Y = [yij] Mn,m Y X =: Z Mm,p, 93 kde Z =: [zij], zij = X(:, j), Y (:, i) ( S3) = Y (:, i), X(:, j) i, j. Tedy zij je skalární součin j-ho sloupce matice X s i-tým sloupcem matice Y . Speciálně pro X = Y Mn,m je X X =: Z Mm,m, kde Z =: [zij], zij = X(:, j), X(:, i) ( S3) = X(:, i), X(:, j) i, j. Matice X X je tzv. Gramova matice. (10) Součin s diagonální maticí: Nechť D = diag(d1, . . . , dm). Pak A =: [r1; . . . ; rm] DA = [d1r1; . . . ; dmrm] a podobně A =: [s1, . . . , sm] AD = [d1s1, . . . , dmsm]. Tedy vynáso- bení diagonální čtvercovou maticí zleva (zprava) vede k vyná- sobení řádků (sloupců) odpovídajícími diagonálními prvky. (11) Provedení permutace pomocí maticového násobení: Nechť : J J je permutace transformující přirozeně uspo- řádanou množinu indexů J := {1, . . . , m} na permutovanou množinu {(1), . . . , (m)} a nechť P je matice, která vznikne z jednotkové matice In stejnou permutací jejích řádků (řádek (i) se přesune na i-tou pozici), tj. P := [(i),j]. Pak A = [r1; . . . ; rm] P .A = [r(1); . . . ; r(m)] a podobně A = [s1, . . . , sm] A.P T = [s(1), . . . , s(m)]. Tedy per- mutace řádků (sloupců) nějaké matice dosáhneme jejím vy- násobením zleva (zprava) maticí, která vznikne z jednotkové matice provedením stejné permutace s jejími řádky (sloupci). Je-li A = D = diag(d1, . . . , dm) diagonální, pak složení téže řádkové a sloupcové permutace zřejmě stejným způsobem per- mutuje diagonálu v D: P DP T = diag(d(1), . . . , d(m)). (12) Maticový součin dvou trojúhelníkových (diagonálních) matic: Výsledkem maticového součinu dvou dolních (horních) trojú- helníkových matic je opět dolní (horní) trojúhelníková matice. Na diagonále jsou přitom součiny odpovídajích diagonálních prvků. Analogicky pro diagonální matice. Důkaz. S výjimkou (7) jsou všechny vlastnosti bezprostředním dů- sledkem definic příslušných operací.9 4 4.3. MATICE JAKO OPERÁTOR A HODNOST MATICE. Označení . V konečně rozměrných vektorových prostorech lze báze vždy považo- vat za množiny lineárně uspořádané svými indexy. Vektory souřadni- cového vyjádření operátoru T : V1 V2 z definice 3.35 (dim V1 = n, dim V2 = m, E1 báze ve V1, E2 báze ve V2) pak rovněž můžeme uspo- řádat jako sloupce v matici, tj. [T]E1,E1 =: [[Te1]E2 , . . . , [Ten]E2 ] je pak maticí rozměru m × n nazývanou maticovou reprezentací operátoru T. Nadále ve všech uvažovaných vektorových prostorech předpokládáme souřadnicové vyjádření v pevně zvolených a lineárně uspořádaných bázích, zejména pak v (Fn , LF) jimi budou přirozené báze E, pokud nebude řečeno jinak. V souladu s definicemi 3.31 a 3.35 tedy budou vynechávány indexy jak ve vyjádření vektorů tak i operátorů: píšeme stručně [x] a [T] = [[Te1], . . . , [Ten]]. VĚTA 4.15. Každá matice T Mm,n určuje předpisem x T .x (x Fn ) tzv. maticový lineární operátor T : (Fn , LF) (Fm , LF). Přitom platí: (1) Je-li M =: [x1, . . . , xk] systém vektorů z Fn uspořádaný do sloupců matice, pak jeho obraz v operátoru T je matice T(M) = [T .x1, . . . , T .xk] 4.13a) = T .M. (2) [T] = [[T1], . . . , [Tn]] = T . (3) R(T ) := R(T) = L(s1, . . . , sn) a R(T T ) = L(r1, . . . , rm), kde ri jsou řádky a sj sloupce matice T . (4) Součinu dvou matic odpovídá složení příslušných maticových operátorů. (5) Identická matice určuje identický operátor. Jestliže F C, pak navíc platí: (6) Každá hermitovsky transponovaná matice T určuje operá- tor adjungovaný k operátoru určenému maticí T , přičemž R(T ) = L(r1, . . . , rm). V případě reálné matice T hraje tutéž roli transponovaná matice T T . 95 (7) Operátor určený maticí T je samoadjungovaný právě když matice T je hermitovsky symetrická. V případě reálné matice T hraje tutéž roli symetrická matice. (8) Matice T určuje unitárně izomorfní vnoření právě když její sloupce tvoří ortnormální množinu . Je-li T v takovém pří- padě navíc čtvercová, pak určuje unitární operátor a nazývá se proto unitární maticí (resp. ortogonální maticí v pří- padě F R). DŮKAZ. K důkazu linearity stačí ověřit vlastnosti (1) a (2) z věty 3.27: T .(x + y) = T .x + T .y je důsledkem distributivity 4.14(2). T .(x) = T .x plyne přímo z definice 4.13 maticového násobení:n k=1 T(i, k)xk = n k=1 T(i, k)xk. (1) je opět přímým důsledkem maticového násobení dle 4.13a): totiž j-tý sloupec T(M) je lineární kombinací sloupců T po- mocí j-tého sloupce M(:, j) = xj, což je totéž jako T .xj. (2) [T] = [[T1], . . . , [Tn]] 4.4 = [T1, . . . , Tn] (1) = T .In 4.14(5) = T . (3) Podle 4.13a) je T .x lineární kombinací sloupců T pomocí koeficientů vektoru x Fn . Pak R(T ) = {T .x | x F} 3.12(2) = L(s1, . . . , sn). Podobně pro R(T T ) a R(T ) v (6). (4) je přímým důsledkem asociativity maticového násobení: (U.T ).x 4.14(1) = U.(T .x). (5) dle 4.14(5) platí In.x = x pro každé x Fn . (6) T .x, y 4 .14(9) = y .(T .x) 4.14(1) = (y .T ).x 4.11(4) = (y .T ).x = 4.14(6) = (T .y) .x 4.14(9) = x, T .y . Je-li T reálná, pak T = T T dle 4.11(5). (7) T určuje samoadjungovaný operátor (6) T = T 4.11(6) T je hermitovsky symetrická. (8) ˇ Nechť sloupce T jsou ortonormální. Podle (2) jsou obrazem ONB E a jelikož generují podprostor R(T ) v Fm , tak matice 96 T určuje unitárně izomorfní vnoření dle 3.89. ˇ Nechť naopak matice T určuje unitárně izomorfní vnoření. Pak její sloupce musí být jakožto obraz ONB E také ortonor- mální dle 3.91(2'). ˇ Je-li T čtvercová, pak počet jejích sloupců je roven jejich délce m, která je dimenzí celého prostoru Fm . Sloupce pak tvoří jeho bázi dle 3.24(4)(ii). T tedy určuje unitární operátor opět dle 3.89. P oznámka 4.16. Podle věty 4.15 není tedy nadále třeba rozlišovat mezi maticí T , příslušným lineárním operátorem T a jeho maticovou reprezentací [T] v přirozené bázi. Poznamenejme však, že týž operá- tor může mít v jiné než přirozené bázi jinou maticovou reprezentaci. Naopak táž matice může v různých bázích reprezentovat různé ope- rátory. Jak je ukázáno ve větě B.1 z přílohy B, mohou v tomto smyslu matice dokonce reprezentovat i lineární operátory mezi libovolnými abstraktními vektorovými prostory konečné dimenze. DEFINICE 4.17 (HODNOST MATICE). Sloupcovou (řádkovou) hodností matice A Mm,n, nazýváme dimenzi vektorového podprostoru R(A) v Fm (R(AT ) v Fn ), což je dle 4.15(3) právě podprostor generovaný sloupci (řádky) matice A. Podle níže dokázané věty 4.23 je sloupcová i řádková hodnost stejná, nazývá se hodností matice A a značí se r(A). Matice A se nazývá maticí sloupcově (řádkově) plné hodnosti, jestliže r(A) = n (r(A) = m). Matice A se nazývá regulární15 , je-li současně řádkově i sloupcově plné hodnosti. Čtvercová matice, která není regulární se nazývá sin- gulární. 15Regulární matice musí být čtvercová, neboť počet lineárně nezávislých sloupců n nemůže přesáhnout dimenzi prostoru Fm , tj. musí platit n m. Analogicky z lineární nezávislosti řádků dostáváme m n. 97 Poznámka 4.18. S ohledem na větu 3.19 a její důsledek 3.20 udává sloupcová (řádková) hodnost matice počet prvků libovolné báze (ne- boli maximální lineárně nezávislé podmnožiny) vybrané z generující množiny všech jejích sloupců (řádků). Zejména tedy: a) Matice je sloupcově (řádkově) plné hodnosti právě když všech- ny její sloupce (řádky) jsou lineárně nezávislé. b) Matice je regulární právě když je čtvercová a má lineárně nezávislé všechny řádky i sloupce15 . V dalším se zaměříme na důkaz tvrzení o shodnosti sloupcové a řád- kové hodnosti matice. Zde budou klíčovou roli hrát takové transfor- mace dané matice, které zachovají beze změny její sloupcovou i řád- kovou hodnost. Dále budeme psát A B, pokud matice A a B mají shodné sloupcové i řádkové hodnosti. Takto zavedená relace je zřejmě ekvivalencí na množině všech matic nad týmž skalárním polem F. VĚTA 4.19. (1) Každá regulární matice má stejnou sloupcovou a řádkovou hodnost. (2) A je regulární právě když AT je regulární. (3) Nechť A([i1, . . . , ir], [j1, . . . , jr]) je regulární submatice řádu r matice A typu m/n. Pak sloupce A(:, j1), . . . , A(:, jr) i řádky A(i1, :), . . . , A(ir, :) jsou lineárně nezávislé. (4) Jednotková matice je regulární. DŮKAZ. (1) Dle 4.18b) má regulární matice stejný počet řádků (=řádková hodnost) i sloupců (=sloupcová hodnost). (2) Tvrzení je opět důsledkem 4.18b), neboť AT vznikne z A záměnou řádků za sloupce a naopak. (3) r k=1 kA(:, jk) = 0m,1 r k=1 kA([i1, . . . , ir], jk) = 0r,1 1 = 0, . . . , r = 0 dle 4.18b). Nezávislost řádků se dokáže podobně. (4) Řádky i sloupce jednotkové matice jsou prvky přirozené báze a tudíž jsou lineárně nezávislé. 98 V ĚTA 4.20. (1) Matice A je sloupcově plné hodnosti právě když příslušný ma- ticový operátor je izomorfní vnoření. (2) Matice A je řádkově plné hodnosti právě když příslušný ma- ticový operátor je surjektivní. (3) Matice A je regulární právě když příslušný maticový operátor je izomorfizmus. DŮKAZ. (1) Matice A typu m/n je sloupcově plné hodnosti 4.18a) její sloupce jsou lineárně nezávislé 4.13a) [A.x = 0 x = 0] N (A) = {0} 3.30(1) A určuje izomorfní vnoření. (2) Ukážeme ekvivalenci negovaných výroků (viz 1.1(6)): Matice A typu m/n není řádkově plné hodnosti AT nemá lineárně nezávislé sloupce A nemá lineárně nezá- vislé sloupce (srov. důkaz 4.23) matice A typu n/m není sloupcově plné hodnosti (1) maticový operátor příslušný k A není izomorfní vnoření 3.30(1) 0 = y Fm : A y = 0 3.58(S4) 0 = y Fm : A y, A y = 0 0 = y Fm : Ax, y 3 .82,4.15(6) = x, A y = 0 x Fn 0 = y R(A) z Rm - R(A) : z = PR(A)z + y (bez újmy na obec- nosti lze za z zvolit rovnou 0 = y R(A) ) maticový operátor příslušný k A není surjektivní. (3) Matice A je regulární 4.17 je současně sloupcově i řádkově plné hodnosti (1),(2) A určuje surjektivní izomorfní vnoření A určuje izomorfizmus. 9 9 LEMMA 4.21. Sloupcová ani řádková hodnost matice se nemění při jejím násobení zleva (zprava) maticí sloupcově (řádkově) plné hodnosti. DŮKAZ. Nechť R Mp,m je matice sloupcově plné hodnosti m a A nějaká matice typu m/n. Pak a) R(R.A) = {R.(A.x) | x Fn } = {R.y | y R(A)} 4.20(1) R(R.A) je izomorfním obrazem podprostoru R(A) 3.33 dim R(R.A) = dim R(A) matice R.A a A mají stejnou sloupcovou hodnost. b) RT je řádkově plné hodnosti 4.20(2) RT je surjekce R((R.A)T ) 4.14(6) = R(AT .RT ) = {AT .(RT .x) | x Fp } = {AT .y | y R(RT ) = Fm } = R(AT ) dim R((R.A)T ) = dim R(AT ) 4.17 matice R.A a A mají stejnou řádkovou hod- nost. Násobení zprava maticí řádkově plné hodnosti lze transpozicí převést na násobení zleva maticí sloupcově plné hodnosti: (A.R)T = RT .AT . Dle předcházející části mají (A.R)T a AT stejnou řádkovou i sloup- covou hodnost a tedy totéž musí platit i pro A.R a A.V ĚTA 4.22 (Skeletní rozklad matice). Nechť A je nenulová matice typu m/n sloupcové hodnosti r, pak exis- tuje matice sloupcově plné hodnosti B typu m/r a matice řádkově plné hodnosti C typu r/n tak, že A = B.C. Přitom C má stejnou řádko- vou i sloupcovou hodnost r a platí R(A) = R(B), R(AT ) = R(CT ) a N(A) = N(C). Přitom C lze zvolit tak, aby Ir byla její submaticí. DŮKAZ. Položme B := A(:, [j1, . . . , jr]) rovno submatici v A se- stávající z vhodně vybraných sloupců tvořících bázi v R(A). Takový výběr je vždy možný dle 3.20. Tyto sloupce jsou lineárně nezávislé, takže B je dle 4.18a) sloupcově plné hodnosti a přitom R(A) = R(B). Každý sloupec matice A patří do R(A), takže musí být nějakou line- ární kombinací bázových sloupců z B. Nechť C je matice, jejíž j-tý 100 sloupec C(:, j) je příslušný vektor souřadnic j-tého sloupec matice A v bázi B. Na základě 4.13a) tedy můžeme psát A = B.C. Vekto- rem souřadnic k-tého bázového sloupce A(:, jk) je k (k = 1, . . . , r), což znamená, že jednotková matice Ir = C(:, [j1, . . . , jr]) je subma- ticí matice C. Jelikož Ir je dle 4.19(4) regulární, jsou podle 4.19(3) lineárně nezávislé jak všechny řádky matice C (tj. C je řádkově plné hodnosti), tak i sloupce C(:, j1), . . . , C(:, jr). Ty dokonce tvoří bázi v R(C) = Fr , neboť dim Fr = r (viz 3.24(4)(ii)). Tedy r je nejen řádková, ale i sloupcová hodnost matice C. V části b) důkazu lemmatu 4.21 jsme ukázali R(AT ) = R((B.C)T ) = R(CT ). Platí také N(A) = N(C): B určuje dle 4.20(1) izomorfní vnoření, takže N(B) 3.30(1) = {0} a platí x N(A) 0 = A.x = B.(C.x) C.x N(B) = {0} 0 = C.x x N(C).V ĚTA 4.23 (Tvrzení o shodě řádkové a sloupcové hodnosti). Každá matice A má stejnou řádkovou i sloupcovou hodnost, neboli dim R(A) = dim R(AT ). Zejména platí r(A) = r(AT ). V případě F C platí také r(A) = r(A ). DŮKAZ. Nechť A = B.C je skeletní rozklad matice A. Pak A C dle 4.21. Tedy matice A má stejnou řádkovou i sloupcovou hodnost jako C. Ta má však obě hodnosti stejné, takže totéž musí platit pro A. V případě F C rovnost h := r(A) = r(A ) plyne z 3.88(5)(iv). Dá se ale dokázat i přímo jako důsledek faktu, že operace komplexního sdružení zachovává lineární nezávislost: totiž značí-li ri například řádky matice A pak ri jsou sloupce matice A . Přitom k j=1 jrij = 0 = 0 = k j=1 jrij , kde j = 0 j = 0. V důsledku toho je ri1 , . . . , rih maximální lineárně nezávislá mezi všemi řádky A právě když ri1 , . . . , rih je maximální lineárně nezávislá mezi všemi kom- plexně sdruženými řádky matice A, tj. mezi všemi sloupci matice A . 1 01 VĚTA 4.24 (Řádkové/sloupcové úpravy zachovávající hodnost). (1) Hodnost matice se nemění při jejím násobení zleva (zprava) maticí sloupcově (řádkově) plné hodnosti. (2) Součin dvou matic sloupcově (řádkově) plné hodnosti je opět matice sloupcově (řádkově) plné hodnosti. (3) Hodnost matice se nemění při jejím násobení zleva nebo zprava regulární maticí. (4) Součin regulárních matic je regulární matice. (5) Hodnost matice se nemění permutací jejích sloupců nebo řádků. (6) Hodnost matice se nemění vynecháním sloupce (řádku), který je lineární kombinací ostatních sloupců (řádků). (7) Hodnost matice se nemění vynásobením některého sloupce nebo řádku nenulovým skalárem. (8) Hodnost matice se nemění přičtením skalárního násobku ně- kterých sloupců (řádků) k jinému sloupci (řádku). (9) Hodnost matice se nemění vynecháním nulových sloupců nebo řádků. DŮKAZ. Vzhledem k 4.23 všechny úvahy prováděné dále se sloupci platí i pro řádky a naopak. Tvrzení (1) již bylo dokázáno v lemmatu 4.21. Tvrzení (2) je speciálním případem (1) stejně jako (3), neboť regulární matice má plnou sloupcovou i řádkovou hodnost. Podobně (4) je důsledkem (3). Tvrzení (2) a (4) lze jinou úvahou odvodit také z věty 4.20: totiž součinu matic sloupcově (řádkově) plné hodnosti, resp. regulárních, odpovídá dle 4.15(4) složení dvou izomorfních vnoření (surjektivních lineárních zobrazení), resp. izomorfizmů, což je opět lineární zobrazení téhož typu. Tvrzení (5) je zřejmé, neboť prostor generovaný řádky nebo sloupci (a tedy ani jeho dimenze) nezávisí na uspořádání množiny generátorů. Tvrzení (6)­(8) jsou elementární úpravy z věty 3.14, které rovněž nemění generovaný podprostor a tedy ani jeho dimenzi. Tvrzení (9) je speciálním případem (6), neboť každý nulový sloupec či řádek lze považovat za nulovou lineární kombinaci ostatních sloupců (řádků). 1 02 VĚTA 4.25. Čtvercová matice A řádu n je regulární právě když existují čtvercové matice A1, A2 řádu n takové, že A1.A = A.A2 = In. V takovém případě A1 = A2 =: A-1 je jediná, je regulární a určuje maticový operátor inverzní k operátoru určenému maticí A. Matici A-1 nazý- váme maticí inverzní k A [v MATLABu: inv(A)]. DŮKAZ. A je regulární 4.20(3) A určuje izomorfizmus. ˇ Jestliže A určuje izomorfizmus, nechť A-1 je maticová reprezenatce inverzního operátoru. Pak A-1 .A = A.A-1 = In dle 4.15(4)(5). ˇ Nechť platí A1.A = A.A2 = In. Protože identický operátor In je prosté a surjektivní zobrazení, platí: A.x = A.y A1.A.x = A1.A.y In.x = In.y x = y A je prosté. Podobně pro každé y máme y = In.y = A.A2.y R(A) A je také surjektivní. Celkem A je tedy izomorfizmus. Přitom A2 = In.A2 = A1.A.A2 = A1.In = A1. Po záměně role A a A-1 vidíme, že A-1 je rovněž regulární a určuje izomorfizmus inverzní k izomorfizmu ur- čenému maticí A.V ĚTA 4.26. Každá permutační matice P je regulární a v případě F C je dokonce unitární. DŮKAZ. P řádu n je regulární na základě věty 4.24(5), neboť je dle 4.14(11) permutací řádků jednotkové matice In, která je regulární dle 4.19(4). V případě F C unitárnost matice P pak plyne z 3.90(3): P .x, P .y 4 .14(9) = n i=1 x(i)y(i) = n i=1 xiyi 4.14(9) = x, y , neboť sečítání je komutativní a nezávisí tedy na permutaci sčítanců.V ĚTA 4.27. Čtvercová trojúhelníková (diagonální) matice je regu- lární právě když všechny její prvky na hlavní diagonále jsou nenulové. Důkaz. Vzhledem k 4.19(2) a 4.11(8) stačí tvrzení ověřit například pro horní trojúhelníkovou matici A řádu n. ˇ Nechť aii = 0 pro každé i = 1, . . . , n. Dle 4.18b) a 4.23 stačí uká- zat například jen lineární nezávislost řádků. Z rovnosti [0, . . . , 0] = 103 n i=1 iA(i, :) postupně dostáváme: 0 = 1a11, 0 = 1a12 + 2a22, . . . , 0 = n-1 k kakn + nann. Z 1. rovnice a11 = 0 1 = 0, po dosazení do 2. rovnice analogicky a22 = 0 2 = 0, atd. až z poslední rovnice ann = 0 n = 0. ˇ Předpokládejme, že aii = 0 pro nějaké i. Vezměme nejmenší takové i. Je-li i = 1, pak 1. sloupec je nulový a A tedy není regulární. Je-li i > 1, pak A([1, . . . , i-1], [1, . . . , i-1]) je horní trojúhelníková subma- tice řádu i - 1 s nenulovou diagonálou a tudíž regulární dle předchozí části. Dle 4.19(3) jsou nezávislé celé sloupce A(:, 1), . . . , A(:, i - 1) a protože A([i, . . . , n], [1, . . . , i]) je nulová submatice v důsledku aii = 0, je sloupec A(:, i) lineární kombinací prvých i - 1 sloupců, tj. sloupce A jsou závislé a A opět nemůže být regulární. Diagonální matice je speciálním případem trojúhelníkové matice.D ŮSLEDEK 4.28 (Vlastnosti inverzních matic). Nechť A, B jsou dvě čtvercové matice řádu n. Pak (1) A je regulární právě když AT je regulární. V takovém případě platí (AT )-1 = (A-1 )T . (1') V případě F C je obdobně A regulární právě když A je regulární. V takovém případě platí (A )-1 = (A-1 ) . (2) A, B regulární (A.B)-1 = B-1 .A-1 . (3) Je-li P permutační matice určená permutací dle 4.14(11), pak P -1 = P -1 = P T . (4) Je-li A =: [aij] regulární dolní (horní) trojúhelníková matice řádu n, pak A-1 je rovněž dolní (horní) trojúhelníková matice s prvky a-1 11 , . . . , a-1 nn na hlavní diagonále. Je-li A dokonce diagonální, pak A-1 je rovněž diagonální. Důkaz. (1) AT regulární 4.19(2) A je regulární 4.25 A-1 .A = A.A-1 = In 4.14(6) AT .(A-1 )T = (A-1 )T .AT = IT n 4.11(7) = In 4.25 (AT )-1 = (A-1 )T . 104 (1') Pro A se ukáže podobně. S ohledem na 4.15(6) plyne také přímo z 3.88(5)(vi). (2) Plyne z toho, že inverzní zobrazení se skládají v opačném pořadí. Jiné odvození se opět může opírat o větu 4.25: B-1 .A-1 .A.B = B-1 .B = In a analogicky A.B.B-1 .A-1 = A.A-1 = In. (3) Dle 4.14(11): P = [(i),j] P T = [j,(i)] = [-1(j),i], neboť j = (i) právě když -1 (j) = -1 ((i)) = i. Ma- tice P T tedy reprezentuje operátor inverzní permutace -1 , tj. P -1 = P T . Vezmeme-li v 4.14(11) za diagonální ma- tici jednotkovou matici D = In, pak D se nezmění při per- mutaci samých jedniček na diagonále. Platí tedy P .P T = P .In.P T = In a po záměně za -1 si matice P a P T rov- něž zamění roli, takže také platí P T .P = In a P -1 4.25 = P T . (4) Nechť A =: [aij] je například dolní trojúhelníková regulární matice řádu n. Dle 4.27 jsou aii = 0 pro i = 1, . . . , n. Podle 4.25 musí pro matici X =: [xj,k] inverzní k A platit In = A.X. Srovnáváním naddiagonálových prvků v i-tém řádku a k-tém sloupci na levé a pravé straně této rovnice dostáváme po- stupně pro i = 1, . . . , n a k i: 1k = n j=1 a1jxjk = a11x1k 1 = a11x11 a 0 = a11x1k pro k > 1 x11 = a-1 11 a x1k = 0 pro k > 1. Analogicky pro i = 2: 2k = n j=1 a2jxjk = a21x1k + a22x2k = a22x2k x22 = a-1 22 a x2k = 0 pro k > 2, atd. Případ horní trojúhelníkové matice převedeme na předchozí situaci transpozicí užitím 4.11(8) a 4.14(6): Podle 4.25 musí také platit In = X.A, odtud In = IT n = (X.A)T = AT .XT , kde AT je dolní trojúhelníková, takže dle předchozí části je také XT dolní trojúhelníková a tedy X horní trojúhelníková. Diagonálové prvky se transpozicí také nemění. Matice A je diagonální právě když je současně horní i dolní trojúhelníková, takže její inverze musí také mít obě vlast- nosti, tj. musí být diagonální. 105 V ĚTA 4.29 (Zjišťování hodnosti). Nechť A je matice typu m/n a B typu n/p. Pak platí: (1) r(A) min(m, n). (2) r(A.B) min(r(A), r(B)). Je-li A sloupcově plné hodnosti, resp. B řádkově plné hodnosti, pak nastane rovnost a r(A.B) = r(B), resp. r(A.B) = r(A). (3) Hodnost nenulové matice A je rovna největšímu řádu nějaké její regulární submatice. (4) r(A) = n - dim N(A). (5) V případě F C platí r(A.A ) = r(A .A) = r(A) = r(A ) a speciálně je-li A sloupcově, resp. řádkově plné hodnosti, pak A .A, resp. A.A je regulární. (5') V případě F R platí r(A.AT ) = r(AT .A) = r(A) = r(AT ) a speciálně je-li A sloupcově, resp. řádkově plné hodnosti, pak AT .A, resp. A.AT je regulární. Důkaz. (1) Hodnost matice odpovídá maximálnímu počtu lineárně ne- závislých sloupců (řádků) matice a nemůže proto přesáhnout dimenzi prostoru, do něhož náleží, tj. musí platit r(A) m a současně r(A) n. (2) R(A.B) R(A) 3.24(3) dim R(A.B) dim R(A) 4.17 r(A.B) r(A). Užitím této nerovnosti na transpozici součinu dostaneme i druhou nerovnost: r(A.B) 4.23 = r((A.B)T ) = r(BT .AT ) r(BT ) 4.23 = r(B). Je-li B řádkově plné hodnosti, pak r(A.B) 4.24(1) = r(A) = min(r(A), r(B)), neboť dle (1) je r(A) min(m, n) n = r(B). Analogicky pro A sloupcově plné hodnosti: r(A.B) 4.24(1) = r(B) = min(r(A), r(B)), neboť dle (1) máme r(B) min(n, p) n = r(A). 106 (3) A nenulová existuje alespoň jeden nenulový prvek aij ur- čující regulární submatici [aij] řádu 1. Označíme-li r největší řád nějaké regulární submatice, pak tedy r 1 a dle 4.19(3) lze v matici vybrat r nezávislých řádků (resp. sloupců), které lze doplnit na bázi o h := r(A) prvcích. Platí tedy h r. Naopak z matice A hodnosti h lze vybrat submatici B o h lineárně nezávislých sloupcích (sloupcová báze), která má sloupcovou plnou hodnost h. Dle 4.23 je i řádková hodnost matice B rovna h, takže z B lze vybrat h nezávislých řádků. Výsledná submatice řádu h má rovněž h nezávislých řádků (a tedy i sloupců) a je proto regulární. Protože r udává nej- větší řád takové submatice, platí i opačná nerovnost h r a celkem tedy h = r. Takto zkonstruovaná submatice má pak největší možný řád h. (4) Nechť A = B.C je skeletní rozklad podle věty 4.22, r := r(A). Nechť Q je vhodná permutační matice (viz 4.14(11)), kterou přeuspořádáme sloupce C tak, aby jednotková matice Ir ob- sažená v C byla jejím prvním blokem: C.Q =: [Ir, C ] . Stej- ným způsobem přeuspořádáme vektory x Fn : QT .x =: [y; t], kde výsledný vektor rozdělíme na dva sloupcové bloky y Fr a t Fn-r . Pak dostáváme: x N(A) 4.22 = N(C) C.x = 0 4.28(3) C.Q.QT .x = 0 [Ir, C ] .[y; t] = 0 Ir.y + C . t = 0 y = -C . t [y; t] = [-C ; In-r] = :C . t x = Q.[y; t] R(Q.C ) . Tedy N(A) = R(Q.C ) dim N(A) = dim R(Q.C ) = r(Q.C ) 4.24(5) = r(C ) (3) = n - r, neboť C o bsahuje regulární submatici In-r, která je maximálního možného řádu, protože n - r je sloupcový rozměr matice C . (5) Rovnost hodností plyne z 3.88(5)(iii),(iv). A sloupcově plné hodnosti r(A) = n A .A je řádu n o hodnosti n a tedy 107 regulární. Podobně A řádkově plné hodnosti A má sloup- cově plnou hodnost m. Pak dle předchozí části po záměně role A a A dostáváme: r(A.A ) = r(A .A ) = r(A ) = m. Matice A.A je řádu m a tedy regulární. (5') Je důsledkem (5), neboť v případě reálné matice je A = AT dle 4.11(5). D ŮSLEDEK 4.30. Hodnost schodovité matice je rovna počtu jejích nenulových řádků (tzv. schodů). Důkaz. Pro nulovou matici je tvrzení zřejmé. Nechť S typu m/n je schodovitá matice s k nenulovými řádky, k 1. Vynecháme-li m - k nulových řádků, dostaneme dle 4.24(9) matici S t ypu k/n stejné hodnosti: r(S) = r(S ) . Podle 4.6 matice S o bsahuje horní trojúhel- níkovou submatici řádu k s nenulovou diagonálou, která je regulární dle 4.27. Jelikož řádkový rozměr matice S j e k, je tato submatice maximální taková a tedy celkem r(S) = r(S ) 4.29(3) = k.P ŘÍKLAD 4.31. Vlastnost (5') neplatí obecně pro matice s prvky z nereálného skalárního pole F. Jednoduchý protipříklad najdeme již v případě komplexních matic (F = C): Uvažujme matici A = 1 i -i 1 , kde [-i, 1] = -i[1, i] r(A) = 1. Totiž za sloupcovou (řádkovou) bázi (maximální lineárně nezávis- lou podmnožinu) matice A lze v tomto případě zvolit jednoprvkovou množinu tvořenou libovolným sloupcem (řádkem), neboť každá jed- noprvková množina obsahující nenulový vektor je triviálně lineárně 108 nezávislá dle 3.3(L5). Pak dostáváme A.AT = 1 i -i 1 . 1 -i i 1 = 0 0 0 0 = r(A.AT ) = 0. AT .A = 1 -i i 1 . 1 i -i 1 = 0 0 0 0 = r(AT .A) = 0. Podstata problému tkví v tom, že prvky například matice AT .A jsou sice konstruovány podobně jako u Gramovy matice v 4.14(9), tj. jsou ve tvaru výrazů x1y1 + x2y2, kde x a y jsou vybrány ze sloupců A. Tyto výrazy jsou skalárními součiny v R, nikoliv avšak v C, kde ztrá- címe platnost axiomu (S3) a tím i ortogonalitu: například pro sloupce A máme [1, -i], [i, 1] = 1.i + (-i).1 = 1.(-i) + (-i).1 = -2.i = 0, i když 1.i+(-i).1 = 0. Vzhledem k 3.68 tak nemáme garantovánu ani lineární nezávislost, kterou jsme v tomto příkladu skutečně ztratili. Ztratili jsme takto dokonce i vlastnost ortogonálního rozkladu dle 3.88(5)(i), přestože 3.88(5)(v) platí dle 4.29(4): dim N(A) = dim C2 - r(A) = 2 - 1 = 1. Totiž C2 nemůže být ortogonálním součtem pod- prostorů R(AT ) a N(A), neboť není ani jejich přímým součtem: 1. sloupec v A.AT je roven A.[1, i]T = [0, 0]T [1, i]T N (A). Současně ale také AT .[1, 0]T = [1, i]T [1, i]T R(AT ) a tedy 0 = [1, 0]T R(AT ) N(A) 3.43 R(AT ) + N(A) = R(AT ) N(A). POZNÁMKA 4.32 (Maticový zápis bilineární a kvadratické formy). Nechť A =: [aij] je čtvercová matice řádu n a x =: [x1; . . . ; xn], y =: [y1; . . . ; yn] vektory z Fn . Bilineární forma určená maticí A je funkce Fn ×Fn F definovaná vztahem: yT .A.x = ni =1 ( nj =1 aijxj)yi = ni =1 nj =1 aijyixj, kde výraz v závorce je i-tá složka vektoru A.x. Pro x = y bilineární forma přejde v zobrazení Fn F a nazývá se 109 kvadratickou formou určenou maticí A: xT .A.x = ni =1 nj =1 aijxixj. V případě F R je můžeme vzhledem k 4.14(9) a 4.15(6) vyjádřit také pomocí skalárního součinu: yT .A.x = A.x, y , resp. xT .A.x = A.x, x , což je v souladu s poznámkou 3.84. V komplexním případě F C užijeme A místo AT , takže dostáváme vyjádření: A.x, y = y .A.x = ni =1 nj =1 aijyixj, A.x, x = x .A.x = ni =1 nj =1 aijxixj. Matice A se nazývá pozitivně semidefinitní (pozitivně defi- nitní), jestliže určuje operátor, který je pozitivní (striktně pozitivní) ve smyslu poznámky 3.84. V takovém případě kvadratická forma nabývá pouze reálných nezáporných hodnot (kladných hodnot pro x = 0) a A je hermitovsky symetrická matice. 110 4.4. PŘEVOD NA SCHODOVITÝ TVAR A LU-ROZKLAD. Věta 4.29 sice uvádí některé užitečné vlastnosti hodnosti matic umož- ňující její zjištění v některých speciálních případech, nikoliv však obecně pro libovolnou zadanou matici A, řekněme typu m/n. V tomto odstavci odvodíme univerzální algoritmus tzv. Gaussovy eliminace, který požadovanou úlohu beze zbytku řeší a navíc dává konstrukci báze obou prostorů svázaných s maticí (operátorem) A, tj. jak oboru hodnot R(A), tak jádra N(A). Jako jeho důsledek obdržíme navíc tzv. LU-rozklad matice A, který představuje jeden z mnoha mož- ných skeletních rozkladů. Na rozdíl od důkazu věty 4.22, který byl nekonstruktivní, Gaussova eliminace poskytuje (nikoliv obecně jed- noznačnou) konstrukci takového rozkladu. Princip Gaussovy eliminace spočívá v postupném provádění elemen- tárních řádkových úprav16 , které nemění hodnost matice. V zásadě vystačíme pouze s úpravami typu (5) a (8) z věty 4.24 a to dokonce ve zjednodušené podobě: záměna dvou řádků a přičtení skalárního násobku nějakého řádku k jinému řádku. V dalším zkonstruujeme speciální regulární transformační matice, kterými budeme danou ma- tici postupně násobit zleva -- viz též 4.24(3). Výsledkem bude převod zadané matice A na schodovitý tvar, jehož hodnost (shodná s r(A)) se snadno zjistí podle 4.30. DEFINICE 4.33 (Transformační matice pro některé řádkové úpravy). Nechť m je řádkový rozměr transformované matice A. (1) Záměna i-ho a j-ho řádku: Nechť := ij značí permutaci provádějící záměnu indexu i a j. Pak zřejmě = -1 . Označíme-li P i,j := P odpovídající permutační matici řádu m, pak P i,j = P -1 i,j 4.28(3) = P T i,j a tedy při násobení touto maticí zleva (zprava) dochází k záměně i-tého a j-tého řádku (sloupce) -- viz 4.14(11). V případě i = j je P ii = Im identita. 16Obdobně je možno provádět sloupcové úpravy. Jelikož je lze transpozicí matice vždy převést na řádkové úpravy, upřednostňujeme nadále tento případ. 111 (2) Přičtení -násobku j-ho řádku k i-tému (i = j): Nechť pro F značí R () ij := Im + Eij čtvercovou matici řádu m. Tato matice je trojúhelníková s jednotkovou diagonálou, prvkem v i-tém řádku a j-tém sloupci a nulami všude jinde. Zřejmě platí R ()T ij = R () ji , přičemž při násobení maticí R () ij zleva (maticí R () ji zprava) dochází k přičtení -násobku j-tého řádku (sloupce) k i-tému řádku (sloupci). (3) Vynásobení i-ho řádku skalárem = 0: Podle 4.14(10) je příslušnou transformační maticí diagonální matice D () i := diag(1, . . . , 1, , 1, . . . , 1), kde je i-tým prvkem na jinak jednotkové diagonále. Věta 4.34 (Vlastnosti transformačních matic P ij, R () ij a D () i ). Všechny uvedené matice jsou regulární a platí pro ně: (1) Nechť index j je pevný a i F je m skalárů (i = 1, . . . , m), kde j = 0. Pak R () j := R (1) 1j . . . R (m) mj je jednotková ma- tice, k jejímuž j-tému sloupci je přičten vektor := [1, . . . , m]T . Tato matice realizuje složení m řádkových úprav: k i-tému řádku je přičten i-násobek j-tého řádku pro i = 1, ..., m. Na pořadí provádění těchto úprav (tj. na pořadí násobení matic R (i) ij ) přitom nezáleží. Zřejmě = 0 R () j = Im. (2) Výsledná matice R () j je regulární a pokud i = 0 pro i j (i j), pak je navíc dolní (horní) trojúhelníková. V takovém případě budeme obvykle psát L () j (U () j ) místo17 R () j . Inverzní matice je určena vztahem: (R () j )-1 = R (-) j . Je tedy téhož typu, kde pouze skaláry mají obrácené zna- ménko. Zejména také dostáváme (R () ij )-1 = R (-) ij , neboť R () ij je speciálním případem matice R () j , kde i = a k = 0 pro k = i. 17Značení je dáno zvyklostmi anglosaské odborné literatury: písmeno L, resp. U je odvozeno od počátečních písmen slov Lower a Upper. 112 (3) Pro libovolné tři indexy i, j, k {1, . . . , m}, i = j, k = j platí P ik.R () j = R (P ik.) j .P ik. Tedy matice P ik a R () j jsou při násobení záměnitelné až na pořadí skalárů ve vektoru , kde dojde k záměně jeho složek i a k. (4) L := L (1) 1 .L (2) 2 . . . L (m) m a U := U (m) m .U (m-1) m-1 . . . U (1) 1 je po řadě regulární dolní a horní trojúhelníková matice s jed- notkovou diagonálou, kde L(i, j) = j(i) a U(i, j) = j(i) pro každé i = j, neboli sloupce v L, resp. U odpovídají po řadě příslušným sloupcům matic L (j ) j , resp. U (j ) j . Pozna- menejme, že na rozdíl od (1) v tomto případě již záleží na pořadí provádění úprav (tj. na pořadí násobení matic L (j ) j , resp. U (j ) j ). (5) D (1) 1 .D (2) 2 . . . D (m) m = diag(1, 2, . . . , m) je při všech nenulových i = 0 regulární diagonální matice. Tato ma- tice realizuje složení m řádkových úprav: i-tý řádek je vynáso- ben skalárem i pro i = 1, ..., m. Na pořadí provádění těchto úprav (tj. na pořadí násobení matic D (i) i ) přitom nezáleží. Důkaz. Pro větší názornost zobrazme nejprve strukturu matice R () j : R () j = 1 . . . 0 1 0 . . . 0 . . . 0 ... ... ... ... ... ... ... ... ... 0 . . . 1 j-1 0 . . . 0 . . . 0 0 . . . 0 1 0 . . . 0 . . . 0 0 . . . 0 j+1 1 . . . 0 . . . 0 ... ... ... ... ... ... ... ... ... 0 . . . 0 i 0 . . . 1 . . . 0 ... ... ... ... ... ... ... ... ... 0 . . . 0 m 0 . . . 0 . . . 1 . 113 Všechny uvažované matice jsou buď trojúhelníkové nebo diagonální s jednotkovou diagonálou, případně jsou součinem takových matic. Podle 4.27 a případně i s ohledem na 4.24(4) jsou tedy regulární. Součin dolních (horních) trojúhelníkových matic je opět matice téhož typu dle 4.14(12). Strukturu matic ve tvaru součinu si čtenář snadno odvodí jako snadné cvičení provedením tohoto součinu, resp. přísluš- ných řádkových úprav při postupném násobení zprava doleva. Při důkazu tvrzení (2) stačí podobně na základě věty 4.25 ověřit přímým vynásobením platnost identit: R (-) j .R () j = R () j .R (-) j = Im.P oznámka 4.35. Je-li A matice typu m/n, pak s uvážením 4.14(8)b) snadno nahléd- neme, že R () j .A = A + .A(j, :). Maticový výraz vpravo tak před- stavuje alternativní způsob provedení stejných řádkových úprav v matici A, jaké odpovídají násobení maticí R () j zleva. V některých situacích může být tento druhý způsob z hlediska programové imple- mentace efektivnější, neboť není třeba dopředu vytvářet a do paměti ukládat matici R () j , která je řídká (má velké množství nulových prvků), což může vést k plýtvání pamětí. VĚTA 4.36 (Převod matice na schodovitý tvar Gaussovou elimi- nací18 ). Každá matice se dá konečným počtem řádkových elementár- ních transformací typu 4.33(1),(2) převést na matici ve schodovitém tvaru o stejné hodnosti. DŮKAZ. Důkaz této věty je konstruktivní, to znamená, že dává po- stup řešení této úlohy, který je možno použít v konkrétním případě. Tento postup bývá nazýván Gaussův algoritmus a spočívá v následu- jících krocích pro matici A =: [aij] typu m/n: (G0) Jestliže matice A je nulová, již je ve schodovitém tvaru a jsme hotovi. (G1) V opačném případě nechť j1 je index prvního nenulového sloupce. Existuje tedy k N, 1 k m tak, že akj1 = 0. 18 viz též skripta [KaSk:V9.3 s.80-81] nebo [Šik:V1.26 s.9-10] 114 Řádek k-tý vyměňme s prvním řádkem, pokud k = 1. Tím dostaneme matici B =: [buv] typu m/n takovou, že sloupce 1, 2, . . . , j1 - 1 jsou nulové a b1j1 = 0. (G2) V matici B ke každému u-tému řádku (2 u m) při- čteme první řádek vynásobený číslem - buj1 b1j1 . Dostaneme ma- tici C = [cuv] typu m/n takovou, že sloupce 1, 2, . . . , j1 - 1 jsou nulové, c1j1 = 0 a cuj1 = 0 pro každé 2 u m. Tím je určen první řádek hledané schodovité matice. Není-li matice C ještě ve schodovitém tvaru, aplikujeme kroky (G1) a (G2) na subma- tici C([2, . . . , m], :). Po jejich provedení bude druhý řádek celé matice druhým řádkem hledané schodovité matice, atd. Tímto způsobem po- stupujeme tak dlouho, až obdržíme matici ve schodovitém tvaru, tj. jakmile buď byl proveden maximální možný počet kroků m a nebo všechny zbývající řádky jsou již nulové.D ůsledek 4.37 (Maticový zápis Gaussovy eliminace). Nechť A je matice typu m/n, r(A) = r. Pak Gaussova eliminace reku- rentně konstruuje posloupnost matic A =: A0 A1 Ar =: S téže hodnosti, kde S =: [sij] je schodovitá matice s r nenulovými řádky (schody) a horní trojúhelníkovou submaticí řádu r s diagoná- lovými prvky siji = 0, 1 j1 < < jr n (viz 4.6). Nechť pro i {1, . . . , r} byla již zkonstruována matice Ai-1. Pak Ai dostaneme ve dvou krocích takto: (G1) Záměna i-tého a k-ho řádku v matici Ai-1: Bi := P i.Ai-1 =: [buv], kde P i := P ik pro vhodné i k m takové, že Ai-1(k, ji) = 0 (k závisí na i). Takto zajistíme biji = 0. (G2) Eliminace koncové části ji-tého sloupce v matici Bi: Ai := L (i) i .Bi, kde i = [0, . . . , 0 i × , - bi+1ji biji , . . . , - bmji biji ]T . Sloučením obou kroků do jednoho dostáváme rekurentní vztah: Ai = L (i) i .P i.Ai-1 pro i = 1, . . . , r. 115 Sloučením všech kroků, pak dostáváme: R.A = S, kde R := L (r) r .P r . . . L (2) 2 .P 2.L (1) 1 .P 1 je regulární ma- tice řádu m realizující provedení všech elementárních úprav převodu na schodovitý tvar. Důkaz. Transformační vztahy jsou důsledkem 4.33(1) a 4.34(1)(2), kde transformační matice R (i) i = L (i) i je skutečně dolní trojú- helníková, neboť i(u) = 0 pro u i. Volba i(u) = - buji biji pro i+1 u m pak zajistí požadovanou eliminaci koncové části ji-tého sloupce, neboť přičtením i(j)-tého násobku i-tého řádku matice Bi k jejímu u-tému řádku dostáváme: a) ji-tý sloupec: Ai(u, ji) = buji + i(u)biji = buji + (- buji biji )biji = 0. b) Úvodní sloupce pro 1 v < ji: Ai(u, v) = buv + i(u)biv = 0 zůstávají nulové, neboť buv = biv = 0 byly nulové již z předchozích kroků. Regularita výsledné transformační matice R je důsledkem 4.24(4) a regularity všech zúčastněných matic.D ŮSLEDEK 4.38 (LU-rozklad matice). Platí L.S = P .A, kde L =: [lui] je čtvercová dolní trojúhelníková ma- tice řádu m s jednotkovou diagonálou (lii = 1 pro i = 1, . . . , m) a pod hlavní diagonálou s prvky lui = bu ji bi ji pro i = 1, . . . , r 0 pro i = r + 1, . . . , m , kde u = i+1, . . . , m a bu ji jsou prvky z ji-tého sloupce matice Bi := Ai-1 ze všech r kroků (G1) provedených během Gaussovy eliminace pře- dem permutované matice P .A, přičemž P = P r . . . P 2.P 1 je matice permutace vzniklé složením všech r řádkových záměn provedených v krocích (G1) během Gaussovy eliminace původní nepermutované ma- tice A. 116 ˇ Označíme-li L : = L(:, [1, . . . , r]) a S = S([1, . . . , r], :) submatice po řadě v L, resp. S tvořené jejich prvými r sloupci, resp. řádky, do- stáváme modifikovaný rozklad L . S = P .A. ˇ Je-li speciálně A čtvercová a regulární, pak L = L a S = S =: U, kde U je horní trojúhelníková matice s nenulovou diagonálou, takže dostáváme rozklad L.U = P .A, který je obvykle nazýván LU-rozkladem matice A. V dalším takto budeme nazývat i kterýkoli z výše uvede- ných obecnějších rozkladů L.S = P .A nebo L . S = P .A, které jsou platné pro libovolnou matici A. Důkaz. Matice L má tuto strukturu: L = 1 0 . . . 0 0 . . . 0 b2 j1 b1 j1 1 . . . 0 0 . . . 0 ... ... ... ... ... ... ... br j1 b1 j1 br j2 b2 j2 . . . 1 0 . . . 0 br +1j1 b1 j1 br +1j2 b2 j2 . . . br +1jr brjr 1 . . . 0 ... ... ... ... ... ... ... bm j1 b1 j1 bm j2 b2 j2 . . . bm jr brjr 0 . . . 1 . ˇ Konstrukce rozkladu L.S = P .A: Dle 4.37 platí S = R.A, kde R := L (r) r .P r . . . L (2) 2 .P 2.L (1) 1 .P 1. Užijme opakovaně 4.34(3) pro postupné provádění záměn: P 2.L (1) 1 = L (P 2.1) 1 .P 2, P 3.L (2) 2 = L (P 3.2) 2 .P 3, P 3.L (P 2.1) 1 = L (P 3.P 2.1) 1 .P 3, atd. Po jejich provedení obdržíme: S = L (r) r .L (P r.r-1) r-1 . . . L (P r...P 3.2) 2 .L (P r...P 2.1) 1 . P r . . . P 1 P .A. Odtud:L(r) r .L (P r.r-1) r-1 . . . L (P r...P 3.2) 2 .L (P r...P 2.1) 1 -1 .S = P .A. 117 Stačí jen upravit inverzi ze součinu matic vlevo, kterou označíme L: L := L(r) r .L (P r.r-1) r-1 . . . L (P r...P 3.2) 2 .L (P r...P 2.1) 1 -1 4.28(2) = L(P r...P 2.1) 1 -1 . L(P r...P 3.2) 2 -1 . . . L(P r.r-1) r-1 -1 . L(r) r -1 4.34(2) = L (-P r...P 2.1) 1 .L (-P r...P 3.2) 2 . . . L (-P r.r-1) r-1 .L (-r) r . L (0) r+1 . . . L(0) m = Im . Matice L má dle 4.34(4) požadovanou strukturu. K tomu stačí jen uvážit, že permutace P r . . . P i+1 prováděné s vektory koeficientů i z úpravy matice A přesně odpovídají nepermutovaným vektorům i koeficientů z úpravy předem permutované matice P .A, kdy krok (G1) vynecháváme, neboť pro každé i = 1, . . . , r již máme předem zajiš- těno Ai-1(i, ji) = 0, tj. P i = Im a tedy Bi := Ai-1 pro každé i = 1, . . . , m. ˇ L . S = L.S: Stačí uvážit, že posledních m - r řádků schodovité matice S je nulo- vých, takže při násobení maticí L zleva na jejích hodnotách v posled- ních m - r sloupcích nezáleží (jsou během součinu násobeny nulami). ˇ Případ regulární čtvercové matice A: V tomto případě m = r, takže L = L a S = S . Navíc také n = r, takže S je čtvercová řádu r a dle 4.6 současně obsahuje regulární horní trojúhelníkovou submatici U téhož řádu r. To může nastat, jen když S = U.D ŮSLEDEK 4.39 (Konstrukce báze prostoru R(A)). Nechť A je matice typu m/n a A = L.S = L . S j e její LU-rozklad, kde U = S ( :, [j1, . . . , jr]) je regulární horní trojúhelníková subma- tice v S . Pak sloupce matice L t voří bázi prostoru R(A) a rovněž A(:, j1), . . . , A(:, jr) tvoří jeho sloupcovou bázi. DŮKAZ. Sloupce L j sou lineárně nezávislé, neboť jsou vybrány z nezávislé množiny sloupců regulární matice L, tvoří tak bázi v R(L ) a sou- časně L j e sloupcově plné hodnosti. Dále A(:, [j1, . . . , jr]) = L . S ( :, [j1, . . . , jr]) = L . U 4.24(1) 118 r(A(:, [j1, . . . , jr])) = r(S) = r 4.36 = r(A) sloupce A(:, j1), . . . , A(:, jr) jsou lineárně nezávislé a tvoří proto podle 3.24(4)(ii) bázi prostoru R(A), neboť dim R(A) = r. Z vyjádření A = L . S s oučasně plyne (viz 4.13a)), že každý sloupec matice A (tj. každý z generátorů prostoru R(A)) je lineární kom- binací sloupců L , tj. patří do R(L ) . Pak A(:, j1), . . . , A(:, jr) musí také tvořit bázi v R(L ) a oba prostory jsou proto stejné.D ŮSLEDEK 4.40 (Konstrukce báze prostoru N(A)). Nechť A je matice typu m/n a A = L . S j e její LU-rozklad, kde U = S ( :, [j1, . . . , jr]) je regulární horní trojúhelníková submatice v S . Nechť S j e submatice v S t vořená zbývajícími n - r sloupci nezařazenými do matice U. Buď Q vhodná permutační matice, kterou přeuspořá- dáme sloupce S t ak, aby U byla prvním blokem a S d ruhým blo- kem: S . Q = [U, S ] . Pak n - r sloupců blokově sestavené matice N =: Q.[-U-1 .S ; In-r] Mn,n-r tvoří bázi prostoru N(A). DŮKAZ. Všech n - r sloupců matice N je zřejmě lineárně nezávis- lých, neboť N obsahuje regulární submatici maximálního možného řádu n-r (viz 4.29(3)). Podle téže věty dim N(A) 4.29(4) = n-r, takže stačí ukázat, že každý sloupec matice N patří do N(A). Podle 4.15(1) je tedy třeba ověřit, že A.N je nulová matice: A.N = L . S Q .QT .N = L . [U, S ] .QT .Q.[-U-1 .S ; In-r] = L . [U, S ] .[-U-1 .S ; In-r] = L . (-U.U-1 .S + S . In-r) = L . (-S + S ) = 0n,n-r.P oznámka 4.41. (1) Při konstrukci báze prostoru N(A) dle 4.40 se inverzní ma- tice U-1 snadno spočte postupem naznačeným v důkazu 4.28(4). V rovnici Ir = X.U postupně počítáme neznámé prvky matice X := U-1 srovnáváním prvého sloupce vlevo a vpravo (tím spočteme prvý sloupec X), pak prvého řádku vlevo a vpravo (tím dopočteme prvý řádek X), pak podobně pro druhý sloupec a řádek, atd. Alternativně můžeme také 119 řešit maticovou rovnici U.X = -S p ostupně pro jednot- livé sloupce: U.X(:, j) = -S ( :, j), což je vzhledem k trojú- helníkové struktuře matice U snadné (podrobněji bude pro- bráno později v odstavci věnovaném řešení systémům line- árních rovnic). Obdržíme tak matici X = -U-1 .S , což je právě horní blok ve vyjádření řádkově permutované ma- tice N. (2) LU-rozklad A = L . S n ení nic jiného než speciální případ skeletního rozkladu 4.22, kde L h raje roli matice B a Sh raje roli matice C. Porovnání obou rozkladů ukazuje, že se liší ve dvou aspektech: ˇ Roli regulární jednotkové submatice řádu r v B nyní hraje horní trojúhelníková submatice U řádu r v S . Konstrukce prostoru N(A) popsaná v důkazu tvrzení 4.29(4) koresponduje s konstrukcí ze 4.40: jestliže U na- hradíme jednotkovou maticí Ir, tak horní blok -U-1 .Sv e vyjádření N přejde v matici -I-1 n .S = -S , která koresponduje s maticí -C . Nevýhodou je nutnost vy- počítat -U-1 .S , což dle (1) odpovídá řešení maticové rovnice U.X = -S . ˇ Konstrukce LU-rozkladu je konstruktivní, zatímco dů- kaz 4.22 nikoliv: u konkrétní matice totiž obvykle není snadné určit její sloupcovou bázi pro konstrukci B. Te- oreticky bychom mohli sice využít 4.39. Mnoho bychom si však nepomohli, protože nalezení C by vyžadovalo řešit vzhledem k C maticovou rovnici A = B.C, což opět není snadné, neboť B nemá obecně žádnou spe- ciální strukturu, která by toto usnadnila. Tyto kompli- kace zdaleka nejsou vyváženy výhodou snadného nale- zení báze prostoru N(A), které nevyžaduje řešení žádné inverzní úlohy. (3) LU-rozklad není jediným užitečným rozkladem skeletního typu. Další hojně využívaný (jen pro F C) je tzv. QR-rozklad: 120 A = Q.R. Jeho výhodou je, že sloupce matice Q tvoří orto- normální bázi prostoru R(A), matice R je horní trojúhelní- ková a dle 4.13a) její sloupce opět představují vektory sou- řadnic sloupců matice A v ONB dané maticí Q. Sloupce Q lze vždy doplnit na ONB celého prostoru Fm (viz 3.79) a matici R pak stejným počtem nulových řádků. Můžeme tedy bez újmy na obecnosti předpokladat, že Q je unitární matice: analogie s LU-rozkladem, kde regulární matici L můžeme po- važovat za doplnění sloupcové báze L p rostoru R(A) na bázi celého prostoru Fm . QR-rozklad se s výhodou užívá místo Gram-Schmidtova al- goritmu 3.78 k nalezení ONB prostoru R(A). Ten totiž trpí numerickou nestabilitou v situacích, kdy některý sloupcový vektor matice A je blízký lineární kombinaci ostatních. Při numerických výpočtech se proto doporučuje dávat přednost QR-algoritmu. Teoretické odvození QR-rozkladu jde nad rá- mec tohoto kurzu. Čtenář jej může najít například ve skrip- tech [Šik : odst. 13.2 s.105 - 110]. (4) Jordanova eliminace je modifikací Gaussovy eliminace, kdy v matici A eliminujeme postupně nejen pod diagonálou, ale i nad diagonálou. Regulární horní trojúhelníková submatice S([1, . . . , r], [j1, . . . , jr]), ve schodovitém tvaru se tak stane diagonální maticí s nenulovou diagonálou (r = r(A)). Mů- žeme také postupovat tak, že eliminujeme horní části sloupců S([1, . . . , i + 1], ji), i = 1, . . . , r ve schodovitém tvaru S až dodatečně. Jestliže každý řádek takto získané diagonální sub- matice S([1, . . . , r], [j1, . . . , jr]) navíc vydělíme nenulovým di- agonálním prvkem siji , i = 1, . . . , r (neboli násobíme S zleva postupně regulárními transformačními maticemi D (1/siji ) i pro i = 1, . . . , r), přejde S([1, . . . , r], [j1, . . . , jr]) dokonce v jed- notkovou matici Ir. Výše uvedeným postupem lze tedy každou regulární matici A převést na jednotkovu matici In, neboť v tomto případě 121 r = n. Na závěr poznamenejme, že příslušná transformační matice R realizující Jordanovu eliminaci na diagonální tvar (ať obecný či s jednotkovou diagonálou) sice zůstane regulární, ztratí však svůj dolní trojúhelníkový tvar. Podobně v příslušném LU-rozkladu již ani matice L nebude dolní trojúhelníková, ale jen regulární. Relevantní procedury v MATLABu: rref . . . převod matice na schodovitý tvar a určení sloupcové báze (rref=reduced row echelon form) lu . . . nalezení LU-rozkladu matice qr . . . nalezení QR-rozkladu matice orth . . . nalezení ONB prostoru R(A) užitím QR-rozkladu null . . . nalezení ONB prostoru N(A). 122 4.5. PERMUTACE, DETERMINANT A STOPA MATICE. V tomto odstavci zavedeme dvě z nejdůležitějších skalárních veličin přiřazovaných k matici: determinant matice a stopu matice. Pojem determinantu patří mezi základní pojmy lineární algebry. V tomto odstavci uvedeme některé jeho základní vlastnosti a metody jeho výpočtu. Poznamenejme, že v dnešní době je praktické použití determinantů na ústupu vzhledem k existenci efektivnějších algoritmů pro řešení úloh, v nichž se tradičně používaly (řešení systému lineár- ních rovnic, inverze matice aj.) Nicméně pro teoretickou oblast li- neární algebry, vyjadřování různých algebraických i geometrických vlastností je pojem determinantu stále nezbytný. Pojem determinantu se vztahuje ke čtvercovým maticím následovně: Každé čtvercové matici A = [aij] řádu n je podle přesně uvedeného pravidla (viz dále 4.44) přiřazen skalár z F (obvykle reálné nebo kom- plexní číslo) nazývané determinantem matice A a označované sym- boly det A nebo a 11 a1n ... ... an1 ann = : |A|. I když je det A skalár, užíváme pro determinant názvy týkající se ma- tic a rozumíme jimi názvy pojmů matice A. Tak například mluvíme o řádku determinantu, sloupci, hlavní diagonále determinantu a pod. Ke přesné definici determinantu je nezbytné nejprve zavést pojem parity permutace. DEFINICE 4.42 (Parita permutace [Šik:odst.2.1 s.12]). Nechť je permutace nějaké n-prvkové úplně uspořádané množiny J. Bez újmy na obecnosti můžeme předpokládat J = {1, 2, . . . , n}. Jestliže označíme (i) := i, pak pro permutaci budeme používat buď jednořádkový zápis [] := [1, 2, . . . , n] 123 nebo dvouřádkový zápis = 1 2 . . . n 1 2 . . . n n ebo případně i 1 i2 . . . in j1 j2 . . . jn , kde i1, i2, . . . , in jsou prvky J uspořádané v jiném pořadí a jk = (ik) pro k = 1, 2, . . . , n. Říkáme, že i, j stojí v inverzi, jestliže i < j a i > j. Per- mutace se pak nazývá sudá, resp. lichá, když (-1)p = +1, resp. (-1)p = -1, kde p je počet inverzí permutace (neboli když v per- mutaci je sudý, resp. lichý počet navzájem různých dvojic i, j stojících v inverzi). Číslo sgn := (-1)p se pak nazývá paritou nebo také znaménkem permutace . Jestliže existuje k > 1 navzájem různých prvků K := {i1, . . . , ik} množiny J takových, že [i1 , . . . , ik ] představuje permutaci množiny K, pak tuto permutaci nazýváme cyklem permutace a číslo k dél- kou cyklu. Cyklům délky 2 se říká záměna prvků i1 a i2. VĚTA 4.43 (Vlastnosti parity permutace). (1) Identická permutace má sudou paritu. (2) Inverzní permutace k permutaci má stejnou paritu: sgn -1 = sgn . (3) Při skládání permutací se jejich parity násobí: sgn (12) = sgn (21) = sgn 1.sgn 2. (4) Záměnou dvou různých prvků v jednořádkovém zápisu per- mutace dostaneme novou permutaci s opačnou paritou (zna- ménkem). (5) Jsou-li [] a [ ] jednořádkové zápisy dvou permutací, pak jeden z druhého se dá dostat posloupností záměn19 a obě per- mutace mají stejnou (různou) paritu právě když počet záměn je sudý (lichý). (6) Počet všech permutací je n!, přičemž pro n > 1 je toto číslo sudé, jedna polovina permutací má sudou paritu a druhá po- lovina lichou paritu. 19dokonce se můžeme omezit jen na záměny sousedních prvků. 124 Důkaz. (1) V identické permutaci nevystupuje žádná inverze (-1)0 = 1 a parita je tedy sudá. (2) i, j jsou v inverzi i < j a k := i > j =: l l < k a j = -1 (l) > -1 (k) = i -1 (l), -1 (k) jsou v inverzi. Tedy i -1 mají stejný počet inverzí a tudíž i stejnou paritu. (3) Nechť := 21, p1 je počet inverzí v 1 a p2 počet in- verzí v 2. Pak každá z p2 inverzí permutace 2 buď zruší nějakou existující inverzi v 1 nebo ji naopak přidá. Pro- tože (-1)p1+1 = (-1)p1-1 , bude mít paritu (-1)p1+p2 = (-1)p1 (-1)p2 = (sgn 1)(sgn 2). Pro 12 analogicky zámě- nou role 1 a 2. (4) Nechť i < j a [] = [1 . . . i . . . j . . . n], [ ] = [1 . . . j . . . i . . . n]. Pokud i, j jsou sousední (j - i = 1), dojde ke změně inverze jen jednou a to u dvojice i, j. Tedy parita permutace se změní. Pokud j - i > 1, změní se navíc inverze ještě všech indexů k, kde i < k < j, a to jak vzhledem k i, tak vzhledem j. Takových indexů k je j - i - 1, takže celkový počet změn je liché číslo 2(j - i - 1) + 1 a tudíž i v tomto případě dojde ke změně parity permutace. (5) [ ] dostaneme ze [] následující posloupností záměn: Je-li i1 = 1 a i1 = 1, pak záměnou 1 a i1 dosáhneme správ- ného umístění 1 na první pozici. Podobně pro i2 = 2 a i2 = 2 záměnou 2 a i2 umístíme 2 správně na druhou po- zici, atd. Každou záměnu na pozicích, které nejsou sousední přitom jistě můžeme nahradit posloupností záměn sousedních prvků. (6) Pro n > 1 je n! = 1.2 . . . sudé číslo. Vyberme libovolně ně- jakou permutaci (J). K [] můžeme dle (4) přiřadit permutaci [ ] opačné parity záměnou prvých dvou prvků v 125 []. Ze zbylého sudého počtu n! - 2 permutací opět analo- gicky vytvoříme další obdobnou dvojici. Celkem dostaneme n!/2 takových dvojic, kde jeden člen má sudou a jeden lichou paritu. D EFINICE 4.44 (Determinant). Nechť A =: [aij] je čtvercová matice řádu n a (J) množina všech permutací (card (J) = n!) množiny jejích sloupcových indexů J = {1, 2, . . . , n}. Pak číslo (skalár) det A := (J) (sgn )a11 . . . ann nazýváme determinantem matice A. Součin a11 . . . ann nazýváme členem determinantu a sgn jeho znaménkem. Poznámka 4.45. Z definice plyne, že každý člen determinantu se do- stane jako součin prvků matice A vybraných přesně po jednom z každého jejího řádku. Podle věty 4.43(6) je počet všech členů n!, při- čemž pro n > 1 jedna polovina z nich má kladné a druhá polovina záporné znaménko. VĚTA 4.46 (Základní vlastnosti determinantu [Šik:V2.6 s.14]). Nechť A =: [aij] =: [a1; . . . ; an] je matice řádu n a a1, . . . , an její řádky. Pak platí (1) Obsahuje-li A nulový řádek, pak det A = 0. (2) Je-li b =: [b1, . . . , bn] řádkový vektor, pak pro matici zís- kanou z A přičtením vektoru b k jejímu i-tému řádku ai 126 (i = 1, . . . , n) platí: det a1 ... ai-1 ai + b ai+1 ... an = det a1 ... ai-1 ai ai+1 ... an A + det a1 ... ai-1 b ai+1 ... an . (3) Výměnou dvou různých řádků v matici A se změní znaménko jejího determinantu det A. (3a) Důsledek 120 : Má-li A dva různé řádky stejné, pak det A = 0. (3b) Důsledek 2: Je-li nějaká permutace množiny {1, . . . , n} a P příslušná permutační matice (viz 4.14(6)), pak det P = sgn . Zejména det P i,j = -1, kde P i,j je permutační matice řádu n pro záměnu i-ho a j-tého řádku jako v definici 4.33(1). (3c) Důsledek 3: det(P A) = det P . det A = sgn . det A a po- dobně det(AP ) = det A. det P = sgn . det A. Zejména det(P i,jA) = det P i,j. det A = - det A a podobně det(AP i,j) = det A. det P i,j = - det A. (4) Determinant trojúhelníkové (diagonální) matice je roven sou- činu jejích prvků v hlavní diagonále. (4a) det In = 1, kde In je jednotková matice řádu n. (5) det AT = det A. (5a) Důsledek: Všechny výroky této věty týkající se řádků platí i pro sloupce. (5b) Důsledek: V případě F C platí det A = det A. 20Toto tvrzení platí jen když pole skalárů F nemá charakteristiku 2 (srov. 2.71), tedy například pro F = R nebo F = C, což jsou pole nekonečné charakte- ristiky (viz příklad 2.76). 127 (6) Nechť A j e matice získaná z A vynásobením některého jejího řádku skalárem , pak det A = . det A. (6a) Důsledek 1: det D () i = , kde D () i je transformační matice řádu n jako v definici 4.33(3). (6b) Důsledek 2: det(D () i A) = det D () i . det A = . det A a po- dobně det(AD () i ) = det A. det D () i = . det A. (6c) Důsledek 3: det(.A) = n . det A. (7) det A se nemění přičtením -násobku j-ho řádku k i-tému (i = j). (7a) Důsledek 1: det R () ij = 1, kde R () ij je transformační matice řádu n jako v definici 4.33(2). (7b) Důsledek 2: det(R () ij A) = det R () ij . det A = det A a po- dobně det(AR () ij ) = det A. det R () ij = det A. (8) Je-li R součin transformačních matice typu P ij, R () ij nebo D () i pak det(RA) = det R. det A a det(AR) = det A. det R. (8a) Je-li T trojúhelníková (diagonální) matice řádu n, pak det(T A) = det T . det A a podobně det(AT ) = det A. det T . (9) Cauchyova věta o determinantu součinu matic: Pro libovol- nou čtvercovou matici B řádu n platí det(AB) = (det A).(det B). (10) Matice A je regulární (neboli dle 4.18b) má lineárně nezávislé řádky, resp. sloupce) právě když det A = 0. (11) Nechť X je čtvercová matice, pro niž platí AX = In (resp. XA = In), pak platí také druhá identita XA = In (resp. AX = In) a tedy X = A-1 (viz též větu 4.25)21 . (12) Když A-1 existuje, pak det A-1 = (det A)-1 . Důkaz. (1) Nechť ai je nulový řádek. Pak det A := (J)(sgn )a11 . . . aii . . . ann = 0, neboť aii = 0 pro každou permutaci (J). 21Toto tvrzení říká, že k definici inverzní matice stačí jen jeden z definičních vztahů AX = In nebo XA = In. 128 (2) Pro determinant na levé straně rovnosti platí vztah: (J) (sgn )a11 . . . (aii + bi ) . . . ann = (J) (sgn )a11 . . . aii . . . ann + (J) (sgn )a11 . . . bi . . . ann , což je právě součet determinantů matic vpravo. (3) Nechť B =: [bij] je matice vzniklá z A záměnou řádků ai a aj. Pak det B = (J) (sgn )b11 . . . bii . . . bjj . . . bnn = (J) (sgn )a11 . . . aji . . . aij . . . ann = (J) (-sgn ) a11 . . . aii . . . ajj . . . ann = - det A, neboť [ ] vznikla ze [] záměnou i a j, takže dle 4.43(4) sgn = -sgn v e všech členech determinantu. (3a) Nechť ai = aj pro i = j. Jejich záměnou se matice nezmění, takže det A = det B (3) = - det A. Odtud (2 det A) = 0 a tedy také det A = 0, pokud F nemá charakteristiku 2. (3b) Podle 4.43(5) se [] dá získat posloupností záměn z identické permutace. Pak dle 4.43(1)(4) sgn = (-1)p , kde p je počet takových záměn. Tvrzení je pak důsledkem (3) a (4a): P dostaneme z In pomocí p řádkových záměn, takže det P = (-1)p det In (4a) = (-1)p . (3c) P A je matice získaná z A pomocí p řádkových záměn ur- čujících jako ve (3b). Pak det(P A) (3) = (-1)p det A (3b) = det P . det A. 129 (4) Člen determinantu dolní trojúhelníkové matice může být ne- nulový jen když do něj nevybíráme nulové prvky nad hlavní diagonálou. V 1. řádku jediný takový prvek je a11, ve 2. řádku a21 již vybrat nelze, takže zbývá a22, atd. až z posledního řádku zbude také jen možnost ann. Jediný člen který může být nenulový je tedy a11 . . . ann, který odpovídá identické permutaci sudé parity. V případě horní trojúhelníkové ma- tice obdobně postupujeme odzdola nahoru. (4a) Plyne ze (4), neboť jednotková matice je speciální případ di- agonální matice. (5) Označíme-li AT =: [ai j], ai j := aji a a := a11 . . . ann člen determinantu det A, pak a = a 11 . . . a nn = a1-1(1) . . . an-1(n) je také členem determinantu det AT odpovídajícímu permu- taci -1 . Parita obou permutací je stejná dle 4.43(2), takže oba determinanty maji všechny členy stejné včetně znaménka. (5a) Zřejmé užitím (5). (5b) det A 4.10 = det AT 4.44 = det AT (5) = det A. (6) Z každého členu determinatu lze vytknout a tedy jej lze vytknout i z det A, který je jejich součtem. (6a) Matice det D () i vznikla z In vynásobením jejího i-ho řádku číslem . Pak tedy det D () i (6) = . det In (4a) = . (6b) Je důsledkem (6) a (6a). (6c) A je matice, jejíž každý řádek byl vynásoben číslem . Stačí aplikovat (6) postupně pro každý z n řádků. (7) Ve (2) položme b = aj. Užitím (6) pak poslední sčítanec bude ve tvaru součinu čísla s determinantem matice, v níž je řádek aj dvakrát. Podle (3a) je proto nulový a zůstane tak jen prvý sčítanec det A. (7a) Plyne ze (4a), neboť R () ij vznikne z jednotkové matice přičte- ním -násobku jejího j-tého řádku k i-tému. Tvrzení plyne také přímo ze (4), neboť R () ij je trojúhelníková matice s jed- notkovou diagonálou. 130 (7b) Je důsledkem (7) a (7a). (8) Dostane se opakovaným užitím (3c), (6b) nebo (7b). (8a) Nechť T =: [tij] je například horní trojúhelníková matice. Snadno nahlédneme, že T = D (tnn) n . . . R (t2n) 2n . . . R (t23) 23 D (t22) 2 R (t1n) 1n . . . R (t12) 12 D (t11) 1 . Násobení těmito maticemi v pořadí zprava doleva postupně vytváří 1. řádek, pak 2. řádek, atd. až poslední řádek ma- tice T . V případě dolní trojúhelníkové matice postupujeme obdobně od posledního řádku k prvnímu. Tvrzení je pak dů- sledkem (8). (9) Nechť P A = LU je LU-rozklad matice A dle 4.38. Pak det P . det(AB) (3c) = det(P AB) = det(L(UB)) (8a) = (det L. det U). det B (8a) = det(LU). det B = det(P A). det B (3c) = det P . det A. det B. Po zkrácení hodnotou det P (3b) = 1 do- stáváme požadovaný vztah. (10) Matice A řádu n je podle definice 4.17 regulární r(A) = n 4.37 po Gaussově eliminaci schodovitým tvarem matice A je horní trojúhelníková čtvercová matice S řádu n s nenulovou diagonálou pro schodovitý tvar S =: [sij] matice A platí 0 = s11 . . . snn (4) = det S (3),(7) = det A det A = 0. (11) Platí-li AX = In pro čtvercové matice A a X, pak 1 (4a) = det In = det(AX) (9) = (det A)(det X). Tedy zejména det A = 0 a tudíž podle (10) je matice A regulární a na základě 4.25 k ní existuje inverzní matice A-1 . Vynásobe- ním rovnice AX = In = AA-1 zleva maticí A-1 obdržíme X = A-1 AX = A-1 AA-1 = A-1 . (12) AA-1 = In (det A)(det A-1 ) (9) = det In (4a) = 1 a tedy det A-1 = (det A)-1 . 1 31 DEFINICE 4.47 (Minory, adjunkt matice). Nechť A je matice rozměru m × n a B = A([i1, . . . , ik], [j1, . . . , jk]), 1 i1 < < ik m, 1 j1 < < jk n její čtvercová subma- tice (viz též definici 4.2) řádu k min(m, n), pak det B nazýváme minorem (nebo též subdeterminantem) řádu k matice A. Tento minor budeme značit M := M i1,...,ik j1,...,jk (A). Doplňkovým minorem (stručně doplňkem) minoru M ve čtver- cové matici A řádu n při k < n rozumíme minor složený ze zbý- vajících řádků a sloupců matice A. Značíme jej C i1,...,ik j1,...,jk (A) nebo jen stručně C. Algebraický doplněk minoru M je C i1,...,ik j1,...,jk (A) := (-1)s C i1,...,ik j1,...,jk (A), kde s = i1 + + ik + j1 + + jk. Je-li minor složen z jediného prvku aij (tj. k = 1, i1 = i a j1 = j), pak jeho dopl- něk, resp. algebraický doplněk značíme Cij(A), resp. Cij(A). V tomto případě tedy platí Cij(A) = (-1)i+j Cij(A). Matice A : = [ai j], kde ai j = Cji(A) se nazývá adjunktem k matici A a značí se adj A. Poznámka 4.48 (Značení). Pokud nebude hrozit nedorozumění (pevně daná matice A), budeme nadále minory matice A a jejich doplňky označovat zjednodušeně M i1,...,ik j1,...,jk , C i1,...,ik j1,...,jk , Cij, C i1,...,ik j1,...,jk a Cij nebo jen M, C a C, pokud rovněž výběrové indexy budou pevně dány. V dalším budeme v případě čtvercové matice A řádu n pracovat s následujícími výrazy : R(i1, . . . , ik) := t 1,...,tk M i1,...,ik t1,...,tk C i1,...,ik t1,...,tk , S(j1, . . . , jk) := t 1,...,tk M t1,...,tk j1,...,jk C t1,...,tk j1,...,jk , kde t1, . . . , tk probíhají všechna přirozená čísla s vlastností 1 t1 < < tk n. Počet sčítanců v každém z výrazů je tedy n k . 132 VĚTA 4.49 (Laplaceova věta o rozvoji determinantu). Předpokládejme označení z poznámky 4.48. Pak pro každý výběr řád- kových indexů i1, . . . , ik, resp. sloupcových indexů j1, . . . , jk platí R(i1, . . . , ik) = S(j1, . . . , jk) = det A. Důkaz. Nechť M := M i1...ik j1...jk je nějaký minor matice A a C = (-1)s Mj eho algebraický doplněk, kde s := k t=1(it + jt). Položme J := {j1, . . . , jk} a J : = {1, . . . , n} - J1. 1) Předpokládejme nejprve, že M leží vlevo nahoře (it = jt = t), pak s := k t=1(t + t) = 2(1 + 2 + + k) je sudé číslo, takže jeden ze sčítanců M.C = M.M v e výrazu R(i1, . . . , ik) nabude tvaru M.M 4.44 = (J) (sgn )a11 . . . akk . (J ) (sgn ) ak+1,1 . . . an,n -k = (J) (J ) (sgn )a11 . . . akk (sgn ) ak+1,1 . . . an,n -k 4.43(3) = (J) (J ) (sgn ) a11 . . . akk ak+1,k+1 . . . ann , kde [ ] = [1, . . . , k, k+1, . . . , n] je permutace množiny {1, . . . , n} získaná složením dvou cyklů [] =: [1, . . . , k] a [ ] =: [1 , . . . , n -k], kde i =: k+i pro i = 1, . . . , n - k. Každý ze sčítanců je tedy jedním členem determinantu d := det A včetně správného znaménka. 2) Nechť nyní minor M je tvořen řádky a sloupci s obecnými indexy i1 < < ik a j1 < < jk. Přemístěme řádky a sloupce (sou- sedními výměnami) na prvních k pozic tak, aby se zachovalo jejich pořadí. Výměn řádků a sloupců bude celkem (i1 -1)+ +(ik -k)+(j1 -1)+ +(jk -k) = s-2(1+2+ +k). Výměnami přejde determinant d v nový determinant d 4.46(3) = (-1)s-2(1+2++k) d = (-1)s d, 133 kde M se přesune do levého horního rohu a jeho doplněk M d o pra- vého dolního rohu. Podle části 1) součin M.M b ude roven součtu některých členů determinantu d , opatřených znaménky, která jim přísluší v determinantu d . Tato znaménka se liší od znamének členů determinantu d jen faktorem (-1)s , takže M.C = M.(-1)s M j e sou- čet některých členů determinantu d, která jim přísluší v d. Je patrné, že sčítanci v M.C jsou (formálně) různí a jejich počet je k!(n - k)!. Když uvážíme, že lze vybrat n k m inorů z (pevně) zvolených k řádků matice A, bude všech sčítanců k!(n-k)! n k = k!(n-k)! n! k!(n-k)! = n!, tj. celkem součet všech členů determinantu d včetně správných zna- mének.U žijeme-li k výpočtu determinantu matice A výrazu R(i1, . . . , ik) resp. S(j1, . . . , jk), pak řekneme, že jsme jej počítali Laplaceovým rozvojem podle řádků i1, . . . , ik resp. sloupců j1, . . . , jk nebo že jsme det A rozvinuli (Laplaceovým rozvojem) podle řádků i1, . . . , ik resp. sloupců j1, . . . , jk. DŮSLEDEK 4.50 (Laplaceův rozvoj podle jednoho řádku/sloupce). Nechť i je nějaký řádkový, resp. j sloupcový index. Pak platí nt =1 aitCit = nt =1 atjCtj = det A. Lemma 4.51. Nechť A = [aij] je čtvercová matice řádu n a nechť i, j N, 1 i, j n. Pak platí: (1) n t=1 aitCjt(A) = 0 , jestliže i = j det A, jestliže i = j, (2) n t=1 atjCti(A) = 0 , jestliže i = j det A, jestliže i = j. Důkaz. Jestliže i = j, pak výraz (1) je dle 4.50 Laplaceův rozvoj det A podle i-tého řádku a obdobně výraz (2) Laplaceův rozvoj podle i-tého sloupce. 134 Jestliže i = j, pak výraz (1) je dle 4.50 Laplaceův rozvoj podle j-tého řádku determinantu matice, kde j-tý řádek byl nahrazen i-tým řád- kem. Obdobně výraz (2) představuje Laplaceův rozvoj podle i-tého sloupce determinantu matice, kde i-tý sloupec byl nahrazen j-tým sloupcem. Tyto determinanty jsou však podle 4.46(3a) nulové.V ĚTA 4.52. Pro čtvercovou matici A řádu n máme: A(adj A) = (adj A)A = (det A).In Důkaz. Tvrzení plyne z lemmatu 4.51 a z definice matice adj A ve 4.49.D ŮSLEDEK 4.53. Pro regulární čtvercovou matici A platí A-1 = 1 det A adj A. Důkaz. Podle 4.46(10) je det A = 0. Rovnici ve 4.52 můžeme tedy tímto determinantem vydělit, takže dostáváme A 1 det A adj A = 1 det A adj A A = In, a tedy A-1 = 1 det A adj A podle 4.25.D ŮSLEDEK 4.54 (Cramerovo pravidlo). Nechť A je regulární čtvercová matice řádu n a b sloupcový vektor délky n. Pak A-1 b = det A1 det A , . . . , det An det A T , kde Aj je matice získaná z A nahrazením jejího j-tého sloupce vek- torem b (j = 1, . . . , n). DŮKAZ. Označme b =: [bt] a položme y := [yj] := (adj A)b. Pak yj = n t=1 Ctjbt = n t=1 btCtj představuje Laplaceův rozvoj podle j-tého sloupce determinantu matice Aj, tj. yj = det Aj (j = 1, . . . , n). Tvrzení pak ihned dostáváme po vynásobení rovnice ve 4.53 zprava vektorem b. 1 35 POZNÁMKA 4.55 (Metody výpočtu determinantu). ˇ Přímý výpočet z definice 4.44: Je vhodný pouze pro matice nízkých řádů, obvykle nejvýše řádu 3: Řád 1: Pro čtvercovou matici A = [a] řádu 1 je výpočet jednoduchý. Jedinou permutací jednoprvkové množiny je identická permutace sudé parity, takže dostáváme: det A = det[a] = a. Řád 2: Jedinými permutacemi dvouprvkové mmnožiny je identická permutace [1, 2] sudé parity a [2, 1] liché parity. Dostáváme tak vztah: det A = a11a22 - a12a21. (4.2a) Řád 3: Tříprvkovou mmnožinu lze uspořádat šesti způsoby (= 3!), přičemž dle 4.43(6) tři permutace mají sudou paritu (+) a tři lichou paritu (-): [1, 2, 3], [2, 3, 1], [3, 1, 2] s počtem inverzí po řadě 0, 2, 2 (+) [3, 2, 1], [2, 1, 3], [1, 3, 2] s počtem inverzí po řadě 3, 1, 1 (-). Dostáváme tak vztah: det A = a11a22a33 + a12a23a31 + a13a21a32 - a13a22a31 - a12a21a33 - a11a23a32. (4.2b) Výše uvedené vztahy si lze snadno zapamatovat takto: trojice prvků vybíraná rovnoběžně s hlavní diagonálou dává příslušnému členu zna- ménko +, zatímco trojice prvků vybíraná rovnoběžně s vedlejší dia- gonálou dává znaménko -. Toto pravidlo je také známo jako tzv. Sarrusovo pravidlo. ˇ Rekurentní výpočet užitím Laplaceova rozvoje: Opakovaným používáním Laplaceova rozvoje postupně na zadaný de- terminant, pak na vybírané minory a jejich doplňky, atd. vede k po- stupnému snižování řádu determinantů až na úroveň, kde můžeme užít přímý výpočet. Indexy i1, . . . , ik, resp. j1, . . . , jk vybíráme tak, aby ve vybraných řádcích, resp. sloupcích bylo co nejvíce nulových 136 prvků. Pak totiž mnoho minorů v rozvoji bude nulových a výpočet se zjednoduší. Můžeme také tomu napomoci prováděním vhodných elementárních transformací dle 4.46(7-7b), které nemění hodnotu po- čítaného determinantu. Obvykle se provádí rozvoj pouze podle jednoho řádku, resp. sloupce, z něhož nejprve eliminujeme co nejvíce nenulových prvků. Ideální je, když tam zůstane pouze jeden takový prvek, řekněme aij. Pak se roz- voj redukuje jen na jeden sčítanec det A = aij(-1)i+j Cij, kde Cij je řádu n - 1. Na něj pak aplikujeme podobný postup, čímž se řád dále sníží na n - 2, atd. ˇ Užití Gaussovy eliminace, resp. LU-rozkladu: Při Gaussově eliminaci se matice A řádu n převede posloupností ele- mentárních řádkových úprav 4.46(7) a řádkových záměn 4.46(3) na čtvercovou matici ve schodovitém tvaru S rovněž řádu n. Uvažme dále, že S je horní trojúhelníková matice. Zatímco řádkové úpravy 4.46(7) nemění hodnotu det A, tak každá řádková záměna 4.46(3) obrací její znaménko. Označíme-li p počet provedených řádkových záměn, dostáváme (-1)p det A = det S 4.46(4) = s11 . . . snn a odtud hle- daný vztah det A = (-1)p s11 . . . snn. (4.3) Obdobný vztah dostáváme z rovnice L.S = P A pro LU-rozklad dle 4.38. Totiž L je dolní trojúhelníková s jednotkovou diagonálou, takže det L = 1 dle 4.46(4). Matice P je permutační matice složená z výše zmíněných řádkových záměn, takže det P = (-1)p dle 4.43(3) a 4.46(3b). Kromě determinantu, další běžně užívanou skalární veličinou přiřa- zovanou čtvercové matici je stopa matice: DEFINICE 4.56 (Stopa matice). Stopou (angl. trace) čtvercové matice A =: [aij] řádu n nazýváme součet jejích prvků na hlavní diagonále. Píšeme tr A := n i=1 aii. V teorii polynomů hraje důležitou roli tzv. Vandermondova matice: 137 DEFINICE 4.57 (Vandermondova matice). Vandermondovou maticí danou vektorem x := [x1, . . . , xn] Fn rozumíme následující čtvercovou matici řádu n: V (x) := V (x1, . . . , xn) := 1 x1 x2 1 xn-1 1 1 x2 x2 2 xn-1 2 ... ... ... ... 1 xn x2 n xn-1 n . (4.4a) V jejím i-tém řádku a j-tém sloupci se nachází prvek xj-1 i , můžeme proto psát stručně22 V (x) = [xj-1 i ]. VĚTA 4.58 (Vandermondův determinant). Determinant z Vandermondovy matice se nazývá Vandermondův determinant. Vandermondův determinant řádu n 2 se spočte z následujícího vztahu: det V (x1, . . . , xn) = 1 i 2 (indukční krok): Předpokládejme, že (4.4b) již bylo doká- záno pro n-1. Proveďme s maticí (4.4a) následující sloupcové úpravy neměnící hodnotu determinantu (viz 4.46(5a)(7)): Pro každé j = n, n - 1, . . . , 2 odečteme od j-tého sloupce xn-násobek (j - 1)-ho sloupce. V posledním řádku zůstane v 1. sloupci jediný nenulový prvek 1, podle něhož determinant rozvineme: det V (x1, . . . , xn) = 1.(-1)n+1 det C, kde z každého řádku determi- nantu doplňkové matice C lze před něj vytknout rozdíl (xi - xn), 22pokud xi = 0, pak v 1. sloupci neurčitý výraz 00 nahradíme jedničkou. 138 i = 1, . . . , n - 1 (užijeme (n - 1)-krát vlastnost 4.46(6)). Pak det C = (x1 - xn) . . . (xn-1 - xn) det V (x1, . . . , xn-1) I.P. = (-1)n-1 (xn - x1) . . . (xn - xn-1) 1 i 1) rozměru n × n: A = a1 c1 0 . . . 0 0 0 b2 a2 c2 . . . 0 0 0 ... ... ... ... ... ... ... 0 0 0 . . . bn-1 an-1 cn-1 0 0 0 . . . 0 bn an . Potom její LU-rozklad A = LU je tvaru L = 1 0 . . . 0 0 2 1 . . . 0 0 ... ... ... ... ... 0 0 . . . 1 0 0 0 . . . n 1 , U = 1 c1 0 . . . 0 0 2 c2 . . . 0 ... ... ... ... ... 0 0 0 . . . cn-1 0 0 0 . . . n , kde 1 = a1 i = bi i-1 i = ai - ici-1 pro i = 2, 3, . . . , n. (5.5a) Důkaz. Vztahy pro neznámé i a i snadno nalezneme formálním po- rovnáním prvků matic na levé a pravé straně po roznásobení maticové rovnice A = LU: viz též poznámku 5.9(3).1 51 Poznámka 5.9. (1) Jinou variantu algoritmu (5.5a) lze odvodit pro L = 1 0 . . . 0 0 b2 2 . . . 0 0 ... ... ... ... ... 0 0 . . . n-1 0 0 0 . . . bn n , U = 1 1 . . . 0 0 0 1 . . . 0 0 ... ... ... ... ... 0 0 . . . 1 n-1 0 0 . . . 0 1 , kde 1 = a1, 1 = c1 1 i = ai - bii-1 i = ci i pro i = 2, 3, . . . , n. (5.5b) (2) Analogické algoritmy obdržíme pro blokově tridiagonální ma- tice, kde ai, bi, ci, i, i (resp. i) jsou submatice kompatibil- ních rozměrů. Pak místo 1 i-1 násobíme inverzní maticí -1 i-1 zprava v (5.5a) (resp. místo 1 i maticí -1 i zleva v (5.5b)). (3) V případě obecné regulární čtvercové matice A lze výše po- psaný postup zobecnit pro přímý výpočet prvků matic L a U tak, že postupně sestavujeme rovnice pro prvky 1. řádku U, 1. sloupce L, 2. řádku U, 2. sloupce L, atd. 5.4. Přibližné řešení SLR metodou nejmenších čtverců. Pokud neexistuje řešení SLR Ax = b, je to důsledkem toho, že b / R(A). V tomto případě má smysl hledat řešení x, které minimali- zuje v nějakém smyslu chybu b-Ax. Chybu obvykle měříme vhodnou normou b - Ax . Nejčastěji se pro tento účel užívají p-normy (viz 3.56). Pokud je norma odvozena24 z nějakého vnitřního součinu , , stačí nahradit pravou stranu b její ortogonální projekcí b R(A) na 24viz 3.62(S9). 152 R(A), což je dle věty o ortogonální projekci 3.77 vektor z R(A) mini- malizující b - b . Místo původní rovnice pak řešíme rovnici Ax = b tzv. metodou nejmenších čtverců (MNČ) podle následující věty. VĚTA 5.10 (Metoda nejmenších čtverců ve (V, LF)). Nechť (V, LF) je VS-prostor nad skalárním polem F C a W := L(A) jeho vektorový podprostor generovaný konečnou množinou vektorů A := {a1, . . . , an}. Pak =: [1, . . . , n] Fn je ve smyslu věty 3.77 řešením úlohy ortogonální projekce PW b =: b = 1a1 + + nan vektoru b V na podprostor W právě když je přesným řešením následujícího systému lineárních rovnic, který je vždy řešitelný: a1, a1 1 + a2, a1 2 + . . . + an, a1 n = b, a1a 1, a2 1 + a2, a2 2 + . . . + an, a2 n = b, a2. .. ... ... ... a1, an 1 + a2, an 2 + . . . + an, an n = b, an . (5.6a) DŮKAZ. W je konečně rozměrný, takže podle 3.80 lze užít větu 3.77 o ortogonální projekci. Podle věty 3.86 je PW b = b b - b W 3.72 b - b ai pro i = 1, . . . , n b - n j=1 jaj, ai = 0 pro i = 1, . . . , n (3.1) b, ai - n j=1 j aj, ai = 0 pro i = 1, . . . , n n j=1 j aj, ai = b, ai pro i = 1, . . . , n je řešením (5.6a). Řešitelnost tohoto systému je garantována větou o ortogonální pro- jekci.D ŮSLEDEK 5.11 (Metoda nejmenších čtverců ve (Fm , LF)). Nechť A =: [a1, . . . , an] je matice typu m/n tvořená sloupcovými vektory a1, . . . , an a b Fm libovolný vektor. Pak x Fn je řešením rovnice Ax = b nad skalárním polem F C právě když x je přesným řešením následujícího systému lineárních rovnic: (A A)x = A b. (5.6b) 153 Tento systém je vždy řešitelný a jeho maticí soustavy je Gramova matice A A -- viz 4.14(9). DŮKAZ. Jestliže nahradíme v předchozí větě vektorem x, pak b = x1a1 + + xnan 4.13 = Ax. Vektor x je tedy řešením této úlohy právě když je řešením SLR (5.6a), kde i = xi. Tomuto systému odpo- vídá dle 4.14(9) maticový zápis (5.6b). Jeho řešitelnost je dána před- chozí větou nebo také přímo plyne ihned z toho, že jeho pravá strana A b R(A ) 3.88(5)(iii) = R(A A).P oznámka 5.12. (1) Jestliže F R, pak v (5.6b) je A 4.11(5) = AT . (2) Je-li W nějaká pozitivně definitní matice řádu m (tzv. vá- hová matice), pak lze pomocí ní zavést v Fm vážený skalární součin x, y W := W x, y 4 .14(9) = y W x (podrobnosti dále v kapitole 6). Systém (5.6a) tak přejde v (A W A)x = A W b. (5.6c) Jeho řešení nazýváme řešením úlohy Ax = b tzv. váže- nou metodu nejmenších čtverců s váhovou maticí W . Obvykle W je diagonální matice s kladnými diagonálními vahami wii > 0 (jinak W by totiž nebyla pozitivně de- finitní). Nechť r := b - Ax značí vektor odchylek řešení od pravé strany (tzv. reziduální vektor). Malá hodnota wii v odvozené normě r W = W r, r W = rW r = m i=1 wiiriri = m i=1 wii|ri|2 snižuje vliv odchylky ri na hodnotu normy a připouští tudíž větší odchylku i-té složky oproti j-té složce, kde wjj > wii. (3) Je-li b R(A), pak b = PW b 3.76(1) = b, takže každé řešení soustavy (5.6b) je současně přesným řešením původní rovnice Ax = b. V MATLABu pro nečtvercovou matici pomocí ope- rátoru levého dělení x = A\b spočteme nějaké (partikulární) 154 MNČ-řešení systému (5.6b). Toto řešení je přesné, pokud je původní systém řešitelný -- viz poznámku v 5.2(1)c). 5.5. Řešení maticové rovnice A.X = B a výpočet inverze A-1 . Nechť A typu m/n a B typu m/p jsou dané matice. Řešením ma- ticové rovnice A.X = B rozumíme každou matici X kompatibil- ního typu n/p, která tuto rovnici splňuje. Protože A.X = B A.X(:, k) = B(:, k) pro k = 1, . . . , p, vidíme, že sloupce X jsou po řadě řešení p systémů lineárních rovnic s pravými stranami tvořenými odpovídajícími sloupci matice B. Všechny tyto systémy mají přitom stejnou maticí soustavy A. V zásadě můžeme po drobné modifikaci užít metody (1) až (3) z odst. 5.2. (1) Gaussova nebo Jordanova eliminace V kroku a) převádíme na schodovitý tvar matici soustavy rozšířenou o všechny pravé strany, tj. matici A = [A, B]. Obdržíme [S, B ] . V kroku b) rozhodnutí o řešitelnosti maticové rovnice spočívá v roz- hodnutí o řešitelnosti všech ekvivalentních soustav s měnícími se pra- vými stranami B ( :, k), k = 1, . . . , p. Snadno nahlédneme, že nutnou a postačující podmínkou je opět podmínka r(A) = r(A), tj. stejný počet nenulových řádků v maticích S a [S, B ] . V kroku c) pak (5.3) řešíme postupně s pravými stranami b = B ( :, k) pro k = 1, . . . , p. Krok d) zůstane beze změny, neboť nezávisí na pravé straně. (2) Užití LU-rozkladu Jak již bylo zmíněno v 5.7, stačí vlastní LU-rozklad z kroku a) provést pouze jednou, v kroku b) pak provedeme řádkovou permutaci P B celé matice B, což odpovídá řádkovým permutacím všech pravých stran. Nakonec pro každou pravou stranu (sloupce matice B) opakujeme kroky c)d), čímž postupně dostáváme jako řešení odpovídající sloupce neznámé matice X. 155 Analogicky jako v odst. 5.4 lze přibližné MNČ-řešení maticové rovnice A.X = B nalézt řešením maticové rovnice (A A)X = A B, která je vždy řešitelná. Je-li A regulární čtvercová matice řádu n, pak k nalezení inverze X = A-1 stačí podle 4.46(11) řešit maticovou rovnici A.X = In. Tato úloha je tak speciálním případem maticové rovnice (m = n = p). Poznamenejme ještě, že v případě regulární matice, je A-1 B (jedi- ným) řešením obecné maticové rovnice s libovolnou pravou stranou B. V případě regulární matice A nízkého řádu, můžeme pro výpočet její inverze užít také determinantovou metodu dle důsledku 4.53. 5.6. Problémy s numerickou nestabilitou při řešení SLR. Matice A se nazývá špatně podmíněná, jestliže malé změny pravé strany b mají za následek velké změny řešení x. Například pro čtverco- vou matici A tato situace nastává v případech, kdy A je sice regulární, avšak s malou hodnotou determinantu, neboli říkáme, že je "skoro sin- gulární". Tato situace nastane, když některý sloupcový (řádkový) vek- tor v A svírá malý úhel s nadrovinou generovanou ostatními sloupci (řádky). Jako příklad uvažme následující systém dvou lineárních rovnic: x + 2y = 2 2x + 3y = 3, 4 Přesné řešení x = 0, 8, y = 0, 6 aproximujme dosti nepřesně hodno- tami x = 1, y = 0, 48. Po jejich dosazení do obou rovnic dostáváme po řadě 1, 96 místo 2 a 3, 44 místo 3, 4, což jsou malé odchylky řádově v setinách ve srovnání s chybou řešení, která je řádově v desetinách. Příčina tkví v tom, že hledáme průsečík dvou přímek, které svírají velmi malý úhel o směrnicích -1 2 a -2 3 . Řádky [1, 2] a [2, 3] ma- tice soustavy v tomto případě totiž reprezentují souřadnice kolmic k oběma přímkám a svírají tedy stejný úhel jako přímky samotné. 156 Se zmenšujícím se úhlem se blížíme ke stavu lineární závislosti obou vektorů, tj. ke stavu, kdy matice soustavy je singulární. Podobně lze zkonstruovat situace, kdy při libovolně velké odchylce řešení lze dosáhnout libovolně malé odchylky od pravé strany. ZÁVĚR: Nelze tedy hodnotit přesnost nalezeného řešení podle odchy- lek od pravé strany po jeho dosazení do rovnic! Lze pouze hodnotit podmíněnost matice. Ta se měří číslem podmíně- nosti, které se zpravidla počítá jako poměr největšího ku nejmenšímu singulárnímu číslu matice. Singulární čísla matice A jsou druhé od- mocniny vlastních čísel symetrické matice AT A -- tedy v případě symetrické matice splývají s jejími vlastními čísly (podrobněji viz následující kapitolu). Toto číslo podmíněnosti v systému MATLAB počítá funkce cond. Čím větší číslo podmíněnosti má daná matice, tím je hůře podmíněná a více se blíží k singulární matici. Jinak počí- tané reciproké číslo podmíněnosti v intervalu [0, 1] vrací funkce rcond. V tomto případě špatnou podmíněnost indikují hodnoty blízké k nule. 5.7. Iterační metody pro řešení systému lineárních rovnic. Princip: Rovnici Ax = b, kde A je čtvercová regulární matice řádu n, převe- deme na rovnici tvaru x = x + , kterou generujeme posloupnost iterací. Obecný postup hledání a : Matici A vhodně rozložíme do tvaru A = N -M, kde N je regulární matice. Pak platí Ax = b (N - M)x = b Nx = Mx + b x = N-1 M x + N-1 b . 157 Iterační proces: x(0) . . . počáteční iterace x(k+1) = x(k) + pro k = 0, 1, . . . . (5.7) DEFINICE 5.13 (Jacobiho prosté iterace). Položíme N := diag(A) = a11 0 . . . 0 0 a22 . . . 0 ... ... ... ... 0 0 . . . ann M := N - A = 0 -a12 . . . -a1n -a21 0 . . . -a2n ... ... ... ... -an1 -an2 . . . 0 , pak = 0 -a12 a11 . . . -a1n a11 -a21 a22 0 . . . -a2n a22 ... ... ... ... - an1 ann - an2 ann . . . 0 , = b1 a11 b2 a22 ... bn ann . Rozepsáním (5.7) do jednotlivých rovnic dostáváme Jacobiho iterační proces: x (0) 1 , . . . , x (0) n . . . počáteční iterace x (k+1) j = 1 ajj b j - n i=1 i=j aji x (k) i , j = 1, . . . , n; k = 0, 1, . . . . (5.8) 158 Vidíme, že vztah pro x (k+1) j odpovídá formálnímu vyřešení j-té rov- nice vzhledem k proměnné xj. Jestliže nyní v (5.8) použijeme pro i < j již spočtenou iteraci x (k+1) i místo x (k) i , obdržíme následující zřejmě poněkud rychleji konvergující iterační proces. DEFINICE 5.14 (Gauss-Seidelovy iterace). Položíme N := a11 0 . . . 0 a21 a22 . . . 0 ... ... ... ... an1 an2 . . . ann , M := N - A = 0 -a12 . . . -a1n 0 0 . . . -a2n ... ... ... ... 0 0 . . . 0 , pak z Nx(k+1) = Mx(k) + b dostáváme ihned rovnice pro Gauss-Seidelův iterační proces: x (0) 1 , . . . , x (0) n . . . počáteční iterace x (k+1) j = 1 ajj b j - j-1 i=1 aji x (k+1) i - n i=j+1 aji x (k) i , j = 1, . . . , n; k = 0, 1, . . . . (5.9) DEFINICE 5.15. Čtvercová matice A řádu n se nazývá striktně diagonálně dominantní, jestliže |ajj| > n i=1 i=j |aji| pro j = 1, 2, . . . , n. VĚTA 5.16 (Konvergence Jacobiho a Gauss-Seidelovy metody). Nechť A je striktně diagonálně dominantní matice. Potom systém li- neárních rovnic Ax = b má jediné řešení a Jacobiho i Gauss-Seidelův 159 iterační proces konverguje k tomuto řešení při libovolně zvolené počá- teční aproximaci x(0) . POZNÁMKA 5.17. Obecně z konvergence jedné z obou metod ne- plyne konvergence druhé. Pokud konvergují obě, pak Gauss-Seidelova metoda konverguje rychleji. PŘÍKLAD 5.18. Jak ukazuje následující příklad, může pouhou změnou pořadí rovnic dojít ke ztrátě konvergence. Uvažme SLR 4x - y + z = 7 4x - 8y + z = -21 -2x + y + 5z = 15 Jacobiho iterace tohoto SLR odstartované v počáteční aproximaci x(0) = [1, 2, 2] konvergují k přesnému řešení x = [2, 4, 3], neboť matice soustavy je striktně diagonálně dominantní. Jestliže zaměníme první a poslední rovnici, tak se tato vlastnost po- ruší a SLR -2x + y + 5z = 15 4x - 8y + z = -21 4x - y + z = 7 při téže počáteční iteraci diverguje od přesného řešení. Poznámka 5.19. Iterační metody jsou vhodné zejména pro rozsáhlé systémy lineárních rovnic s řídkou maticí soustavy (malým počtem nenulových prvků), kde u Gaussovy eliminace bývají problémy s nu- merickou stabilitou (viz 5.6) a větší výpočetní nároky vzhledem k ne- možnosti účelně využít případné řídkosti matice soustavy. Snažíme se vhodnou záměnou pořadí rovnic (řádkovou permutací rozšířené matice soustavy) a změnou pořadí nezávisle proměnných (sloupcová permutace matice soustavy) soustředit největší nenulové prvky kolem hlavní diagonály s cílem dosáhnout (pokud možno) strikt- ně diagonální dominantnosti. To je zpravidla snazší u řídké matice, která se stane pásovou (nenulové prvky soustředěny kolem hlavní di- agonály). 160 ANGLICKÁ TERMINOLOGIE PRO LINEÁRNÍ ROVNICE systém lineárních rovnic (SLR) system of linear equations (SLE) matice systému matrix of the system pravá strana right-hand side vektor neznámých vector of unknowns (ne)homogenní systém (non-)homogeneous system rozšířená matice SLR augmented matrix of a SLE množina řešení solution set partikulární řešení particular solution algoritmus dopředného dosazování forward-substitution algorithm algoritmus zpětného dosazování back-substitution algorithm SLR s dolní trojúhelníkovou maticí lower-triangular SLE SLR s horní trojúhelníkovou maticí upper-triangular SLE výpočetní složitost computational complexity tridiagonální matice tridiagonal matrix pásová matice band matrix přibližné řešení approximate solution metoda nejmenších čtverců (MNČ) least-squares (LSQ) solution vážená MNČ weighted LSQ method váhová matice weight matrix maticová rovnice matrix equation numerická (ne)stabilita numerical (in)stability špatně podmíněná matice badly-conditioned matrix dobře podmíněná matice well-conditioned matrix číslo podmíněnosti condition number iterační metoda iterative method 161 6. Transformace souřadnic a diagonalizace matic Látka je předběžně zpracována v souborech TrSour.tif a DiagMat.tif, které jsou zkomprimovány v TrSour.zip a v DiagMat.zip na https://www.econ.muni.cz/stud/verejne/verejne/Predmety/Podzim% 202004/PMZMI/prednaska/. 162 Příloha A. Operace s komplexními čísly Nechť dále značí a := a1 + ia2, b := b1 + ib2 dvě komplexní čísla v kartézském tvaru a a = |a|(cos + i sin ) = |a|ei , b = |b|(cos + i sin ) = |b|ei jejich vyjádření v goniometrickém, resp. Eulerově tvaru. Jelikož funkce kosinus je sudá (cos(-x) = cos(x)) a funkce sinus lichá (sin(-x) = - sin(x)), dostáváme: ei = e-i a tedy a = |a|e-i a b = |b|e-i . A.1. Sečítání, odčítání. a + b := (a1 + b1) + i(a2 + b2) a - b := (a1 - b1) + i(a2 - b2) A.2. Násobení. ab = (a1 + ia2)(b1 + ib2) = (a1b1 - a2b2) + i(a2b1 + a1b2) nebo ab = |a|ei |b|ei = |a||b|ei(+) = |a||b|(cos( + ) + i sin( + )). Zejména platí aa = a2 1 + a2 2 = |a|2 . A.3. Dělení. Nechť b = 0, pak a b = ab bb = a1b1 + a2b2 b2 1 + b2 2 + i a2b1 - a1b2 b2 1 + b2 2 nebo a b = |a|ei |b|ei = |a| |b| ei(-) = |a| |b| (cos( - ) + i sin( - )). A.4. Umocňování. Tvrzení (Moivreova věta). an = |a|n (cos n + i sin n), kde n Z Důkaz. Indukcí vzhledem k |n| užitím vztahu A.2 pro násobení při n > 0, resp. vztahu A.3 pro dělení komplexních čísel při n < 0.1 63 A.5. Odmocňování. 1. Druhá odmocnina v kartézských souřadnicích a1 + ia2 = (u1 + iu2), kde u1 = 1 2 (|a| + a1) u2 = sgn(a2) 1 2 (|a| - a1), kde sgn(a2) udává znaménko a2. 2. n-tá odmocnina Uvažme, že vzhledem k periodicitě funkcí kosinus a sinus platí a = |a|(cos +i sin ) = |a|(cos(+2k)+i sin(+2k)) = |a|ei(+2k) pro každé k Z. Odtud dostaneme ihned vztah pro všechny n-té odmocniny z a: n a = n | a|ei +2k n = n | a| c os + 2k n + i sin + 2k n p ro k = 0, 1, . . . , n - 1. 3. n-tá odmocnina z 1 Z předchozího dostaneme volbou a = 1 všechny n-té odmocniny z 1: n 1 = ei 2k n = c os 2k n + i sin 2k n p ro k = 0, 1, . . . , n - 1. Tvrzení (Vlastnosti). (1) Všechny hodnoty n-té odmocniny z komplexního čísla a do- staneme vynásobením jedné z těchto hodnot všemi hodno- tami n-té odmocniny z 1. (2) Jsou-li 1, 2 n-té odmocniny z 1, pak 12 je rovněž n-tá odmocnina z 1. (3) Je-li k-tá odmocnina z 1 a l = kq, pak je rovněž l-tá odmocnina z 1. 164 (4) Je-li n-tá odmocnina z 1, pak k := k je rovněž n-tá od- mocnina z 1 pro k = 0, 1, . . . , n - 1. (5) se nazývá primitivní n-tá odmocnina z 1, platí-li: (i) n = 1 (ii) k = 1 pro k = 1, 2, . . . , n - 1. (6) Je-li n-tá odmocnina z 1, pak je primitivní právě když hodnoty k jsou pro k = 0, 1, . . . , n - 1 navzájem různé. Zejména := e i2 n je vždy primitivní, neboť k = e i2k n jsou pro k = 0, 1, . . . , n - 1 navzájem různá komplexní čísla. (7) Nechť je primitivní n-tá odmocnina z 1. Pak k je primitivní n-tá odmocnina z 1 právě když n a k jsou nesoudělné. (8) Nechť p je prvočíslo, pak všechny p-té odmocniny z 1 různé od 1 jsou primitivní. A.6. Goniometrické vzorce. 1. Vyjádření goniometrických funkcí sin n, cos n pomocí sin , cos Použitím Moivreovy věty a binomické věty dostáváme: cos n + i sin n = (cos + i sin )n = = nk =0 n k c osk (i)n-k sinn-k . Stačí pak porovnat reálné, popřípadě imaginární části výrazů vlevo a vpravo. Zejména pro n = 2 tak dostáváme známé vztahy pro dvojná- sobný úhel: cos 2 = cos2 - sin2 , sin 2 = 2 sin cos . Ty jsou však speciálním případem obecnějších vztahů pro součet a rozdíl úhlů, získaných z A.2 volbou a1 = cos , a2 = sin a b1 = cos() = cos , b2 = sin() = sin . Jelikož |a| = |b| = 1, obdržíme: cos( ) = cos cos sin sin , sin( ) = sin cos cos sin . 165 2. Vyjádření goniometrických funkcí sinn , cosn pomocí sin k, cos k Z Eulerova vztahu dostáváme vyjádření pro sin a cos : sin = ei - e-i 2i , cos = ei + e-i 2 . Ty stačí umocnit na n-tou opět užitím binomické věty: sinn = 1 2nin nk =0 n k e ik (-1)n-k e-i(n-k) cosn = 1 2n nk =0 n k e ik e-i(n-k) . Například spočtěme sin3 = 1 23i3 (ei3 - 3ei2 e-i + 3ei e-i2 - e-i3 ) = = 1 8i3 (2i sin 3 - 3.2i sin ) = 1 4i2 (sin 3 - 3 sin ) = = 1 4 (3 sin - sin 3). 166 Příloha B. Maticová reprezentace abstraktních vektorových prostorů konečné dimenze Věta B.1. Nechť (V1, LF), (V2, LF) a (V3, LF) jsou tři vektorové pro- story konečných dimenzí dim V1 = n, dim V2 = m a dim V3 = p. Pak zobrazení T [T] (T L(V1, V2)) je izomorfizmem vektorového pro- storu L(V1, V2) všech lineárních operátorů z V1 do V2 (viz 3.38) na vektorový prostor všech matic Mm,n (viz 4.9). Přitom platí: (1) [Tx] = [T].[x] pro každé x V1. (2) Složení dvou operátorů T : V1 V2 a U : V2 V3 odpovídá v souřadnicovém vyjádření součin matic: [UT] = [U].[T]. (3) Maticovou reprezentací identického operátoru I : V1 V1 je jednotková matice: [I] = In. (4) Operátor T je surjektivní právě když je reprezentován maticí řádkově plné hodnosti25 . (5) Operátor T je izomorfní vnoření právě když je reprezentován maticí sloupcově plné hodnosti25 . (6) Operátor T je izomorfizmus právě když je reprezentován re- gulární maticí25 . Přitom platí [T]-1 = [T-1 ], kde [T]-1 je matice inverzní26 k [T]. V případě VS-prostorů (F C) navíc platí: (7) Maticovou reprezentací operátoru adjungovaného k T je her- mitovsky transponovaná matice: [T ] = [T] . Zejména mati- covou reprezentaci samoadjungovaného operátoru je hermi- tovsky symetrická matice. (8) Operátor T je unitární právě když je reprezentován unitární maticí. Důkaz. Nadále E = {e1, . . . , e1} je nějaká pevně zvolená báze ve V1. ˇ Linearita zobrazení T [T]: [T1 + T2] = [[(T1 + T2)e1], . . . , [(T1 + T2)en]] = 25Viz definici 4.17. 26Matice určující maticový operátor inverzní k operátoru určenému maticí [T ] dle věty 4.25. 167 [[T1e1 + T2e1], . . . , [T1en + T2en]] 3.92 = [[T1e1] + [T2e1], . . . , [T1en] + [T2en]] = [[T1e1], . . . , [T1en]] + [[T2e1], . . . , [T2en]] = [T1] + [T2]. [T] = [[(T)e1], . . . , [(T)en]] = [[(Te1)], . . . , [(Ten)]] 3.92 = [[Te1], . . . , [Ten]] = [[Te1], . . . , [Ten]] = [T]. ˇ T [T] je prosté: T1 = T2 3.35 i : T1ei = T2ei 3.92 i : [T1ei] = [T2ei] [[T1e1], . . . , [T1en]] = [[T2e1], . . . , [T2en]] [T1] = [T2]. ˇ T [T] je surjekce: Buď A libovolná matice typu m/n. Dle 3.92 je [] surjekce, takže ke každému sloupci A(:, j) existuje vektor vj V2 tak, že [vj] = A(:, j). Podle 3.36(6) lze zobrazení ej vj rozšířit na lineární operátor V1 V2, takže [Tej] = [vj] = A(:, j) [T] = [[Te1], . . . , [Ten]] = [A(:, 1), . . . , A(:, n)] = A. ˇ Vlastnost (1): Nechť x = n i=1 iei, tj. = [x]. Pak [Tx] = [T( n i=1 iei)] = [ n i=1 iTei] 3.92 = n i=1 i[Tei] 4.13a) = [[Te1], . . . , [Ten]]. = [T].[x]. ˇ Vlastnost (2): [UT] = [[U(Te1)], . . . , [U(Ten)]] (1) = [[U].[Te1], . . . , [U].[Ten]] 4.15(1) = [U].[[Te1], . . . , [U].[Ten]] = [U].[T]. ˇ Vlastnost (3): [I] = [[Ie1], . . . , [Ien]] = [[e1], . . . , [en]] = [1, . . . , n] = In. ˇ Vlastnosti (4)­(6),(8): Označíme-li S1 : V1 Fn a S2 : V2 Fm unitární izomorfizmy při- řazení souřadnic (Si zastupije zápis [] ve 3.92), pak [Tx] (1) = [T].[x] lze psát ve tvaru S2Tx = [T].(S1x) 4.15 = [T]S1x pro každé x Fn , což je ekvivalentní s rovností složených operátorů S2T = [T]S1. Apli- kujeme-li na tuto rovnost S-1 2 zleva, resp. S-1 1 zprava, obdržíme vy- jádření: T = S-1 2 [T]S1, resp. [T] = S2TS-1 1 . Složení tří izomorf- ních vnoření (surjekcí, izomorfizmů) je zřejmě opět izomorfní vnoření (surjekce, izomorfizmus). Jelikož S1 i S2 jsou izomorfizmy (surjektivní 168 izomorfní vnoření), z výše uvedených vyjádření T a [T] vidíme, že T je izomorfní vnoření (surjekce, izomorfizmus) [T] určuje izomorfní vnoření (surjekci, izomorfizmus), což je podle věty 4.20 ekvivalentní s dokazovanými tvrzeními o matici [T]. Protože Si jsou unitární izo- morfizmy a také složení tří unitárních izomorfizmů je rovněž unitární izomorfizmus, dostáváme podobně ekvivalenci s unitaritou matico- vého operátoru [T] a tedy i s maticí [T] (viz 4.15(8)). T izomorfizmus T-1 T = I a TT-1 = I jsou identity na V1 a V2 (2),(3) [T-1 ].[T] = In a [T].[T-1 ] = Im, což podle věty 4.25 znamená, že [T-1 ] = [T]-1 . ˇ Vlastnost (7): Nechť x V1 a y V2 jsou libovolné. Protože [] je unitární, dostá- váme užitím 3.90(3): Tx, y = [Tx], [y] ( 1) = [T].[x], [y] 4 .15(6) = [x], [T] .[y] , x, T y = [x], [T y] ( 1) = [x], [T ].[y] . Pak Tx, y = x, T y [x], [T] .[y] = [x], [T ].[y] , kde [x], resp. [y] probíhá všechny prvky Fn , resp. Fm (totiž [] je izomorfizmus a tedy surjekce). Adjungovaný operátor je dle 3.82 určen jednoznačně, takže operátory určené maticemi [T] a [T ] jsou stejné. Dle úvodní části důkazu této věty existuje jednojednoznačná korespondence mezi maticemi a příslušnými operátory, takže také [T] = [T ].1 69 Příloha C. Matematické symboly v systému LATEX MATHEMATICAL FONTS DEMO (mathfont.aml) (definitions from the input file mathfont.tex assumed) Math roman \mathrm: ABCDEFGH. Math roman bold \mathbf: ABCDEFGH. Math blackboard bold \mathbb or \Bbb ABCDEFGH. Math normal \mathnormal: ABCDEFGH. Math bold normal \bm: ABCDEF GH. Math italic \mathit: ABCDEFGH . Math sans serif \mathsf: ABCDEFGH. Math typewriter \mathtt: ABCDEFGH. Math script \mathcal or \cal: ABCDEFGH. Math bold script \bcal: ABCDEFGH. Euler script \matheu or \eu: ABCDEFGH. Euler bold script \beu: ABCDEFGH. Math fraktur \mathfrak or \frak: ABCDEFGH. Math bold fraktur \bfrak: ABCDEFGH. The set of natural numbers \Nset: N The set of integers \Zset: Z The set of integers modulo N \ZNset{N}: ZN The set of rational numbers \Qset: Q The set of real numbers \Rset: R The set of complex numbers \Cset: C 170 GREEK CHARACTERS (greek.tex) Type: Print: Type: Print: Type: Print: \alpha \beta \gamma \digamma \delta \epsilon\ varepsilon \zeta \eta \theta \vartheta \iota \kappa \varkappa \lambda \mu \nu \xi \pi \varpi \rho \varrho \sigma \varsigma \tau \upsilon \phi \varphi \chi \psi \omega Type: Print: Type: Print: \Gamma \varGamma \Delta \varDelta \Theta \varTheta \Lambda \varLambda \Xi \varXi \Pi \varPi \Sigma \varSigma \Upsilon \varUpsilon \Phi \varPhi \Psi \varPsi \Omega \varOmega HEBREW LETTERS (hebrew.tex) Type: Print: Type: Print: \aleph \beth\ daleth \gimel1 71 BINARY OPERATIONS (binoper.tex) Type: Print: Type: Print: \pm \mp\ dotplus \cdot \times × \centerdot\ ltimes \rtimes\ leftthreetimes \rightthreetimes\ ast \star\ diamond \circ \bullet ˇ \div ÷ \setminus \ \smallsetminus\ cap \cup \Cap \Cup\ sqcap \sqcup\ wedge \vee \barwedge \doublebarwedge\ curlywedge \curlyvee\ veebar \intercal\ oplus \ominus\ uplus \And & \otimes \oslash\ odot \circleddash\ circledast \circledcirc\ boxminus \boxtimes\ boxdot \boxplus\ triangleleft \triangleright\ lhd \rhd \unlhd \unrhd ¤ \bigtriangleup \bigtriangledown\ dagger \ddagger \wr \bigcirc\ amalg \divideontimes1 72 BIG OPERATORS (bigoper.tex) Type: Print: Type: Print: \prod {i=1}^{n} n i=1 \coprod {i=1}^{n} n i=1 \bigcap {i=1}^{n} n i=1 \bigcup {i=1}^{n} n i=1 \bigvee {i=1}^{n} n i=1 \bigwedge {i=1}^{n} n i=1 \bigsqcup {i=1}^{n} n i=1 \biguplus {i=1}^{n} n i=1 \bigotimes {i=1}^{n} n i=1 \bigoplus {i=1}^{n} n i=1 \bigodot {i=1}^{n} n i=1 \sum {i=1}^{n} n i=1 \int a^b b a \oint a^b b a \iint {E 2} E 2 \iiint {E 3} E 3 \iiiint {E 4} E 4 \idotsint {E n} E n ni =1 ni =1 ni =1 ni =1 ni =1 ni =1 ni =1 ni =1 ni =1 ni =1 ni =1 ni =1 b a b a E 2 E 3 E 4 E n 173 BINARY RELATIONS (binrel.tex) Type: Print: Type: Print: \leq \geq \leqslant \geqslant\ eqslantless \eqslantgtr\ lesssim \gtrsim\ lessapprox \gtrapprox\ approxeq\ lessdot \gtrdot\ ll \gg\ lll \ggg\ lessgtr \gtrless\ lesseqgtr \gtreqless\ lesseqqgtr \gtreqqless\ prec \succ\ preceq \succeq\ doteqdot \eqcirc\ circeq \fallingdotseq\ risingdotseq \triangleq\ equiv \sim \simeq \backsim\ thicksim \backsimeq\ approx \thickapprox \preccurlyeq \succcurlyeq\ curlyeqprec \curlyeqsucc\ precsim \succsim\ precapprox \succapprox1 74 Type: Print: Type: Print: \subset \supset \subseteq \supseteq \subseteqq \supseteqq\ Subset \Supset\ sqsubset ` \sqsupset a \sqsubseteq \sqsupseteq\ vartriangleleft \vartriangleright\ trianglelefteq \trianglerighteq\ vdash \dashv\ vDash \Vdash\ Vvdash \models |= \smile \smallsmile\ frown \smallfrown\ mid | \shortmid\ parallel \shortparallel\ asymp \cong = \bumpeq \Bumpeq\ between \pitchfork\ propto \varpropto \bowtie \Join I \in \ni\ backepsilon \doteq . = \blacktriangleleft \blacktriangleright\ therefore \because\ perp 175 NEGATED BINARY RELATIONS (nebinrel.tex) Type: Print: Type: Print: \ne = \notin / \nless \ngtr\ nleq \ngeq\ nleqslant \ngeqslant\ nleqq \ngeqq\ lneq \gneq\ lneqq \gneqq\ lvertneqq \gvertneqq\ lnsim \gnsim\ lnapprox \gnapprox\ nprec \nsucc\ npreceq \nsucceq\ precneqq \succneqq\ precnsim \succnsim\ precnapprox \succnapprox\ nsim \ncong\ nshortmid \nshortparallel\ nmid \nparallel\ nvdash \nvDash\ nVdash \nVDash\ ntriangleleft \ntriangleright\ ntrianglelefteq \ntrianglerighteq1 76 Type: Print: Type: Print: \nsubseteq \nsupseteq\ nsubseteqq \nsupseteqq\ subsetneq \supsetneq\ varsubsetneq \varsupsetneq\ subsetneqq \supsetneqq\ varsubsetneqq \varsupsetneqqT o put a slash through a symbol type \not before it, e.g. \not= gives =. 177 ARROWS (arrows.tex) Type: Print: Type: Print: \leftarrow \rightarrow or \to \longleftarrow - \longrightarrow - \Leftarrow \Rightarrow \Longleftarrow = \Longrightarrow = \leftrightarrow \longleftrightarrow \Leftrightarrow \Longleftrightarrow \leftleftarrows \rightrightarrows\ leftrightarrows \rightleftarrows\ Lleftarrow \Rrightarrow\ twoheadleftarrow \twoheadrightarrow\ leftarrowtail \rightarrowtail\ looparrowleft \looparrowright\ uparrow \downarrow \Uparrow \Downarrow \upuparrows \downdownarrows\ updownarrow \Updownarrow\ nearrow \searrow\ swarrow \nwarrow\ mapsto \longmapsto - \hookleftarrow \hookrightarrow \leftharpoonup \rightharpoonup\ leftharpoondown \rightharpoondown\ upharpoonleft \upharpoonright\ downharpoonleft \downharpoonright\ multimap \rightsquigarrow\ leftrightsquigarrow \leadsto Y Type: Print: Type: Print: \nleftarrow \nrightarrow\ nLeftarrow \nRightarrow\ nleftrightarrow \nLeftrightarrow1 78 MISCELLANEOUS SYMBOLS (miscell.tex) Type: Print: Type: Print: \hbar \hslash\ imath i \jmath \ell \complement\ wp \Re Re \Im Im \partial \infty \smallint \P \S § \prime \backprime\ emptyset \varnothing \Bbbk k \backslash \ \diagup \diagdown\ triangle \nabla\ vartriangle \blacktriangle\ triangledown \blacktriangledown\ square \lozenge \Box P \Diamond Q \blacksquare \blacklozenge\ forall \exists \nexists \neg \angle \sphericalangle\ measuredangle \|\ surd \Vert\ top \bot \dag \ddag \flat \natural\ sharp\ clubsuit \diamondsuit \heartsuit \spadesuit \circledS \bigstar\ mho H \eth \Finv \Game1 79 Additional symbols can be made by stacking one symbol on top of another with the \stackrel command, e.g. $A \stackrel{\alpha}{\rightarrow} B$ gives A B. 180