Lineární algebra Vektory a matice Petr Liška Mendelova univerzita 10.04.2024 Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 1 / 37 Stěhování Předpokládejme, že populace se stěhuje mezi dvěma regiony, např. venkovem a městem, podle následujícího schématu. Každý rok se 50% obyvatel venkova přestěhuje do měst a 25% obyvatel měst se přestěhuje na venkov. Je-li například na začátku polovina obyvatel ve městě a tento vzor migrace bude pokračovat, jak bude vypadat stav po dvou letech? A jak bude rozdělení obyvatelstva vypadat z dlouhodobého hlediska? Vyprázdní se venkov? Nebo se situace stabilizuje tak, že část obyvatel bude žít ve městě a část na venkově? V M 0,5 0,25 0,5 0,75 Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 2 / 37 Leslieho model populace Uvažujme například populaci hmyzu rozdělenou na tři životní etapy: mláďata, mladistvé a dospělé jedince, přičemž každá životní etapa trvá jeden rok. Pravděpodobnost přežití mláďat je 50 % a nerozmnožují se. Mladiství mají pravděpodobnost přežití 25 % a každý z nich má průměrně čtyři mláďata. Dospělí jedinci mají pravděpodobnost přežití 0 % a každý z nich má průměrně tři mláďata. Předpokládejme, že máme 100 samiček, přičemž 40 jsou mláďata, 40 jsou mladiství a 20 dospělí. Jak se bude taková populace samiček vyvíjet v čase? Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 3 / 37 Sociální sítě Kdo je nejvýznamnější postavou v této síti vztahů? 16 17 18 19 20 21 22 23 24 2512 3 4 5 6 7 8 9 10 11 12 13 14 15 Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 4 / 37 Leontiefův model Ekonomika regionu se skládá ze tří odvětví: průmysl, zemědělství a služby. Každý sektor produkuje komodity a zdrojem jeho příjmů je prodej těchto komodit, přičemž každý sektor potřebuje vstupní komodity (od sebe i ostatních sektorů): výstupy Průmysl Zemědělství Služby Průmysl 0,40 0,20 0,20 vstupy Zemědělství 0,20 0,40 0,20 Služby 0,20 0,10 0,40 Kromě toho existuje externí poptávka v hodnotě 30, 30 a 10 miliard na průmysl, zemědělství a služby. Jak velká musí být produkce jednotlivých odvětví? Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 5 / 37 Vektory a počítání s nimi Vektor Vektorem rozumíme libovolnou uspořádánou n-tici (x1, x2, . . . , xn). Značíme ⃗x = (x1, x2, . . . , xn). Jednotlivým prvkům x1, x2, . . . , xn říkáme složky vektoru, číslo n se nazývá dimenze vektoru ⃗v. Dva vektory ⃗x = (x1, x2, . . . , xn) a ⃗y = (y1, y2, . . . , yn) jsou si rovny, jestliže se rovnají odpovídající si složky, tj. ⃗x = ⃗y ⇐⇒ x1 = y1, x2 = y2, . . . , xn = yn. Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 6 / 37 Vektorový prostor Rn Množina všech vektorů ⃗x = (x1, x2, . . . , xn), kde xi ∈ R společně s operacemi sčítání vektorů ⃗x+⃗y = (x1, x2, . . . , xn)+(y1, y2, . . . , yn) = (x1 +y1, x2 +y2, . . . , xn +yn) a násobením vektoru číslem c ∈ R c · (x1, x2, . . . , xn) = (c · x1, c · x2, . . . , c · xn) se nazývá vektorový prostor Rn. Vektor ⃗o = (0, 0, . . . , 0) se nazývá nulový vektor. Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 7 / 37 Základní algebraické vlastnosti Nechť ⃗u, ⃗v a ⃗w jsou libovolné vektory z Rn a c, d ∈ R, pak 1. ⃗u + ⃗v = ⃗v + ⃗u 2. (⃗u + ⃗v) + ⃗w = ⃗u + (⃗v + ⃗w) 3. ⃗u + ⃗o = ⃗u 4. ⃗u + (−⃗u) = ⃗o 5. c(⃗u + ⃗v) = c⃗u + c⃗v 6. (c + d)⃗u = c⃗u + d⃗u 7. c(d⃗u) = (cd)⃗u 8. 1 · ⃗u = ⃗u Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 8 / 37 Skalární součin Nechť ⃗x, ⃗y ∈ Rn. Potom skalární součin ⃗x · ⃗y je definován jako ⃗x·⃗y = (x1, x2, . . . , xn)·(y1, y2, . . . , yn) = x1y1+x2y2+· · ·+xnyn = n k=1 xkyk (1, 2, −2) · (2, 3, −1) = 1 · 2 + 2 · 3 + (−2) · (−1) = 10 Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 9 / 37 Skalární součin Nechť ⃗x, ⃗y ∈ Rn. Potom skalární součin ⃗x · ⃗y je definován jako ⃗x·⃗y = (x1, x2, . . . , xn)·(y1, y2, . . . , yn) = x1y1+x2y2+· · ·+xnyn = n k=1 xkyk Velikost (norma) vektoru Velikostí vektoru ⃗x = (x1, x2, . . . , xn) ∈ Rn rozumíme nezáporné číslo |⃗x| = √ ⃗x · ⃗x = x2 1 + x2 2 + · · · + x2 n. Ortogonální vektory Vektory ⃗x a ⃗y nazveme ortogonální, právě když ⃗x · ⃗y = 0 . Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 10 / 37 Lineární kombinace, závislost a nezávislost vektorů Lineární kombinace Nechť ⃗x1, ⃗x2, . . . , ⃗xn je konečná posloupnost vektorů z vektorového prostoru V . Vektor ⃗x, pro který platí ⃗x = t1⃗x1 + t2⃗x2 + · · · + tn⃗xn, kde t1, t2, . . . , tn jsou nějaká reálná čísla, se nazývá lineární kombinace vektorů ⃗x1, ⃗x2, . . . , ⃗xn. LZ a LN Řekneme, že vektory ⃗x1, ⃗x2, . . . , ⃗xn jsou lineárně závislé, jestliže existují reálná čísla t1, t2, . . . , tn, z nichž alespoň jedno je různé od nuly, taková, že platí ⃗o = t1⃗x1 + t2⃗x2 + · · · + tn⃗xn. V opačném případě říkáme, že vektory jsou lineárně nezávislé. Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 11 / 37 Tedy například vektory (1, 2, 1), (2, −3, 1), (4, 1, 3) jsou lineárně závislé, protože 2 · (1, 2, 1) + (2, −3, 1) = (4, 1, 3). Vektory (1, 0, 0), (0, 1, 0), (0, 0, 1) jsou zřejmě lineárně nezávislé. Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 12 / 37 Matice Definice Maticí A rozumíme schéma A = (aij) =      a11 a12 . . . a1n a21 a22 . . . a2n ... ... ... ... am1 am2 . . . amn      kde aij pro i = 1, . . . , m a j = 1, . . . , n jsou reálná čísla nebo funkce. Je-li tato matice (tabulka) sestavená z m řádků a n sloupců, říkáme, že A je matice typu m × n. Je-li m = n nazývá se matice A čtvercová matice, jinak obdélníková matice. Je-li A čtvercová matice, říkáme, že prvky tvaru aii, tj. prvky, jejichž řádkový a sloupcový index jsou stejné, tvoří hlavní diagonálu. Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 13 / 37 Operace s maticemi Nechť k ̸= 0 je reálné číslo. Výsledkem násobení matice A číslem k je matice C, jejíž prvky jsou tvaru cij = k · aij. Příklad 4 · 2 5 7 −1 0 4 = 8 20 24 −4 0 16 Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 14 / 37 Nechť A, B jsou matice téhož typu m × n. Součtem matic A, B nazýváme matici C, jejíž prvky jsou cij = aij + bij. Příklad 2 5 7 −1 0 4 + 1 −3 −2 0 2 1 = 3 2 5 −1 2 5 Nechť A je matice typu m × n a B je matice typu n × p. Součinem matic A a B (v tomto pořadí) nazýváme matici C (typu m × p), jejíž prvky jsou cij = ai1b1j + ai2b2j + . . . ainbnj = n k=1 aikbkj. Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 15 / 37 Příklad Pro dané matice spočtěte A·B A = 2 5 7 −1 0 4 B =   3 2 1 7 −4 0 6 1 2 11 1 −2   Řešení: A·B = 2 5 7 −1 0 4 ·   3 2 1 7 −4 0 6 1 2 11 1 −2   = = 2·3 + 5·(−4) + 7·2 2·2 + 5·0 + 7·11 2·1 + 5·6 + 7·1 2·7 + 5·1 + 7·(−2) −1·3 + 0·(−4) + 4·2 −1·2 + 0·0 + 4·11 −1·1 + 0·6 + 4·1 −1·7 + 0·1 + 4·(−2) = = 0 81 39 5 5 42 3 −15 Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 16 / 37 Definice Je-li A matice typu m × n, pak transponovaná matice AT je matice typu n × m, která vznikne z matice A záměnou řádků za sloupce, tj. i-tý sloupec matice AT je i-tý řádek matice A pro všechna i. Příklad 3 5 4 −2 1 6 T =   3 −2 5 1 4 6   Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 17 / 37 Definice Diagonální matice je čtvercová matice, která má všechny prvky mimo hlavní diagonálu rovny nule. Definice Jednotková matice je čtvercová matice, která má v hlavní diagonále všechny prvky rovny jedné a všechny prvky mimo diagonálu rovny nule. Tuto matici budeme značit I. Příklad 3 0 0 6 ,   1 0 0 0 1 0 0 0 1   Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 18 / 37 Základní vlastnosti počítání s maticemi Nechť matice A, B, C mají správné rozměry tak, aby se dali provést naznačené operace a k ∈ R. Pak 1. A + B = B + A 2. (A + B) + C = A + (B + C) 3. A(BC) = (AB)C 4. A(B + C) = AB + AC 5. (A + B)C = AC + BC 6. k(A + B) = kA + kB 7. k(AB) = (kA)B = A(kB) Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 19 / 37 Proč se to dělá zrovna takto? f x1 x2 = ax1 + bx2 cx1 + dx2 g x1 x2 = Ax1 + Bx2 Cx1 + Dx2 f g x1 x2 = f Ax1 + Bx2 Cx1 + Dx2 = (aA + bC)x1 + (aB + bD)x2 (cA + dC)x1 + (cB + dD)x2 F = a b c d G = A B C D H = aA + bC aB + bD cA + dC cB + dD a b c d · A B C D = aA + bC aB + bD cA + dC cB + dD Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 20 / 37 Některé aplikace matic Grafem rozumíme konečnou množinu bodů (těm říkáme vrcholy) a konečnou množinu hran, kdy každá z nich spojuje dva vrcholy (ne nutně různé). A B C D E A B D E C Stejný graf můžeme ale také popsat pomocí tzv. matice sousednosti. Pro graf o n vrcholech se jedná o čtvercovou matici n × n definovanou takto aij = 1 je-li hrana mezi vrcholy i a j, 0 jinak. Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 21 / 37 A B C D E A B D E C Pro náš graf dostaneme matici A =       0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 1 0       Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 22 / 37 V mnoha aplikacích, které můžeme modelovat pomocí grafu, je mezi vrcholy zároveň nějaký vztah, který vede k tomu, že hrana by měla být orientovaná. Tímto dostaneme tzv. orientovaný graf. A B C D E F G I pro orientovaný graf můžeme zavést matici sousednosti, kde pro jednotlivé koeficienty platí aij = 1 vede-li hrana z vrcholu i do vrcholu j, 0 jinak. Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 23 / 37 A B C D E F G Pro náš graf dostaneme matici A =           0 0 0 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0           Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 24 / 37 Cestou v grafu rozumíme posloupnost hran, která nám umožní cestovat z jednoho vrcholu do jiného. Její délka je pak číslo určující počet hran, které obsahuje. Uvažme matici A2 = A · A =       3 0 2 2 1 0 2 1 0 2 2 1 3 1 2 2 0 1 2 0 1 2 2 0 3       Co reprezentují čísla v této matici? Z definice násobení matic víme, že A2 13 = a11a13 + a12a23 + a13a33 + a14a43 + a15a53 . Tento výraz bude nenulový, když alespoň jeden ze součinů a1kak3 bude nenulový, což ale nastane jen tehdy, když oba členy a1k i ak3 budou nenulové. To ale znamená, že existuje hrana mezi prvním a k-tým vrcholem a taky hrana mezi k-tým a třetím vrcholem, tedy existuje cesta délky 2, která spojuje první a třetí vrchol. Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 25 / 37 Tyto myšlenky můžeme ilustrovat na celé řadě příkladů. Uvažme například následující graf a příslušnou matici sousednosti, které zobrazují přímé letecké spoje mezi Brnem, Edinburghem, Lisabonem, Mnichovem a Paříží. B M P L E A =      B E L M P B 0 0 0 1 1 E 0 0 0 1 1 L 0 0 0 1 1 M 1 1 1 0 1 P 1 1 1 1 0      Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 26 / 37 Nyní můžeme například snadno odpovědět na otázku, kolik existuje různých letů z Brna do libovolného města s dvěma přestupy: A + A2 + A3 =       4 4 4 9 9 4 4 4 9 9 4 4 4 9 9 9 9 9 10 11 9 9 9 11 10       Odpověď dává první řádek naší matice. Vidíme, že například z Brna do Edinburghu existují čtyři různé cesty s dvěma přestupy a do Paříže je jich už devět. Která z těchto cest by byla nejkratší nebo nejrychlejší je již ale jiný příběh (i když stále z teorie grafů). Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 27 / 37 Představme si například pětici hráčů, kteří hrají turnaj ve stylu každý s každým. Výsledky můžeme snadno zachytit pomocí grafu, kdy hranu od prvního hráče k druhému vedeme tehdy, když první druhého porazí. Dostaneme tak například následující graf a příslušnou matici sousednosti A B C D E A =       0 1 0 1 1 0 0 1 1 1 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0       Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 28 / 37 Dejme tomu, že chceme seřadit hráče podle počtu jejich vítězství. Pro tento účel nám stačí samozřejmě jen sečíst, kolik jedniček je v každém řádku. Tento výpočet můžeme také nahradit následujícím násobením: A · J =       0 1 0 1 1 0 0 1 1 1 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0       ·       1 1 1 1 1       =       3 3 2 1 1       Vidíme, že někteří hráči (A a B, C a D) mají stejný počet výher. Pokud bychom chtěli rozhodnout, který z nich je lepší, můžeme například použít kritérium nepřímých vítězství, tj. kolik hráčů porazili hráči, které daný hráč porazil. Ve slovech matic (po předchozím příkladu je snad jasné proč) dostaneme (A + A2 ) · J =       8 7 6 2 3       Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 29 / 37 Sociální sítě Kdo je nejvýznamnější postavou v této síti vztahů? 16 17 18 19 20 21 22 23 24 2512 3 4 5 6 7 8 9 10 11 12 13 14 15 Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 30 / 37                                             0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0                                             Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 31 / 37 Leslieho model Příklad Uvažujme například populaci hmyzu rozdělenou na tři životní etapy: mláďata, mladistvé a dospělé jedince, přičemž každá životní etapa trvá jeden rok. Pravděpodobnost přežití mláďat je 50 % a nerozmnožují se. Mladiství mají pravděpodobnost přežití 25 % a každý z nich má průměrně čtyři mláďata. Dospělí jedinci mají pravděpodobnost přežití 0 % a každý z nich má průměrně tři mláďata. Předpokládejme, že máme 100 samiček, přičemž 40 jsou mláďata, 40 jsou mladiství a 20 dospělí. Jak se bude taková populace samiček vyvíjet v čase? Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 32 / 37 Po jednom roce bude počet mláďat 40 · 4 + 20 · 3 = 220. Počet mladistvých bude počet mláďat, která přežijí, tj. 40 · 0,5 = 20 a podobně pro dospělé 40 · 0,25 = 10. Všechny tyto výpočty můžeme snadno zapsat jednou maticovou rovnicí L · x0 =   0 4 3 0,5 0 0 0 0,25 0   ·   40 40 20   =   220 20 10   = x1 . Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 33 / 37 t P 1000 2000 3000 4000 1 2 3 4 5 6 7 8 9 t P[%] 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 5 10 15 Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 34 / 37 Stěhování Předpokládejme, že populace se stěhuje mezi dvěma regiony, např. venkovem a městem, podle následujícího schématu. Každý rok se 50% obyvatel venkova přestěhuje do měst a 25% obyvatel měst se přestěhuje na venkov. Je-li například na začátku polovina obyvatel ve městě a tento vzor migrace bude pokračovat, jak bude vypadat stav po dvou letech? A jak bude rozdělení obyvatelstva vypadat z dlouhodobého hlediska? Vyprázdní se venkov? Nebo se situace stabilizuje tak, že část obyvatel bude žít ve městě a část na venkově? V M 0,5 0,25 0,5 0,75 Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 35 / 37 Řešení: vk+1 = 0,5vk + 0,25mk mk+1 = 0,5vk + 0,75mk vk+1 mk+1 = 0,5 0,25 0,5 0,75 · vk mk ⃗pk+1 = T · ⃗pk ⃗pk+2 = T · ⃗pk+1 = T · (T · ⃗pk) = T2 · ⃗pk ⃗p2 = T2 · ⃗p0 = 0,375 0,3125 0,625 0,6875 · 0,5 0,5 = 0,34375 0,65625 ⃗p = T · ⃗p Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 36 / 37 Markovův řetězec Markovův řetězec je náhodný proces, který popisuje posloupnost možných událostí. Pro tento proces platí, že pravděpodobnost přechodu procesu do následujícího stavu závisí pouze na současném stavu. Matice přechodu Matici, která obsahuje v každém sloupci (řádku) pravděpodobnosti přechodu od jednoho stavu k druhému, nazveme maticí přechodu daného Markovova řetězce. Stacionární distribuce Je-li T matice přechodu daného Markovova řetězce a existuje-li vektor ⃗v takový, že ⃗v = T · ⃗v nazveme vektor ⃗v stacionární distribucí (rovnovážným stavem) Markovova řetězce. Petr Liška (Mendelova univerzita) Lineární algebra 10.04.2024 37 / 37