Nejdříve připomeneme pojmy, které jsou vám známy ze střední školy:

1

Úvod

Nejdříve připomeneme pojmy, které jsou vám známy ze střední školy:

1.1

Elementy matematické logiky

Výroky Připomeňme, že výrok chápeme jako jazykové vyjádření myšlenek, jimiž přisuzujeme předmětům jisté vlastnosti nebo jimiž stanovíme vztahy mezi předměty; je to (jazykový) výraz, o němž má smysl říci, že je pravdivý nebo nepravdivý. Například „číslo 3 je sudéÿ je nepravdivý výrok, naproti tomu sdělení „přijď brzy domůÿ, „číslo Brno je modréÿ, „sin x > 0ÿ výroky nejsou (druhé sdělení je nesmyslná snůška slov, třetí sdělení je tzv. výroková funkce s proměnnou x). Výrokům přiřazujeme tzv. pravdivostní hodnoty: je-li výrok pravdivý, má pravdivostní hodnotu 1, nepravdivý výrok má pravdivostní hodnotu 0. Složené výroky sestavujeme pomocí výrokotvorných částic – spojek; jsou-li p, q výroky, definujeme: p¯, ¬p, p0 p∧q p∨q p⇒q p⇔q

negace výroku p konjunkce výroků p a q disjunkce výroků p a q implikace výroků p a q ekvivalence výroků p a q

opačný výrok a, současně nebo (nevylučovací!) z p plyne q * p je ekvivalentní s q **

* p implikuje q, jestliže p pak q, q je nutná podmínka pro p, p je postačující podmínka pro q, ** p právě když q, p tehdy a jen tehdy když q, p když a jen když q, p je nutná a postačující podmínka pro q. Jednotlivé výrokové spojky mají specifické vlastnosti: například negací pravdivého výroku získáme výrok nepravdivý a naopak, konjunkce dvou výroků je pravdivá pouze v případě, jsou-li oba výroky pravdivé atd. Přehledněji vlastnosti jednotlivých výrokových spojek popíšeme pomocí pravdivostních hodnot: p 1 1 0 0

¬p 0 1

q 1 0 1 0

p∧q 1 0 0 0

p∨q 1 1 1 0

1

p⇒q 1 0 1 1

p⇔q 1 0 0 1

Stejně tak pomocí tabulky pravdivostních hodnot nejsnáze zjistíme, při jaké kombinaci elementárních výroků je pravdivý nebo nepravdivý komplikovanější výrok. Příklad 1.1:

Řešení:

p 1 1 0 0

Vyšetříme výrok (p ∧ q) ⇔ ¬(p ⇒ ¬q).

q 1 0 1 0

¬q 0 1 0 1

p∧q 1 0 0 0

p ⇒ ¬q 0 1 1 1

¬(p ⇒ ¬q) 1 0 0 0

(p ∧ q) ⇔ ¬(p ⇒ ¬q) 1 1 1 1

Daný výrok je tedy pravdivý bez ohledu na to, jsou-li výroky p, q pravdivé nebo nepravdivé. Složitější výroky jsou někdy nepřehledné vzhledem k vysokému počtu závorek, které udávají pořadí, ve kterém se mají jednotlivé spojky aplikovat; proto užíváme konvenci o pořadí, jak „silněÿ spojky vážou elementární výroky. Pořadí je následující: • negace, • konjunkce a disjunkce, • implikace a ekvivalence. Tedy např. místo (p ∧ (q ∨ r)) ⇔ ((p ∧ q) ∨ (p ∧ r)) píšeme p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r), a místo ((¬p) ∧ q) ⇒ (p ∨ (¬q)) píšeme ¬p ∧ q ⇒ p ∨ ¬q.

Viděli jsme, že některé složené výroky mohou mít takový tvar, že jsou vždy pravdivé bez ohledu na to, jsou-li jednotlivé elementární výroky, ze kterých je tento složený výrok sestaven, pravdivé nebo nepravdivé (tedy mají pravdivostní hodnotu 1 při libovolném vyhodnocení); takové výroky se nazývají tautologie; výrok, který je vždy nepravdivý (pro libovolné ohodnocení elementárních výroků má pravdivostní hodnotu 0), se nazývá kontradikce.

2

Uvedeme si některé další tautologie (jako cvičení prověřte, že se o tautologie skutečně jedná): (p ⇔ q) ⇔ (p ⇒ q) ∧ (q ⇒ p) (p ⇒ q) ⇔ (¬q ⇒ ¬p) (p ⇒ q) ⇔ (¬p ∨ q) negace implikace

¬(p ⇒ q) ⇔ (p ∧ ¬q)

De Morganova pravidla

¬(p ∨ q) ⇔ (¬p ∧ ¬q) ¬(p ∧ q) ⇔ (¬p ∨ ¬q) p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)

distributivita

p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r) dvojí negace

p ⇔ ¬(¬p)

zákon vyloučeného třetího

p ∨ ¬p

Až na poslední vztah mají všechny uvedené tautologie tvar ekvivalence; výroky napravo jsou pravdivé právě tehdy, když jsou pravdivé výroky nalevo. Pravdivostní hodnota složeného výroku se tedy nezmění, nahradíme-li dílčí výrok v něm vystupující výrokem s ním ekvivalentním (provedeme ekvivalentní úpravu). To nám umožňuje složité výroky postupně zjednodušovat. Příklad 1.2:

Pomocí výše uvedených ekvivalentních úprav zjednodušíme výrok

¬ [(p ∧ q ⇒ ¬q) ∧ (p ⇒ q)]: ¬ [(p ∧ q ⇒ ¬q) ∧ (p ⇒ q)] ⇔

(De Morganův vzorec)

⇔

¬(p ∧ q ⇒ ¬q) ∨ ¬(p ⇒ q)

⇔

(negace implikace)

⇔

[(p ∧ q) ∧ ¬¬q] ∨ (p ∧ ¬q)

⇔

(dvojí negace)

⇔

(p ∧ q ∧ q) ∨ (p ∧ ¬q)

⇔

⇔

(p ∧ q) ∨ (p ∧ ¬q)

⇔

⇔

p ∧ (q ∨ ¬q)

⇔

⇔

p

(distributivita)

Výrokové funkce – predikáty Představme si, že pro x ∈ R zkoumáme výraz x > 3. Tento výraz není výrok; stane se jím, až za x dosadíme některé konkrétní reálné číslo, a v závislosti na tom, které číslo zvolíme, bude pravdivý nebo nepravdivý. Takový výraz se nazývá výroková funkce (forma), také predikát. Výroková funkce obsahuje proměnné; proměnná se dá chápat 3

jako prázdné místo, kam lze dosazovat libovolné prvky z určité množiny, např R (C), která se nazývá přípustný obor dané proměnné. Po dosazení za všechny proměnné se predikát stane výrokem – buď pravdivým nebo nepravdivým. Prvky množiny, pro něž je výrok pravdivý, tvoří obor pravdivosti výrokové formy. Příklad 1.3:

x 2

∈ N je predikát s přípustným oborem (například) R;

dosadíme-li za x například π, 8, − 32 , dostaneme výroky

π 2

∈ N, 4 ∈ N, − 34 ∈ N,

z nichž druhý je pravdivý a první a třetí nepravdivý. Obor pravdivosti tvoří všechna kladná sudá čísla. Kvantifikátory Je-li V predikát obsahující proměnnou x (event. i další) pak výraz ∃x (V ) nebo ∃x : V

existuje x tak, že platí V chápeme jako tvrzení

∀x (V ) nebo ∀x : V

pro každé x platí V

Přitom ∃ se nazývá existenční kvantifikátor, ∀ se nazývá všeobecný kvantifikátor. Poznamenejme, že ve výrazech s kvantifikátory často uvádíme přímo přípustný obor pro proměnnou; píšeme ∀x ∈ M : V (x), ∃x ∈ M : V (x).

Jestliže predikát V obsahuje jedinou proměnnou x, je ∃x (V ) resp. ∀x (V ) výrok; říkáme, že proměnná x je vázaná kvantifikátorem. V opačném případě jde zase o predikát s tzv. volnou proměnnou a můžeme utvořit nové výrazy (predikáty, výroky) ∀y ∃x (V ), ∃y ∃x (V ) a podobně.

Příklad 1.4: Máme zjistit, který z následujících predikátů s proměnnou x ∈ R je pravdivý výrok: a) x ≤ 2

b) ∀x (x ≤ 2)

c) ∃x (x ≤ 2)

d) ∀x (x ∈ (−∞, 2i ⇔ x ≤ 2) Řešení: a) není výrok (proměnná x je volná); b) je nepravdivý výrok; lze najít číslo a ∈ R (např. a = 3) tak, že výrok a ≤ 2 je nepravdivý; c) je pravdivý výrok; stačí najít jedno konkrétní číslo a ∈ R (např. a = 0) tak, že výrok a ≤ 2 je pravdivý;

4

d) jedná se o pravdivý výrok, kterým definujeme interval. Kvantifikátory tedy můžeme řadit za sebou, přičemž na jejich pořadí záleží. Např. ∀x ∈ R ∃y ∈ R (x2 = y)

je jiný výrok než

∃y ∈ R ∀x ∈ R (x2 = y)

(první je pravdivý, druhý nepravdivý). Příklad 1.5: x a y:

Máme vyšetřit pravdivost následujících výroků pro reálné proměnné

a) ∀x ∃y (x < y)

b) ∃y ∀x (x < y)

Řešení: a) Výrok je pravdivý; stačí pro libovolné pevně zvolené x položit y = x + 1 – výrok x < x + 1 je pravdivý pro každé reálné x. b) Výrok je nepravdivý; jeho pravdivost by znamenala, že existuje největší reálné číslo. (∞ není reálné číslo!) Při vyšetřování reálných čísel se osvědčilo zavést symbol R = R ∪ {−∞, ∞}. Použijeme-li toto označení, můžeme formulovat pravdivý výrok ∃y ∈ R ∀x ∈ R (x < y).

Často potřebujeme utvořit negaci výroku s kvantifikátory. Užíváme přitom tyto ekvivalence: ¬ (∀x ∈ M : V (x)) ⇔ ∃x ∈ M : ¬V (x),

¬ (∃x ∈ M : V (x)) ⇔ ∀x ∈ M : ¬V (x).

Příklad 1.6: ¬ [∀x ∈ M : (P (x) ⇒ Q(x))] ⇔ ∃x ∈ M : ¬[P (x) ⇒ Q(x)] ⇔ ∃x ∈ M : (P (x) ∧ ¬Q(x)).

5

1.2

Matematická teorie a její výstavba

Hlavním znakem současné matematiky je, že své jednotlivé discipliny buduje axiomaticky. Stručně lze tuto výstavbu charakterizovat takto: Výsledky svých bádání vyjadřuje každý obor v matematických větách, nové pojmy zavádí pomocí definic. Věty dokazuje pomocí dříve dokázaných vět prostředky matematické logiky, v definicích se vyskytují pojmy, které jsme definovali dříve. Důsledný postup v tomto směru, jemuž říkáme dedukce, předpokládá, že na začátku jsou tzv. primitivní neboli nedefinované pojmy a soubor vět, které přijímáme bez důkazu (prohlásíme je za pravdivé), tzv. axiómy. Výběr soustavy primitivních pojmů a axiomů není zcela libovolný, nýbrž se řídí různými hledisky; především účelem, za jakým je disciplina budována. Úlohu zde často hraje též intuice, která se opírá o zkušenost, pokus apod. Na systém axiomů klademe zejména požadavek bezespornosti (nemožnost odvodit výrok a současně jeho negaci), nezávislosti (žádný z axiomů nelze odvodit z ostatních logickou dedukcí) a úplnosti (každou větu teorie, která není axiomem, lze buď dokázat, nebo vyvrátit). Zatímco na požadavku bezespornosti vždy trváme, nebývají zbylé dva z různých důvodů splněny.

Známým příkladem axiomatického vybudování takové teorie z historie matematiky je elementární geometrie v Euklidových „Základechÿ (asi r. 350 před n.l.). V knize se užívají primitivní pojmy jako „bodÿ, „přímkaÿ, „rovinaÿ, „leží naÿ apod., axiomatizují se základní geometrické vlastnosti. Slavný je pátý axiom - bodem mimo přímku lze vést právě jednu rovnoběžku - jehož nahrazením jiným axiomem dostaneme tzv. neeuklidovskou geometrii. Z pozdější doby uveďme jako příklad systém Peanových axiomů množiny přirozených čísel, které jsou základem pro vybudování aritmetiky reálných a komplexních čísel. Předpokládá se pouze znalost symbolů = (rovná se) a 6= (nerovná se): 1. axiom: 1 je přirozené číslo 2. axiom: Ke každému přirozenému číslu n existuje právě jedno přirozené číslo n0 , které nazýváme následníkem čísla n. 3. axiom: Pro každé přirozené číslo n platí n0 6= 1. 4. axiom: Je-li n0 = m0 , je n = m. 5. axiom: Nechť číslo 1 má vlastnost V a nechť platí: má-li přirozené číslo n vlastnost V , má i následovník tohoto čísla vlastnost V . Potom všechna přirozená čísla mají vlastnost V (princip indukce). S uvedenými základními požadavky výstavby axiomatické teorie jsou spojeny ještě další otázky, např. otázka existence struktury (tzv. modelu), která soustavě axiomů vyhovuje. Technika - inženýra zpravidla nezajímá matematická teorie sama o sobě, ale jako prostředek k porozumění odborným disciplinám, kde se matematika užívá, a k řešení inženýrských úloh. I když se otázkami výstavby matematické teorie nebudeme podrobně zabývat, domníváme se, že základním prvkům výstavby musí v dostatečné míře rozumět každý, 6

kdo chce matematiku s úspěchem užívat. Proto pojednáme o základních prvcích výstavby každé matematické teorie. Strukturu vybudované matematické discipliny a do značné míry i její studium je možno stručně charakterizovat trojicí základních stavebních kamenů: definice, věta, důkaz. Definice vymezuje význam zaváděného pojmu příslušné discipliny pomocí známých, tj. dříve definovaných nebo primitivních pojmů. Může mít různou formu; častá je forma ekvivalence začínající slovy „říkáme, že. . .ÿ. Příklad 1.7:

Říkáme, že pravoúhelník je čtverec, právě když je rovnostranný.

Jako ekvivalenci musíme chápat definici, i když je vyslovena formou implikace. Proto i definici „pravoúhelník je čtverec, jestliže je rovnostrannýÿ musíme chápat tak, jak je uvedeno v předchozím příkladě. Někdy zavádíme nový pojem pomocí tzv. definiční rovnosti, např.
n Eulerovo číslo e := lim 1 + n1 . n→+∞

Dvojtečka před rovnítkem upozorňuje na to, že objekt na pravé straně (jehož existence byla již předtím dokázána) označujeme symbolem uvedeným na levé straně. Nepřípustná je tzv. definice v kruhu, tj. užijeme-li v definujícím výrazu pojem, který máme definovat. Definice musí být korektní, tj. musí být jednak zaručena existence objektu, který je definován, jednak musí umožnit jednoznačně rozhodnout, zda daný objekt má či nemá vlastnost, která se definuje. Definice nemůže být také ve sporu s již dříve zavedenými pojmy a s axiomy. Své výsledky formuluje matematická disciplina v pravdivých výrocích, které se nazývají věty (poučky, teorémy). Věty, které obsahují návod k provedení výpočtu nebo konstrukce, se nazývají též pravidla. Za větu dané teorie však nepovažujeme každý výrok, ale pouze takový, který má pro výstavbu teorie nebo její aplikaci určitý význam. Jsou to zejména výroky začínající obecným kvantifikátorem (obecné výroky) nebo existenčním kvantifikátorem (existenční výroky), případně výroky začínající některým číselným kvantifikátorem. Většina matematických vět, které mají charakter obecného výroku, je formulována jako implikace nebo ekvivalence. V implikaci tvaru p ⇒ q se výrok p nazývá předpoklad, výrok q závěr. Říkáme, že p je postačující podmínkou pro q nebo též že q je nutná podmínka pro p. Příklad 1.8:

Pro každé celé číslo platí: je-li dělitelné šesti, je dělitelné dvěma.

Tato věta je obecným výrokem. Výrok „číslo je dělitelné šestiÿ je předpoklad, výrok „číslo je dělitelné dvěmaÿ je závěr. První výrok je postačující podmínkou, druhý podmínkou nutnou. Tedy k tomu, aby celé číslo bylo dělitelné dvěma, stačí – není však nutné – aby bylo dělitelné šesti, k tomu, aby celé číslo bylo dělitelné šesti, je nutné – ale nestačí – aby bylo dělitelné dvěma. Symbolicky můžeme uvedenou větu zapsat takto: ∀n ∈ Z : 6|n ⇒ 2|n. (Čteme: jestliže šest dělí n, pak dvě dělí n.)

7

Při slovní formulaci matematických vět se však často odchylujeme od klasické formy implikace, tj. spojení „ jestliže. . ., pak. . .ÿ, vynecháváme obvykle obecný kvantifikátor, neuvádíme obor proměnných apod. To může zejména začátečníka splést a je proto vhodné, abychom si takovou větu převedli do „přesné matematické řečiÿ. Například věta v předchozím příkladu bývá častěji formulována takto: Číslo dělitelné šesti je dělitelné dvěma. Větě, v níž je předpoklad vyměněn za závěr, se říká věta obrácená. Ta ovšem nemusí platit. Například věta obrácená k poslední uvedené větě zní: Číslo dělitelné dvěma je dělitelné šesti. Je zřejmé, že neplatí. Větu, která má tvar implikace p ⇒ q, můžeme též vyslovit ve tvaru ¬q ⇒ ¬p, protože oba výroky jsou logicky ekvivalentní. Takto formulovaná věta se někdy nazývá obměněná věta k dané větě. Například k větě v předchozím příkladu obměněná věta zní „není-li číslo dělitelné dvěma, není dělitelné šestiÿ, která vyjadřuje totéž co věta původní. Má-li věta tvar ekvivalence, tedy výroku p ⇔ q, je konjunkcí dvou implikací, tj. (p ⇒ q) ∧ (q ⇒ p), neboli konjunkcí dané věty a věty k ní obrácené. Podmínka p(q) je nutná a postačující pro platnost podmínky q(p). Větu často vyslovujeme ve tvaru „p platí tehdy a jen tehdy, platí-li qÿ nebo „p platí, právě když platí qÿ. Příklad 1.9: Věta „sudé číslo je dělitelné pěti, právě když končí nulouÿ je konjunkcí implikací „ jestliže je sudé číslo dělitelné pěti, pak končí nulouÿ a „ jestliže celé číslo končí nulou, pak je sudé a dělitelné pětiÿ. Podmínka „sudé číslo je dělitelné pětiÿ je nutná a postačující pro to, aby „číslo končilo nulouÿ a obráceně. Důkazem věty rozumíme logický proces, jehož účelem je prokázat pravdivost tvrzení (závěru) věty pomocí axiomů, definic a dříve dokázaných vět. Důkazy mohou mít různou formu, nejčastějšími typy důkazu jsou důkaz přímý, důkaz nepřímý a důkaz úplnou indukcí. Při přímém důkazu věty mající tvar obecného výroku ∀x ∈ M : P (x) ⇒ Q(x) zpravidla postupujeme takto: Představíme si, že na místě proměnné x je libovolný prvek a ∈ M a dokazujeme výrok P (a) ⇒ Q(a), čímž jsme vlastně vyloučili z dalších úvah obecný kvantifikátor. Najdeme konečnou posloupnost výroků p1 , p2 , ..., pk takových, že každý z výroků je buď dříve dokázanou větou příp. axiomem, nebo předpokladem P (a). Jestliže z těchto výroků již plyne výrok Q(a), pak platí implikace P (a) ⇒ Q(a). Jak tuto posloupnost zvolit, v tom zpravidla spočívá „vtipÿ důkazu. Předchozí popis vlastně znamená opakované použití odvozovacího pravidla Modus Ponens, které má následující tvar: Jsou-li pravdivé výroky p a p ⇒ q, je pravdivý výrok q.

Příklad 1.10: Dokážeme větu: Jestliže a2 +b2 = 1, pak |ab| ≤ 21 . Přesněji formulováno, jde o větu: Pro všechna reálná čísla a, b platí: Je-li a2 + b2 = 1, pak |ab| ≤ 21 . 8

Důkaz: Platí (|a| − |b|)2 ≥ 0; přitom (|a| − |b|)2 = |a|2 − 2|a||b| + |b|2 = a2 − 2|ab| + b2 , takže a2 − 2|ab| + b2 ≥ 0. Odtud 2|ab| ≤ a2 + b2 . protože podle předpokladu je a2 + b2 = 1, máme 2|ab| ≤ 1, odkud |ab| ≤ 21 . (V průběhu důkazu jsme použili známý vzorec pro (x − y)2 , vlastnosti absolutní hodnoty a vlastnosti uspořádání.) Nepřímý důkaz implikace p ⇒ q provádíme tak, že předpokládáme pravdivost její negace, tj. výroku p ∧ ¬q a dokážeme nepravdivost této negace, tj. pravdivost výroku ¬(p ∧ ¬q) (podle logického zákona o vyloučeném třetím nemůže platit výrok a současně jeho negace). To můžeme udělat tak, že přímým důkazem dokážeme platnost jedné z těchto implikací, které jsou s posledním výrokem ekvivalentní: I. ¬q ⇒ ¬p, II. p ∧ ¬q ⇒ ¬p, III. p ∧ ¬q ⇒ q, IV. p ∧ ¬q ⇒ r ∧ ¬r (r je libovolný výrok), V. p ∧ ¬q ⇒ ¬s (s je libovolný známý pravdivý výrok). Implikaci I. známe jako větu obměněnou k dané větě, v případě IV. vede implikace k současné platnosti výroku a jeho negace, v případě V. k neplatnosti známého pravdivého výroku. V posledních dvou případech říkáme, že jsme došli ke sporu. Příklad 1.11: Dokažme větu: Jsou-li dvě přímky v rovině rovnoběžné s třetí, pak jsou rovnoběžné navzájem. Důkaz: přímky označme a, b, c, znak k je znakem rovnoběžnosti. Je-li výrok p : akc ∧ bkc, výrok q : akb, dokážeme nepřímo implikaci p ⇒ q. předpokládejme tedy, že platí ¬q : a ∦ b (tj. přímka a není rovnoběžná s přímkou b). Výrok ¬q znamená že se přímky a, b protínají v jednom bodě; odtud a z výroku p plyne, že bodem lze vést k přímce dvě různé rovnoběžky, což je ve sporu s axiomem, že „bodem lze vést k přímce jedinou rovnoběžkuÿ. Došli jsme tedy k (spornému) závěru, že p ∧ ¬q ⇒ ¬s, kde s je uvedený axiom o rovnoběžkách. Úplnou (též matematickou) indukcí dokazujeme výrok tvaru ∀n ∈ N, n ≥ n0 : P (n), kde P (n) je výroková forma, n0 přirozené číslo. Často bývá n0 = 1. Princip důkazu spočívá na vlastnosti přirozených čísel, vyjádřené pátým Peanovým axiomem. Důkaz se provádí ve dvou krocích: I. Dokážeme, že věta je pravdivá pro n = n0 . II. Předpokládáme platnost věty pro přirozené číslo k ≥ n0 a dokážeme její pravdivost i pro k + 1. Tím je dokázáno, že platí pro včechna přirozená čísla n ≥ n0 . Příklad 1.12: Dokažme, že platí rovnost 1 + 2 + · · · + n = 12 n(n + 1) pro všechna přirozená n. Důkaz: I. Pro n = 1 rovnost zřejmě platí. II. Předpokládejme, že rovnost platí pro nějaké přirozené k ≥ 1, tj. 1 + 2 + · · · + k = 1 k(k +1), a dokažme, že platí i pro k +1, tj. 1+2+· · ·+k +(k +1) = 12 (k +1)(k +2). Levou 2 stranu můžeme psát ve tvaru 1+2+· · ·+k +(k +1) = 12 k(k +1)+(k +1) = 12 (k +1)(k +2) a to je pravá strana dokazované rovnosti.

9

1.3

Množiny

Ze střední školy je vám známo, že v matematice nazýváme jakýkoliv soubor či systém navzájem rozlišitelných objektů množinou. Množiny vymezujeme výčtem prvků nebo predikátem – charakterizací (vlastností): Je-li V (x) predikát, potom symbol {x | V (x)} označuje množinu všech prvků a, pro které je V (a) pravdivý výrok; někdy uvádíme obor přípustný pro proměnnou x a píšeme např.: {x ∈ R | V (x)}. Příklad 1.13:

{x ∈ R | x ≤ 2} = (−∞, 2i,

{0, 1, 2, 3, 4} = { x | x je celé číslo a 0 ≤ x ≤ 4}. Značí-li A množinu jistých objektů a x je jeden z těchto předmětů, říkáme, že x je prvkem množiny A (x patří do A) a píšeme x ∈ A. Není-li y prvkem množiny A, píšeme y 6∈ A. Počet prvků konečné množiny nazýváme mohutnost množiny a značíme symbolem |A|. V dalším textu zavedeme pojem mohutnosti i pro nekonečné nmožiny. Jestliže S je množina, jejíž prvky jsou opět množiny, nazýváme ji zpravidla systémem množin. Dvě množiny mají stejné prvky (tedy jsou si rovny), jestliže jsou charakterizovány ekvivalentními výroky: {x | U (x)} = {x | V (x)} ⇔ ∀x (U (x) ⇔ V (x)). Operace s množinami Nechť A, B jsou množiny. Potom definujeme vztahy mezi množinami a operace s množinami pomocí následujících výroků: rovnost množin

A = B ⇔ ∀x(x ∈ A ⇔ x ∈ B)

podmnožina

A ⊂ B ⇔ ∀x(x ∈ A ⇒ x ∈ B)

průnik množin

∀x(x ∈ A ∩ B ⇔ x ∈ A ∧ x ∈ B)

sjednocení množin

∀x(x ∈ A ∪ B ⇔ x ∈ A ∨ x ∈ B)

rozdíl množin

∀x(x ∈ A \ B ⇔ x ∈ A ∧ x 6∈ B)

Poznamemejme, že platí A = B ⇔ A ⊂ B ∧ B ⊂ A. Je-li A ⊂ B, označujeme množinu B \A symbolem A a nazýváme ji doplňkem (komplementem) množiny A v množině B. Tuto symboliku používáme především tehdy, zkoumáme-li komplementy více množin k jedné pevné množině, „univerzuÿ.

10

Příklad 1.14: Nechť A = {1, 2, 3, 4}, B = {2, 4, 6}, C = {1, 2, 4, 8} a X = {1, 2, . . . , 10}. Máme popsat výčtem prvků množiny (doplňky se rozumí vzhledem k X): A ∪ B, B ∩ C, A \ B, B \ A, A ∪ (B ∩ C), (A ∪ B) ∩ C, A ∪ B, A ∪ B. Řešení: A ∪ B = {x | x ∈ A ∨ x ∈ B} = {1, 2, 3, 4, 6} B ∩ C = {x | x ∈ B ∧ x ∈ C} = {2, 4} A \ B = {x | x ∈ A ∧ x 6∈ B} = {1, 3} B \ A = {x | x ∈ B ∧ x 6∈ A} = {6} A ∪ (B ∩ C) = {x | x ∈ A ∧ x ∈ B ∩ C} = {1, 2, 3, 4} (A ∪ B) ∩ C = {x | x ∈ A ∪ B ∧ x ∈ C} = {1, 2, 4, } A ∪ B = {x | x ∈ X ∧ x 6∈ A ∪ B} = {5, 7, 8, 9, 10} A = {x | x ∈ X ∧x 6∈ A} = {5, 6, 7, 8, 9, 10}, B = {x | x ∈ X ∧x 6∈ B} = {1, 3, 5, 7, 8, 9, 10} A ∪ B = {x | x ∈ A ∨ x ∈ B} = {1, 3, 5, 6, 7, 8, 9, 10} Povšimněme si množin z předchozího příkladu ještě z jiné strany – zkoumejme jejich mohutnosti. Zřejmě je |A| = 4, |B| = 3, |C| = 4,

jistě ale |A ∪ B| = 6 |A| + |B|,

protože prvky, které jsou společné oběma množinám, bychom počítali dvakrát. Zřejmě tedy platí |A ∪ B| = |A| + |B| − |A ∩ B|.

Na množinách A, B, C z předchozího příkladu můžeme demonstrovat zobecnění pravidla na tři množiny: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C| : A = {1, 2, 3, 4},

|A| = 4,

B = {2, 4, 6},

|B| = 3,

C = {1, 2, 4, 8},

|C| = 4,

A ∩ B = {2, 4},

|A ∩ B| = 2,

A ∩ C = {1, 2, 4},

|A ∩ C| = 3,

B ∩ C = {2, 4},

|B ∩ C| = 2,

A ∩ B ∩ C = {2, 4},

|A ∩ B ∩ C| = 2,

A ∪ B ∪ C = {1, 2, 3, 4, 6, 8},

|A ∪ B ∪ C| = 6, 11

a také |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C| = 4 + 3 + 4 − 2 − 3 − 2 + 2 = 6. Toto pravidlo zobecněné na n konečných množin se nazývá princip inkluze a exkluze. Příklad 1.15:

V jistém podniku sestavili následující přehled o svých zaměstmamcích:

V podniku pracuje celkem 250 mužů a 200 žem. Předepsanou kvalifikaci má 160 mužů a 140 žen. Do práce dojíždí 180 mužů a 100 žen. Kvalifikovaných mužů dojíždí 150, kvalifikovaných žen 20. Máme ukázat, že hlášení je nepravdivé. Řešení: Ukážeme, že podle tohoto hlášení by mohutnost množiny nekvalifikovaných nedojíždějících žen byla rovna −20. Množina neobsahující žádné prvky se nazývá prázdná množina . Tuto množinu značíme symbolem ∅, výrok ∃x (x ∈ ∅) je tedy nepravdivý. Prázdnou množinu můžeme definovat libovolnou kontradikcí, například ∅ = {x | x ∈ A ∧ x 6∈ A}. Prázdná množina má mnoho překvapivých vlastností, se kterými se setkáme později; některé jsou ověřeny v následujícím příkladu: Příklad 1.16: 1. Ukažme, že pro libovolnou množinu A platí ∅ ⊂ A. 2. Prověřme pravdivost následujících výroků: a) ∅ 6∈ ∅ b) ∅ ⊂ ∅ c) ∅ ∈ {∅}

d) ∅ ⊂ {∅}

Řešení: 1. Použijeme výrok definující podmnožinu: ∅ ⊂ A ⇔ ∀x(x ∈ ∅ ⇒ x ∈ A) x ∈ ∅ je nepravda, tedy implikace ve zkoumaném výroku je vždy pravdivá (nepravda ⇒ cokoliv). 2.

a) b) c) d)

Prázdná množina nemá žádné prvky, tedy ani samu sebe. viz 1. pro A = ∅. {∅} je množina zadaná výčtem prvků, jediný její prvek je ∅; tedy ∅ ∈ {∅}. viz 1. pro A = {∅}.

V první části předchozího příkladu jsme ukázali, že pro každou množinu A platí ∅ ⊂ A; podobně jistě platí A ⊂ A pro každou množinu. O množinách ∅, A říkáme, že jsou to nevlastní podmnožiny množiny A; všechny ostatní podmnožiny množiny A se nazývají vlastní. Množinu všech podmnožin dané množiny A nazýváme potenční množinou a označujeme P(A). Tedy P(A) := {X | X ⊂ A}. 12

Příklad 1.17:

P({a, b}) = {∅, {a}, {b}, {a, b}}.

Ukážeme,že je-li A konečná množina, |A| = n, platí |P(A)| = 2n : Podmnožinu o k prvcích
(v množině A) můžeme utvořit nk různými způsoby (je to počet kombinací k-té třídy z n prvků). Máme tedy

n n k-prvkových podmnožin podmnožin o 0 prvcích (což je ∅) k 0
.. n jednoprvkových podmnožin . 1

n n dvouprvkových podmnožin n-prvkových podmnožin 2 n Celkem         n n n n + + ··· + + ··· + = (1 + 1)n = 2n . 0 1 k n Proto se také někdy množina všech podmnožin dané množiny A označuje symbolem 2A . Příklad 1.18:

Pro množiny z příkladu 1.14 máme určit

P(A ∩ C), P(B), P(A ∩ C) ∩ P(B) a P(A ∩ B ∩ C). Řešení: A ∩ C = {1, 2, 4} P(A ∩ C) = {∅, {1}, {2}, {4}, {1, 2}, {1, 4}, {2, 4}, {1, 2, 4}}, P(B) = {∅, {2}, {4}, {6}, {2, 4}, {2, 6}, {4, 6}, {2, 4, 6}}, P(A ∩ C) ∩ P(B) = {∅, {2}, {4}, {2, 4}}; A ∩ B ∩ C = {2, 4}, P(A ∩ B ∩ C) = {∅, {2}, {4}, {2, 4}}. Věta 1.19: (Pravidla pro množinové operace) Jsou-li A, B, U množiny, A ⊂ U, B ⊂ U , U \ A = A, U \ B = B, platí:  A∪B =B∪A komutativní zákony A∩B =B∩A  A ∪ (B ∪ C) = (A ∪ B) ∪ C asociativní zákony A ∩ (B ∩ C) = (A ∩ B) ∩ C  A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C distributivní zákony A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)  A∪B =A∩B De Morganova pravidla A∩B =A∪B Kartézským součinem A × B množin A, B (v tomto pořadí) nazýváme množinu A × B = {(a, b) | a ∈ A ∧ b ∈ B}. 13

Přitom (a, b) znamená uspořádanou dvojici prvků a, b. Je-li speciálně A = B, pak A × A značíme A2 . Například R2 bude značit množinu všech uspořádaných dvojic (x, y) reálných čísel. Jsou-li A, B, A 6= B neprázdné množiny, pak A × B 6= B × A: Příklad 1.20: Nechť A = {1, 2}, B = {3}. Potom A × B = {(1, 3), (2, 3)}, a B × A = {(3, 1), (3, 2)}. Obecně zavádíme kartézský součin systému množin: A1 × A2 × · · · × An = {(x1 , x2 , . . . , xn ) | x1 ∈ A1 , x2 ∈ A2 , . . . , xn ∈ An }; (x1 , x2 , . . . , xn ) je uspořádaná n-tice. Je-li A1 = A2 = · · · = An = A, označujeme A × A × · · · × A =: An .

14

2

Relace a operace na množině

2.1

Binární relace, zobrazení

Binární relace Definice 2.1: Libovolnou množinu R, která je podmnožinou kartézského součinu množin A, B, tj. R ⊂ A × B, nazveme (binární) relací z A do B. Je-li A = B, R ⊂ A2 , řekneme, že R je relace na množině A. Je-li (x, y) ∈ R, řekneme, že prvky x, y (v tomto pořadí!) jsou v relaci R. Inverzní relace R−1 ⊂ B × A k relaci R je definovaná vztahem (y, x) ∈ R−1 ⇔ (x, y) ∈ R.

Pro přehlednější charakterizaci relace se někdy používají jiné popisy, než výčtem dvojic, které jsou v relaci. Možnosti popisů ukážeme na příkladu: Příklad 2.2: Nechť A = {a1 , a2 }, B = {b1 , b2 , b3 , b4 } a R = {(a1 , b2 ), (a1 , b3 ), (a2 , b1 ), (a2 , b2 ), (a2 , b4 )}. maticový popis

a1 a2

b1 0 1

b2 1 1

Příklad 2.3:

b3 1 0

graf relace

spojnicový popis

b4 0 1

Nechť A = {2, 3, 4}, B = {3, 4, 5, 6, 7, 8, 9}. Potom

R = {(2, 4), (2, 6), (2, 8), (3, 3), (3, 6), (3, 9), (4, 4), (4, 8)} je relace z A do B, kterou můžeme interpretovat tak, že (x, y) ∈ R, právě když x dělí y. Přitom R−1 = {(4, 2), (6, 2), (8, 2), (3, 3), (6, 3), (9, 3), (4, 4), (8, 4)} a tuto relaci můžeme interpretovat tak, že (a, b) ∈ R−1 , právě když a je dělitelné b. Relacím na množině se budeme věnovat podrobně později; na tomto místě si povšimneme blíže speciálního typu relací z jedné množiny do druhé, kterými jsou zobrazení (funkce).

15

Zobrazení (funkce) Definice 2.4:

Nechť F ⊂ A × B je relace pro kterou platí:

∀x ∈ A ∃!y ∈ B : (x, y) ∈ F, neboli ke každému x ∈ A existuje právě jedno y ∈ B, pro které je (x, y) ∈ F . Potom řekneme, že F je zobrazení z A do B a píšeme F : A → B, y = F (x). x se nazývá argument funkce F , y funkční hodnota. Příklad 2.5: Nechť A = {a1 , a2 , a3 , a4 }, B = {b1 , b2 , b3 }. Máme zjistit, zda následující relace F1 , F2 jsou zobrazení: F1 = {(a1 , b1 ), (a1 , b2 ), (a2 , b1 ), (a3 , b2 ), (a4 , b3 )},

F2 = {(a1 , b3 ), (a2 , b2 ), (a3 , b1 ), (a4 , b2 )}.

Řešení: F1 není zobrazení, protože (a1 , b1 ), (a1 , b2 ) ∈ F1 , F2 je zobrazení.

Definice 2.6: Zobrazení F : A → B se nazývá surjekce (surjektivní zobrazení, zobrazení A na B), jestliže platí ∀y ∈ B ∃x ∈ A : y = F (x). Zobrazení F : A → B se nazývá injekce (injektivní zobrazení, prosté zobrazení), jestliže platí ∀x1 , x2 ∈ A (x1 6= x2 ⇒ F (x1 ) 6= F (x2 )) . Zobrazení F : A → B se nazývá bijekce (bijektivní zobrazení, jednojednoznačné zobrazení), je-li současně surjekce a injekce. Jako cvičení dokažte větu: Věta 2.7: Zobrazení F : A → B je bijektivní, právě když inverzní relace F −1 ⊂ B × A je zobrazení F −1 : B → A. Definice 2.8:

Zobrazení F −1 z předchozí věty se nazývá inverzní zobrazení.

Pomocí zobrazení se definují mohutnosti nekonečných množin: 16

Definice 2.9: Nechť N značí množinu přirozených čísel. Řekneme, že množina A je spočetná, jestliže existuje bijekce F : N → A. Nekonečná množina, která není spočetná, se nazývá nespočetná. Mohutnost spočetné množiny označujeme symbolem ℵ0 . (ℵ je první písmeno arabské abecedy „alefÿ.) Poznamenejme, že existence bijekce F : N → A znamená, že prvky množiny A můžeme seřadit do posloupnosti – označíme F (1) = a1 , F (2) = a2 , . . . a každé a ∈ A je podle předpokladu obrazem některého přirozeného čísla (a současně každé přirozené číslo k se na některé ak ∈ A zobrazí). Příklad 2.10:

Množina všech sudých celých čísel

A = {2, 4, 6, . . . } = {y | y = 2x, x ∈ N} je spočetná – hledaná bijekce má tvar F : N → A, F (x) = 2x. Příklad 2.11:

Ukážeme, že množina {x | 0 < x < 1} = (0, 1) je nespočetná.

Řešení: Předpokládejme, že tato množina je spočetná, tedy že existuje bijekce F : N → (0, 1) a prvky intervalu (0, 1) můžeme seřadit do posloupnosti, tedy že platí (0, 1) = {x1 , x2 , x3 , . . . }. Každé číslo tohoto intervalu má dekadický rozvoj tvaru 0, a1 a2 a3 . . . , ai ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Některá racionální čísla mají dva rozvoje – např. 1 = 0, 50000 . . . , 2

kde

1 = 0, 49999 . . . . 2

ale také

(O prvním rozvoji říkáme, že je konečný – nuly na konci obvykle nepíšeme, o druhém říkáme že je nekonečný.) V případě dvou možných rozvojů pro jedno číslo vezmeme v úvahu ten konečný. Napíšeme dekadické rozvoje předpokládané posloupnosti pod sebe: x1 x2 x3 x4 x5

= = = = =

0, 0, 0, 0, 0,

a11 a21 a31 a41 a51

a12 a22 a32 a42 a52

a13 a23 a33 a43 a53

a14 a24 a34 a44 a54

a15 a25 a35 a45 a55

··· ··· ··· ··· ···

Zvolme reálné číslo y tvaru  y = 0, b1 b2 b3 . . . ,

kde bk =

akk + 1, je-li akk = 6 9, 0 je-li akk = 9.

Zřejmě je y ∈ (0, 1), ale není prvkem naší posloupnosti, protože se od každého xi liší v i-té cifře. Proto se prvky intervalu (0, 1) nedají seřadit do posloupnosti, tedy požadovaná bijekce F : N → (0, 1) neexistuje a tento interval je nespočetná množina. 17

Definice 2.12: je funkce

Nechť A ⊂ U, U univerzum. Charakteristická funkce množiny A 

χA : U → {0, 1},

χA (x) =

1 pro x ∈ A 0 pro x 6∈ A

Příklad 2.13: Nechť univerzum U = R– množina všech reálných čísel, nechť Q je množina všech racionálních čísel. Potom klademe  1 pro x racionální χ(x) := χQ (x) = 0 pro x iracionální Relace na množině Definice 2.14: Binární relace R ⊂ A × A se nazývá relace na množině A. Vztah (x, y) ∈ R, zapisujeme ve tvaru xRy (infix), nebo R(x, y) (prefix). Relace R na množině A se nazývá reflexivní,

jestliže platí

xRx ∀x ∈ A,

symetrická,

jestliže

xRy ⇒ yRx ∀x, y ∈ A,

antisymetrická,

jestliže

xRy ∧ yRx ⇒ x = y ∀x, y ∈ A,

tranzitivní,

jestliže

xRy ∧ yRz ⇒ xRz ∀x, y, z ∈ A.

Příklad 2.15: 1. Identická relace (relace rovnosti) na množině A je relace ∆A = {(x, x) | x ∈ A}. Značí se také symbolem idA . Je reflexivní, symetrická a tranzitivní. 2. Nechť M je množina a P(M ) systém jejích podmnožin. Potom inkluze ⊂ je relace na P(M ) (A, B) ∈⊂⇔ A ⊂ B), která je zřejmě reflexivní, antisymetrická a tranzitivní. 3. Nechť N je množina přirozených čísel. Relace ≤ definovaná na N vztahem (m, n) ∈≤⇔ m ≤ n je opět reflexivní, antisymetrická a tranzitivní. Ekvivalence a rozklady Definice 2.16: Systém A neprázdných podmnožin množiny A se nazývá rozklad množiny A, jestliže platí: [ 1. Ai = A, 2. pro Ai , Aj ∈ A, i 6= j je Ai ∩ Aj = ∅. i

Množiny systému A se nazývají třídy rozkladu. 18

Příklad 2.17: Uvažujme množinu A v sousedním obrázku. Potom A = {A1 , A2 , A3 , A4 , A5 , A6 } je rozklad množiny A, A1 , . . . , A6

jsou třídy rozkladu.

Definice 2.18: Reflexivní, symetrická a tranzitivní relace ε na množině A se nazývá relace ekvivalence. Pro každý prvek a ∈ A položíme

[a] := {x ∈ A | x ε a}.

Poznámka: Ekvivalenci obvykle značíme symboly ∼, ' a píšeme místo a ε b raději a ∼ b atd. Věta 2.19:

Platí

1. a ∈ [a] 2. [a] ∩ [b] 6= ∅ ⇒ [a] = [b]. Důkaz: Je-li x ∈ [a] ∩ [b], potom platí x ∼ a ∧ x ∼ b. Odtud ze symetrie ∼ plyne a ∼ x ∧ x ∼ b a odtud z tranzitivity dostaneme a ∼ b, neboli [a] = [b].

Systém množin {[a] | a ∈ A} tedy tvoří rozklad na množině A indukovaný ekvivalencí ∼. Naopak, je-li dán rozklad A množiny A, potom existuje ekvivalence ∼, která tento rozklad indukuje: Stačí definovat x ∼ y ⇔ x, y patří do téže třídy rozkladu A.

Příklad 2.20:

Nechť A = {a, b, c, d, e} a

∼ = {(a, a), (a, b), (b, a), (b, b), (c, c), (d, d), (d, e), (e, d), (e, e)} je ekvivalence na A. Potom [a] = {a, b} = [b], [c] = {c}, [d] = {d, e} = [e]. Rozklad má tvar:

a |{z}b

c |{z}

d |{z}e

Příklad 2.21: Libovolné zobrazení F : A → B indukuje na A ekvivalenci, tedy také rozklad, předpisem ∀a1 , a2 ∈ A : a1 ∼ a2 ⇔ F (a1 ) = F (a2 ). Například charakteristická funkce χ z příkladu 2.13, χQ : R → {0, 1} vytvoří rozklad reálných čísel na racionální a iracionální. 19

Uspořádání Definice 2.22: Reflexivní, tranzitivní a antisymetrická relace ≺ ⊂ A × A se nazývá uspořádání. Platí tedy • a≺a • a≺b ∧ b≺c ⇒ a≺c • a ≺ b ∧ b ≺ a ⇒ a = b. Říkáme, že (A, ≺) – množina A vybavená relací uspořádání – je uspořádaná množina. Uspořádání se obvykle označuje „nesymetrickými symbolyÿ ≺, ≤ a pod. Příklad 2.23: Uvažujme množinu M a její podmnožiny A, B, C, D, v následujícím obrázku. Potom ({M, A, B, C, D}, ⊂) je uspořádaná množina. Uspořádání můžeme znázornit tzv. Hasseovým diagramem – viz obrázek napravo.

Definice 2.24: Buď (A, ≤) uspořádaná množina. Prvky a, b ∈ A se nazývají nesrovnatelné, jestliže neplatí ani a ≤ b, ani b ≤ a. Píšeme a k b. Příklad 2.25: Prvky A, D z předchozího příkladu jsou nesrovnatelné – neplatí ani A ⊂ D, ani D ⊂ A. Definice 2.26: Uspořádaná množina, ve které nejsou nesrovnatelné prvky, se nazývá řetězec resp. lineárně uspořádaná množina. Příklad 2.27:

({1, 2, 3, 4}, ≤) je řetězec; také (N, ≤) je řetězec.

Definice 2.28: Nechť (M, ≤) je uspořádaná množina, B ⊂ M . Prvek b ∈ M takový, že pro každé x ∈ B je x ≤ b (x ≥ b) se nazývá horní (dolní) ohraničení množiny B. Horní resp. dolní ohraničení množiny M se nazývají univerzální ohraničení nebo největší a nejmenší prvek. 20

Definice 2.29:

Buď (M, ≤) uspořádaná množina, A ⊂ M .

1. Prvek a ∈ M nazveme suprémem množiny A, jestliže (a) ∀x ∈ A : x ≤ a (a je horní ohraničení) (b) (∀x ∈ A : x ≤ a1 ) ⇒ a ≤ a1

(a je nejmenší horní ohraničení).

Píšeme a = sup A. 2. Prvek a ∈ M nazveme infimem množiny A, jestliže (a) ∀x ∈ A : a ≤ x (a je dolní ohraničení) (b) (∀x ∈ A : a1 ≤ x) ⇒ a1 ≤ a (a je největší dolní ohraničení). Píšeme a = inf A. Příklad 2.30:

Buď M = (R, ≤),

a) A = (0, 1i. Potom sup A = 1, inf A = 0. b) A = {x | x =

n+1 , n

n ∈ N}. Potom inf A = 1, sup A = 2.

Suprémum a infimum dvouprvkových množin má svůj speciální název: Definice 2.31:

Nechť a, b ∈ M , M uspořádaná množina. Potom

1. sup{a, b} =: a ∨ b se nazývá spojení 2. inf {a, b} =: a ∧ b se nazývá průsek prvků a, b. Uspořádaná množina, ve které každé dva prvky mají spojení a průsek, se nazývá svazově uspořádaná nebo krátce svaz. Příklad 2.32: množin.

V následujícím obrázku jsou Hasseovy diagramy dvou uspořádaných

V obrázku nalevo je svaz, zatímco napravo není svaz – zde neexistuje d ∧ e a c ∨ d.

21

Příklad 2.33: Přitom

Věta 2.34:

Je-li M libovolná množina, potom (P(M ), ⊂) je svaz.  A∪B je „spojení,ÿ A∩B je „průsek.ÿ

V každém svazu platí

L1 :

x ∧ x = x, x ∨ x = x

(idempotentnost)

L2 :

x ∧ y = y ∧ x, x ∨ y = y ∨ x

(komutativita)

L3 :

x ∧ (y ∧ z) = (x ∧ y) ∧ z x ∨ (y ∨ z) = (x ∨ y) ∨ z

(asociativita)

L4 :

x ∧ (x ∨ y) = x x ∨ (x ∧ y) = x

(absorbce)

Důkaz: L1 : Podle definice x ∧ y = inf{x, y}, tedy x ∧ x = inf{x} = x. Analogicky pro spojení.

L2 : x ∨ y = sup{x, y} = sup{y, x} = y ∨ x (na pořadí prvků v množině nezáleží). Analogicky pro průsek.

L3 : Položme v := x ∧ (y ∧ z), w := (x ∧ y) ∧ z). Ukážeme, že platí v ≤ w a současně w ≤ v. v = x ∧ (y ∧ z) ⇒ v ≤ x a současně v ≤ y ∧ z, tedy současně platí v ≤ x, v ≤ y, v ≤ z. Odtud plyne v ≤ x ∧ y a současně v ≤ z, tedy v ≤ w. Opačná nerovnost se dokáže analogicky, stejně jako asociativita spojení.

L4 dokažte za cvičení.

22

2.2

Algebry s jednou a dvěma operacemi

Binární operace na možině Definice 2.35: Zobrazení ? : A × A → A se nazývá binární operace na množině A. Pro (x, y) ∈ A × A označujeme hodnotu této operace symbolem x ? y. Množina s jednou nebo více takovými operacemi se nazývá algebra. Algebry označujeme symboly (A, ?), (A, +, ·) a pod. Příklad 2.36:

Najdeme všechny binární operace na množině A = {0, 1}.

Řešení: Máme tedy najít všechna zobrazení A × A → A. Každé z těchto zobrazení je charakterizováno tím, které z prvků kartézského součinu A × A se zobrazí na prvek 1 (zbývající se zobrazí na 0) – tedy se jedná o charakteristické funkce všech podmnožin množiny A × A a těch je právě tolik, kolik má tato množina podmnožin. Množina A×A = {(0, 0), (0, 1), (1, 0), (1, 1)} má čtyři prvky, tedy má 24 = 16 podmnožin. Je třeba najít 16 různých funkcí, reprezentujících 16 různých operací, např.

můžeme popsat tabulkou:

můžeme popsat tabulkou:

můžeme popsat tabulkou:

tedy 0 o1 0 = 0, 0 o2 0 = 1, atd.

23

0 0 1

1 1

1 1

1

0 0 0

1 1

1 1

1

0 0 0

1 1

1 1

0

Definice 2.37: Nechť (A, ?) je algebra, B ⊂ A je taková podmnožina, že pro libovolné b1 , b2 ∈ B je také b1 ? b2 ∈ B, tj. že B je podmnožina uzavřená k operaci ?. Potom se (B, ?) nazývá podalgebra algebry (A, ?). Příklad 2.38: podalgebrou.

Uvažujme algebru ({0, 1}, o3 ) z příkladu 2.36. Potom ({0}, o3 ) je její

Příklad 2.39: Algebra reálných čísel s operací sečítání (R, +) je zřejmě podalgebrou algebry komplexních čísel s operací sečítání (C, +). Definice 2.40: Nechť (A1 , ?1 ), (A2 , ?2 ) jsou dvě algebry s jednou binární operací. Zobrazení f : A1 → A2 je homomorfismus algeber (A1 , ?1 ), (A2 , ?2 ), jestliže platí (∀x, y ∈ A1 ) : f (x ?1 y) = f (x) ?2 f (y).

Příklad 2.41: Položme A1 = R, A2 = (0, ∞), f : A1 → A2 definujme předpisem f (x) = ex . Potom f je homomorfismus algeber (A1 , +) a (A2 , ·): ∀x, y ∈ R : f (x + y) = ex+y = ex · ey = f (x) · f (y). Grupa, těleso Definice 2.42: pro každé platí:

Řekneme, že algebra (A, ?) s jednou binární operací je grupa, jestliže

G1) (∀ a, b, c ∈ A) :

(a ? b) ? c = a ? (b ? c)

G2) (∃ e ∈ A) (∀ a ∈ A) :

a?e=a=e?a

G3) (∀ a ∈ A) (∃ a−1 ∈ A) :

a ? a−1 = e = a−1 ? a

(asociativita) (neutrální prvek ) (inverzní prvek )

Jestliže v grupě pro operaci ? platí navíc (∀ a, b ∈ A) :

a?b=b?a

komutativita),

řekneme, že je komutativní. Poznámka: Při aditivním zápisu grupové operace (A, +) se obvykle neutrální prvek e nazývá nulový a označuje symbolem 0 a inverzní prvek k prvku a se nazývá opačný a označuje symbolem −a, při multiplikativním zápisu operace (A, ·) se neutrální prvek nazývá jednotkový a označuje symbolem 1. Příklad 2.43:

(Z, +), (R, +), (R \ {0}, ·)

24

jsou zřejmě komutativní grupy.

Příklad 2.44:

Algebra ({0, 1}, +), kde + je o3 z příkladu 2.36 je komutativní grupa:

(+) je obvyklé sčítání dodefinované „cyklickyÿ: 1 + 1 = 0. Komutativita je zřejmá (např. z tabulky), asociativitu prověříme (s využitím komutativity jen pro některé trojice). Neutrální prvek je 0, každý z prvků 0, 1 je sám k sobě opačný. Definice 2.45: Řekneme, že algebra (T, +, ·) se dvěma binárními operacemi +, · je těleso, jestliže platí: T1)

(T, +) je komutativní grupa s neutrálním prvkem 0,

T2)

(T \ {0}, ·) je grupa,

T3)

a · (b + c) = a · b + a · c (a + b) · c = a · c + b · c

 distributivita.

Příklad 2.46: 1. Těleso reálných čísel (R, +, ·), 2. těleso komplexních čísel (R, +, ·).

Poznámka: Podalgebry grup resp. těles se nazývají podgrupy resp. podtělesa. Svaz jako algebra Věta 2.47: Algebra (S, ∨, ∧) se dvěma binárními operacemi ∨, ∧, které splňují vztahy L1 – L4 z věty 2.34, je svaz vzhledem k uspořádání zadaném předpisem x≤y

⇔

x∧y =x

(x ∨ y = y).

Naopak každá uspořádaná možina, která je svazem ve smyslu definice 2.31, je algebra se dvěma binárními operacemi, kterými jsou spojení a průsek: x ∨ y = sup{x, y},

x ∧ y = inf{x, y}.

Je tedy zřejmé, že není třeba rozlišovat, zda je svaz definován jako algebra, nebo jako uspořádaná množina – říkáme, že je to svaz. Příklad 2.48: je inkluze.

(P(X), ∪, ∩) je algebraicky definovaný svaz, kde indukované uspořádání

Poznámka: Podalgebra svazu se nazývá podsvaz.

25

Příklad 2.49: A = {0, a, b, c, d, 1} je uspořádaná množina, A1 = {0, a, c, d, 1}, A2 = {0, a, b, c, 1} její podmnožiny s indukovaným uspořádáním; Hasseovy diagramy jsou v následujícím obrázku: Jak se snadno přesvědčíme, všechny tři množiny jsou svazy. Vyšetříme, jedná-li se o podsvazy. Je třeba zjistit, zda s každými dvěma prvky v podmnožině je zde i jejich původní spojení a průsek. Zřejmě musíme vyšetřit pouze nesrovnatelné prvky (u srovnatelných je podmínka triviálně splněna). V A1 jsou nesrovnatelné c a d:  (v A1 ) = a c∨d= (v A) = a v A2 jsou nesrovnatelné c a b:  (v A2 ) = 0, c∧b= (v A) = d

 c∧d=

(v A1 ) = 0 (v A) = 0

⇒ A1 je podsvaz svazu A,

⇒ A2 není podsvaz svazu A.

Mějme dva svazy L a S a definujme na kartézském součinu L × S následující operace: (l1 , s1 ) ∧ (l2 , s2 ) := (l1 ∧ l2 , s1 ∧ s2 ), (l1 , s1 ) ∨ (l2 , s2 ) := (l1 ∨ l2 , s1 ∨ s2 ). Potom (L × S, ∨, ∧) je svaz, který se nazývá direktní součin svazů L a S.

Příklad 2.50: Nechť 2 je dvouprvkový řetězec. Potom 2 × 2 je v sousedním obrázku:

26

Distributivní svazy Uvažujme svaz podmnožin nějaké množiny s operacemi průniku a sjednocení (P(X), ∪, ∩). Tento svaz kromě podmínek L1 – L4 z věty ?? splňuje tzv. distributivní zákony A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C),

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C),

naproti tomu svaz v následujícím obrázku distributivní zákony nesplňuje:

c ∧ (b ∨ d) = c ∧ a = c (c ∧ b) ∨ (c ∧ d) = e ∨ d = d

Definice 2.51: D:

Svaz (L, ∨, ∧) ve kterém platí distributivní zákony

x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)

∀x, y, z ∈ L

x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)

se nazývá distributivní svaz. Jako cvičení ukažte, že v každém svazu platí: x ∧ (y ∨ z) ≥ (x ∧ y) ∨ (x ∧ z) x ∨ (y ∧ z) ≤ (x ∨ y) ∧ (x ∨ z)

∀x, y, z ∈ L

Komplementární svazy Definice 2.52: Existuje-li ve svazu (L, ∨, ∧) nejmenší prvek 0 a největší prvek 1, tj. prvky, pro které platí ∀x ∈ L :

x ∧ 1 = x a současně x ∨ 1 = 1 a

∀x ∈ L :

x ∧ 0 = 0 a současně x ∨ 0 = x

neboli 0 = inf L,

1 = sup L,

řekneme, že (L, ∨, ∧) je svaz s univerzálním ohraničením. Příklad 2.53: (N, ≤) je svaz, který nemá největší prvek; (Z, ≤) je svaz, který nemá ani největší ani nejmenší prvek. Konečné svazy jsou svazy s univerzálním ohraničením.

27

Definice 2.54: Nechť (L, ∨, ∧) je svaz s univerzálním ohraničením. Nechť x ∈ L. Existuje-li prvek x0 ∈ L, pro který platí x ∨ x0 = 1,

x ∧ x0 = 0,

nazýváme ho komplementem prvku x. Komplement prvku nemusí být jediný: Příklad 2.55: Uvažujme množinu M = {1, 2, 3, 5, 30}, přičemž x ∧ y znamená největší společný dělitel čísel x, y v M , x∨y nejmenší společný násobek čísel x, y v M . Dostaneme svaz s Hasseovým diagramem v sousedním obrázku: Svaz není distributivní: 2 ∨ (3 ∧ 5) = 2 ∨ 1 = 2,

ale (2 ∨ 3) ∧ (2 ∨ 5) = 30 ∧ 30 = 30.

Svaz má zřejmě 0 a 1 – 0 = 1 a 1 = 30. Každý prvek tohoto svazu má komplement, ale např. 2 má dva komplementy – 3 a 5: 2 ∧ 3 = 2 ∧ 5 = 1,

2 ∨ 3 = 2 ∨ 5 = 30.

Platí ale věta: Věta 2.56: V distributivním svazu s univerzálním ohraničením má každý prvek nejvýš jeden komplement. Důkaz: Nechť a ∧ x = a ∧ y = 0 a∨x = a ∨ y = 1. Potom x = x ∨ (a ∧ y) = (x ∨ a) ∧ (x ∨ y) = x ∨ y ⇒ x = y. y = y ∨ (a ∧ x) = (y ∨ a) ∧ (y ∨ x) = y ∨ x

Věta 2.57:

V distributivním svazu tvoří všechny prvky mající komplement podsvaz.

Důkaz: Nechť C ⊂ L je množina prvků svazu L, které mají komplement. Nechť a, b ∈ C. Potom (a ∧ b) ∧ (a0 ∨ b0 ) = (a ∧ b ∧ a0 ) ∨ (a ∧ b ∧ b0 ) = 0 ∨ 0 = 0, (a ∧ b) ∨ (a0 ∨ b0 ) = (a ∨ a0 ∨ b0 ) ∧ (b ∨ b0 ∨ a0 ) = 1 ∧ 1 = 1.

Definice 2.58: Svaz s univerzálním ohraničením, ve kterém má každý prvek komplement, se nazývá komplementární. Booleovy algebry Definice 2.59:

Distributivní komplementární svaz se nazývá Booleova algebra.

28

Příklad 2.60: 1. (P(A), ∪, ∩) je Booleova algebra: A = 1,

∀M ⊂ A : M 0 = A \ M.

∅ = 0,

2. Dvouprvkový řetězec 2 = {a, b}, kde a ≥ b je Booleova algebra: a = 1, b = 0,

00 = 1, 10 = 0 atd.

3. Direktní součin 2 × 2 (viz příklad 2.49) je Booleova algebra: (a, a) = 1, (b, b) = ), (a, b)0 = (b, a) atd. Věta 2.61:

V Booleově algebře (A, ∧, ∨) platí

B1 :

(a0 )0 = a

B2 :

(a ∨ b)0 = a0 ∧ b0 (a ∧ b)0 = a0 ∨ b0

B3 :

a ≤ b ⇔ a ∧ b0 = 0

∀a, b ∈ A:

(involuce)  (de Morganova pravidla)

Důkaz: B1 : – z jednoznačnosti komplementu, B2 : (a ∧ b) ∧ (a0 ∨ b0 ) = |z distributivity| = [(a ∧ b) ∧ a0 ] ∨ [(a ∧ b) ∧ b0 ] = |z komutativity a asociativity| = = [(a ∧ a0 ) ∧ b] ∨ [a ∧ (b ∧ b0 )] = (0 ∧ b) ∨ (a ∧ 0) = 0 ∨ 0 = 0, analogicky B3 : (⇒) :

(a ∧ b) ∨ (a0 ∨ b0 ) = [a ∨ a0 ∨ b0 ] ∧ [b ∨ a0 ∨ b0 ] = (1 ∨ b0 ) ∧ (a0 ∨ 1) = 1 ∧ 1 = 1,

(a ≤ b) ⇒ |a = a ∧ b, b0 = (a ∨ b)0 = a0 ∧ b0 | ⇒ a ∧ b0 = (a ∧ b) ∧ (a0 ∧ b0 ) =

= |asociativita a komutativita| = (a ∧ a0 ) ∧ (b ∧ b0 ) = 0, (⇐) :

a ∧ b0 = 0 ⇒ a ∧ b = (a ∧ b) ∨ 0 = (a ∧ b) ∨ (a ∧ b0 ) = |distributivita| =

= [(a ∧ b) ∨ a] ∧ [(a ∧ b) ∨ b0 ] = |1. závorka absorbce| = a ∧ (a ∨ b0 ) = |absorbce| = a.

Poznámka: Booleova algebra je tedy algebra se dvěma binárními operacemi ∧, ∨, s jednou tzv. unární operací (0 ), která každému prvku přiřazuje jeho komplement, a se dvěma význačnými prvky 0, 1 – tedy (A, ∧, ∨,0 , 0, 1), která splňuje axiomy L1 – L4 , distributivní zákony a B1 , B2 .

Homomorfismy Booleových algeber Je-li f : A → B zobrazení, potom je f homomorfismus Booleových algeber (A, ∧, ∨,0 , 0A , 1A ) a (B, ∧, ∨,0 , 0B , 1B ), jestliže ∀a, b ∈ A platí: f (a ∨ b) = f (a) ∨ f (b), f (a0 ) = (f (a))0 ,

f (a ∧ b) = f (a) ∧ f (b),

f (0A ) = 0B ,

f (1A ) = 1B . 29

Příklad 2.62:

1 a a0 0

Definice 2.63: platí:

∀x ∈ B :

7→ 7 → 7 → 7 →

1 1 0 0

   

je homomorfismus.

  

Prvek a Booleovy algebry (B, ∧, ∨,0 , 0, 1) se nazývá atom, jestliže

x∧a = a nebo x∧a = 0.

(je-li x ≤ a, potom x = 0 nebo x = a) Poznámka: Nechť B je konečná Booleova algebra, x ∈ B, x 6= 0. Potom existuje atom a takový, že a ≤ x (neboli a ∧ x = a). Platí 0 < x. Jestliže x není atom, existuje prvek a1 tak, že 0 < a1 < x. Podobně není-li a1 atom, existuje a2 tak, že 0 < a2 < a1 < x atd., tedy existuje posloupnost (an ) s vlastností x > a1 > a2 > · · · > 0. Není-li žádné an atom, je tato posloupnost nekonečná a to je spor.

Věta 2.64: Každý nenulový prvek konečné Booleovy algebry se dá jediným způsobem vyjádřit jako spojení jejích atomů. Důkaz: Buď B konečná Booleova algebra, x ∈ B, x 6= 0. Nechť A = {a1 , a2 , . . . , an } = {a | a je atom, a ≤ x}. Položme y = a1 ∨ a2 ∨ · · · ∨ an ; ukážeme, že y = x. Zřejmě je y ≤ x, předpokládejme, že x 6≤ y, tj. x ∧ y 0 6= 0. Existuje tedy atom a ≤ x ∧ y 0 , neboli platí a ≤ x a zároveň a ≤ y 0 . Je-li a atom takový, že a ≤ x, je a ≤ y (podle definice y), ale a ≤ y 0 , tedy a ≤ y ∧ y 0 = 0, a proto a = 0, tj. a není atom a to je spor. Proto platí x ≤ y a odtud plyne x = y, neboli x je rovno spojení všech atomů menších nebo rovných x. Dokážeme jednoznačnost tohoto vyjádření: Buď x = b1 ∨ b2 ∨ · · · ∨ bm . Potom ∀i : bi ≤ x, tedy platí 0 6= bi = bi ∧ x = bi ∧ (a1 ∨ a2 ∨ · · · ∨ an ) = (bi ∧ a1 ) ∨ (bi ∧ a2 ) ∨ · · · ∨ (bi ∧ an ), tedy bi ∧ aj 6= 0 pro některé j. Protože aj je atom, platí bi ∈ A ∀i. Podobně se ukáže, že aj ∈ {b1 , b2 , . . . , bm } ∀j.

Důsledkem předchozí pomocné věty je následující důležité tvrzení o množinové reprezentaci konečných Booleových algeber: Věta 2.65: Nechť B je konečná Booleova algebra, A množina všech jejích atomů. Potom je B izomorfní s množinovou Booleovou algebrou (P(A), ∩, ∪, ¬, ∅, A) (¬A označuje A = A \ A).

30

Důkaz: Položme h : B → P(A),

h(x) = {a ∈ A | a ≤ x}.

Podle předchozí věty je h bijekce; ukážeme, že je to homomorfismus. Nechť h(x) = {a1 , . . . , an } = A1 , h(y) = {b1 , . . . , bm } = A2 . Potom x = a1 ∨ · · · ∨ an , Potom x ∨ y = a1 ∨ · · · ∨ an ∨ b1 ∨ · · · ∨ bm a h(x ∨ y) = A1 ∪ A2 = h(x) ∪ h(y), x ∧ y = (a1 ∨  · · · ∨ an ) ∧ (b1 ∨ · · · ∨ bm ) = ∨i,j (ai ∧ bj ). 0 pro ai 6= bj , Ale ai ∧ bj = , tedy h(x ∧ y) = A1 ∩ A2 = h(x) ∩ h(y). ai pro ai = bj  h(x ∨ x0 ) = h(1) = A Označme h(x0 ) = A3 . Potom ⇒ A3 = A \ A1 . h(x ∧ x0 ) = h(0) = ∅

y = b1 ∨ · · · ∨ bm .

z Důsledek: 1. Každá konečná Booleova algebra má 2k prvků (pro některé k ∈ N), 2. Dvě konečné Booleovy algebry o stejném počtu prvků jsou izomorfní.

31

3

Formální systém výrokové logiky

32

4

Lineární algebra

Lineární algebra vznikla z potřeby řešit soustavy lineárních rovnic, a to někdy velmi rozsáhlé – obsahující až tisíce rovnic. To vedlo k pojmu matice a determinantu a dále se ukázalo užitečné zavést abstraktní pojem vektorový (lineární) prostor, který má další hojné použití jak v samotné lineární algebře, tak v dalších matematických partiích i například ve fyzice. Připomeňme, že lineární rovnicí s neznámými x1 , x2 , . . . xn rozumíme rovnici tvaru a1 x1 + a2 x2 + · · · + an xn = b, kde a1 , a2 , . . . , an , b jsou čísla. Slovem lineární zdůrazňujeme, že neznámé x1 , x2 , . . . , xn jsou v rovnici obsaženy nejvýše v první mocnině, jsou násobeny číslem, a nejsou v žádném jiném vztahu. Soustava lineárních rovnic, tedy několik rovnic se stejnými neznámými, tvoří přirozený matematický model pro většinu tecnických problémů; např. v elektrotechnice pomocí nich řešíme elektrické sítě, ve statice tvoří základní matematický nástroj pro vyšetřování rovnovážných stavů. Dále se tyto soustavy vyskytují jako součást výpočetního postupu jiných matematických úloh; např. při řešení soustav diferenciálních a diferenčních rovnic užitím operátorového počtu (Laplaceovy resp. Z-transformace) nebo pomocí numerických metod.

33

4.1

Aritmetické vektory

Nejdříve si všimneme „ jednořádkového schématuÿ, tedy uspořádané n-tice čísel; zavedeme mezi nimi aritmetické operace, analogické operacím s čísly, a budeme studovat další jejich vlastnosti. Základní pojmy, aritmetické operace Definice 4.1: Nechť n je nějaké přirozené číslo. Uspořádanou n-tici reálných čísel a = (a1 , a2 , a3 , . . . , an ) ∈ Rn nazýváme n-rozměrným aritmetickým vektorem. Číslo ai , i = 1, . . . , n se nazývá i-tá složka vektoru a . O dvou vektorech a,b říkáme, že se rovnají a píšeme a = b , právě když se rovnají jejich odpovídající si složky, tedy když platí ai = bi ∀i. Součtem a + b dvou n-rozměrných vektorů o složkách ai , bi nazýváme vektor c o složkách ci = ai + bi ∀i. Součinem αa reálného čísla α s n-rozměrným vektorem a o složkách ai nazýváme vektor d o složkách di = αai , i = 1, . . . , n. Vektor, jehož všechny složky jsou rovny nule, nazýváme nulovým vektorem a značíme o. Místo (−1)a píšeme −a a místo a + (−b) píšeme a − b a tento vektor nazýváme rozdílem vektorů a, b. Množinu všech reálných n-rozměrných aritmetických vektorů, v níž jsou definovány uvedené operace sečítání a násobení číslem, tedy (Rn , +, .), krátce Rn , nazýváme n-rozměrným aritmetickým vektorovým prostorem nad oborem reálných čísel .

Snadno prověříme následující tvrzení: Věta 4.2:

Pro operace v aritmetickém vektorovém prostoru platí následující pravidla:

1. a + b = b + a, (a + b) + c = a + (b + c) (komutativita a asociativita sečítání) 2. existuje takový vektor o (je to nulový vektor), že a + o = a , α(a + b) = αa + αb 3.

(distributivita násobení číslem) (α + β)a = αa + βa

4. α(βa) = (αβ)a, 0 a = o, αo = o 5. rovnost αa = o nastane, právě když α = 0 nebo když a = o 6. −(αa) = (−α)a = α(−a) 34

Poznamenejme, že vztahy 1) a 2) znamenají, že (Rn , +) je komutativní grupa s neutrálním prvkem o.

Důkaz se provede využitím vlastností operací s čísly; např: 1. Nechť a = (a1 , a2 , . . . an ), b = (b1 , b2 , . . . bn ). Potom a + b = (a1 + b1 , a2 + b2 , . . . an + bn ) = (b1 + a1 , b2 + a2 , . . . bn + an ) = b + a, protože výraz ak + bk je součet čísel, pro který platí komutativní zákon. Analogicky budeme postupovat při důkazu platnosti asociativního zákona pro součet aritmetických vektorů využitím asociativního zákona pro součet čísel – jednotlivých souřadnic. 2. Nechť o = (o1 , o2 , . . . on ). Potom platí a+o=a

⇔

(a1 + o1 , a2 + o2 , . . . an + on ) = (a1 , a2 , . . . an )

a1 + o1 = a1 , a2 + o2 = a2 , . . . an + on = an

⇒

⇔

o1 = o2 = · · · = on = 0,

tedy o je nulový vektor. Zbylé části věty dokažte podobně jako cvičení.

Definice 4.3: 1. Skalárním součinem u · v dvou n-rozměrných vektorů o složkách ui , vi , i = 1, 2, ..., n nazýváme číslo definované vztahem u · v = u 1 v 1 + u2 v 2 + · · · + un v n . 2. Platí-li pro u, v ∈ Vn : u · v = 0, řekneme, že u a v jsou ortogonální. (Jedná se o zobecnění pojmu „kolmostÿ.) 3. Systém vektorů u1 , u2 , ..., uk ∈ Rn se nazývá ortogonální systém vektorů, jsouli tyto vektory po dvou ortogonální. Platí-li navíc ui · ui = 1 ∀i, říkáme, že systém je ortonormální. Příklad 4.4: a) Nechť a = (1, 0, −2), b = (3, 2, 0). Potom a + b = (4, 2, −2), 3a = (3, 0, −6) a a · b = 3. b) Systém vektorů {i, j, k}, kde i = (1, 0, 0), j = (0, 1, 0), k = (0, 0, 1) tvoří zřejmě ortonormální systém vektorů. Vektory ve fyzice, geometrická reprezentace Obvykle se poprvé setkáme s pojmem vektoru v nějakém fyzikálním kontextu – při studiu mechaniky, elektrických a magnetických polí atp. Zde se studují vektory v dvoj- a troj-dimenzionálním prostoru a odpovídají síle, rychlosti, pozici částice atd. Mají jednak velikost, jednak směr; mohou být zvětšovány (zmenšovány) pomocí multiplikativního faktoru, sečítány pomocí rovnoběžníkového pravidla; mezi vektory je definován skalární a vektorový součin atd. Určující charakteristiky fyzikálního vektoru – velikost a směr – motivují jeho reprezentaci 35

pomocí orientované úsečky, nebo „šipkyÿ, kde její délka určuje velikost vektoru; povšimněme si, že umístění vektoru zde není specifikováno. Pro geometrickou interpretaci uvažujme trojrozměrný vektorový prostor – všechny uspořádané trojice reálných čísel – a intuitivně jej chápejme jako prostor bodů v prostoru, kde složky trojice udávají souřadnice bodu v některé souřadné soustavě. Fyzikální vektor v = (v1 , v2 , v3 ) potom bude systém všech orientovaných úseček, které jsou rovnoběžné a stejně dlouhé jako orientovaná úsečka s počátečním bodem v počátku zvolené souřadné soustavy a s koncovým bodem v bodě o souřadnicích [v1 , v2 , v3 ]. Lineární závislost, báze, souřadnice vektoru Definice 4.5: • Řekneme, že vektor a ∈ Rn je lineární kombinací vektorů a1 , a2 , ..., ak z Rn , existují-li taková čísla α1 , α2 , ..., αk , že platí

a = α1 a1 + α2 a2 + · · · + αk ak . • Řekneme, že vektory a1 , a2 , ..., ak z Rn jsou lineárně závislé, jestliže alespoň jeden z nich je lineární kombinací ostatních. Nejsou-li vektory a1 , a2 , ..., ak z Rn lineárně závislé, potom říkáme, že jsou lineárně nezávislé. V předchozí definici jsme nepředpokládali nenulovost čísel α1 , α2 , ..., αk , tedy některá z nich, nebo dokonce všechna tato čísla mohou být rovna nule. Tedy zřejmě libovolná k-tice vektorů obsahující nulový vektor je pro k > 1 lineárně závislá; pro úplnost dodefinujeme tento pojem i na případ k = 1 – jeden vektor o budeme považovat za lineárně závislý. Příklad 4.6: Nechť a = (3, 1, 0), b = (−1, 0, 2), c = (7, 2, −2). Vektory a, b, c jsou lineárně závislé, protože c = 2a − b. Naproti tomu vektory e1 = (1, 0, 0), e2 = (0, 1, 0, ), e3 = (0, 0, 1) jsou zřejmě lineárně nezávislé. Snadno ukážeme, že platí následující věta: Věta 4.7: Vektory a1 , a2 , . . . , ak z Rn jsou lineárně závislé, právě když existují čísla β1 , β2 , . . . , βk taková, že alespoň jedno z nich je různé od nuly a platí β1 a1 + β2 a2 + · · · + βk ak = o. Důkaz: Nechť jsou vektory a1 , a2 , . . . , ak lineárně závislé. Pro k = 1 je a1 = o a to je závislý vektor. Nechť k > 1. Podle definice je jeden z nich lineární kombinací ostatních; nechť je to např. a1 . Tedy a1 = α2 a2 + . . . + αk ak

⇔

−a1 + α2 a2 + . . . + αk ak = o.

Stačí tedy položit αi = βi pro i 6= 1, β1 = −1. Opačné tvrzení se dokáže analogicky; proveďte jako cvičení.

36

Definice 4.8: Libovolnou uspořádanou n-tici (a1 , a2 , ..., an ) tvořenou n lineárně nezávislými vektory z Rn nazýváme bází vektorového prostoru Rn . Nejjednodušší takovou bází je systém vektorů (e1 , e2 , . . . , en ), kde e1 = (1, 0, . . . , 0), e2 = (0, 1, 0, . . . , 0), . . . en = (0, 0, . . . , 0, 1), tedy vektory ei jsou dány uspořádanými n-ticemi (0, . . . , 0, 1, 0, . . . , 0), kde 1 je na i-tém místě. Tato báze se nazývá kanonická. Vektory kanonické báze tvoří lineárně nezávislý systém; utvoříme-li jejich libovolnou lineární kombinaci α1 e1 + α2 e2 + . . . + αn en , dostaneme vektor (α1 , α2 , . . . , αn ), který je roven nulovému vektoru pouze v případě α1 = α2 = · · · = αn = 0 a to podle věty 4.7 znamená, že dané vektory jsou lineárně nezávislé. Existují samozřejmě i jiné báze než kanonická: Příklad 4.9:

Ukážeme, že systém vektorů

B = (v1 , v2 , v3 ),

kde v1 = (1, 1, 1), v2 = (0, 1, 1), v3 = (0, 0, 1),

tvoří bázi aritmetického vektorového prostoru V3 . Řešení: Protože n = 3 a vektory jsou tři, stačí prověřit jejich lineární nezávislost. Předpokládejme, že existují čísla a, b, c, která nejsou současně všechna rovna nule, tak že platí a v1 + b v2 + c v3 = o, tedy a (1, 1, 1) + b (0, 1, 1) + c (0, 0, 1) = (a, a + b, a + b + c) = (0, 0, 0). Uspořádané trojice čísel nalevo i napravo poslední rovnosti se musí rovnat, tedy platí a = 0 a+b = 0 a +b +c = 0

⇒

a=b=c=0

⇒

dané vektory jsou lineárně nezávislé, tvoří bázi aritmetického vektorového prostoru V3 . Důležitost existence báze v aritmetickém vektorovém prostoru ukazuje následující věta: Věta 4.10: Nechť (a1 , a2 , ..., an ) je libovolná báze vektorového prostoru Rn . Potom každý vektor a z prostoru Rn je lineární kombinací vektorů z této báze, tj. existují čísla α1 , α2 , ..., αn taková, že platí a = α1 a1 + α2 a2 + · · · + αk an .

Důkaz bude triviální až se seznámíme s analýzou řešitelnosti soustav lineárních rovnic.

37

Definice 4.11: Čísla α1 , α2 , ..., αn z věty 4.10 se nazývají souřadnice vektoru a vzhledem k bázi (a1 , a2 , ..., an ). V případě kanonické báze je zřejmě i-tá souřadnice daného vektoru a = (a1 , a2 , . . . an ) právě číslo ai . Příklad 4.12: kladu 4.9.

Najděme souřadnice vektoru a = (1, 2, −1) vzhledem k bázi B z pří-

Řešení: Hledáme čísla a, b, c pro která platí a = (1, 2, −1) = a (1, 1, 1) + b (0, 1, 1) + c (0, 0, 1). Hledaná čísla budou řešením soustavy a = 1 a+b = 2 a + b + c = −1

⇒

a = 1, b = 1, c = −3.

Píšeme aB = (1, 1, −3). Podprostory Jestliže geometricky interpretujeme prostor trojic reálných čísel tak, jak jste zvyklí ze střední školy, jako prostor bodů, kde trojice udává souřadnice bodu v nějaké souřadné soustavě, existují zde některé trojice – body, které leží v rovině; jestliže uvažujeme všechny body, které vyplňují některou rovinu, dostaneme množinu, která je v jistém smyslu také vektorovým prostorem. To nás vede k následující definici: Definice 4.13: Neprázdnou podmnožinu V vektorového prostoru Rn nazveme podprostorem prostoru Rn , jestliže pro každé dva prvky u, v ∈ V a každé číslo α je u + v ∈ V a αu ∈ V – tj. když podmnožina V je uzavřená k příslušným operacím. V tomto případě píšeme V v Rn . Uvažujme podmnožinu V ⊂ V3 , pro kterou platí V = {(x1 , x2 , 0)| x1 , x2 ∈ R} – množinu trojic reálných čísel, jejichž třetí souřadnice jsou nulové. Snadno se ukáže, že V je podprostor V3 (ukažte jako cvičení). Při geometrické interpretaci zmíněné v úvodu této části se jedná o „souřadnou rovinu xyÿ. Vektory e1 , e2 jsou zřejmě lineárně nezávislé a dále pro každý aritmetický vektor v ∈ V platí v = (v1 , v2 , 0) = v1 (1, 0, 0) + v2 (0, 1, 0) = v1 e1 + v2 e2 , každý vektor z V lze vyjádřit jako lineární kombinaci vektorů e1 , e2 . Tedy maximální možný počet lineárně nezávislých vektorů podprostoru V je 2, přitom podle naší geometrické interpretace jej chápeme jako rovinu, a ta je dvojrozměrná. Dále je přirozené chápat systém (e1 , e2 ) jako bázi podprostoru V. To nás vede k následující definici: 38

Definice 4.14:

Buď V v Rn .

1. Maximální počet lineárně nezávislých vektorů podprostoru V se nazývá dimenze podprostoru V; značíme dim V. 2. Libovolný systém k lineárně nezávislých vektorů, kde k = dim V, se nazývá báze podprostoru V. Poznámka: Protože jistě platí Rn v Rn , je dim Rn = n. Velmi důležitou aplikaci pojmu podprostoru a jeho dimenze uvidíme v kapitole o řešení soustav lineárních rovnic. Uvažujme v trojrozměrném prostoru dvě roviny procházející počátkem – dva dvojrozměrné prostory. Jejich průnikem je přímka (procházející počátkem), tedy také podprostor, a to jednorozměrný. Stejná situace platí u obecných aritmetických prostorů: Věta 4.15: Průnik libovolného neprázdného systému podprostorů vektorového prostoru Rn je opět podprostorem prostoru Rn . Důkaz plyne přímo z definice podprostoru.

Nyní již můžeme zavést velmi důležitý pojem tzv. lineárního obalu množiny: Definice 4.16:

Buď M podmnožina vektorového prostoru Rn .

1. Průnik V všech podprostorů prostoru Rn obsahujících množinu M nazýváme lineárním obalem množiny M a značíme hM i. Je-li M = {u1 , u2 , ..., uk }, pak místo h{u1 , u2 , ..., uk }i budeme psát hu1 , u2 , ..., uk i. 2. Podmnožina M se nazývá množinou generátorů prostoru V. Budeme též říkat, že množina M generuje V. Tedy lineárním obalem dané množiny je nejmenší vektorový prostor obsahující prvky dané množiny – generátory; k dané množině musíme tedy dodat součty každých dvou prvků dané množiny a každý násobek prvků dané množiny, jestliže je již neobsahovala. Speciálně je třeba přidat násobek nulou, tedy nulový vektor. Souhrnnou charakteristiku podprostorů generovaných podmnožinami vektorového prostoru Rn dává následující věta: Věta 4.17:

Buď M podmnožina vektorového prostoru Rn . Pak platí:

1. je-li M = ∅, je hM i = {o}, 2. je-li M 6= ∅, pak hM i je množina všech lineárních kombinací

k P i=1

kde ui ∈ M, i = 1, 2, ...k. 39

αi ui ,

Hodnost systému vektorů V dalším textu, při studiu matic a determinantů, budeme pomocí jistých „transformacíÿ převádět systém vektorů (řádky matice) na jiný, jednodušší, přičemž budeme požadovat zachování vlastností systému z hlediska lineární nezávislosti. Proto uvedeme ještě následující definici:

Nechť jsou dány dva systémy vektorů z Rn :

Definice 4.18:

M 0 = {u0 1 , u0 2 , ..., u0 k }.

M = {u1 , u2 , ..., uk },

Řekneme, že M 0 vznikne z M elementární transformací, jestliže existuje index i tak, že pro j 6= i je uj = u0 j a dále platí jedna z následujících možností: • ∃α 6= 0 tak, že platí u0 i = αui – vynásobení jednoho vektoru nenulovým číslem; • ∃k 6= i tak, že platí u0 i = ui + uk – připočtení jiného vektoru k danému. Věta 4.19: Buďte M = {u1 , u2 , ..., uk }, M 0 = {u0 1 , u0 2 , ..., u0 k } dva systémy vektorů z Rn a nechť M 0 vznikne z M konečným počtem elementárních transformací. Potom vektory z M 0 jsou lineárně nezávislé, právě když vektory z M jsou lineárně nezávislé. Důkaz provedeme pro případ tří vektorů A = {u, v, w}, při obecném počtu by postup byl analogický, ovšem zápis nepřehledný. Postup lze zobecnit matematickou indukcí. 1. Nechť systém A je lineárně nezávislý, tedy

au + bv + cw = o

⇔

a = 0 ∧ b = 0 ∧ c = 0.

a) Uvažujme systém A0 = {u0 , v0 , w0 }, kde u0 = αu, α 6= 0, v0 = v, w0 = w, a předpokládejme, že A0 je lineárně závislý systém. Existují tedy taková čísla a0 , b0 c0 , která nejsou vesměs nulová, že platí a0 u0 + b0 v0 + c0 w0 = o. Ale a0 u0 + b0 v0 + c0 w0 = a0 αu + b0 v + c0 w = o

a0 α = 0 ∧ b0 = 0 ∧ c0 = 0 (α 6= 0),

protože systém A je lineárně nezávislý, tedy musí platit a0 = 0 ∧ b0 = 0 ∧ c0 = 0 a to je spor s předpokladem A0 je lineárně závislý. b) Uvažujme systém A0 = {u0 , v0 , w0 }, kde u0 = u + v, v0 = v, w0 = w a předpokládejme, že A0 je lineárně závislý systém. Existují tedy taková čísla a0 , b0 c0 , která nejsou vesměs nulová, že platí a0 u0 +b0 v0 +c0 w0 = o. Ale a0 u0 + b0 v0 + c0 w0 = a0 (u + v) + b0 v + c0 w = a0 u + (a0 + b0 ) v + c0 w = o a0 = 0 ∧ a0 + b0 = 0 ∧ c0 = 0, protože systém A je lineárně nezávislý, tedy musí platit a0 = 0 ∧ b0 = 0 ∧ c0 = 0 a to je spor s předpokladem A0 je lineárně závislý. 2. Nechť systém A je lineárně závislý, tedy jeden z vektorů systému lze vyjádřit jako lineární kombinaci zbývajících. Nechť např. w = a u + b v. a) Uvažujme systém A0 = {u0 , v0 , w0 }, kde u0 = αu, α 6= 0, v0 = v, w0 = w. Potom w0 = w = a u + b v = a

1 0 u + b v0 α

⇒

systém A0 tvoří lineárně závislé vektory. b) Uvažujme systém A0 = {u0 , v0 , w0 }, kde u0 = u + v, v0 = v, w0 = w . Potom w0 = w = a u + b v = a u0 − v0 + b v0 = a u0 + (b − a) v0 systém

A0

tvoří lineárně závislé vektory.

40

⇒

Definice 4.20: Nechť je dán systém {a1 , a2 , ..., an } libovolných vektorů z Rn . Jestliže v systému existuje h lineárně nezávislých vektorů a ne více, potom číslo h nazýváme hodností systému. Příklad 4.21:

Hodnost systému vektorů a, b, c, kde

a = (3, 1, 0), b = (−1, 0, 2), c = (7, 2, −2), je rovna dvěma, protože vektory a, b jsou lineárně nezávislé, zatímco (jak již víme, viz příklad 4.6) vektory a, b, c jsou lineárně závislé.

4.2

Matice

Nyní se budeme zabývat obdélníkovými schématy čísel, s kterými jsme pracovali v úvodu k lineární algebře – maticemi. První odstavec bude seznamem důležitých pojmů týkajících se matic; budou nám sloužit pro jednodušší vyjadřování při práci s nimi: Základní pojmy Definice 4.22:  a11 a12  a21 a22  . ..  . .  .   ai1 ai2  . ..  .. . am1 am2

Soubor ··· ··· ...

a1j a2j .. .

··· ··· ...

a1n a2n .. .

· · · aij · · · ain .. .. .. .. . . . . · · · amj · · · amn

        

m · n čísel nazýváme maticí typu (m,n). Matice budeme označovat velkými tučnými tiskacími písmeny, nebo také symbolem (aij )nm . Čísla aij se nazývají prvky matice, aritmetický vektor (ai1 , ai2 , ..., ain ) nazýváme i-tým řádkem matice, aritmetický vektor (a1j , a2j , ..., anj ) nazýváme j-tým sloupcem matice. Prvky aii , i = 1, ..., k, k = min(m, n) tvoří tzv. hlavní diagonálu matice A = (aij )nm . Je-li m ≤ n (matice A má nanejvýš tolik řádků kolik sloupců), všechny prvky v hlavní diagonále matice A jsou různé od nuly a všechny její prvky pod hlavní diagonálou jsou nulové, říkáme, že matice A je v Gaussově tvaru (gaussovská). Jestliže jsou všechny prvky matice typu (m,n) nulové, potom ji nazýváme nulovou maticí typu (m,n) a označujeme Onm , nebo jen O. Platí-li pro matici A = (aij )nm m = n, říkáme, že matice A je čtvercová řádu n. Čtvercovou matici, jejíž všechny prvky neležící na hlavní diagonále jsou nulové, nazýváme 41

diagonální maticí. Jsou-li všechny prvky v hlavní diagonále diagonální matice rovny jedné, nazýváme ji jednotkovou maticí řádu n a značíme En , nebo krátce E. Jestliže jsou ve čtvercové matici všechny prvky pod (resp. nad) hlavní diagonálou rovny nule, nazýváme ji horní (resp. dolní) trojúhelníkovou maticí. Čtvercová matice A = (aij )nn , pro jejíž všechny prvky platí aij = aji (resp. aij = −aji ) , se nazývá symetrická (resp. antisymetrická).

Nechť je dána matice A = (aij )nm . Matici, kterou získáme z matice A vynecháním některých řádků event. sloupců, nazýváme submaticí matice A. Matici, kterou získáme z matice A vynecháním j-tého řádku a k-tého sloupce, nazýváme submaticí matice A příslušnou k prvku ajk a budeme ji označovat symbolem Ajk . Příklad 4.23:  a11 A =  a21 a31

Pro matici  a12 a13 a22 a23  a32 a33

je  A11 =

a22 a23 a32 a33



 , A13 =

a21 a22 a31 a32



 , A33 =

a11 a12 a21 a22



Transponovaná matice Definice 4.24: Nechť je dána matice A = (aij )nm typu (m,n). Matici B = (bij )m n typu (n,m) , pro jejíž prvky platí bij = aji ,

i = 1, 2, ..., n, j = 1, 2, ..., m,

nazveme maticí transponovanou k matici A a označujeme ji AT . Příklad 4.25:  A=

Je-li

2 5 0 −3 1 5





 2 −3 1 . , je AT =  5 0 5

Je-li A symetrická matice, platí zřejmě AT = A. Každý aritmetický vektor x dimenze n lze zřejmě považovat za jednořádkovou matici typu (1, n) nebo za jednosloupcovou matici typu (n, 1). Pro naše účely je výhodnější chápat

42

vektory jako matice sloupcové, tedy   x1  x2    x =  ..  , xT = [x1 x2 · · · xn ]  .  xn Někdy budeme v dalším textu pro jednoduchost psát, tak jak jsme zavedli, x = (x1 , x2 , · · · , xn ) bude-li z kontextu zřejmé, chápeme-li vektor jako matici jednořádkovou nebo jednosloupcovou. Aritmetické operace Definice 4.26: O dvou maticích A = (aij )nm , B = (bij )nm říkáme, že se sobě rovnají, a píšeme A = B, jestliže jsou téhož typu a odpovídající si prvky se rovnají, tj. platí-li aij = bij

∀ i = 1, 2, . . . , m, j = 1, 2, . . . , n

Součtem dvou matic A = (aij )nm , B = (bij )nm stejného typu (m,n) rozumíme matici C = (cij )nm typu (m,n) takovou, že cij = aij + bij . Píšeme C = A + B. Součet matic různého typu se nedefinuje. Součinem čísla α s maticí A = (aij )nm rozumíme matici C = (cij )nm takovou, že cij = αaij . Píšeme C = αA. Místo (−1)A píšeme −A a místo A + (−1)B píšeme A − B a tuto matici nazýváme rozdílem matic A, B. Příklad 4.27:  3  A = −1 2

Nechť jsou dány matice    4 2 1 −1 2 2 3  1 −2  B= 2 1 4 3 2 1

Potom 

 4 3 4 A+B= 1 3 1  5 3 5 Věta 4.28:



 2 5 0 1 5  A − B =  −3 −1 −1 3



 6 8 4 2A =  −2 4 6  4 2 8

Pro sečítání matic a pro násobení matice číslem platí následující pravidla:

1. A + B = B + A

(komutativita součtu)

2. (A + B) + C = A + (B + C)

(asociativita součtu)

3. A + O = A

(nulová matice)

4. k maticím A, B existuje právě jedna matice X taková, že A + X = B; platí X = B − A 5. α(A + B) = αA + αB,

(α + β)A = αA + βA

(distributivita násobení číslem)

Důkaz se provede analogicky důkazu věty 4.2 o aritmetických operacích s vektory; proveďte za cvičení.

43

Násobení matic, inverzní matice Definice 4.29: Součinem AB matice A = (aij )pm typu (m, p) s maticí B = (bij )np typu (p, n) nazýváme matici C = (cij )nm typu (m, n) , pro jejíž prvky platí cij = ai1 b1j + ai2 b2j + · · · + aip bpj =

p X

air brj .

r=1

Jinak řečeno: řádky matice A a sloupce matice B považujeme za vektory dimenze p a potom prvek cij dostaneme jako skalární součin i-tého řádku matice A a j-tého sloupce matice B. Protože skalární součin vektorů je definován jen pro vektory stejné dimenze, je násobení matic definováno jen v případě, že první matice má stejný počet sloupců jako druhá matice řádků. Příklad 4.30:  17  AB = 12 16

Uvažujme matice A, B z 4.27. Potom    5 0 8 4 7 9 −3  BA =  1 8 −1  7 6 9 17 16

Příklad 4.31: Nechť   4 2 5 A= 0 3 2  0 4 3



 1/4 14/4 −11/4 3 −2  B= 0 0 −4 3

Potom 

 1 0 0 AB =  0 1 0  0 0 1

Příklad 4.32:   1 2 3 A= 4 5 6  7 8 9 Věta 4.33:



 1 0 0 BA =  0 1 0  0 0 1



 1 B =  −2  1



 0 AB =  0  0

Pro násobení matic A, B, C platí následující pravidla:

1. A(BC) = (AB)C 2. (A + B)C = AC + BC,

(asociativita součinu) C(A + B) = CA + CB

3. OA = O, AO = O 44

(distributivita)

4. (AB)T = BT AT 5. α(AB) = (αA)B = A(αB) pokud jsou příslušné součty a součiny definovány, tj. mají-li matice A, B, C předepsané typy. Důkaz je dosti pracný a spočívá v použití definice pro předepsané součiny; ukážeme si to na části 1. a 4., zbylé proveďte analogicky jako cvičení: 1. Nechť q n n A = (aij )pm , B = (bij )qp , C = (cij )n q , AB = ((ab)ij )m , BC = ((bc)ij )p , A(BC) = (dij )m ,

(ab)ij = ai1 b1j + · · · + aip bpj =

p X

(bc)ij = bi1 c1j + · · · + biq cqj =

ais bsj ,

s=1

q X

(AB)C = (d0ij )n m

kde

bir crj

r=1

Potom p X

dij = ai1 (bc)1j + · · · + aip (bc)pj =

d0ij = (ab)i1 c1j + · · · + (ab)iq cqj =

ais (bc)sj =

p X

q X

ais

s=1

s=1

q X

q X

p X

r=1

s=1

(ab)ir crj =

r=1

! bsr crj

=

r=1

ais bsr crj ,

s=1 r=1

! ais bsr

p X q X

crj =

q X p X

ais bsr crj = dij .

r=1 s=1

4. Nechť n T m T p T m T T 0 m A = (aij )pm , B = (bij )n p , AB = (cij )m , A = (αij )p , B = (βij )n , (AB) = (γij )n , B A = (γij )n ,

kde αij = aji , βij = bji a dále

cij = ai1 b1j + · · · + aip bpj =

p X

air brj

⇒

γij = cji =

r=1

p X

ajr brj .

r=1

Potom γ 0 ij = βi1 α1j + · · · + βip αpj =

p X r=1

βir αrj =

p X

bri ajr = γij .

r=1

Pro násobení matic neplatí obecně analogická pravidla, jaká platí pro násobení čísel. Neplatí obecně komutativní zákon, nemusí tedy platit AB = BA (viz př. 4.30). Platí-li AB = BA , říkáme, že matice A, B komutují. V př. 4.32 jsme dále viděli, že součinem dvou nenulových matic může být matice nulová. Jednotková matice hraje při násobení matic roli jednotky: Nechť A = (aij )nm je libovolná matice typu (m,n), Em , En jsou jednotkové matice řádu m a n. Potom zřejmě platí AEn = Em A = A Pro součin A A užíváme zkrácený zápis A A = A2 , analogicky A A A = A3 ,. . . , A0 = E. S využitím tohoto zápisu můžeme dosadit matici do polynomu: Nechť f (x) = a0 + a1 x + a2 x2 + · · · + an xn .

45

Hodnotu f (A) definujeme jako matici f (A) = a0 E + a1 A + a2 A2 + · · · + an An . Tyto výpočty můžeme pochopitelně realizovat jen v případě čtvercových matic (proč?). Pro čtvercové matice platí následující věta:

Věta 4.34: B = C.

Buďte A,B,C čtvercové matice řádu n takové, že BA = En = AC. Potom

Důkaz se provede snadno s použitím předpokladů věty, definice jednotkové matice a asociativního zákona pro násobení matic: B = BEn = B(AC) = (BA)C = En C = C.

Definice 4.35: Nechť A je čtvercová matice řádu n. Jestliže existuje čtvercová matice B téhož řádu n taková, že BA = AB = En , kde En je jednotková matice řádu n, potom tuto matici nazýváme inverzní maticí k A a značíme symbolem A−1 . Matice A, k níž existuje inverzní matice, se nazývá regulární (invertovatelná), v opačném případě se A nazývá singulární. Ne matici existuje inverzní matice, snadno se dá ukázat, že například matice  ke každé  1 0 není regulární: 0 0 Hledejme čísla a, b, c, d tak, aby platilo       a b 1 0 1 0 · = . c d 0 0 0 1 Podle definice součinu matic musí platit pro prvek a22 matice napravo c · 0 + d · 0 = 1 a to je spor. Věta 4.36:

Buďte A,B regulární matice řádu n. Potom

1. součin AB je regulární matice a platí (AB)−1 = B−1 A−1 , 2. matice A−1 je regulární a platí (A−1 )−1 = A. Důkaz je triviální:

AB B−1 A−1 = A(BB−1 )A−1 = AA−1 = E.

V dalším textu budeme potřebovat ještě jeden speciální druh matic, které popisuje následující definice: Definice 4.37:

Nechť A je regulární matice. Platí-li

A−1 = AT , řekneme, že A je ortonormální matice. 46

Příklad 4.38: Máme ukázat, že   1/9 8/9 −4/9 A =  4/9 −4/9 −7/9  8/9 1/9 4/9 je ortonormální matice. Řešení: Stačí ukázat, že AAT = E:   1/9 8/9 −4/9 1/9 4/9 AAT =  4/9 −4/9 −7/9   8/9 −4/9 8/9 1/9 4/9 −4/9 −7/9   1 + 64 + 16 4 − 32 + 28 8 + 8 − 16 1  4 − 32 + 28 16 + 16 + 49 32 − 4 − 28  = = 81 8 + 8 − 16 32 − 4 − 28 64 + 1 + 16

 8/9 1/9  = 4/9     81 0 0 1 0 0 1  0 81 0  =  0 1 0  . 81 0 0 81 0 0 1

Z předchozího příkladu bylo patrné že ortonormální matice mají následující vlastnost:

Věta 4.39:

Řádky (sloupce) ortonormální matice tvoří ortonormální systém vektorů.

Důkaz: Je-li vi i-tý řádek matice A, je zároveň i-tým sloupcem matice AT a tedy  vi · vi = 1, A · AT = E ⇒ vi · vj = 0 pro i 6= j

Hodnost matice, ekvivalence matic Definice 4.40: Hodností matice A rozumíme hodnost soustavy vektorů vytvořených řádky této matice. Označujeme ji h(A). Matice A má tedy hodnost h(A), jestliže v ní existuje právě h(A) lineárně nezávislých řádků. Platí velmi užitečná následující věta: Věta 4.41:

Platí

h(A) = h(AT ), tedy transponovaná matice má stejnou hodnost jako matice původní – počet lineárně nezávislých řádků matice je stejný jako počet lineárně nezávislých sloupců. Důkaz je dosti komplikovaný; využívá věty o řešitelnosti rovnic. Provádět ho nebudeme. (Viz Bican: Lineární algebra a geometrie.)

Jak víme z předchozí kapitoly, hodnost soustavy vektorů se nemění při použití libovolného počtu elementárních transformací – tento fakt použijeme při vyšetřování hodnosti matic. V následující definici aplikujeme definici elementární transformace na matice: 47

Definice 4.42:

Elementární transformací matice A nazveme

1. vynásobení řádku (sloupce) nenulovým číslem, 2. připočtení násobku jednoho řádku (sloupce) k jinému. Jestliže tedy aplikujeme větu 4.19 na řádky (sloupce) matice, můžeme formulovat větu: Věta 4.43:

Elementární transformace nemění hodnost matice.

Nyní si blíže povšimneme elementárních transformací matic: Věta 4.44:

Platí

• Záměna dvou řádků (sloupců) je složením elementárních transformací. • Inverzní transformace k elementárním jsou rovněž složením elementárních transformací. • (Realizace elementárních transformací vynásobením regulární maticí): 1. Vynásobení k-tého řádku matice A typu (m, n) číslem α je možné realizovat vynásobením matice A zleva diagonální maticí, ve které je aii = 1 pro i 6= k, akk = α. 2. Připočtení l-tého řádku ke k-tému řádku v matici A je možné realizovat vynásobením matice A zleva maticí, která vznikne z příslušné jednotkové matice, jestliže nulu na místě prvku akl nahradíme jedničkou, tedy maticí (bij ), kde bii = 1, bkl = 1, bij = 0 pro i 6= j, i 6= k, j 6= l. 3. Příslušné sloupcové elementární transformace se dají realizovat analogicky vynásobením vhodnou maticí zprava.

Důkaz provádět nebudeme, rozmyslete si ho jako cvičení s využitím postupů v následujícím příkladu.

Příklad 4.45: 1. Záměnu dvou řádků (zde 2. a 3.) provedeme posloupností následujících elementárních transformací: ∼1) 2.ř.+3.ř; ∼2) −1×2.ř; ∼3) 3.ř.+2.ř; ∼4) −1×2.ř; ∼5) 2.ř.+3.ř; ∼6) −1×3.ř:     a11 a12 a13 a11 a12 a13  a21 a22 a23  ∼1)  a21 + a31 a22 + a32 a23 + a33  ∼2) a31 a32 a33 a31 a32 a33   a11 a12 a13 ∼2)  −a21 − a31 −a22 − a32 −a23 − a33  ∼3) a31 a32 a33   a11 a12 a13 ∼3)  −a21 − a31 −a22 − a32 −a23 − a33  ∼4) −a21 −a22 −a23 48



 a11 a12 a13 ∼4)  a21 + a31 a22 + a32 a23 + a33  ∼5) −a21 −a22 −a23     a11 a12 a13 a11 a12 a13 a32 a33  ∼6)  a31 a32 a33  ∼5)  a31 −a21 −a22 −a23 a21 a22 a23 2. Realizace připočtení řádku k jinému řádku (zde třetího k druhému) vynásobením regulární maticí zleva:       1 0 0 a11 a12 a13 a11 a12 a13  0 1 1  ·  a21 a22 a23  =  a21 + a31 a22 + a32 a23 + a33  0 0 1 a31 a32 a33 a31 a32 a33 Definice 4.46: Matice A, B nazveme ekvivalentní a píšeme A ∼ B, jestliže se dá jedna na druhou převést pomocí elementárních transformací. Věta 4.47:

A ∼ B, právě když existují regulární matice R, S tak, že B = R · A · S.

Důkaz: Směr (⇒) je zřejmý; tvrzení je pouze jinak formulované tvrzení věty předchozí. Opačný směr vyžaduje vyjádření libovolné regulární čtvercové matice ve tvaru součinu matic zprostředkujících elementární transformace a provádět ho nebudeme.

Věta 4.48:

(Gaussova eliminace)

1. Pomocí řádkových elementárních transformací lze každou matici převést na stupňovou matici, tj. takovou, že první nenulový člen každého řádku má větší sloupcový index než první nenulový člen předchozího řádku a počet nenulových řádků je roven hodnosti matice. 2. Pomocí řádkových elementárních transformací a permutací sloupců lze každou matici převést na takový stupňovitý tvar, že první nenulový člen každého řádku má o jedničku větší sloupcový index než první nenulový člen předchozího řádku a počet nenulových řádků je roven hodnosti matice. Důkaz spočívá v konstrukci příslušného algoritmu: (0) Označíme A = (aij ) = A(0) = (aij ) – daná matice, A(k) – matice, kterou získáme po k-tém kroku algoritmu, ri (A(k) ) – i-tý řádek příslušné matice. Při tomto označení platí ri (A(k) ) = (k−1)

kde mik = −

aik

(k−1)

akk



ri (A(k−1) ) ri (A(k−1) ) + mik rk (A(k−1) ) (k−1)

, za předpokladu akk

pro pro

i≤k i>k

6= 0.

(k−1) akk

(k−1)

(k−1)

(k−1)

Je-li = 0, provedeme permutaci sloupců – testujeme postupně akk+1 , akk+2 , . . . , akk+l a v případě nenulového čísla zaměníme sloupce.

V předchozím jsme prováděli pouze řádkové elementární transformace, event. záměny 49

sloupců – v dalším textu uvidíme, že když je příslušná matice maticí koeficientů lineární soustavy rovnic, výsledná matice po provedení těchto úprav je maticí soustavy, která až na případné transformace proměnných, odpovídající záměnám sloupců, má stejné řešení jako výchozí soustava. Jestliže budeme provádět i sloupcové ekvivalentní úpravy, dostaneme také ekvivalentní matice, ale pochopitelně již ne ekvivalentní soustavy rovnic. Tyto sloupcové úpravy provádíme kvůli vyšetřování hodnosti matic; platí totiž věta: Věta 4.49: (Jordanova eliminace) Každá matice A typu (m, n) je ekvivalentní s diagonální maticí tvaru 

1

0

0

               

0 .. .

1

0 0 ··· .. .

0 ···

0 ···

0

1

0

0 ··· .. .

0 .. .

0 .. .

0 .. .

·

·

·

·

0 ···

0

0

0

··· 0



 ··· 0   ..  .   ··· 0    ··· 0   ..  .    ·  ··· 0

←−

h-tý řádek

a h = h(A), tj. počet nenulových řádků je roven hodnosti matice A. Důkaz je analogický důkazu předchozí věty; opět spočívá v konstrukci příslušného algoritmu.

Důsledek: Matice téhož typu jsou ekvivalentní, právě když mají stejnou hodnost. Dále se snadno přesvědčíme, že platí věty Věta 4.50: číslu m.

Hodnost každé gaussovské matice A typu (m,n), kde m ≤ n, je rovna

Důkaz si rozmyslete jako cvičení, stejně tak jako důkaz následující věty:

Věta 4.51:

Čtvercová matice stupně n je regulární, právě když h(A) = n.

Příklad 4.52: Máme určit hodnost h(A) matice   1 −2 3 −4 2  1 2 −1 0 −1    . 1 −1 2 −3 0 A=    0 1 −1 1 −2  2 3 −1 1 4 Provedeme postupně následující úpravy: 50

1) 1.ř. ponechat, 2.ř. - 1.ř., 3.ř. - 1.ř., 4.ř. ponechat, 5.ř. - 2× 1.ř.; 2) vyměnit 2. a 3.ř., vynechat 4.ř.; 3) 1.a 2.ř. ponechat, 3.ř. - 4× 2.ř., 4.ř. - 7× 2.ř.; 4) vyměnit 3. a 5. sloupec; 5) 1., 2., 3.ř. ponechat, 4.ř. - (14/5)× 3.ř. Dostaneme postupně:     1 −2 3 −4 2 1 −2 3 −4 2  1  2 −1 0 −1  4 −4 4 −3    1)  0     2 −3 0 ∼  0 1 −1 1 −2  A =  1 −1   0  0 1 −1 1 −2  1 −1 1 −2  2 3 −1 1 4 0 7 −7 9 0    1 −2 3 −4 2 1 −2 3 −4 2   0 1 −1 1 −2  1 −1 1 −2    ∼3)  0 ∼2)   0  0 0 0 0 5  4 −4 4 −3  0 0 0 2 14 0 7 −7 9 0     1 −2 2 −4 3 1 −2 2 −4 3  0  1 −2 1 −1  1 −2 1 −1   ∼5)  0  ∼4)   0  0 0 5 0 0  0 5 0 0  0 0 14 2 0 0 0 0 2 0 

Poslední matice je však již gaussovská, a tedy h(A)=4. Výpočet inverzní matice 1 Z předchozích úvah plyne, že • každá regulární matice A řádu n je ekvivalentní s jednotkovou maticí stejného řádu, a tedy se dá postupnými řádkovými elementárními transformacemi na ni převést, • tato úprava se dá realizovat násobením vhodnou maticí zleva. Tedy existuje matice R tak, že platí R · A = E – ale taková matice je právě matice inverzní k A, tedy R = A−1 . Jestliže stejné řádkové transformace použijeme na jednotkovou matici, provedeme součin A−1 · E = A−1 . Budeme tedy postupovat následujícím způsobem: • K zadané matici, kterou máme invertovat, připíšeme jednotkovou matici stejného řádu. • Elementárními řádkovými transformacemi upravíme vzniklou matici tak, aby v levé části (na místě zadané matice) vznikla matice jednotková. • V pravé části matice (na místě jednotkové matice) je hledaná matice inverzní: A|E ∼ A−1 · A|A−1 · E = E|A−1 .

51

Příklad 4.53: Nalezněte inverzní matici k matici   4 2 5 A =  0 3 2 . 0 4 3 Řešení: Sestavíme matici soustavy rozšířenou o příslušnou jednotkovou matici a budeme postupně upravovat: 1) 3.ř.-(4/3)× 2.ř., 3×3.ř.; 2) 1.ř.-5×3.ř., 2.ř.-2×3.ř.; 3) (1/3)×2.ř.; 4) 1.ř.-2×2.ř.; 5) (1/4)×1.ř.:   4 2 5 1 0 0 4 2 5  0 3 2 0 1 0  ∼1)  0 3 2 0 4 3 0 0 1 0 0 1 

 4 2 0 1 20 −15 9 −6  ∼3) ∼2)  0 3 0 0 0 0 1 0 −4 3   4 0 0 1 14 −11 3 −2  ∼5) ∼4)  0 1 0 0 0 0 1 0 −4 3 

 1 0 0 0 1 0  0 −4 3

 4 2 0 1 20 −15  0 1 0 0 3 −2  0 0 1 0 −4 3   1 0 0 1/4 14/4 −11/4  0 1 0 0 3 −2  0 0 1 0 −4 3 

tedy platí 

A−1

4.3

 1/4 14/4 −11/4 3 −2  . = 0 0 −4 3

Determinanty

Motivace Uvažujme soustavu a11 x1 + a12 x2 = b1 a21 x1 + a22 x2 = b2 dvou rovnic o dvou neznámých. Násobme první rovnici číslem a22 , druhou číslem −a12 a takto získané rovnice sečteme. Dále vynásobíme první rovnici číslem −a21 , druhou číslem a11 a znovu sečteme. Dostaneme soustavu (a11 a22 − a12 a21 )x1 = b1 a22 − b2 a12 (a11 a22 − a12 a21 )x2 = a11 b2 − a21 b1 52

Je vidět, že naše soustava bude mít řešení jedině v tom případě, jestliže číslo D = a11 a22 − a12 a21 bude různé od nuly; toto číslo má tedy podstatnou úlohu při řešení naší jednoduché soustavy – determinuje její řešení.   a11 a12 Toto číslo nazveme determinantem matice A = a označujeme ho a21 a22 a11 a12 a21 a22 , nebo |A|, popřípadě det A . Označíme-li b1 a12 a11 b1 = b1 a22 − b2 a12 , = a11 b2 − a21 b1 , D1 = D2 = b2 a22 a21 b2 platí pro řešení naší soustavy   D1 D2 (x1 , x2 ) = , . D D Vzorec pro výpočet hodnoty determinantu a11 a12 = a11 a22 − a12 a21 |A| = a21 a22 se nazývá křížové pravidlo pro determinant druhého řádu (prvky determinantu se násobí do kříže). Všimneme si ještě soustavy tří rovnic o třech neznámých a11 x1 + a12 x2 + a13 x3 = b1 a21 x1 + a22 x2 + a23 x3 = b2 a31 x1 + a32 x2 + a33 x3 = b3 První rovnici násobíme číslem a22 a23 = a22 a33 − a23 a32 , |A11 | = a32 a33 druhou číslem a a |A21 | = 12 13 a32 a33

= a12 a33 − a13 a32 ,

třetí číslem a a |A31 | = 12 13 a22 a23

= a12 a23 − a13 a22

a vzniklé rovnice sečteme. Dostaneme (a11 |A11 | − a21 |A21 | + a31 |A31 |)x1 = b1 |A11 | − b2 |A21 | + b3 |A31 |. 53

Koeficient u x1 je číslo a11 a22 a33 + a13 a21 a32 + a12 a23 a31 − a12 a21 a33 − a11 a23 a32 − a13 a22 a31 , které opět označíme písmenem D. Provedeme další analogické úpravy pro osamostatnění proměnných x2 , x3 a dostaneme Dx1 = b1 |A11 | − b2 |A21 | + b3 |A31 | Dx2 = −b1 |A12 | + b2 |A22 | − b3 |A32 | Dx3 = b1 |A13 | − b2 |A23 | + b3 |A33 | a odtud již snadno určíme řešení soustavy za předpokladu, že číslo D je různé od nuly. Číslo D opět nazveme a11 a12 |A| = a21 a22 a31 a32

determinantem matice A a označíme ho |A|. Platí tedy a13 a23 = a11 a22 a33 + a13 a21 a32 + a12 a23 a31 − a33 −a12 a21 a33 − a11 a23 a32 − a13 a22 a31 .

Tento postup výpočtu hodnoty determinantu třetího řádu se nazývá Sarusovo pravidlo; asi nejlépe si ho zapamatujeme takto: Utvoříme následující schema : a11 a12 a13 a11 a12 a21 a22 a23 a21 a22 a31 a32 a33 a31 a32 a budeme násobit trojice prvků v diagonálách shora dolů; ve směru zleva doprava je opatříme znaménkem + a ve směru zprava doleva znaménkem − a vzniklé výrazy sečteme. Vraťme se k naší soustavě: Jestliže dále označíme a11 b1 a13 a11 a12 b1 b1 a12 a13 D1 = b2 a22 a23 , D2 = a21 b2 a23 , D3 = a21 a22 b2 , a31 b3 a33 a31 a32 b3 b3 a32 a33 platí pro řešení soustavy   D1 D2 D3 (x1 , x2 , x3 ) = , , . D D D Pro řešení rozsáhlejších soustav analogickým způsobem je užitečné zavést pojem determinantu obecně. Nejdříve připomeneme pojem permutace, potřebný v hlavní definici: Permutace Definice 4.54: Permutací p množiny M rozumíme libovolné bijektivní zobrazení p : M → M . Je-li M = {1, 2, ..., n} (množina indexů), p – permutace této mno  1 2 ··· n žiny, zapisujeme ji obvykle ve tvaru p = , nebo jednoduše p(1) p(2) · · · p(n) p = (p(1) p(2) · · · p(n)). 54

Příklad 4.55:

Buď M = {1, 2, 3, 4}. Definujme zobrazení p předpisem

p(1) = 3, p(2) = 4,

p(3) = 2, p(4) = 1.

Toto zobrazení je permutace a píšeme   1 2 3 4 p= neboli p = (3 4 2 1). 3 4 2 1 Definice 4.56: 1. Inverzí v permutaci p = (p(1) p(2) · · · p(n)) nazýváme dvojici (i, j) takovou, že i < j, p(i) > p(j). 2. Permutace p je sudá (resp. lichá), má-li sudý (resp. lichý) počet inverzí. 3. Číslo (−1)k , kde k je počet inverzí v permutaci p, se nazývá znaménko permutace p a značí se sgn(p). Příklad 4.57: a) Identická permutace id = (1 2 · · · n) nemá žádnou inverzi – je sudá. b) Permutace p = (2 3 · · · n 1) má n − 1 inverzí. c) Permutace z předchozího příkladu, p (3, 2), (3, 1), (4, 2), (4, 1), (2, 1) – je lichá.

=

(3 4 2 1), má 5 inverzí –

Definice 4.58: Inverzní permutace k permutaci p je permutace definovaná předpisem p−1 = {(i, j)|(j, i) ∈ p}.  Příklad 4.59: Je-li p = (2 4 1 3), neboli p =     2 4 1 3 1 2 3 4 −1 p = = neboli p−1 = (3 1 4 2). 1 2 3 4 3 1 4 2

1 2 3 4 2 4 1 3

 , je

Věta 4.60: 1. Permutace p a p−1 mají stejný počet inverzí. 2. Jestliže permutace p0 vznikla z p záměnou hodnot na dvou pozicích (transpozicí), t.j. existují r, s tak, že p(r) = p0 (s), p(s) = p0 (r), p(i) = p0 (i) pro i 6= r, s, potom sgn(p0 ) = −sgn(p). Důkaz 1. Tvrzení je zřejmé: Je-li (i, j) inverze v p, tj. i < j, p(j) < p(i), potom (p(j), p(i)) je inverze v p−1 . 2. Prověření tohoto tvrzení je komplikovanější a vyžaduje více znalostí o permutacích, provádět ho nebudeme.

55

Definice determinantu Definice 4.61: Nechť je  a11 a12 · · ·  a21 a22 · · ·  A =  .. .. . .  . . . an1 an2 · · ·

dána čtvercová matice  a1n a2n   ..  . .  ann

Nechť p(1), p(2), · · · , p(n) je libovolná permutace čísel 1, 2, ..., n (permutací je n!). Utvořme součin a1p(1) · a2p(2) · a3p(3) · · · anp(n) a vynásobme jej číslem (−1) v případě, že permutace je lichá; jinak ponechejme součin beze změny. Provedeme-li to pro všechny permutace, dostaneme n! součinů. Jejich součet se pak nazývá determinant n-tého řádu matice A a označuje se |A|, popřípadě det A. Píšeme a11 a12 · · · a1n a21 a22 · · · a2n |A| = .. .. . . .. . . . . . an1 an2 · · · ann Platí tedy |A| =

X

sgn(p)a1p(1) a2p(2) · · · anp(n) ,

p

kde se sčítá přes všechy permutace p množiny {1, 2, ..., n}. Jinak řečeno: sestavujeme všechny možné součiny o n činitelích tak, že z každého sloupce a každého řádku vybereme vždy právě jeden činitel. V každém takovém součinu uspořádáme činitele podle prvních (řádkových) indexů (musí se, pochopitelně, vyskytnout všechny); pořadí sloupcových indexů tvoří permutaci, jejíž sudost nebo lichost určuje znaménko tohoto součinu ve výsledném součtu. Takových součinů je tolik, jako je permutací množiny sloupcových indexů – tedy pro determinant n-tého řádu je to n!. Součet všech takto vytvořených součinů opatřených pčíslušnými znaménky je pak hodnota determinantu. Jako cvičení je dobré ověřit, že křížové resp. Sarusovo pravidlo, jak jsme je výše uvedli, přesně odpovídá výpočtu hodnoty determinantu druhého resp. třetího řádu podle definice. Využitím hlubší znalosti vlastností permutací se dá dokázat následující důležitá věta: Věta 4.62:

Nechť A je čtvercová matice. Potom platí: |AT | = |A|.

Význam věty spočívá v tom, že nahradíme-li v libovolném tvrzení o determinantech slovo „řádekÿ slovem „sloupecÿ, dostáváme opět platné tvrzení o determinantech. Proto budeme formulovat věty pro determinanty pouze pro řádky. Základní vlastnosti determinantů, výpočet determinantů Výpočet hodnoty determinantu přímo z definice se prakticky neprovádí – počet sčítanců v definiční sumě je n!. Efektivnější metody výpočtu vyplývají z následujících tvrzení: 56

Věta 4.63:

Nechť A je čtvercová matice. Potom platí:

1. Jestliže matice A obsahuje nulový řádek, potom |A| = 0. 2. Jestliže matice B vznikne z matice A výměnou dvou řádků, potom platí |B| = −|A|. 3. Jestliže matice A má dva řádky stejné, potom |A| = 0. 4. Jestliže B vznikne z matice A vynásobením jednoho řádku číslem λ, potom platí |B| = λ|A|. 5. Pro libovolné číslo j ∈ {1, 2, ..., n} platí a11 · · · a1n a · · · a 11 1n . . . . . . . . .. .. .. .. . . aj1 + bj1 · · · ajn + bjn = aj1 · · · ajn . . .. .. ... .. . . ... . . a an1 ··· ann n1 · · · ann

+

a11 · · · a1n .. . . . . .. . bj1 · · · bjn .. . . . . .. . a ··· a n1

nn

6. Determinant matice v níž je jeden řádek lineární kombinací ostatních je roven nule. 7. Determinant se nezmění, jestliže k libovolnému řádku přičteme lineární kombinaci ostatních. 8. Determinant trojúhelníkové resp. diagonální matice je roven součinu prvků v její hlavní diagonále. 9. Determinant jednotkové matice je roven jedné. Důkaz spočívá v aplikaci definice determinantu; je vhodné jako cvičení prověřit některou část na determinantu třetího nebo raději čtvrtého řádu.

Příklad 4.64: Máme vyjádřit následující součet tří determinantů jedním determinantem: 1 1 0 2 3 2 3 3 5 −2 + 2 −1 −2 + 2 2 −1 −2 . 5 4 2 −1 −2 4 1 2 −1 2 3 Řešení: Ve druhém determinantu zaměníme 2. a 3. řádek, ve třetím nejdříve 2. a 3. řádek a poté 1. a 2. řádek; vzniklý 2. řádek násobíme koeficientem 2: 1 1 1 2 3 2 3 2 3 −2 5 4 − 4 2 −1 + 0 6 10 = 2 −1 −2 2 −1 −2 2 −1 −2 Vzniklé determinanty se liší pouze ve druhém řádku, podle části 5. věty 4.63 tedy dostaneme 1 1 2 3 2 3 9 15 = −3 2 −3 5 = −6 2 −1 −2 2 −1 −2 57

Poznámka: Hodnotu determinantu můžeme vyčíslit tak, že pomocí pravidel ve větě 4.63 (Gaussovou eliminací) matici upravíme na trojúhelníkový tvar a poté vynásobíme prvky v hlavní diagonále: Příklad 4.65: Pomocí dovolených úprav máme vypočítat hodnotu determinantu 1 1 1 1 1 2 3 4 . D = 1 3 6 10 1 4 10 20 Řešení: Provedeme postupně následující operace: 1) 2.ř.-1.ř., 3.ř.-2.ř., 4.ř.-3.ř.; 2) 3.ř.-2.ř., 4.ř.-3.ř.; 3) 4.ř.-3.ř.: 1 1 1 1 1 1 1 1 0 1 2 3 0 1 2 3 =2) =3) D =1) 0 0 1 3 0 1 3 6 0 1 4 10 0 0 1 4

1 0 0 0

1 1 0 0

1 2 1 0

1 3 3 1

.

To je determinant horní trojúhelníkové matice, a tedy D = 1.

Pomocí podrobnějšího rozepsání definice determinantu dostaneme rekurzivní metodu pro výpočet determinantu; nejdříve definujeme pomocný pojem algebraického doplňku a dále pojem adjungované matice, který budeme později potřebovat: Definice 4.66: 1. Je-li |Aij | determinant submatice (subdeterminant) matice A, která je příslušná k prvku aij , tedy vznikla vynecháním i-tého řádku a j-tého sloupce v matici A, potom číslo Aij definované předpisem Aij = (−1)i+j |Aij | se nazývá algebraickým doplňkem prvku aij matice A. 2. Matice A∗ = (Aij )T se nazývá adjungovaná matice k matici A. Příklad 4.67:  1  A=

3 2 3 2 3

Vypočítáme |A| a A∗ , je-li 2  − 23 3  1 − 3 − 23  2 3

1 3

58

Řešení: 1 −2 2 1 1 2 1 −2 = |A| = 27 27 2 2 1 1 −2 2 1 1 1 1 = − = − 0 3 3 0 2 −1 A11 = (−1)1+1

A12 =

−2 2 −3 −3 = 6 −3 1 −2 2 0 1 1 = 1 0 0 −3

1 −1 −2 1 = (−1 + 4) = 9 2 1 9

(−1)1+2 91

A13 = (−1)1+3

1 0 0

1 3

2 −2 = − 1 (2 + 4) = − 2 9 3 2 1

1 2 −1 1 = (4 + 2) = 9 2 2 9

2 3

A21 =

(−1)2+1 91

−2 2 1

A22 =

(−1)2+2 91

1 2 2 1

A23 =

(−1)2+3 91

1 −2 = − 1 (2 + 4) = − 2 9 3 2 2

A31 =

(−1)3+1 91

−2 2 −1 −2

A32 =

(−1)3+2 91

1 2 2 −2

A33 = (−1)3+3

= − 1 (−2 − 4) = 9

1 = (1 − 4) = − 1 3 9

1 1 −2 9 2 −1

1 = (4 + 2) = 9

2 3

= − 1 (−2 − 4) = 9 1 = (−1 + 4) = 9 

(Aij ) = A,

2 3

 A∗ = (Aij )T = 

1 3 − 23 2 3

2 3 − 13 − 23

2 3

1 3 2 3 2 3 1 3

  

Pomocí pojmu algebraického doplňku můžeme formulovat větu, na základě které se skutečně vyhodnocují determinanty řádu většího než tři: 59

Věta 4.68: (Laplaceova o rozvoji determinantu) Nechť A je čtvercová matice n-tého řádu a nechť r je libovolné číslo z množiny {1, 2, ..., n}. Potom platí vztahy |A| = ar1 Ar1 + ar2 Ar2 + · · · + arn Arn – rozvoj determinantu podle r-tého řádku a |A| = a1r A1r + a2r A2r + · · · + anr Anr – rozvoj determinantu podle r-tého sloupce. Důkaz spočívá v podrobnějším rozepsání definice determinantu; opět je dobré ověřit tvrzení věty na determinantu čtvrtého řádu. Odtud zobecněním bude patrný postup v obecném případě.

Příklad 4.69: Máme vypočítat hodnotu determinantu 1 4 0 3 2 −1 1 5 . D = 0 4 1 4 3 5 9 2 Řešení: Provedeme rozvoj podle prvního sloupce: −1 1 5 4 0 3 4 0 3 4 0 3 D = 1 4 1 4 − 2 4 1 4 + 0 −1 1 5 − 3 −1 1 5 . 5 9 2 5 9 2 5 9 2 4 1 4 Determinanty třetího řádu vypočítáme Sarusovým pravidlem a dostaneme D = 1 · 201 − 2 · (−43) − 3 · (−19) = 344. Věta 4.70: (Determinant součinu matic) Nechť A,B jsou čtvercové matice n-tého řádu. Potom platí: |AB| = |A| · |B|. Důkaz opět spočívá v podrobném rozepsání definice determinantů obou násobených matic a je dost pracný.

Věta 4.71: |A| = 6 0.

Čtvercová matice A je regulární, právě když pro její determinant platí

Důkaz: Směr ⇒ je důsledkem věty 4.70; Nechť je A regulární čtvercová matice a A−1 matice k ní inverzní. Tedy A−1 · A = En a odtud ihned plyne 1 |A−1 | · |A| = |En | = 1, tj. |A| 6= 0 a současně |A−1 | = |A| . Opačný směr dokazovat nebudeme.

Má-li tedy čtvercová matice nenulový determinant, je regulární, a tudíž její hodnost je rovna jejímu řádu. Hodnost matice můžeme určit s využitím jistých determinantů i v případě singulární matice resp. v případě matice obdélníkové; budeme vyšetřovat determinanty čtvercových submatic dané matice. Ty mají svůj speciální název: 60

Definice 4.72: Minorem k-tého řádu matice A typu (m, n) se rozumí determinant čtvercové matice, která vznikne z matice A vynecháním libovolných m − k řádků a n − k sloupců. Pro hodnost matice platí věta: Věta 4.73:

Hodnost matice je rovna maximálnímu řádu nenulových minorů.

Důkaz provádět nebudeme.

Příklad 4.74: Jsou dány čtyři aritmetické vektory v1 = (3, 1, −2, 1), v2 = (2, 4, 2, 2), v3 = (7, −3, −5, −1), v4 = (3, −1, 1, −1). Máme mezi nimi najít maximální systém lineárně nezávislých vektorů. Řešení: Hodnost matice   3 1 −2 1  2 4 2 2     7 −3 −5 −1  3 −1 1 −1 je rovna 3, protože 3 1 −2 2 4 2 = 50 6= 0, 7 −3 −5

a



3 1 −2 1 2 4 2 2 = 0. 7 −3 −5 −1 3 −1 1 −1

Tedy vektory v1 , v2 , v3 jsou lineárně nezávislé a vektor v4 je jejich lineární kombinací. Podobně i vektory v2 , v3 , v4 jsou lineárně nezávislé a vektor v1 je jejich lineární kombinací. Výpočet inverzní matice 2 V této části si uvedeme jiný postup výpočtu inverzní matice, který využívá jejího determinantu; tedy je vhodný pro matice nepříliš vysokých řádů: Věta 4.75: Buď A = (aij )nn regulární matice a A−1 = (a∗ij )nn matice k ní inverzní. A∗ , tedy Potom platí A−1 = |A| a∗ij =

Aji , |A|

kde číslo Akl je algebraický doplněk prvku akl matice A (viz definice 4.66). Důkaz Nechť A jePregulární matice, A∗ matice k ní adjungovaná. Potom A · A∗ = ( k aik Ajk ); Pro i = j je X

aik Aik = |A|

k

61

podle Laplaceovy věty, Pro i 6= j je tedy je roven nule. Odtud A · A∗ = |A| · E ⇒ A ·



P

k

aik Ajk roven determinantu, který získáme z |A| tak, že j-tý řádek nahradíme i-tým,

1 · A∗ |A|

 =E ⇒

1 · A∗ = A−1 . |A|

Příklad 4.76: Máme najít inverzní matici k matici   1 1 1 A =  0 1 1 . 0 0 1 Řešení: Platí zřejmě |A| = 1 a dále 1 1 |A11 | = |A21 | = |A22 | = |A32 | = |A33 | = 0 1 0 1 0 1 = 0, |A12 | = = 0, |A13 | = 0 1 0 0 1 1 1 1 =0 |A23 | = = 0, |A31 | = 0 0 1 1

= 1,

a dále A11 = (−1)1+1 |A11 | = 1, A21 = (−1)2+1 |A21 | = −1, A22 = (−1)2+2 |A22 | = 1, A32 = (−1)3+2 |A32 | = −1, A33 = (−1)3+3 |A33 | = 1 a ostatní algebraické doplňky jsou rovny nule. Odtud   1 −1 0 1 −1  . A−1 =  0 0 0 1 Jako cvičení se můžete přesvědčit, že A · A−1 = E3 . Příklad 4.77: Inverzní matice k matici A z příkladu 4.67 je zřejmě přímo rovna matici adjungované a protože platí |A| = 1, dostáváme A−1 = A∗ = AT . tj. A je ortonormální.

4.4

Soustavy lineárních rovnic

Všechny naše dosavadní úvahy jsme motivovali snahou řešit soustavy lineárních rovnic; v této kapitole se jim budeme věnovat podrobněji, hlavně z hlediska existence a jednoznačnosti řešení.

62

Maticový zápis soustavy lineárních rovnic, rozšířená matice soustavy Definice 4.78:

Mějme libovolnou soustavu m lineárních rovnic o n neznámých:

a11 x1 + a12 x2 + · · · + a1n xn = b1 a21 x1 + a22 x2 + · · · + a2n xn = b2 ··· am1 x1 + am2 x2 + · · · + amn xn = bm Označme    A=     b= 

a11 a21 .. .

a12 a22 .. .

··· ··· ...

a1n a2n .. .

am1 am2 · · · amn b1 b2 .. .





  , 

  A|b =  

bm

   , 

   x= 

x1 x2 .. .

   , 

xn a11 a21 .. .

a12 a22 .. .

··· ··· .. .

a1n a2n .. .

am1 am2 · · · amn



b1 b2 .. .

   . 

bm

Používáme následující názvy: A x b A|b

– – – –

matice soustavy, vektor neznámých, vektor pravých stran, rozšířená matice soustavy,

Ax = b

– maticový zápis soustavy.

Navíc je-li A regulární matice (tedy čtvercová), můžeme tuto maticovou rovnici násobit zleva maticí k ní inverzní A−1 a dostaneme řešení ve tvaru x = A−1 b

Tento postup je jednoduchý pouze zdánlivě; výpočet inverzní matice u rozsáhlejších soustav je totiž podstatně náročnější než jiné současné metody přímo řešící soustavu (např. Gaussova eliminační metoda). V následujícím příkladu si ukážeme, že i v případě soustavy tří rovnic může být postup řešení pomocí inverzní matice zbytečně komplikovaný: Příklad 4.79: x1

+ x2 x2

Pomocí inverzní matice řešte soustavu rovnic + x3 = 3 + x3 = 2 x3 = 1

63

Řešení: Matice soustavy má tvar   1 1 1 A =  0 1 1 , 0 0 1 je to horní trojúhelníková matice, je gaussovská. Zpětným chodem ihned dostaneme x = (x1 , x2 , x3 ) = (1, 1, 1), což ostatně vidíme na první pohled. Máme ovšem řešení najít pomocí inverzní matice. Inverzní matici k matici A jsme našli v příkladu 4.76, kde vyšlo   1 −1 0 1 −1  . A−1 =  0 0 0 1 Tedy 

    1 −1 0 3 1 −1      1 −1 2 = 1 . x=A b= 0 0 0 1 1 1 Řešení soustavy pomocí inverzní matice bylo skutečně zbytečně komplikované. Definujeme ještě další potřebné pojmy: Definice 4.80: Je-li v soustavě lineárních rovnic Ax = b matice A čtvercová (stejný počet rovnic jako neznámých), nazývá se i soustava čtvercová soustava. Je-li vektor pravých stran soustavy nulový, tj. b = o, nazývá se soustava homogenní. Řešitelnost soustavy, Frobeniova věta V odstavci ?? jsme viděli, že při přímém chodu v Gaussově eliminační metodě dospějeme k jedné ze dvou možností:   6= x x · · · x x · · · x x  0 6= x · · · x x · · · x x      a)  0 0 6= · · · x x · · · x x   .. .. .. . . . . .. . .   . . . . .. .. . .. ..  ←− k 0 0 0 ··· = 6 x ··· x x   6= x x · · · x x · · · x x  0 6= x · · · x x · · · x x     0 0 6= · · · x x · · · x x    b)  .. .. .. . . .. .. . . .. ..   . . . . . . . . .     0 0 0 ··· = 6 x · · · x x  ←− k 0 0 0 · · · 0 0 · · · 0 6= 64

kde symbol 6= znamená libovolné číslo různé od nuly, x libovolné číslo a (←− k) označuje k-tý řádek. V prvním případě má soustava řešení (alespoň jedno), ve druhém případě nemá žádné řešení. Přitom elementární úpravy soustavy rovnic odpovídají příslušným elementárním transformacím řádkových vektorů rozšířené matice soustavy. Všimneme-li si, že v prvním případě mají matice soustavy i rozšířená matice soustavy stejnou hodnost, ve druhém případě nikoliv, vidíme, že platí: Věta 4.81:

(Frobeniova)

1. Soustava Ax = b, x = (x1 , x2 , . . . , xn ) má řešení, právě když h(A) = h(A|b) (hodnost matice soustavy je stejná jako hodnost rozšířené matice soustavy). 2. Jestliže h(A) = h(A|b) = k, potom v případě k < n má soustava nekonečně mnoho řešení, která mohou být zapsána pomocí n − k parametrů, a v případě k = n má soustava právě jedno řešení. Důkaz 1. Jestliže má soustava Ax = b, tedy soustava a11 x1 a21 x1 ··· am1 x1

+ +

a12 x2 a22 x2

+ +

··· ···

+ +

a1n xn a2n xn

= =

b1 b2

+

am2 x2

+

···

+

amn xn

=

bm

řešení y = (y1 , y2 , . . . , yn ), tedy když platí, že a11 y1 a21 y1 ··· am1 y1

+ +

a12 y2 a22 y2

+ +

··· ···

+ +

a1n yn a2n yn

= =

b1 b2

+

am2 y2

+

···

+

amn yn

=

bm

,

je poslední sloupec rozšířené matice A|b soustavy lineární kombinací prvních n sloupců, protože poslední rovnosti znamenají,že y1 (a11 , a21 , . . . , am1 ) + y2 (a12 , a22 , . . . , am2 ) + · · · + yn (a1n , a2n , . . . , amn ) = (b1 , b2 , . . . , bm ). Odtud plyne, že h(A) = h(A|b), protože matice A|b vznikne z matice A přidáním jediného sloupce, který je lineární kombinací sloupců matice A. 2. Jestliže platí h(A) = h(A|b), nemá matice A|b více lineárně nezávislých sloupců než matice A. Její poslední sloupec tedy musí být lineární kombinací předchozích sloupců, tj. existují čísla y1 , y2 , . . . , yn tak, že platí y1 (a11 , a21 , . . . , am1 ) + y2 (a12 , a22 , . . . , am2 ) + · · · + yn (a1n , a2n , . . . , amn ) = (b1 , b2 , . . . , bm ). Tedy y = (y1 , y2 , . . . , yn ) je řešení dané soustavy.

Je-li soustava čtvercová, je buď h(A) = n, nebo h(A) < n. V prvním případě je automaticky h(A) = h(A|b) a podle Frobeniovy věty má soustava právě jedno řešení a navíc je |A| = 6 0, tj. matice A je regulární. Ve druhém případě je |A| = 0, tj. matice A je singulární, a podle Frobeniovy věty soustava buď nemá žádné řešení, nebo má nekonečně mnoho řešení. Je-li soustava homogenní, je automaticky splněna podmínka h(A) = h(A|b) = k a podle Frobeniovy věty má soustava jedno řešení (pro k = n), nebo nekonečně mnoho řešení (pro k < n). V prvním případě se pochopitelně jedná pouze o nulové řešení. 65

Příklad 4.82: x1 2x1 3x1 −2x1

Je dána soustava lineárních rovnic

+ x2 − x2 − 7x2 + 5x2

− x3 + x3 − 2x3 + x3

= −1 = 4 = −1 = 1

Pomocí Frobeniovy věty máme zjistit, zda soustava má řešení a kolik; v kladném případě všechna řešení najít. Řešení: Pomocí elementárních úprav vyšetříme hodnosti matic soustavy: 1) 2ř.-2×(1.ř.), 3.ř.-3×(1.ř.), 4.ř.+2×(1.ř.); 2) 2.ř.:(-3); 3) 3.ř.+10×(2.ř.), 4.ř.-7×(2.ř.); 4) 4.ř.+(6/9)×(3.ř.):      1 1 −1 −1 1 1 −1 −1 1 1 −1  2 −1     1 4  1)  0 −3 3 6  2)  0 1 −1  ∼   3 −7 −2 −1  ∼  0 −10  1 2 0 −10 1 −2 5 1 1 0 7 −1 −1 0 7 −1     1 1 −1 −1 1 1 −1 −1  0 1 −1 −2  4)  0 1 −1 −2     ∼3)   0 0 −9 −18  ∼  0 0 −9 −18  0 0 6 13 0 0 0 1

 −1 −2   2  −1

Tedy h(A) = 3, h(A|b) = 4. Soustava nemá řešení. (Můžeme si povšimnout, že poslední řádek poslední matice vlastně znamená 0 · x3 = 1.) Příklad 4.83: Pomocí Frobeniovy věty rozhodněte, pro která α má následující soustava rovnic alespoň jedno řešení: x + 2y − z = 2x − y + z = −x + y + αz =

3 0 1

Řešení: Rozšířená matice soustavy má tvar   1 2 −1 3 1 0  , A|b =  2 −1 −1 1 α 1 matici upravíme na trojúhelníkový tvar (Gaussovou eliminací) a dostaneme   1 2 −1 3 −3 6  . A|b ∼  0 5 0 0 5α + 4 2 Aby soustava měla řešení, nesmí být hodnost rozšířené matice větší než hodnost matice soustavy – tedy musí platit 4 5α + 4 6= 0 ⇒ α 6= − . 5 4 Je-li α = − 5 , soustava nemá řešení. 66

Homogenní soustavy Uvažujme homogenní soustavu lineárních rovnic A · x = o, x ∈ Vn , o ∈ Vm (soustavu o n neznámých – počet rovnic může být jiný). Je zřejmé, že homogenní soustava je vždy řešitelná – nulový vektor x = o ∈ Vn je vždy jejím řešením; toto řešení se nazývá triviální. Dále platí důležitá věta: Věta 4.84: Množina W všech řešení homogenní soustavy A · x = o je podprostorem prostoru Vn a dimW = n − h(A) . Důkaz: 1. W v Vn : x, y řešení ⇒ A · (x + y) = Ax + Ay = o + o = o α ∈ R ⇒ Aαx = αAx = αo = o. 2. Gaussovou eliminační metodou upravíme matici A = (aij ) na stupňovitý tvar C = (cij ) (nulové řádky vynecháme): a11  a21  A= ..  . am1 

a12 a22 .. . am2

··· ··· .. . ···

a1n a2n .. . amn





    ∼C=  

c11 0 .. . 0

c12 c22 0

··· ··· .. . ···

c1h c2h .. . chh

··· ···

c1n c1n .. . chn

···

    

Soustava tedy přejde na tvar c11 y1

+

c12 y2 c22 y2

+ +

··· ···

+ +

c1h yh c2h yh

+ +

··· ···

+ +

c1n yn c2n yn

chh yh

+

···

+

chn yn

= = .. . =

0 0

0

kde h = h(A) a (y1 , . . . , yn ) je permutace neznámých (x1 , . . . , xn ) vzniklá při výměně sloupců. (yk+1 , . . . , yn ) jsou volné neznámé, které můžeme volit libovolně. Po úpravě dostaneme c11 y1

+

c12 y2 c22 y2

+ +

··· ···

+ +

c1h yh c2h yh

= = .. . =

chh yh

− −

c1h+1 yh+1 c2h+1 yh+1

− −

··· ···

− −

c1n yn c2n yn

−

chh+1 yh+1

−

···

−

chn yn

což je soustava s regulární maticí při libovolné volbě (yh+1 , . . . , yn ). Položme postupně (yh+1 , . . . , yn ) rovno jednotkovým vektorům z Vn−h a řešení, která obdržíme, označme postupně b1 , . . . , bn−h . Je-li y = (y1 , . . . , yn ) libovolné řešení naší soustavy, lze je jediným způsobem vyjádřit jako lineární kombinaci y = yh+1 b1 + · · · + yn bn−h , neboť vektory na levé i pravé straně mají posledních n− h složek stejných, a musí se tedy rovnat. Tedy b1 , . . . , bn−h je báze W.

Jinak řečeno, smysl předcházející věty je tento: Máme-li homogenní soustavu lineárních rovnic o n neznámých, jejíž matice má hodnost h (tedy jen h rovnic je nezávislých), potom n-tice, která je řešením soustavy, závisí na n − h parametrech. Vše snad bude jasnější na základě příkladu. Nejdříve uvedeme následující definici: 67

Definice 4.85: Libovolná báze b1 , . . . , br , r = n − h(A), prostoru řešení se nazývá fundamentální systém řešení homogenní soustavy. Každé řešení x se dá jediným způsobem vyjádřit ve tvaru x = α1 b1 + · · · + αr br , který se nazývá obecné řešení. Příklad 4.86:

Řešte homogenní soustavu rovnic

3x1 + 2x2 + 5x3 + 2x4 + 7x5 6x1 + 4x2 + 7x3 + 4x4 + 5x5 3x1 + 2x2 − x3 + 2x4 − 11x5 6x1 + 4x2 + x3 + 4x4 − 13x5 Řešení:  3  6   3 6

= = = =

Matici soustavy upravíme   2 5 2 7 3   4 7 4 5   0 ∼ 2 −1 2 −11   0 0 4 1 4 −13

0 0 0 0

Gaussovou eliminací (nulové řádky vynecháme):  2 5 2 7   0 −3 0 −9   ∼ 3 2 0 2 −8 . 0 −6 0 −18  0 0 1 0 3 0 −9 0 −27

Máme tedy soustavu 3x1 = −2x2 − 2x4 + 8x5 x3 = −3x5 Položme postupně 1. (x2 , x4 , x5 ) = (1, 0, 0), 2. (x2 , x4 , x5 ) = (0, 1, 0), 3. (x2 , x4 , x5 ) = (0, 0, 1) a dostaneme 1. x1 = − 23 , x3 = 0 ⇒ b1 = (− 23 , 1, 0, 0, 0), 2. x1 = − 23 , x3 = 0 ⇒ b2 = (− 23 , 0, 0, 1, 0), 3. x1 = 83 , x3 = −3 ⇒ b3 = ( 83 , 0, −3, 0, 1). Obecné řešení soustavy má tvar x = α1 b1 +α2 b2 +α3 b3 ; položme α1 = 3c1 , α2 = 3c2 , α3 = 3c3 a dostaneme    x = c1   

−2 3 0 0 0





     + c2     

−2 0 0 3 0





     + c3     

8 0 −9 0 3

   .  

Povšimněme si, že pro vektorový prostor W řešení naší soustavy platí W = hb1 , b2 , b3 i, W v V5 (soustava má pět neznámých) a dim W = 3 = 5 − h(A). 68

Nehomogenní soustavy Uvažujme nehomogenní soustavu lineárních rovnic A · x = b, x ∈ Vn , b ∈ Vm . Pro řešitelnost soustavy, jak víme, platí Frobeniova věta; obecný tvar řešení nehomogenní soustavy popisuje následující věta: Věta 4.87:

Každé řešení x soustavy A · x = b se dá vyjádřit ve tvaru

x = x∗ + α1 b1 + · · · + αr br , kde x∗ je jedno pevně zvolené řešení dané rovnice (tzv. partikulární řešení) a b1 , . . . , br je fundamentální systém příslušné homogenní soustavy rovnic A · x = o. Důkaz se pokuste provést sami dosazením předpokládaného řešení přímo do soutavy.

Příklad 4.88:

Řešme soustavu rovnic

3x1 + 2x2 + 5x3 + 2x4 + 7x5 6x1 + 4x2 + 7x3 + 4x4 + 5x5 3x1 + 2x2 − x3 + 2x4 − 11x5 6x1 + 4x2 + x3 + 4x4 − 13x5

= = = =

1 8 13 20

Řešení: V příkladu 4.86 jsme řešili příslušnou homogenní soustavu; dostali jsme řešení ve tvaru       −2 −2 8  3   0   0             x0 = c1  0  + c2  0  + c3   −9  .  0   3   0  0 0 3 Dále se snadno (dosazením) přesvědčíme, že x∗ = (1, −1, 1, 1, −1) je jedno řešení soustavy nehomogenní. Každé řešení nehomogenní rovnice tedy dostaneme volbou konstant ve výrazu         8 1 −2 −2  −1   3   0   0                . −9 x =  1  + c1  0  + c2  0  + c3     0   1   0   3  0 3 −1 0 Cramerovo pravidlo V této části využijeme pojmu determinantu při formulaci zobecněného vztahu pro řešení soustavy lineárních rovnic, analogického s postupem, který jsme odvodili v odstavci 4.3 o motivaci k pojmu determinantu: 69

Věta 4.89: (Cramerovo pravidlo) Je-li dána soustava n lineárních rovnic o n neznámých Ax = b, jejíž matice A je regulární, platí   |A1 | |A2 | |An | (x1 , x2 , . . . , xn ) = , ,..., , |A| |A| |A| kde Ak je matice vytvořená z matice A tak, že její k-tý sloupec je nahrazen sloupcem pravých stran b. Důkaz: Řešíme soustavu Ax = b. Násobíme zleva inverzní maticí k matici soustavy A−1 : x = A−1 b =

1 A∗ b. |A|

Odtud xj =

|Aj | 1 (b1 A1j + · · · + bn Anj ) = . |A| |A|

Příklad 4.90: rovnic

Užitím Cramerova pravidla máme najít x1 a x2 vyhovující soustavě

2x1 + x2 x1 + 2x2 + x3 x2 + 2x3 + x4 x3 + 2x4

= = = =

1 0 0 0

Řešení: 

2  1 A=  0 0

1 2 1 0

0 1 2 1 D = |A| = 2 · 1 1 0 0 2 1 D1 = 0 1 2 0 0 1 2 1 0 1 0 1 D2 = 0 0 2 0 0 1

 2 1 0 0 1  1 2 1 0 0   A|b =   0 1 2 1 0 , 0 0 1 2 0 2 1 0 1 0 0 1 2 1 − 1 2 1 = 2 · 4 − 3 = 5, 0 1 2 0 1 2 0 2 1 0 D1 4 0 = 1 2 1 = 4, x1 = = , 1 D 5 0 1 2 2 0 1 1 0 D2 3 0 = − 0 2 1 = −3, x2 = =− . 1 D 5 0 1 2 2  0 0  , 1  2



70

Z hlediska složitosti výpočtu je pro větší počet rovnic Cramerovo pravidlo nevhodné (jeho součástí je výpočet n + 1 determinantů n-tého řádu; přitom determinant n-tého řádu je součtem n! součinů po n činitelích) – používá se obvykle nejvýše pro tři rovnice o třech neznámých, resp. v situaci, kdy nepotřebujeme najít všechny neznámé, ale třeba jen jednu. Navíc je Cramerovo pravidlo použitelné pouze na čtvercové soustavy. Většinou se používá Gaussova eliminační metoda nebo některá její modifikace. Při jejich použití není třeba předem vědět, zda soustava má či nemá řešení – to zjistíme během řešení, protože Frobeniova věta je vlastně výsledkem této metody. Navíc zde nemusí být stejný počet rovnic jako neznámých. Poznámka o zaokrouhlovacích chybách a špatně podmíněných soustavách V této části si povšimneme soustav rovnic z hlediska numerického:

Soustavy rovnic, které vycházejí z praxe, obvykle řešíme s využitím počítače (nebo alespoň na kalkulačce). Při těchto výpočtech jsou vstupující čísla pochopitelně zaokrouhlovány na nějaký konečný počet platných cifer a tím vznikají zaokrouhlovací chyby . Přitom předpokládáme (nebo doufáme), že takové malé změny vedou k výsledkům s malou chybou. Například soustava x + y = 2 x − 1,014 y = 0 má řešení x = ˙ 1,007, y = ˙ 0,993, zatímco řešení soustavy, kterou dostaneme zaokrouhlením na dvě desetinná místa: x + y = 2 x − 1,01 y = 0 je velmi „podobnéÿ: x = ˙ 1,005, y˙= 0,995. Naproti tomu soustava x + y = 2 x + 1,014 y = 0 má řešení x = ˙ 144,9 y = ˙ − 142,9, zatímco řešení „zaokrouhlené soustavyÿ x + y = 2 x + 1,01 y = 0 je x = ˙ 202 y = ˙ − 200. Poslední soustava je příkladem tzv. špatně podmíněné sousavy , kdy malá změna v koeficientech soustavy vede k velké změně řešení.

71

4.5

Vektorové prostory

Pro aritmetické vektory – uspořádané n-lice čísel – jsme odvodili některé vlastnosti: komutativitu a asociativitu sečítání, vlastnosti nulového vektoru, distributivní zákony o násobení skalárem a tp. Nyní postup obrátíme: budeme zkoumat množiny nějakých objektů, pro které zavedeme operace sečítání a skalární násobek tak, aby takovéto vlastnosti platily. Základní pojmy Definice 4.91: Vektorovým prostorem nad R rozumíme neprázdnou množinu prvků V, na níž je definována • operace sčítání dvojic prvků (tj. každé dvojici prvků u, v ∈ V je jednoznačně přiřazen prvek u + v ∈ V ) a • násobení prvků z V prvky z R (tj. každému u ∈ V a každému α ∈ R je jednoznačně přiřazen prvek αu ∈ V). Uvedené operace musí přitom splňovat tyto podmínky: 1. u + v = v + u, u, v ∈ V 2. (u + v) + w = u + (v + w), u, v, w ∈ V 3. existuje prvek o ∈ V takový, že o + u = u pro každé u ∈ V, 4. ke každému u ∈ V existuje vektor −u ∈ V tak, že u + (−u) = o. 5. α(u + v) = αu + αv, u, v ∈ V, α ∈ R 6. (α + β)u = αu + βu, u ∈ V, α, β ∈ R 7. α(βu) = (αβ)u, u ∈ V, α, β ∈ R 8. 1 · u = u, u ∈ V. Prvky vektorového prostoru se nazývají vektory. Vektor o se nazývá nulový vektor.

Příklad 4.92: Aritmetický vektorový prostor je (pochopitelně) vektorový prostor i podle této definice; speciálně prostor reálných (ale i komplexních) čísel je vzhledem k obvyklým operacím sčítání a násobení vektorový prostor – plyne bezprostředně z definice. Aritmetický vektorový prostor tvořený n-ticemi reálných čísel budeme označovat Rn . Příklad 4.93: Množina Mnm všech matic typu (m,n) spolu s operacemi sčítání a násobení číslem tvoří vektorový prostor:

72

Řešení: Nechť A = (aij )nm , B = (bij )nm ∈ Mnm . Potom A + B = (aij + bij )nm ∈ Mnm ,

∀α ∈ R : αA = (αaij )nm ∈ Mnm

– prostor matic typu (m,n) je uzavřen k operacím sečítání a násobení reálným číslem. Dále je třeba prověřit, že platí podmínky 1. – 8.; vesměs se prověří „po složkáchÿ: 1. A + B = (aij + bij )nm = (bij + aij )nm = B + A, 2. (A + B) + C = ((aij + bij ) + cij )nm = (aij + (bij + cij ))nm = A + (B + C), 3. Nulový prvek prostoru matic je zřejmě nulová matice, 4. −A = (−1) · A, 5. αA + B = (α(aij + bij ))nm = (αaij + αbij )nm = (αaij )nm + (αbij )nm = αA + αB, 6. (α + β)A = ((α + β)aij )nm = (αaij + βaij )nm = (αaij )nm + (βaij )nm = αA + βA, 7. α(βA) = α(βaij )nm = ((αβ)aij )nm = (αβ)A, 8. 1 · A = 1 · (aij )nm = (1 · aij )nm = (aij )nm = A. Podprostor obecného vektorového prostoru definujeme obvyklým způsobem tak, jak se definují v algebře podstruktury – jako podmnožinu, která má vlastnosti vektorového prostoru: Definice 4.94: Neprázdnou podmnožinu W vektorového prostoru nazveme podprostorem prostoru V , jestliže W je vektorovým prostorem vzhledem k operacím sčítání a násobení číslem, které jsou definovány na V . V tomto případě budeme používat označení W v V. V kapitole o aritmetických vektorových prostorech jsme podprostor definovali poněkud jinak – jako podmnožinu uzavřenou k příslušným operacím. Rozmyslete si, že obě definice jsou ekvivalentní. Důsledkem předcházejícího tvrzení je následující elementární věta: Věta 4.95: Průnik libovolného neprázdného systému podprostorů vektorového prostoru V je opět podprostorem prostoru V. Důkaz: Protože platnost podmínek 1. – 8. pro operace sečítání a násobení číslem plyne z jejich platnosti ve výchozím vektorovém prostoru, stačí vyšetřit, že průnik neprázdného systému podprostorů je množina uzavřená vzhledem k příslušným operacím: T Nechť W = Vi , u, v ∈ W. Potom ∀i : u, v ∈ Vi ⇒ ∀i : u + v ∈ Vi ⇒ u + v ∈ W. i

Uzavřenost průniku podprostorů vzhledem k násobení číslem se ukáže analogicky.

73

Lineární kombinace, lineární závislost Budeme se opět snažit zavést pojem báze vektorového prostoru a souřadnice vektoru vzhledem k této bázi, abychom tak opět získali vyjádření libovolného vektoru jako lineární kombinaci vektorů báze. K tomu potřebujeme definovat i v obecném případě vektorového prostoru pojem lineární kombinace a lineární závislosti. Zatímco lineární kombinace bude v obecném případě definována formálně stejně jako v aritmetických vektorových prostorech, s lineární závislostí to bude poněkud komplikovanější – v aritmetických vektorových prostorech jsme vyšetřovali lineární závislost a nezávislost jen pro konečný systém vektorů, zatímco v obecném případě budeme potřebovat pojem lineární závislosti i pro nekonečné množiny. Naštěstí se ukáže, že nám známé metody vyšetřování závislosti budou použitelné i v obecných vektorových prostorech. Nejdříve uvedeme několik definic a vět, které jsou formálně stejné jako v případě aritmetických vektorových prostorů: Definice 4.96: Buďte u1 , u2 , ..., un vektory z vektorového Lineární kombinací vektorů u1 , u2 , ..., un nazveme každý vektor u = α1 u1 + α2 u2 + · · · + αn un =

n X

prostoru

V.

αi ui

i=1

kde α1 , α2 , ..., αn ∈ R. Lineární kombinace se nazývá triviální, jsou-li všechny její koeficienty rovny nule, a netriviální, je-li alespoň jeden z jejích koeficientů různý od nuly. Definice 4.97: Buď M podmnožina vektorového prostoru V. Průnik všech podprostorů prostoru V, obsahujících množinu M , nazýváme lineárním obalem množiny M a značíme hM i. Je-li množina M konečná, M = {u1 , u2 , ..., un }, pak místo h{u1 , u2 , ..., un }i budeme psát hu1 , u2 , ..., un i. Věta 4.98:

Buď M podmnožina vektorového prostoru V. Pak platí:

1. je-li M = ∅, je hM i = {o}, 2. je-li M 6= ∅, pak hM i je množina všech lineárních kombinací

n P

αi ui ,

i=1

kde ui ∈ M, i = 1, 2, ...n.

Příklad 4.99: Uvažujme homogenní soustavu lineárních rovnic A · x = o, kde matice soustavy A je typu (m, n); tedy soustavu m rovnic o n neznámých (řešením soustavy je n-tice). Množina řešení této soustavy tvoří, jak víme, vektorový prostor – podprostor aritmetického vektorového prostoru Rn – prostoru všech n-tic. Situaci ilustruje následující triviální příklad: Řešení jedné lineární rovnice x + 3y = 0 je tvaru y = α (libovolné), x = −3α, neboli x = α(−3, 1). Tedy prostor řešenní dané rovnice je h(−3, 1)i v R2 .

74

Definice 4.100: Podmnožina M vektorového prostoru V se nazývá množinou generátorů prostoru V, jestliže hM i = V. Budeme též říkat, že množina M generuje V. Věta 4.101: Podmnožina M vektorového prostoru V je množinou generátorů prostoru V, právě když každý vektor z V je lineární kombinací vektorů z množiny M. Všechny předchozí definice a věty jsou formálně naprosto stejné jako u aritmetických vektorových prostorů a věty by se stejně dokazovaly. V následujících příkladech tyto pojmy aplikujeme na případy obecných (ne-aritmetických) prostorů: Příklad 4.102: Vektory    1 0 A= ,B= 0 0    0 1 F= ,G= 0 1

0 1 0 0



1 0 1 0



 ,C=  ,H=

0 0 1 0



1 1 1 1



 ,D=

0 0 0 1



 ,E=

1 0 0 1

 ,

.

tvoří množinu generátorů ve vektorovém prostoru všech čtvercových matic řádu 2.  Řešení: Nechť M =

a b c d

 je obecná čtvercová matice řádu 2. Potom zřejmě platí

M = aA + bB + cC + dD, ale také M = (a + b − c − d)B + (a − c)E + (a − d)G + (−a + c + d)H.

Příklad 4.103: Vektory 1, 1 + x, 1 + x + x2 , 1 + x + x2 + x3 , x + x3 , x3 − x2 + 7 tvoří množinu generátorů prostoru všech polynomů stupně nejvýše třetího. Řešení: 1. Je třeba ukázat, že polynomy stupně nejvýše třetího tvoří vektorový prostor: Nechť P, Q jsou polynomy třetího stupně; tedy funkce P, Q : R → R takové, že pro každé reálné x platí: P (x) = a0 + a1 x + a2 x2 + a3 x3 , Q(x) = b0 + b1 x + b2 x2 + b3 x3 . Potom P + Q resp. αP jsou polynomy třetího stupně (funkce z R do R) takové, že pro každé reálné x platí (P + Q)(x) = P (x) + Q(x) = (a0 + b0 ) + (a1 + b1 )x + (a2 + b2 )x2 + (a3 + b3 )x3

75

resp. (αP )(x) = αP (x) = (αa0 ) + (αa1 )x + (αa2 )x2 + (αa3 )x3 . Platnost podmínek 1. – 8. se prověří bezprostředně (využije se vlastností reálných čísel pro koeficienty). Poznamemejme, že nulový polynom, tj. funkce 0 : R → R, 0(x) = 0 + 0x + 0x2 + 0x3 = 0 ∀x je nulový vektor vyšetřovaného vektorového prostoru. 2. Abycom prověřili, že daná množina polynomů je generující množinou, musíme obecný polynom vyjádřit jako lineární kombinaci polynomů dané množiny. Ihned vidíme, že platí a0 +a1 x+a2 x2 +a3 x3 = (a0 −a1 +a3 )(1)+(a1 −a2 −a3 )(1+x)+a2 (1+x+x2 )+a3 (x+x3 ) a tím jsme hotovi. Příklad 4.104: Vektory 1, x, x2 , . . . , xn , . . . tvoří generující množinu ve vektorovém prostoru všech polynomů. Řešení: Postup při prověřování faktu, že všechny polynomy tvoří vektorový prostor, je identický s postupem v předchozím příkladu. Při prověřování faktu, že daná množina je generující množinou, je potřeba si uvědomit, že sice uvažujeme polynomy všech stupňů, ale jestliže jeden libovolný zvolíme (označme ho Pn (x)), má konkretní konečný stupeň n. Potom je zřejmě Pn (x) = a0 + a1 x + a2 x2 + · · · + an−1 xn−1 + an xn . Tedy každý polynom se dá vyjádřit jako lineární kombinace prvků dané množiny polynomů, tedy daná množina je množinou generátorů. V předchozích příkladech jsme se setkali s různými situacemi – v prvních dvou příkladech jsme pro vyjádření obecného vektoru jako lineární kombinace potřebovali jen některé prvky množiny generátorů, v posledním to bylo jinak: Můžeme si povšimnout, že vynecháme-li zde jeden konkretní prvek ze zadané množiny, nebude již generující množinou prostoru všech polynomů. Navíc to byl případ nekonečné (spočetné) množiny generátorů .

Připomeňme, že směřujeme k pojmu báze a souřadnic vektoru vzhledem k bázi, ta se jistě musí sestávat z navzájem lineárně nezávislých prvků; ale jak ji popsat, jestliže může být, jak jsme viděli v posledním příkladu, i nekonečná? K tomu využijeme faktu, že žádný z prvků takové množiny nesmí být „zbytečnýÿ pro tvorbu lineárního obalu. To vede k následující definici:

76

Definice 4.105: Neprázdná podmnožina M vektorového prostoru V se nazývá lineárně nezávislá, jestliže pro každou vlastní podmnožinu N ⊂ M je hN i ⊂ hM i. V opačném případě, tj. když existuje vlastní podmnožina N množiny M taková, že hN i = hM i, se množina M nazývá lineárně závislá. Tedy množina M je lineárně závislá, můžeme-li některé z jejích prvků vynechat, aniž se zmenší lineární obal množiny M. Definice lineární nezávislosti, jak jsme ji uvedli, nedává žádnou metodu pro praktické zjištění, zda je daná množina lineárně nezávislá nebo ne. U aritmetických vektorů jsme takovou metodu měli – souvisela s lineárními kombinacemi a bylo pro ni důležité, že jsme zkoumali pouze konečné množiny vektorů. Následující dvě věty převádí studium lineární nezávislosti libovolné nmožiny na studium lineární nezávislosti konečných množin vektorů. Nejdříve uvedeme následující větu:

Věta 4.106: Každá neprázdná podmnožina N lineárně nezávislé množiny M vektorů vektorového prostoru V je opět lineárně nezávislá. Důkaz se provede sporem – pokuste se dokázat za cvičení.

Nyní budeme formulovat větu, která má zásadní důležitost. Ukáže totiž, že lineární závislost či nezávislost je vlastností konečných podmnožin dané množiny:

Věta 4.107: Neprázdná množina M vektorů z vektorového prostoru V je lineárně nezávislá, právě když každá její neprázdná konečná podmnožina je lineárně nezávislá. Důkaz: Podmínka je nutná podle předchozí věty. K důkazu postačitelnosti předpokládejme, že M je lineárně závislá, a ukažme, že pak existuje neprázdná konečná podmnožina K ⊂ M , která je rovněž lineárně závislá. To, že M je lineárně závislá, znamená podle definice, že má vlastní podmnožinu se stejným lineárním obalem – tedy existuje N ⊂ M tak, že hM i = hN i. Je-li nyní u ∈ M \N libovolný vektor, pak protože M a N mají stejné lineární obaly, dá se u vyjádřit jako lineární kombinace vektorů z N , tedy existují vektory u1 , u2 , . . . , un ∈ N tak, že platí u = a1 u1 + a2 u2 + · · · + an un . Můžeme samozřejmě předpokládat, že vektory u1 , u2 , . . . , un jsou navzájem různé, a vzhledem k tomu, že u 6∈ N , je K = {u, u1 , u2 , . . . , un } Konečná podmnožina množiny M . Protože u − (a1 u1 + a2 u2 + · · · + an un ) = o, je množina K lineárně závislá.

Převedli jsme tedy studium lineární nezávislosti množin na studium lineární nezávislosti jejich konečných podmnožin. Připomeňme větu popisující studium lineární nezávislosti v konečném případě a ukažme, že je ekvivalentní s naší obecnou definicí: Věta 4.108: Konečná množina vektorů {u1 , u2 , ..., un } z vektorového prostoru V je lineárně nezávislá, právě když pouze triviální lineární kombinace těchto vektorů je rovna nulovému vektoru. Důkaz: Existuje-li netriviální lineární kombinace daných vektorů, která je rovna nulovému vektoru, dá se jeden z vektorů vyjádřit jako lineární kombinace ostatních, tudíž je zbytečný pro tvorbu lineárního obalu a množina je lineárně závislá.

77

V následující větě jsou shrnuta známá pravidla, která umožňují jednoduše rozpoznat lineární závislost a nezávislost konečných množin vektorů: Věta 4.109:

Buďte u1 , u2 , ..., un vektory vektorového prostoru V. Potom:

1. Jsou-li vektory u1 , u2 , ..., un lineárně nezávislé, jsou lineárně nezávislé i vektory ui1 , ui2 , . . . , uik , kde 1 ≤ i1 < i2 < · · · < ik ≤ n. 2. Je-li mezi vektory u1 , u2 , ..., un nulový vektor, jsou vektory u1 , u2 , ..., un lineárně závislé. 3. Jsou-li vektory u1 , u2 , ..., un lineárně závislé, je aspoň jeden z nich lineární kombinací ostatních. 4. Jsou-li vektory u1 , u2 , ..., un lineárně závislé, potom pro libovolné un+1 ∈ V jsou lineárně závislé i vektory u1 , u2 , ..., un , un+1 . Báze, dimenze, souřadnice Pomocí pojmů předcházející kapitoly zavedeme v obecném (ne aritmetickém) vektorovém prostoru důležité pojmy jako je báze, souřadnice vektoru vzhledem k bázi a dimenze prostoru (ta zde není nijak evidentní). Bázi obecného vektorového prostoru definujeme přirozeným způsobem: Definice 4.110: Podmnožina B vektorového prostoru V se nazývá báze vektorového prostoru V, jestliže množina B je lineárně nezávislá a hBi = V. Říkáme také, že báze je lineárně nezávislá generující množina vektorů. V příkladu 4.104 jsme viděli, že generující množina, tedy i báze, může mít nekonečně mnoho prvků. Na základě následující věty ovšem zjistíme, že k vyjádření libovolného vektoru jako lineární kombinace vždy stačí konečný počet vektorů báze: Věta 4.111: 1. Buď B = {u1 , u2 , . . . } báze vektorového prostoru V . Pak každý nenulový vektor x lze jednoznačně vyjádřit ve tvaru x = α1 u1 + α2 u2 + · · · + αn un , kde {u1 , u2 , . . . , un } ⊂ B a vektory ui jsou po dvou různé. 2. Nechť B 6= ∅ je podmnožina vektorového prostoru V. Množina B je bází prostoru V právě tehdy, když každý vektor x ∈ V se dá jednoznačně vyjádřit jako lineární kombinace prvků z B. Důkaz: Protože množina B generuje prostor V, lze každý vektor u ∈ V vyjádřit jako lineární kombinaci vektorů z množiny B podle věty 4.101 a tedy každý nenulový vektor z V má alespoň jedno vyjádření popsané ve větě. Důkaz jednoznačnosti vyjádření a druhé části věty provádět nebudeme.

78

Nyní si více povšimneme prostorů, které mají bázi tvořenou konečnou množinou vektorů: Definice 4.112: Řekneme, konečnou dimenzi, jestliže konečným počtem vektorů.

že ve

netriviální vektorový V existuje množina

prostor V má generátorů tvořená

Pro konečně dimenzionální prostory platí následující důležitá věta: Věta 4.113: vybrat bázi.

Z každé generující množiny vektorového prostoru konečné dimenze lze

Důkaz je triviální – vynecháme lineárně závislé vektory. Vzhledem k tomu, že podle předpokladu je generující množina konečná, dosáhneme toho po konečném počtu kroků.

Příklad 4.114: Generující množina vektorového prostoru čtvercových matic z příkladu 4.102 jistě není báze (je lineárně závislá). Viděli jsme, že libovolnou čtvercovou matici můžeme vyjádřit jako lineární kombinaci pouze čtyř prvků této generující množiny a uvedli jsme dvě takové možnosti. Bázi prostoru M22 tedy tvoří například množina {A, B, C, D}, kde         1 0 0 1 0 0 0 0 A= ,B= ,C= ,D= . 0 0 0 0 1 0 0 1

Věta 4.115: Steinitzova o výměně Nechť {u1 , u2 , . . . , un } tvoří množinu generátorů vektorového prostoru V, nechť {v1 , v2 , . . . , vk } je lineárně nezávislá množina vektorů z V. Potom k ≤ n a při vhodném označení je množina {v1 , v2 , . . . , vk , uk+1 , . . . , un } generující množinou pro V. Důkaz udává přímo postup, kterým přejdeme od jedné báze ke druhé: Vektor v1 ∈ V a proto jej lze vyjádřit jako lineární kombinaci vektorů generující množiny: v1 = α1 u1 + α2 u2 + · · · + αn un , kde aspoň jeden z koeficientů αi , i = 1, 2, . . . , n je nenulový, neboť v1 je vektor z lineárně nezávislé množiny a tedy nemůže být nulový. Bez omezení obecnosti můžeme předpokládat, že nenulový koeficient je u vektoru u1 ( v opačném případě provedeme přeznačení vektorů generující množiny). Z předchozí rovnice si vyjádříme a1 : u1 =

1 [v1 − α2 u2 − · · · − αn un ] . α1

Jestliže nyní ve vyjádření libovolného vektoru x jako lineární kombinace prvků generující množiny nahradíme vektor u1 předchozím vztahem, dostaneme vektor x vyjádřený jako lineární kombinaci vektorů {v1 , u2 , u3 , . . . , un }. Potom tyto vektory tvoří novou generující množinu. Vyjádříme si nyní v2 jako jejich lineární kombinaci: v2 = β1 v1 ) + β2 u2 + β3 u3 ) + · · · + βn un , kde aspoň jeden z koeficientů β2 , . . . , βn bude nenulový. Pokud by byly všechny nulové, pak by v2 bylo násobkem v1 a to nemůže nastat, protože v1 , v2 jsou prvky z lineárně nezávislé množiny. Bez újmy na obecnosti můžeme předpokládat, že nenulový koeficient je u u2 . Z poslední rovnice vyjádříme vektor u2 : u2 =

1 [v2 − β1 v1 − β3 u3 − · · · − βn un ] . β2

79

Jestliže nyní ve vyjádření libovolného vektoru jako lineární kombinace vektorů generující množiny {v1 , u2 , u3 , . . . , un } zaměníme u2 podle poslední rovnosti, dostaneme jeho vyjádření ve tvaru lineární kombinace vektorů {v1 , v2 , u3 , . . . , un }. Indukcí pokračujeme dále a po konečném počtu kroků zastavíme, neboť počet lineárně nezávislých vektorů musí být menší nebo roven počtu vektorů.

Ze Steinitzovy věty zřejmě plyne Důsledek: Každé dvě báze vektorového prostoru V konečné dimenze mají stejný počet prvků a každá lineárně nezávislá podmnožina V s tímto počtem prvků je bází.

Příklad 4.116: Najděte bázi aritmetického vektorového prostoru R4 , jejímiž prvky jsou vektory a = (1, 1, 0, 0), b = (1, 0, 1, 1). Najděte souřadnice obecného vektoru x = (x1 , x2 , x3 , x4 ) vzhledem k této bázi. Řešení: Je třeba prověřit, zda jsou vektory a, b lineárně nezávislé: αa + βb = o

⇔

α+ β = 0 α =0 β =0 β =0

⇒

α = 0, β = 0

– vektory a, b jsou lineárně nezávislé. ¯ = {a, b, e3 , e4 } a potřebujeme v této Podle Steinitzovy věty bude nová báze např. B bázi vyjádřit vektory e1 , e2 : a = e1 + e 2 b = e1 + e 3 + e 4

⇒

e2 = a − b + e 3 + e 4 e1 = b − e3 − e4

Odtud x = (x1 , x2 , x3 , x4 ) = x1 e1 +x2 e2 +x3 e3 +x4 e4 = x2 a+(x1 −x2 )b+(−x1 +x2 +x3 )e3 +(−x1 +x2 +x4 )e4 , tedy xB¯ = (x2 , x1 − x2 , −x1 + x2 + x3 , −x1 + x2 + x4 ). Příklad 4.117: Mějme prostor M22 čtvercových matic řádu 2. Dokažte, že jeho bázi tvoří vektory         1 0 1 1 1 1 1 1 A= ,B = ,C = ,D = . 0 0 0 0 1 0 1 1 Řešení: Zřejmě stačí ukázat, že každý vektor z M22 se dá jednoznačně vyjádřit jako lineární kombinace vektorů A, B, C, D. Mějme libovolný vektor   a b X= c d

80

a hledejme koeficienty α, β, γ, δ tak, aby platilo αA + βB + γC + δD = X neboli  α

1 0 0 0



 +β

1 1 0 0



 +γ

1 1 1 0



 +δ

1 1 1 1



 =

a b c d

 .

Po dosazení dostaneme soustavu α+β+γ+δ β+γ+δ γ+δ δ

= = = =

a b c d

Jde o nehomogenní soustavu s regulární maticí koeficientů (je to trojúhelníková matice), která je jednoznačně řešitelná pro libovolný tvar pravé strany a platí α = a − b, β = b − c, γ = c − d a δ = d. To znamená, že libovolný vektor X se dá jednoznačně vyjádřit jako lineární kombinace prvků A, B, C, D a tedy tyto prvky tvoří bázi vyšetřovaného prostoru. Definice 4.118: 1. Nechť V = 6 {o} je vektorový prostor konečné dimenze. Dimenzí prostoru V nazveme počet prvků jeho báze. Píšeme dim V = n. Triviální vektorový prostor O = {o} má dimenzi 0. Vektorový prostor dimenze n budeme značit Vn . 2. Nechť je množina B = {u1 , u2 , . . . , un } bází vektorového prostoru Vn a pro libovolné x ∈ Vn platí x = α1 u1 + α2 u2 + · · · + αn un , kde koeficienty αi jsou určeny jednoznačně. Čísla α1 , α2 , . . . , αn nazveme souřadnicemi vektoru x vzhledem k bázi B.  Příklad 4.119:

Máme určit souřadnice čtvercové matice řádu 2 M =

dem k bázím z příkladů 4.114 a 4.117. Řešení: 1. Zde je B1 = {A, B, C, D}, kde         1 0 0 1 0 0 0 0 A= ,B= ,C= ,D= 0 0 0 0 1 0 0 1 a tedy M = 2A + B − C + 3D. Proto MB1 = (2, 1, −1, 3). 81

2 1 −1 3

 vzhle-

2. Zde je B2 = {A, B, C, D}, kde         1 0 1 1 1 1 1 1 A= ,B = ,C = ,D = 0 0 0 0 1 0 1 1 a podle výsledku v příkladu 4.117 je M = A + 2B − 4C + 3D. Proto MB2 = (1, 2, −4, 3). Následující věta charakterizuje dimenzi podprostoru: Věta 4.120: Každý podprostor W vektorového prostoru V dimenze n má také konečnou dimenzi m ≤ n. Předchozí věta má zřejmý důsledek: Důsledek: Nechť W je podprostor prostoru Vn . Jestliže dim W = n, potom W = V. Příklad 4.121: V aritmetickém vektorovém prostoru R3 určete v závislosti na parametru α dimenzi lineárního obalu vektorů a = (α, −4, −1), b = (4, −6, −3), c = (1, 1, −α). Řešení: Vyšetříme lineární závislost ev. nezávislost vektorů a, b, c: Sestavíme matici, jejímiž řádky budou zadané vektory a pomocí elementárních úprav tuto matici převedeme na Gaussův tvar:       α −4 −1 1 1 −α 1 1 −α  4 −6 −3  ∼  4 −6 −3  ∼  0 −10 4α − 3  ∼ 1 1 −α α −4 −1 0 −4 − α α2 − 1   1 1 −α 4α − 3  . ∼  0 −10 2 0 0 −6α + 13α − 2 Rovnice −6α2 + 13α − 2 = 0 má kořeny α1 = 2, α2 = 16 . • Jestliže α = 2 resp. α = 16 , je hodnost soustavy vektorů {a, b, c} rovna dvěma a proto dim ha, b, ci = 2; • jestliže α 6= 2 a zároveň α 6= 16 , je hodnost soustavy vektorů {a, b, c} rovna třem a dim ha, b, ci = 3.

4.6

Lineární zobrazení

Transformace souřadnic V této kapitole si blíže všimneme přechodu mezi bázemi ve vektorovém prostoru konečné dimenze – uvidíme, že se dá popsat jistou maticí:

82

Nechť Vn je vektorový prostor dimenze n. Nechť A = (a1 , a2 , . . . , an ) a B = (b1 , b2 , . . . , bn ) jsou dvě báze tohoto prostoru. Každý vektor x ∈ V se dá vyjádřit jednak jako lineární kombinace prvků báze A: x = α1 a1 + α2 a2 + · · · + αn an jednak jako lineární kombinace prvků báze B: x = β1 b1 + β2 b2 + · · · + βn bn Stejně můžeme i prvky báze A vyjádřit jako lineární kombinace prvků báze B: a1 = a11 b1 + a21 b2 + · · · + an1 bn , a2 = a12 b1 + a22 b2 + · · · + an2 bn , ... ... an = a1n b1 + a2n b2 + · · · + αnn bn . Po dosazení dostaneme: x = α1 (a11 b1 + a21 b2 + · · · + an1 bn )+ +α2 (a12 b1 + a22 b2 + · · · + an2 bn )+ ... +αn (a1n b1 + a2n b2 + · · · + αnn bn ) a zapíšeme-li předchozí    β1 a11  β2   a21     ..  =  ..  .   . βn an1

vztah maticově, dostaneme    a12 · · · a1n α1   a22 · · · a2n    α2  .. ..  ·  ..  . ... . .   .  an2 · · · ann αn

Matici (aij )nn = MB A nazveme maticí přechodu od báze A k bázi B. Povšimněme si, že je to matice, jejíž sloupce tvoří souřadnice vektorů „staréÿ báze vzhledem k „novéÿ bázi. Tím jsme odvodili následující větu: Věta 4.122: (O transformaci souřadnic) Nechť A = {a1 , a2 , . . . , an }, B = {b1 , b2 , . . . , bn } jsou dvě báze vektorového prostoru Vn a pro vektor x ∈ Vn platí: xA = (α1 , α2 , . . . , αn ), xB = (β1 , β2 , . . . , βn ). Nechť MB A je maticí přechodu od báze A k bázi B. Potom     β1 α1  β2   α2     B  = M ·  ..  ..  . A   .   .  βn αn 83

Z předchozí kapitoly víme, že každý vektor lze jediným způsobem vyjádřit jako lineární kombinaci vektorů báze; z maticové rovnice v předchozí větě lze tedy jednoznačně vyjádřit vektor (α1 , α2 , . . . , αn ); přitom platí     α1 β1  α2   β2      ·  ..  = MA . , B   .   ..  αn βn −1 kde (MA = MB B) A.

Odtud plyne Věta 4.123:

Matice přechodu je vždy regulární.

Příklad 4.124: V trojrozměrném aritmetickém prostoru R3 jsou dány dvě báze B = {(1, 0, 0, ), (1, 1, 0), (1, 1, 1)}, a C = {(−1, 1, 0), (1, 1, 0), (0, 0, 1)}. Máme najít matici přechodu od báze B k bázi C a naopak. Je-li xB = (−1, 3, 0), yC = (2, 4, 7), máme určit xC , yB . Řešení: Označme B = {a, b, c} , C = {k, l, m}. Prvky báze C vyjádříme jako lineární kombinace prvků báze B: α1 a + β1 b + γ1 c = k, α2 a + β2 b + γ2 c = l, α3 a + β3 b + γ3 c = m, což jsou tři soustavy rovnic každá pro tři neznámé koeficienty αi , βi , γi , i = 1, 2, 3 se stejnou maticí koeficientů a různými pravými stranami; první soustava:         1 1 1 −1 α1 + β1 + γ1 = −1         1 β1 + γ1 = 1 α1 0 + β1 1 + γ1 1 = ∼ 0 0 1 0 γ1 = 0 druhá soustava:         1 1 1 1        α2 0 + β2 1 + γ2 1 = 1  ∼ 0 0 1 0

α2 + β2 + γ2 = 1 β2 + γ2 = 1 γ2 = 0

třetí soustava:         1 1 1 0        α3 0 + β3 1 + γ3 1 = 0  ∼ 0 0 1 1

α3 + β3 + γ3 = 0 β3 + γ3 = 0 γ3 = 1

84

Budeme je všechny tři řešit najednou v jedné matici; nalevo bude matice soustavy, napravo vektory pravých stran a matici převedeme pomocí elementárních úprav na Gaussův tvar:       1 1 1 −1 1 0 1 1 0 −1 1 −1 1 0 0 −2 0 0  0 1 1 1 1 0 ∼ 0 1 0 1 1 −1  ∼  0 1 0 1 1 −1  . 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 V pravé části jsme dostali jednotlivé koeficienty αi , βi , γi , i = 1, 2, 3 a matice přechodu od báze C k bázi B má tvar   −2 0 0  1 1 −1  . MB C = 0 0 1 Matice přechodu od báze B k bázi C bude pak matice inverzní  1  0 0 2 B −1 MC =  12 1 1  . B = (MC ) 0 0 1 1 5 B Vynásobením nyní dostaneme xC = MC B · xB = ( 2 , 2 , 0), yB = MC · yC = (−4, −1, 7).

Viděli jsme, že každá transformace souřadnic vektorového prostoru – přechod od jedné báze ke druhé – je popsána maticí přechodu. Na závěr tohoto odstavce uvedeme ještě bez důkazu větu, která formuluje inverzní postup: Věta 4.125: Nechť A = (a1 , a2 , . . . , an ) je báze vektorového prostoru V, M je regulární matice řádu n. Potom M · [a1 , a2 , . . . , an ] je také báze vektorového prostoru V a všechny báze prostoru V můžeme získat tímto způsobem. Lineární zobrazení V předchozí kapitole jsme se pohybovali stále uvitř jednoho vektorového prostoru – vyšetřovali jsme vlastně zobrazení vektorového prostoru na sebe. Je možné tuto situaci zobecnit – vyšetřovat zobrazení mezi různými vektorovými prostory. Pochopitelně nás zajímají taková zobrazení, která zachovávají příslušné lineární operace, tj. součet a násobení číslem. Obecně v algebře se taková zobrazení nazývají homomorfismy, my budeme preferovat pojem lineární zobrazení. Kapitola je ukázkou obecných teoretických úvah v lineární algebře. Věty zde převážně nedokazujeme; pro naše další úvahy je důležitý samotný pojem lineárního zobrazení, jeho základní vlastosti a to, že je charakterizováno jistou maticí.

Definice 4.126: Nechť V, W jsou vektorové prostory. Zobrazení F : V → W nazveme lineárním zobrazením vektorových prostorů V, W, platí-li ∀u, v ∈ V, α, β ∈ R F(αu + βv) = αF(u) + βF(v). 85

Protože lineární zobrazení zachovává příslušné operace ve vektorových prostorech, je to příklad homomorfismu. Nechť je zobrazení F : R4 → R3 definováno předpisem  x1 − 2x2 + x4 . x1 + x3 F(x) =  x1 + 2x2 + 2x3 − x4       x1 x1 − 2x2 + x4 y1  x2  4   =  y 2  = y ∈ R3 . x1 + x3 Tedy x =  F(x) =   x3  ∈ R , x1 + 2x2 + 2x3 − x4 y3 x4

Příklad 4.127: 

Například pro x = (2, 3, 6, −1) je F(x) = (−5, 8, 21). Definiční vztah daného zobrazení můžeme přepsat do tvaru          x1 − 2x2 + x4 y1 1 −2 0 1 x1 y1   =  y2  ⇔  1 x1 + x3 0 1 0   x2  =  y2  . x1 + 2x2 + 2x3 − x4 y3 1 2 2 −1 x3 y3 Ověřme, zda se jedná o lineární zobrazení:   αu1 + βv1 − 2(αu2 + βv2 ) + αu4 + βv4 = αu1 + βv1 + αu3 + βv3 F(αu + βv) =  αu1 + βv1 + 2(αu2 + βv2 ) + 2(αu3 + βv3 ) − (αu4 + βv4 )     u1 − 2u2 + u4 v1 − 2v2 + v4 +β  = α F(u) + β F(v) u 1 + u3 v1 + v3 = α u1 + 2u2 + 2u3 − u4 v1 + 2v2 + 2v3 − v4 – zobrazení je lineární. V předchozím příkladu jsme viděli, že se dané lineární zobrazení, podobně jako transformace souřadnic v předchozí kapitole, realizovalo pomocí násobení jistou číselnou maticí; tedy platilo F(x) = A · x. Ukážeme, že tato vlastnost je pro lineární zobrazení charakteristická: Mějme lineární zobrazení vektorových prostorů F : U → V, přičemž U = (u1 , . . . , un ) je báze prostoru U, V = (v1 , . . . , vm ) je báze prostoru V (prostory mohou mít různou dimenzi!). Hledejme souřadnice vektoru F(x) (vzhledem k bázi V ), známe-li souřadnice vektoru x (vzhledem k bázi U ): X X x= αj uj ⇒ F(x) = αj F(u)j . j

j

86

Pro obrazy bázových vektorů platí (jejich vyjádření v bázi prostoru V): βi

F(uj ) =

X

aij vi ⇒ F(x) =

X

i

αj

X

j

X zX}| { aij vi = ( aij αj ) vi .

i

i

j

P

Tedy βi = j aij αj , i = 1, 2, . . . , m a odtud       β1 a11 · · · a1n α1  ..   .. ..  ·  ..   . = . .   .  am1 · · · amn

βm

αn

Tedy jsou-li (α1 , . . . , αn ) souřadnice vektoru x, jsou (β1 , . . . , βm ) souřadnice jeho obrazu a matice   a11 · · · a1n  ..  A =  ... .  am1 · · · amn je matice lineárního zobrazení F. Poznámky: • Matice lineárního zobrazení je při daných bázích určena jednoznačně. • Volíme-li speciálně U = V, F prosté vzájemně jednoznačné zobrazení, jedná se o transformaci souřadnic ve V a matice zobrazení F je maticí přechodu mezi bázemi, jak bylo popsáno v minulé kapitole. Protože jak V, tak W jsou vektorové prostory, musí oba obsahovat nulový vektor – pro rozlišení je budeme označovat oV a oW . Zavedeme následující pojmy: Definice 4.128: Im F = F(V) = {w ∈ W | ∃v, F(v) = w} se nazývá obraz, Ker F = F−1 ({oW }) = {v ∈ V | F(v) = oW } se nazývá jádro zobrazení F. O takto definovaných pojmech platí: Věta 4.129:

Je-li F : V → W lineární zobrazení, potom

1. Ker F je podprostor prostoru V, 2. Im F je podprostor prostoru W. 87

Příklad 4.130:

Najděme obraz a jádro zobrazení F z úvodního příkladu:

1. Obraz je množina všech vektorů c ∈ W, pro které má rovnice F(x) = c alespoň jedno řešení x ∈ V. V daném případě je     x1 − 2x2 + x4 c1 x1 −2x2 + x4 = c1     x1 + x3 x1 + x3 = c2 = c2 neboli x1 + 2x2 + 2x3 − x4 = c3 x1 + 2x2 + 2x3 − x4 c3 Maticově:  1 −2 0 1  1 0 1 0 1 2 2 −1

   c1 1 −2 0 1 c1 c2  ∼  0  2 1 −1 c2 − c1 c3 0 0 0 0 c3 − 2c2 + c1

Vidíme, že soustava bude mít řešení jedině v případě c1 − 2c2 + c3 = 0, tedy pro takové vektory c, které leží v rovině c1 − 2c2 + c3 = 0 (procházející počátkem). Tato rovina je dvojrozměrný podprostor prostoru R3 a je to Im F. 2. Jádro zobrazení je množina vektorů z V, které se zobrazí na nulový vektor ve V; tedy v našem příkladě takových, pro které platí     x1 − 2x2 + x4 0 x1 −2x2 + x4 = 0     x1 + x3 x1 + x3 =0 = 0 neboli x1 + 2x2 + 2x3 − x4 0 x1 + 2x2 + 2x3 − x4 = 0 Maticově (soustava je homogennní):     1 −2 0 1 1 −2 0 1  1 0 1 0 ∼ 0 2 1 −1  1 2 2 −1 0 0 0 0

⇒

x1 = 2x2 −x4 x3 =−2x2 +x4

(x2 , x4 ) = (1, 0) ⇒ x1 = 2, x3 = −2 (x2 , x4 ) = (0, 1) ⇒ x1 = −1, x3 = 1 Tedy vektory tvaru x = α(2, 1, −2, 0) + β(−1, 0, 1, 1) jsou řešením naší soustavy a tvoří jádro zobrazení F. Odtud plyne, že Ker F = h(2, 1, −2, 0), (−1, 0, 1, 1)i a to je podprostor prostoru R4 dimenze 2. Nepříliš obtížně se dá dokázat věta, charakterizující prostá zobrazení; ta ovšem platí i v případě homomorfismů jiných algebraických struktur s nulovým prvkem: Věta 4.131: Kerf = {o}.

Lineární zobrazení f : V → W je injektivní (prosté), právě když

Pro dimenze konečnědimenzionálních prostorů při lineárních zobrazeních se dá dokázat následující věta:

88

Věta 4.132: Nechť V má konečnou dimenzi a f : V → W je lineární zobrazení. Potom dim V = dim Ker f + dim Im f. Zavedeme-li následující označení: Je-li A ⊂ V, v ∈ V, potom v + A := {v + x | x ∈ A}, můžeme lineární zobrazení blíže charakterizovat takto: Věta 4.133: Nechť F : V → W je lineární zobrazení, w ∈ Imf . Potom F−1 ({w}) = v + Ker F, kde v je libovolný vektor, pro který F(v) = w. Pomocí předchozích pojmů můžeme vyšetřovat řešitelnost soustav lineárních rovnic: Uvažujme soustavu m lineárních rovnic o n neznámých, která má maticový tvar A · x = b; tedy matice A je typu (m, n), vektor neznámých x ∈ Rn , vektor pravých stran b ∈ Rm . Maticový tvar soustavy tedy představuje zobrazení ˆ : Rn → Rm : x 7→ A · x, A které je, jak se snadno přesvědčíme, lineární. Přitom ˆ • soustava A · x = b je řešitelná ⇔ b ∈ Im(A), ˆ 1 ), ..., A(e ˆ n )i = Im(A). ˆ Ale • jsou-li e1 , ..., en ∈ Rn jednotkové vektory, potom hA(e ˆ j ) = A · ej je j-tý sloupec matice A. Proto Im(A) ˆ je prostor generovaný sloupci A(e ˆ matice A. Speciálně platí dim Im(A) = h(A). Odtud jako důsledek dostáváme tvrzení Frobeniovy věty (soustava A · x = b je řešitelná právě když h(A) = h(A|B)): ˆ ⇔ b je lineární kombinací sloupců A ⇔ h(A) = Soustava je řešitelná ⇔ b ∈ Im(A) h(A|B). Uvažujme nyní příslušnou homogenní soustavu A · x = o. Množina řešení této soustavy ˆ Pro dimenzi tohoto podprostoru ale platí je Ker (A). ˜ = n − dim Im(A) ˜ = n − h(A). dim Ker(A) Odtud speciálně vyplývá, že homogenní soustava má pouze nulové řešení právě když h(A) = n. Jestliže je nyní x∗ jedno řešení nehomogenní soustavy, je množina řešení nehomogenní ˆ indukovaném maticí soustavy A, tvaru soustavy, tedy obraz prostoru Rn při zobrazení A ∗ ˆ x + Ker (A) a obecné řešení nehomogenní soustavy má tvar x = x∗ + α1 b1 + · · · + αr br kde r = n − h(A). Je vidět, že nehomogenní soustava má pouze jedno řešení právě když h(A) = h(A|b) = n. 89

Příklad 4.134: x + 2y + y + x +  1 2 3 A= 0 1 1 1 0 1

3z = 3 z = 1 z = 1      1 2 3 1 2 3 ∼ 0 1 1 ∼ 0 1 1  0 −2 −2 0 0 0

˜ = 3 − 2 = 1. Příslušná homogení soustava je upravena na tvar Tedy h(A) = 2, dim KerA x + 2y + 3z = 0 , y + z = 0 položíme z = α a dostáváme x = y = −α, tedy obecné řešení homogenní soustavy má tvar     x −1  y  = α  −1  . z 1 Jedno řešení zadané nehomogenní soustavy je zřejmě x∗ = (1, 1, 0), tedy obecné řešení nehomogenní soustavy dostáváme ve tvaru     1 −1 x =  1  + α  −1  . 0 1 V následující větě shrneme tvrzení, která platí pro lineární zobrazení v souvislosti s lineární nezávislostí resp. závislostí. Důkaz ponecháme jako cvičení. Věta 4.135: 1. Je-li F : V → W lineární zobrazení, hAi = V ⇒ hF(A)i = W, neboli homomorfním obrazem generující množiny je generující množina. 2. Je-li F : V → W lineární zobrazení a vektory v1 , ..., vn jsou lineárně závislé (v V), potom F(v1 ), ..., F(vn ) jsou lineárně závislé (v W). 3. Je-li F : V → W injektivní lineární zobrazení a vektory v1 , ..., vn jsou lineárně nezávislé (v V), potom F(v1 ), ..., F(vn ) jsou lineárně nezávislé (v W). Na závěr uvedeme tvrzení týkající se kompozice lineárních zobrazení: Věta 4.136: Jsou-li F : U → V, G : V → W lineární zobrazení, potom jejich složení G ◦ F : U → W je také lineární zobrazení.

90

Věta 4.137: 1. Matice složeného zobrazení: Nechť jsou F P : U → V, G : V → W lineární zobrazení, A je matice F, B matice G. P Nechť je x = αi ui , α = P (α1 , ..., αn ), F(x) = βj vj , β = (β1 , ..., βm ), G(F(x)) = (G ◦ F)(x) = γk wk , γ = (γ1 , ..., γr ). Tedy β = A · α, γ = B · β. Odtud γ = B · (A · α) = (B · A) · α, tedy B · A je matice složeného lineárního zobrazení G ◦ F : U → W. 2. Matice zobrazení při změně bází: Nechť {ui }, {u0 i } jsou dvě báze prostoru U s maticí přechodu P1 , {vj }, {v0 j } jsou dvě báze prostoru V s maticí přechodu P2 , F : U → V lineární zobrazení (homomorfismus). Je-li A matice homomorfismu F v nečárkovaných bázích a A’ matice homomorfismu F v čárkovaných bázích, potom A0 = P2 · A · P−1 1 .

4.7

Unitární a Eukleidovské prostory

Skalární součin, norma Pro aritmetické vektory jsme definovali skalární součin jednoduchým způsobem pomocí souřadnic; v tomto odstavci pojem skalárního součinu zavedeme i pro obecné vektorové prostory tak, aby splňoval základní vlastnosti skalárního součinu v aritmetických prostorech: Definice 4.138:

Nechť V je vektorový prostor. Zobrazení

g : V × V → R : (x, y) 7→ g(x, y) se nazývá skalárním součinem na V, jestliže ∀α ∈ R a ∀x, y, z ∈ V platí: 1. g(x, y) = g(y, x),

komutativita

2. g(x + y, z) = g(x, z) + g(y, z),

distributivita

3. g(αx, y) = αg(x, y),

vytýkání skalárního násobku

4. g(x, x) ≥ 0, přičemž g(x, x) = 0 pouze pro x = o. Místo g(x, y) budeme psát x • y. Vektorový prostor se skalárním součinem se nazývá unitární prostor. Vektorový prostor konečné dimenze ve kterém je pevně zvolen skalární součin se nazývá eukleidovský prostor Příklad 4.139: V aritmetickém vektorovém prostoru Rn jsme definovali skalární součin vektorů x, y ∈ Rn , x = (x1 , ..., xn ), y = (x1 , ..., xn ) předpisem x · y = x1 y1 + x2 y2 + · · · + xn yn ; Snadno se přesvědčíme, že tento skalární součin vyhovuje podmínkám naší definice. Tento eukleidovský prostor se obvykle označuje symbolem En . Bezprostředně z definice vyplývá Důsledek: Platí: 91

1. o • x = 0 ∀x ∈ V. P P PP 2. ( αi xi ) • ( βj yj ) = αi βj (xi • yj ). i

j

i

j

Důkaz: 1. Platí o = 0y, y ∈ V. Odtud o • x = 0y • x = 0 · (x • y) = 0. 2. Plyne z podmínek 2. a 3. definice skalárního součinu – dokažte za cvičení.

Dá se ukázat, že platí Věta 4.140: V libovolném vektorovém prostoru konečné dimenze je možné definovat skalární součin. Důkaz provádět nebudeme.

Pomocí takto definovaného skalárního součinu můžeme zobecnit na obecné vektorové prostory pojem ortogonality (kolmosti) zavedený v atitmetickém vektorovém prostoru: Definice 4.141: 1. Platí-li pro x, y ∈ V: x • y = 0, řekneme, že x a y jsou ortogonální. 2. Systém vektorů x1 , x2 , ..., xk ∈ V se nazývá ortogonální systém vektorů, jsou-li tyto vektory po dvou ortogonální. Dále zavedeme zobecněnou „velikostÿ vektoru – normu a úhel vektorů: Definice 4.142: 1. Normou (velikostí) vektoru x ∈ V nazveme číslo √ kxk = x • x. 2. Číslo ϕ ∈ h0, πi vyhovující vztahu cos ϕ =

x•y kxkkyk

nazveme úhlem vektorů x, y.

92

√ √ Příklad 4.143: Vektory a = (1, 3), b = ( 3, 0) ∈ E2 zřejmě svírají úhel π3 – což zjistíme snadno zakreslením do souřadného systému. Výpočtem skutečně dostaneme √ √ 1 1· 3+ 3·0 √ = ; cos ϕ = √ 2 1+3· 3 √ ale také vektory a = (1, −1, 0, 1), b = ( 3, 0, −1, 0) ∈ E4 svírají stejný úhel: √ 1 1· 3 = . cos ϕ = √ √ 2 3· 3+1

Pro výše definované pojmy platí: Věta 4.144:

∀x, y ∈ V platí |x • y| ≤ kxk · kyk

1. Schwarzova nerovnost 2. trojúhelníková nerovnost přičemž rovnost platí právě když

kx + yk ≤ kxk + kyk |x • y| = kxk · kyk

3. Pythagorova rovnost jsou-li x,y ortogonální.

kx + yk2 = kxk2 + kyk2

Důkaz: 1. Pro α ∈ R podle vlastnosti 4. z definice skalárního součinu platí (x + αy)(x + αy) ≥ 0

pro

x, y ∈ V

lib.

Odtud x • x + 2αx • y + α2 y • y = kxk2 + 2αx • y + α2 kyk2 ≥ 0. To je kvadratická nerovnost vzhledem k α (v R) a ta je splněna v případě, kdy diskriminant kvadratického trojčlenu není kladný (příslušná rovnice může mít nanejvýš jeden kořen). Tedy 4(x • y)2 − 4kxk2 kyk2 ≤ 0

⇒

kxk2 kyk2 ≥ (x • y)2

⇒

|x • y| ≤ kxk kyk.

2. kx + yk2 = (x + y) • (x + y) = x • x + x • y + y • x + y • y = kxk2 + 2x • y + kyk2 ≤ ≤ kxk2 + 2|x • y| + kyk2 ≤ kxk2 + 2kxk kyk + kyk2 = (kxk + kyk)2 . 3. Vztah plyne z prvního řádku důkazu (2.), protože x • y = 0.

Pojem ortogonality a ortonormality systému budeme potřebovat především pro báze vektorových prostorů:

93

Definice 4.145: 1. Báze vektorového prostoru se nazývá ortogonální báze, jestliže je tvořena systémem ortogonálních vektorů. 2. Báze vektorového prostoru se nazývá ortonormální báze, jestliže pro její prvky platí  1, i = j xi • xj = δij = . 0, i 6= j Věta 4.146: Gramova—Schmidtova: V každém netriviálním eukleidovském vektorovém prostoru lze sestrojit ortonormální bázi. Důkaz: Větu dokážeme matematickou indukcí: Mějme bázi eukleidovského vektorového prostoru V: A = (a1 , a2 , . . . , an ). Nejdříve vytvoříme ortogonální bázi B = (b1 , b2 , . . . , bn ) a pak ji normalizujeme. Každý prvek nové báze B bude roven stejnolehlému prvku staré báze A a lineární kombinaci již vytvořených prvků nové báze B: b1 = a1 b2 = a2 + αb1 kde α1 je zatím neznámý koeficient. Vynásobíme skalárně tuto rovnost vektorem b1 a protože vektory b1 , b2 mají být ortogonální, musí platit 0 = (a2 • b1 ) + α(b1 • b1 ), neboli α=−

a2 • b1 . b1 • b1

Určili jsme koeficient α a tím také vektor b2 . Vektor b2 musí být nenulový, jinak by platilo, že a2 = −α1 b1 = −α1 a1 a to by byl spor s tvrzením, že a1 , a2 jsou prvky báze, t.j. jsou lineárně nezávislé. Pokračujeme analogicky dále: b3 = a3 + β1 b1 + β2 b2 tedy βi = −

a3 • bi , i = 1, 2. bi • bi

b3 opět musí být nenulový. atd. Dostaneme tedy obecný vztah

bk = ak +

k−1 X

γj bj , k = 1, 2, . . . , n,

j=1

kde

γj = −

ak • bj . bj • bj

Nakonec provedeme normalizaci ci =

bi kbi k

a dostali jsme ortonormální bázi C = (c1 , c2 , . . . , cn ).

Stejným způsobem můžeme postupovat v případě, že hledáme ortonormální bázi podprostoru, který je zadán množinou generátorů. Jestliže jsou vektory generující množiny lineárně závislé, vyjde během konstrukce některý z vektorů bi jako nulový; pak ovšem nemůže být prvkem báze, proto jej vyloučíme a pokračujeme dále. 94

Příklad 4.147:

Určete ortogonální bázi podprostoru generovaného vektory

a = (1, 1, −1, −1), b = (1, −1, 1, 1), c = (−1, −2, 0, 1), d = (1, −2, 0, 1). Řešení: Hledané ortogonální vektory si označíme k, l, m, n. Potom k = a, 1 ⇒ α = , ⇒ l = (3, −1, 1, 1). 2 m = c + βk + γl, ⇒ β = 1, γ = 0, ⇒ m = (0, −1, −1, 0). 1 1 n = d + δk + ηl + ζm, ⇒ δ = , η = − , ζ = −1, ⇒ n = (0, 0, 0, 0). 2 2 Ortogonální bázi proto tvoří vektory k, l, m a podprostor má dimenzi 3. l = b + αk,

Uvažujme nyní dvě ortonormální báze vektorového prostoru Vn . Matici přechodu příslušné transformace souřadnic chatakterizuje věta: Věta 4.148: Matice přechodu od ortonormální báze k jiné ortonormální bázi je ortonormální matice. Důkaz: Nechť A = (aij ) je matice přechodu od ortonormální báze (e1 , ..., en ) k ortonormální bázi (e0 1 , ..., e0 n ). Potom pro vyjádření vektorů nečárkované báze pomocí vektorů čárkované báze platí e1

=

a11 e0 1 + a21 e0 2 + · · · + an1 e0 n ,

e2

=

a12 e0 1 + a22 e0 2 + · · · + an2 e0 n ,

... en

... =

a1n e0 1 + a2n e0 2 + · · · + ann e0 n

(souřadnice bázových vektorů tvoří sloupce matice přechodu); vzhledem k ortonormalitě báze zřejmě platí A · AT = E a tedy AT = A−1 .

Transformace souřadnic z předchozí věty mají speciální název: Definice 4.149: Transformace souřadnic s ortogonální maticí přechodu se nazývá ortogonální zobrazení. Poznámka: Povšimněme si ještě jednou soustavy transformačních rovnic z důkazu předcházející věty. Vynásobme skalárně všechny rovnice postupně všemi vektory čárkované báze; dostaneme e1 • e0 1 e2 • e0 1 ... en • e0 1 ... ei • e0 j ... en • e0 n

= a11 , = a12 , ... = a1n , ... = aij , ... = ann

95

tedy A = (aij ) = (ei • e0 j ).

Příklad 4.150:   Najdeme všechny ortogonální matice druhého řádu. a b Je-li A = ortogonální matice, platí c d a2 + b2 = 1, c2 + d2 = 1, ac + bd = 0. Tedy ∃ϕ, ψ tak, že a = cos ϕ, b = sin ϕ, c = cos ψ, d = sin ψ. Dosadíme do třetí rovnice a dostaneme  π  ϕ + π2 2 ψ−ϕ= ⇒ ψ= 3 π ϕ + 32 π 2     cos ϕ sin ϕ cos ϕ sin ϕ Tedy buď A = nebo A = pro ϕ libovolné. − sin ϕ cos ϕ sin ϕ − cos ϕ Uvažujme ortogonální zobrazení v rovině, tedy transformaci souřadnic, kde jak stará, tak nová soustava tvoří ortonormální systém. Jeho matice přechodu musí mít jeden z předchozích tvarů, ale protože prvky matice přechodu jsou skalární součiny příslušých starých a nových bázových vektorů, jsou všechna ortogonální zobrazení v rovině buď otočení o úhel ϕ, nebo otočení a překlopení. Ortogonální průmět Definice 4.151: 1. Řekneme, že vektor u ∈ V je ortogonální k podprostoru W v V, jestliže ∀x ∈ W : u • x = 0; tedy jestliže je vektor u ortogonální s každým vektorem podprostoru W. 2. Ortogonální průmět (projekce) vektoru v do podprostoru W je vektor w ∈ W, pro který platí v = w + u, kde u je ortogonální k podprostoru W. Věta 4.152: Existuje právě jedna ortogonální projekce vektoru v ∈ V do podprostoru W vektorového prostoru V. Důkaz: Nechť W = he1 , e2 , ..., en i. Budeme hledat w0 , které je ortogonální projekcí vektoru v ∈ V do W: Pro každý vektor báze podprostoru W platí (v − ek ) ⊥ ek ⇔ (v − ek ) • ek = 0 ⇔ v • ek = w0 • ek .

96

Obr. 1: Ortogonální průmět Je-li w0 tvaru w0 = c1 e1 + c2 e2 + · · · + cn en , c1 , ...cn ∈ R, dostáváme pro souřadnice vektoru w0 soustavu n rovnic c1 (e1 • e1 ) + c2 (e2 • e1 ) + · · · + cn (en • e1 )

=

v • e1

c1 (e1 • e2 ) + c2 (e2 • e2 ) + · · · + cn (en • e2 )

=

v • e2

=

.. .

.. .

c1 (e1 • en ) + c2 (e2 • en ) + · · · + cn (en • en ) = v • en Determinant této soustavy je různý od nuly, protože vektory e1 , e2 , ..., en tvoří lineárně nezávislý systém, tedy má soustava právě jedno řešení.

Je-li báze podprostoru W ortogonální, soustava se zjednoduší na tvar ck (ek • ek ) = v • ek ∀k = 1...n ⇒ ck =

v • ek ∀k = 1...n. e k • ek

Předchozí věta má zásadní důležitost – zaručuje nám, že vždy můžeme najít ”nejlepší aproximaci” nějakého vektoru pomocí prvků vybraného podprostoru. Využití této věty je široké zejména v numerické matematice; dá se tak najít tzv. regresní přímka, bezprostředně se užívá při ”metodě nejmenších čtverců” a také při aproximaci funkcí pomocí vybrané třídy funkcí (např. pomocí Fourierových polynomů). Myšlenku ”nejlepší aproximace” popisuje následující věta: Věta 4.153:

Nechť w je ortogonální projekce vektoru v do W, w0 ∈ W. Potom

kv − wk ≤ kv − w0 k

Důkaz: v − w0 = v − w + w − w0 . Protože je v − w ⊥ w − w0 , platí podle Pythagorovy věty kv − w0 k2 = kv − wk2 + kw − w0 k2 . Odtud plyne tvrzení věty.

97

Definice 4.154: Ortogonální projekci w ∈ W vektoru v na podprostor W v V nazýváme nejlepší aproximací vektoru v pomocí prvků podprostoru W. Číslo kv − wk nazýváme chybou aproximace. Příklad 4.155: V aritmetickém vektorovém prostoru R3 určete ortogonální průmět vektoru v = (1, 2, 3) do podprostoru W = ha, bi, kde a = (−1, 1, 1), b = (1, 1, , 1). Řešení: Vektory a, b jsou lineárně nezávislé, tvoří tedy bázi podprostoru W a každý vektor tohoto podprostoru, tedy i hledaný ortogonální průmět, je lineární kombinací těchto vektorů: w = αa + βb a koeficienty α, β hledáme. Má platit v = w + u, v = αa + βb + u kde u ⊥ W a tedy u ⊥ a, b a to znamená, že u • a = u • b = 0. Předchozí rovnost vynásobíme skalárně nejdříve vektorem a a potom vektorem b: v • a = α(a • a) + β(b • a), v • b = α(a • b) + β(b • b). Provedeme příslušné skalární součiny a získáme soustavu rovnic 3α + β = 4, α + 3β = 6, 3 7 α= , β= , 4 4 a pro hledaný průmět w platí: w = αa + βb = 34 (−1, 1, 1) + 74 (1, 1, 1) = (1, 52 , 52 ). Chyba aproximace je kv − wk = k(1, 2, 3) − (1, 25 , 52 )k =

√

2 2

.

Příklad 4.156: Jsou dány dva vektory x = (x1 , ..., xn ), y = (y1 , ..., yn ). Máme najít koeficienty ao , bo tak, aby platilo n X i=1

2

(yi − (ao xi + bo )) ≤

n X

(yi − (axi + b))2 ∀a, b ∈ R

i=1

(Úlohu je možné interpretovat takto: pro hodnoty proměnné x jsme naměřili hodnoty y; body (x, y) máme proložit ”vhodnou” přímku.) Je x, y ∈ Vn , položme u = (1, 1, ..., 1) a zkoumejme vektorový prostor W = hu, xi, tedy 98

prostor generovaný vektory u,x, což je prostor tvořený všemi vektory w tvaru w = ax+bu. Mezi těmito vektory hledáme wo = ao x + bo u tak, aby platilo ky − wo k ≤ ky − wk, tedy hledáme ortogonální projekci daného vektoru y (dimenze n) do podprostoru W (dimenze 2). Je y − wo ⊥ W, tedy y − wo ⊥ x, y − wo ⊥ u a odtud plyne y • x = wo • x = ao (x • x) + bo (u • x) y • u = wo • u = ao (x • u) + bo (u • u) Všechny vektory vystupující ve skalárních součinech jsou známy – jedná se tedy o soustavu dvou rovnic pro dvě neznámé ao , bo .

Položme například x = (1; 2; 3; 4; 5; 6) y = (0, 1; 0, 9; 2, 1; 3, 2; 3, 8; 5, 2) potom y • x = 72, 2; y • u = 15, 3; x • x = 91; x • u = 21; u • u = 6 a dostáváme soustavu 91ao + 21bo = 72, 2 21ao + 6bo = 15, 3 . která má řešení (ao ; bo ) = (1, 11; −1.34) a hledaná přímka má tvar y = 1, 11 x − 1, 34.

Obr. 2: Regresní přímka Jedná se o tzv. regresní přímku a metoda, pomocí které jsme ji získali, se nazývá metoda nejmenších čtverců. V obrázku vidíme geometrický význam metody: Hledáme přímku, pro kterou je součet druhých mocnin délek modrých úseček minimální.

99

Podle polohy naměřených hodnot je možné samozřejmě zvolit pro aproximaci metodou nejmenších čtverců i jiné funkce – chceme-li najít aproximaci například ve tvaru y = c1 + c2 ex + c3 sin x, budeme promítat do podprostoru (dimenze tři) generovaného vektory u = (1, 1, ..., 1) e = (ex1 , ..., exn ) s = (sin x1 , ..., sin xn )

100

5

Grafy

Základní pojmy Definice 5.1: vou,že platí

Mějme dvě konečné disjunktní množiny H, U a relaci ρ z H do U tako-

1 ≤ |ρ(h)| ≤ 2

∀h ∈ H.

Potom G = (H, U, ρ) se nazývá graf. H je množina hran grafu G, G je množina uzlů grafu G, ρ je incidenční relace. Je-li hρu, h ∈ H, u ∈ U , potom h a u incidují, je-li ρ(h) = {u1 , u2 }, potom h spojuje u1 , u2 , je-li |ρ(h)| = 1, potom je h smyčka, je-li ρ(h1 ) = ρ(h2 ) potom jsou h1 , h2 rovnoběžné hrany.

h1 – smyčka ρ(h2 ) = {u1 , u2 } h3 ρ u3 h4 , h5 – rovnoběžné hrany

Definice 5.2: H 0 ⊂ H,

Graf G0 = (H 0 , U 0 , ρ0 ) je podgrafem grafu G = (H, G, ρ), jestliže U0 ⊂ U

a ρ0 (h) = ρ(h) ∀h ∈ H 0 .

G0 je plný podgraf grafu G, jestliže je podgrafem a platí ρ(h) ⊂ U 0 ⇒ h ∈ H 0

∀h ∈ H.

Podgraf G se nazývá faktorem grafu G, jestliže U 0 = U . 101

graf G

podgraf grafu G

plný podgraf grafu G

faktor grafu G

Definice 5.3: Číslo ν(u) = |ρ−1 (u)| + |{h ∈ H | ρ(h) = {u}}| se nazývá násobnost (stupeň) uzlu u. Je-li ν(u) = 0, je u izolovaný uzel.

ν(u) = 3

Věta 5.4:

ν(u) = 4

Pro každý graf G = (H, U, ρ) platí

ν(u) = 0

P

νu = 2 · |H|.

u∈U Důkaz se provede indukcí podle počtu hran.

Souvislost grafů Definice 5.5:

Posloupnost uzlů a hran grafu G = (H, U, ρ) tvaru

S = (u0 , h1 , u1 , h2 , . . . , un−1 , hn , un ),

kde hi ∈ H, ρ(hi ) = {ui−1 , ui }, i = 1, . . . , n,

se nazývá sled v grafu G mezi uzly u0 , un . Uzly u0 a un se nazývají krajní uzly sledu S, uzly u1 , . . . , un−1 se nazývají vnitřní uzly. Číslo n se nazývá délka sledu S.

(u1 , h2 , u3 , h3 , u2 , h3 , u3 , h5 , u5 ) délky 4

–

sled

(u1 , h2 , u3 , h5 , u5 , h4 , u1 ) – sled délky 3 (u1 ) – sled délky 0 (triviální sled)

102

Definice 5.6: Poznámka:

Sled, ve kterém se každý uzel vyskytuje nejvýš jednou, se nazývá cesta.

• V cestě se zřejmě i každá hrana může vyskytovat pouze jednou. • Cestu T = (u0 , h1 , u1 , h2 , . . . , un−1 , hn , un ) můžeme také chápat jako podgraf grafu G S množinou hran {h1 , . . . , hn } a množinou uzlů {u0 , u1 , . . . , un }. V tomto podgrafu má každý vnitřní uzel násobnost 2 a krajní uzly mají násobnost 1 (vzhledem k T ). Věta 5.7: cesta.

Existuje-li mezi uzly u, v grafu G sled, potom mezi těmito uzly existuje také

Důkaz Ze všech sledů mezi u, v vybereme sled T minimální délky – algoritmus uvedeme později a poté ukážeme, že se jedná o cestu.

Definice 5.8: Graf, mezi jehož libovolnými dvěma uzly existuje sled, se nazývá souvislý graf. Poznámka: Z předchozí věty plyne, že graf je souvislý, právě když mezi jeho libovolnými dvěma uzly existuje cesta. Definice 5.9: Každý maximální souvislý podgraf G0 grafu G s nazývá komponenta (tj. každý jiný podgraf, který obsahuje G0 , je nesouvislý).

– souvislý graf

– nesouvislý graf – komponenty

Poznámka: Komponenta je zřejmě plným podgrafem. Definujme na množině uzlů U grafu G binární relaci R následujícím způsobem: uRv

⇔

existuje sled mezi uzly u, v.

103

R je zřejmě ekvivalence (je to reflexivní, symetrická a tranzitivní relace) a indukuje tedy rozklad na množiny navzájem ekvivalentních uzlů U = U1 ∪ U2 ∪ · · · ∪ Uk ,

Ui ∩ Uj = ∅ pro i 6= j.

Je-li Gi plný podgraf grafu G indukovaný množinou uzlů Ui , potom Gi jsou komponenty grafu G a příslušný rozklad je tedy rozklad grafu na komponenty. Definice 5.10: • Sled K = (u0 , h1 , u1 , h2 , . . . , un−1 , hn , u0 ), kde uzly ui jsou navzájem různé, se nazývá kružnice v grafu G. • Graf, který neobsahuje kružnice, se nazývá les. • Strom je souvislý graf, který neobsahuje kružnice. • Kostra grafu G je takový jeho faktor, který neobsahuje kružnice.

strom

kružnice

graf

kostra 1

kostra 2

Poznámka: Kružnici můžeme chápat jako podgraf K = ({h1 , . . . , hn }, {u1 , . . . , un }, ρ), který je souvislý a násobnost každého jeho uzlu je rovna 2. Navíc platí věta:

104

Věta 5.11: je rovna 2.

Graf K je kružnice, právě když je souvislý a násobnost každého jeho uzlu

Věta 5.12:

Každý souvislý graf má kostru.

Věta 5.13:

Nechť G = (H, U, ρ) je strom. Potom

|H| = |U | − 1.

Maticový popis grafu Poznámka: Těleso Z2 je algebra se dvěma operacemi na dvouprvkové množině definovaná následovně: Z2 = ({0, 1}, +, ·), 0+0=0 0+1=1+0=1 1+1=0 Definice 5.14:

0·0=0 0·1=1·0=0 1·1=1

Nechť G = (H, U, ρ) je graf bez smyček,

H = {h1 , . . . , hn }, U = {u1 , . . . , um }. Maticí incidence grafu G nazýváme matici A = (aij ) typu (m, n) nad tělesem Z2 , kde ( 1 pokud hj ρ ui , aij = 0 v opačném případě. Příklad 5.15:

u1 u2 u3 u4

Věta 5.16:

h1 h2 h3 h4 1 1 0 0 1 1 1 1 0 0 1 0 0 0 0 1

Nechť h(A je hodnost matice incidence grafu G = (H, U, ρ). Potom

h(A) < |U | Důkaz Součet všech řádků je nulový vektor.

105

Věta 5.17: Nechť G je souvislý graf. Potom libovolných r řádků matice incidence, kde 0 < r < |U |, je lineárně nezávislých. Důkaz: Nechť řádky a1 , . . . , ar jsou závislé. potom λ1 a1 + · · · + λr ar = o,

λi ∈ Z2 .

Jsou-li některé λi = 0, můžeme příslušné vektory vynechat a zbývající budou opět lineárně závislé. Proto můžeme předpokládat, že λi = 1 pro i − 1, 2, . . . , r. Je tedy a1 + a2 + · · · + ar = o. Dále můžeme předpokládat, že a1 , . . . , ar je prvních r řádků. Potom žádný z uzlů u1 , . . . , ur není spojen hranou se žádným ze zbývajících uzlů a to je spor se souvislostí grafu.

Věta 5.18: 1. Je-li G souvislý graf, potom h(A) = |U | − 1. 2. Je-li G graf o p komponentách, potom h(A) = |U | − p. Důkaz: Očíslujeme-li hrany a uzly podle jednotlivých komponent, potom      A=   

A1

0

0

0

0

A2

0

0

0

0

0

Ap

        

kde Ak je incidenční matice k-té komponenty. V každém sektoru je právě |Uk | − 1 lineárně nezávislých řádků. Celkem p X

(|Uk | − 1) =

k=1

p X

|Uk | − p = |U | − p.

k=1

Definice 5.19:

Graf bez smyček a rovnoběžných hran se nazývá prostý graf.

Věta 5.20:

Nechť pro souvislý prostý graf G platí |H| = |U | − 1. Potom G je strom.

Věta 5.21:

Nechť G = (H, U, ρ) je prostý graf, který se skládá z p komponent. Potom

|H| − |U | + p ≥ 0. Poznámka: Číslo C(G) = |H| − |U | + p se nazývá cyklomatické číslo grafu. Jestliže platí C(G) = 0, potom graf G neobsahuje kružnice. Pro cyklomatické číslo grafu G platí C(G) = |H| − h(A). 106

Hranově ohodnocené grafy Jestliže každé hraně grafu G přiřadíme reálné číslo (hodnotu, cenu), říkáme, že graf je (hranově) ohodnocený. Úloha: Je dán souvislý ohodnocený graf. Máme najít souvislý faktor s minimálním součtem ohodnocení. Takový faktor je jistě strom, je tedy kostrou grafu. Úloha tedy spočívá v nalezení kostry grafu s nejmenší hodnotou. Postup při určování minimální kostry: G = (H, U ) – ohodnocený graf, G1 = (K, U ) – kostra s nejmenší hodnotou. Máme najít množinu hran K. Seřadíme hrany H grafu G tak, aby jejich hodnoty tvořily neklesající posloupnost. Dále použijeme následující algoritmus: 1. Polož H(0) := ∅, i = 1. 2. Obsahuje graf (H(i − 1) ∪ {hi }, U ) kružnici? Pokud ano, přejdi k bodu 3), jinak bod 4). 3. Polož H(i) := H(i − 1), přejdi k bodu 5). 4. Polož H(i) := H(i − 1) ∪ {hi }. 5. Je i = n? pokud ano, přejdi k bodu 7), jinak 6). 6. Polož i := i + 1, přejdi k bodu 2). 7. Polož K = H(i). 8. Konec.

107