Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Drsná matematika I – 5. přednáška Vektory a matice Jan Slovák Masarykova univerzita 17. 10. 2011 Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Obsah přednášky 1 Literatura 2 Vektory 3 Matice nad skaláry 4 Ekvivalentní úpravy matic 5 Lineární závislost Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Kde je dobré číst? vlastní poznámky, texty současného nebo předcházejícího přednášejícího, GOOGLE, atd. Pavel Horák, Úvod do lineární algebry, MU Brno, skripta. Luboš Motl, Miloš Zahradník, Pěstujeme lineární algebru, 3. vydání, Univerzita Karlova v Praze, Karolinum, 348 stran (elektronické vydání také na http://www.kolej.mff.cuni.cz/˜lmotm275/skripta/). Riley, K.F., Hobson, M.P., Bence, S.J. Mathematical Methods for Physics and Engineering, second edition, Cambridge University Press, Cambridge 2004, ISBN 0 521 89067 5, xxiii + 1232 pp. František Šik, Lineární algebra zaměřená na numerickou analýzu, MU, 1998, 176 s. ISBN 80-210-1996-2. Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Definition Symbolem K budeme nadále značit nějakou množinu skalárů. Prozatím budeme vektorem rozumět uspořádanou n-tici skalárů, kde pevně zvolené n ∈ N budeme nazývat dimenzí. Sčítání vektorů definujeme po složkách (skaláry samozřejmě sčítat umíme) a násobení vektoru u = (a1, . . . , an) skalárem b definujeme tak, že každý prvek n-tice u vynásobíme skalárem b (skaláry v K násobit umíme), tj. u + v = (a1, . . . , an) + (b1, . . . , bn) = (a1 + b1, . . . , an + bn) b · u = b · (a1, . . . , an) = (b · a1, . . . , b · an). Zpravidla jsou skaláry z pole, případně komutativního okruhu. Pokud jste se ještě nesmířili s abstrakcí okruhů a polí, přemýšlujte v rámci číselných oborů. Potom okruhy skalárů zahrnují i celá čísla Z a všechny zbytkové třídy, zatímco mezi poli jsou pouze R, Q, C a zbytkové třídy Zk s prvočíselným k. Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Pro sčítání vektorů v Kn zjevně platí (KG1)–(KG4) s nulovým prvkem 0 = (0, . . . , 0) ∈ Kn . Schválně zde používáme pro nulový prvek stejný symbol jako pro nulový prvek skalárů. Konvence značení Podobně budeme pro sčítání a násobení používat stále stejný symbol (plus a buď tečku nebo prosté zřetězení znaků). Navíc nebudeme používat pro vektory žádné speciální značení, a ponecháváme na čtenáři aby udržoval svoji pozornost přemýšlením o kontextu. Pro skaláry ale spíše budeme používat písmena ze začátku abecedy a pro vektory od konce (prostředek nám zůstane na indexy proměných, komponent a v součtech). Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Theorem Pro všechny vektory v, w ∈ Kn a skaláry a, b ∈ K platí a · (v + w) = a · v + a · w (V1) (a + b) · v = a · v + b · v (V2) a · (b · v) = (a · b) · v (V3) 1 · v = v (V4) Důkaz. Pro kterékoliv pole skalárů K se vlastnosti (V1)–(V4) snadno ověří pro každý prostor Kn, protože při ověřování vždy používáme pouze vlastnosti skalárů. Budeme takto pracovat např. s Rn, Qn, Cn, (Zk)n, n = 1, 2, 3, . . .. Všimněme si také, že k ověření vlastností (V1)–(V4) potřebujeme pro použité skaláry pouze vlastnosti okruhu. Vlastnost (P) však bude přesto podstatná později. Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Definition Maticí typu m/n nad skaláry K rozumíme obdélníkové schéma A =      a11 a12 . . . a1n a21 a22 . . . a2n ... ... am1 am2 . . . amn      kde aij ∈ K pro všechny 1 ≤ i ≤ m, 1 ≤ j ≤ n. Matici A s prvky aij značíme také A = (aij ). Vektory (ai1, ai2, . . . , ain) ∈ Kn nazýváme (i–té) řádky matice A, i = 1, . . . , m, vektory (a1j , a2j , . . . , amj ) ∈ Km nazýváme (j–té) sloupce matice A, j = 1, . . . , n. Matici můžeme také chápat jako zobrazení A : {1, . . . , m} × {1, . . . , n} → K. Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Matice typu 1/n nebo n/1 jsou vlastně právě vektory v Kn. Obecné matice lze však chápat jako vektory v Km·n, prostě zapomeneme na řádkování. Zejména tedy je definováno: Sčítání matic a násobení matic skaláry: A + B = (aij + bij ), kde A = (aij ), B = (bij ), a · A = (a.aij ), kde A = (aij ), a ∈ K. Dále pak matice −A = (−aij ) se nazývá matice opačná k matici A. Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Konečně, matice 0 =    0 . . . 0 ... ... 0 . . . 0    se nazývá nulová matice. Zapomenutím řádkování tak získáme následující tvrzení: Theorem Předpisy pro A + B, a · A, −A, 0 zadávají na množině všech matic typu m/n operace sčítání a násobení skaláry splňující axiomy (V1)–(V4). Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Maticový zápis systémů lineárních rovnic Matice lze vhodně využít pro zápis lineárních rovnic. Uvažme následující systém m rovnic v n proměnných: a11x1 + a12x2 + · · · + a1nxn = y1 a21x1 + a22x2 + · · · + a2nxn = y2 ... am1x1 + am2x2 + · · · + amnxn = ym. Posloupnost x1, . . . , xn lze chápat jako vektor proměnných, tj. sloupec v matici typu n/1, a podobně s hodnotami y1, . . . , yn. Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Systém rovnic lze pak formálně psát ve tvaru A · x = y :    a11 . . . a1n ... ... am1 . . . amn    .    x1 ... xn    =    y1 ... yn    Původní rovnice nyní obdržíme tak, že vždy bereme řádky z A a sčítáme součiny odpovídajících komponent, tj. ai1x1 + · · · + ainxn. Tím získáme i-tý prvek výsledného vektoru. V rovině, tj. pro vektory dimenze 2, jsme už zavedli takovýto počet a viděli jsme, že s ním lze pracovat velice efektivně. Nyní budeme postupovat obecněji a zavedeme i na maticích operace násobení. Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Součin matic Pro libovolnou matici A = (aij ) typu m/n nad okruhem skalárů K a libovolnou matici B = (bjk) typu n/q nad K definujeme jejich součin C = A · B = (cik) jako matici typu m/q s prvky cik = n j=1 aij bjk, pro libovolné 1 ≤ i ≤ m, 1 ≤ k ≤ q. Například máme 2 1 1 −1 · 2 1 1 −1 0 1 = 3 2 3 3 1 0 Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Čtvercové matice U matice typu n/n hovoříme o čtvercové matici. Počet řádků a sloupců se nazývá dimenze matice. Matici E = (δij ) =    1 . . . 0 ... ... ... 0 . . . 1    se říká jednotková matice. Na množině čtvercových matic nad K dimenze n je součin matic definován pro každé dvě matice: Theorem Pro libovolný okruh skalárů je na množině všech čtvercových matic dimenze n definována operace násobení. Splňuje vlastnosti (O1) a (O3) vzhledem k jednotkové matici E = (δij ). Dále spolu se sčítáním matic vyhovuje (O4). Obecně však neplatí (O2) ani (OI), zejména tedy neplatí (P). Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Při důkazu předchozího tvrzení není podstatný stejný počet řádků a sloupců, kromě samotné existence operace násobení pro všechny dvojice matice. Příslušné vlastnosti proto platí obecněji: Theorem Násobení matic je asociativní a distributivní, tj. A · (B · C) = (A · B) · C, A · (B + C) = A · B + A · C, kdykoliv jsou tato násobení definována. Jednotková matice je neutrálním prvkem pro násobení zleva i zprava. Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Inverzní matice Se skaláry umíme počítat tak, že z rovnosti a · x = b umíme vyjádřit x = a−1 · b, kdykoliv inverze k a existuje. Podobně bychom to měli umět s maticemi, máme ale problém, jak poznat, zda taková inverzní matice existuje, a jak ji spočítat. Definition Říkáme, že B je matice inverzní k matici A, když A · B = B · A = E. Píšeme pak B = A−1 a je samozřejmé, že obě matice musí mít tutéž dimenzi n. Matici, k níž existuje matice inverzní, říkáme invertibilní matice. Pokud A−1 a B−1 existují, pak existuje i (A · B)−1 = B−1 · A−1. Je totiž (díky právě dokázané asociativitě násobení) (B−1 · A−1) · (A.B) = B−1 · (A−1 · A) · B = E a (A · B) · (B−1 · A−1) = A · (B · B−1) · A−1 = E. Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Protože s maticemi umíme počítat zrovna jako se skaláry, jen mají složitější chování, můžeme formálně snadno řešit systémy lineárních rovnic: Jestliže vyjádříme soustavu n rovnic pro n neznámých součinem matic A · x =    a11 · · · a1m ... am1 · · · amm    ·    x1 ... xm    =    y1 ... ym    = y a existuje matice inverzní k matici A, pak lze násobit zleva A−1 a dostaneme A−1 · y = A−1 · A · x = E · x = x, tj. hledané řešení. Naopak rozepsáním podmínky A · A−1 = E pro neznámé skaláry v hledané matici A−1 dostaneme n systémů lineárních rovnic se stejnou maticí na levé straně a různými vektory napravo. Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Z hlediska řešení systémů rovnic A · x = b je jistě přirozené považovat za ekvivalentní matice A a vektory b, které zadávají systémy rovnic se stejným řešením. Uvedeme si jednoduché manipulace s řádky rovnic a stejným způsobem pak můžeme upravovat i vektor napravo. Když se nám podaří vlevo dostat systém s jednotkovou maticí, bude napravo řešení původního systému. Takovým operacím říkáme řádkové elementární transformace. Jsou to: záměna dvou řádků vynásobení vybraného řádku nenulovým skalárem přičtení řádku k jinému řádku. Je zjevné, že odpovídající operace na úrovni rovnic v systému nemohou změnit množinu všech jeho řešení. Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Sloupcové elementární transformace matic jsou záměna dvou sloupců vynásobení vybraného sloupce nenulovým skalárem přičtení sloupce k jinému sloupci, Tyto operace však nezachovávají řešení příslušných rovnic, protože mezi sebou míchají samotné proměnné. Později budeme vidět, že sloupcové elementární transformace vedou k řešení téhož systému ale v transformovaných souřadnicích. Systematicky můžeme použít elementární řádkové úpravy k postupné eliminaci proměnných. Postup je algoritmický a většinou se mu říká Gausova eliminace proměnných. Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Theorem Nenulovou matici nad libovolným okruhem skalárů K lze konečně mnoha elementárními řádkovými transformacemi převést na tzv. (řádkově) schodovitý tvar: Je-li aij = 0 a všechny předchozí prvky na i-tém řádku jsou také nulové, potom akj = 0 pro všechna k ≥ i je-li a(i−1)j první nenulový prvek na (i − 1)-ním řádku, pak aij = 0. Matice v řádkově schodovitém tvaru vypadá takto         0 . . . 0 a1j . . . . . . . . . a1m 0 . . . 0 0 . . . a2k . . . a2m ... 0 . . . . . . . . . . . . 0 alp . . . ...         a matice může, ale nemusí, končit několika nulovými řádky. Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost K převodu libovolné matice můžeme použít jednoduchý algoritmus: 1 Záměnou řádků docílíme, že v prvním řádku bude v prvním nenulovém sloupci nenulový prvek, nechť je to j-tý sloupec. 2 Pro i = 2, . . ., vynásobením prvního řádku prvkem aij , i-tého řádku prvkem a1j a odečtením vynulujeme prvek aij na i-tém řádku. 3 Opakovanou aplikací bodů (1) a (2), vždy pro zbytek řádků a sloupců v získané matici dospějeme po konečném počtu kroků k požadovanému tvaru. Uvedený postup je obvyklá eliminace proměnných v systémech lineárních rovnic. Pro řešení systémů rovnic má ale uvedený postup rozumný smysl jen, když mezi skaláry neexistují dělitelé nuly. Pokud tvoří skaláry pole, pak můžeme navíc ze schodovitého tvaru snadno spočíst řešení (případně ověřit jeho neexistenci). Rozdíly jsou dobře vidět při porovnání třeba K = Z a K = R, případně Z2 nebo Z3. Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost realizace pomocí elementárních matic Všimněme si, že elementární řádkové (resp. sloupcové) transformace odpovídají vynásobením zleva (resp. zprava) následujícími maticemi: Přehození i-tého a j-tého řádku (resp. sloupce)               1 0 . . . 0 ... ... 0 . . . 1 ... ... ... 1 . . . 0 ... 1               Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost realizace pomocí elementárních matic Vynásobení i-tého řádku (resp. sloupce) skalárem a:             1 ... 1 a 1 ... 1             ← i Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost realizace pomocí elementárních matic Sečtení i-tého řádku (resp. sloupce) s j-tým: i →                1 0 0 ... ... ... 1 ... ... 1                ↑ j Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Toto prostinké pozorování je ve skutečnosti velice podstatné, protože součin invertibilních matic je invertibilní a všechny elementární transformace jsou nad polem skalárů invertibilní. Pro libovolnou matici A tedy dostaneme násobením vhodnou invertibilní maticí P = Pk · · · P1 zleva (postupné násobení k maticemi zleva) její ekvivalentní řádkový schodovitý tvar A = P · A. Jestliže obecně aplikujeme tentýž eliminační postup na sloupce, dostaneme z každé matice B její sloucový schodovitý tvar B vynásobením vhodnou invertibilní maticí Q = Q1 · · · Q . Pokud ale začneme s maticí B = A v řádkově schodovitém tvaru, eliminuje takový postup pouze všechny dosud nenulové prvky mimo diagonálu matice a závěrem lze ještě i tyto elementárními operacemi změnit na jedničky. Celkem jsme tedy ověřili důležitý výsledek, ke kterému se budeme mnohokrát vracet: Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Theorem Pro každou matici A typu m/n nad polem skalárů K existují čtvercové invertibilní matice P dimenze m a Q dimenze n takové, že matice P · A je v řádkově schodovitém tvaru a P · A · Q =           1 . . . 0 . . . . . . . . . 0 ... ... 0 . . . 1 0 . . . . . . 0 0 . . . 0 1 0 . . . 0 0 . . . 0 0 0 . . . 0 ...           . Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Algoritmus pro výpočet inverzní matice V předchozích úvahách jsme se dostali prakticky k úplnému algoritmu pro výpočet inverzní matice. Během jednoduchého níže uvedeného postupu buď zjistíme, že inverze neexistuje, nebo bude inverze spočtena. I nadále pracujeme nad polem skalárů. Ekvivalentní řádkové transformace se čtvercovou maticí A dimenze n vedou k matici P takové, že P · A bude v řádkově schodovitém tvaru. Přitom může (ale nemusí) být jeden nebo více posledních řádků nulových. Jestliže má existovat inverzní matice k A, pak existuje i inverzní matice k P · A. Jestliže však je poslední řádek v P · A nulový, bude nulový i poslední řádek v P · A · B pro jakoukoliv matici B dimenze n. Existence takového nulového řádku ve výsledku (řádkové) Gaussovy eliminace tedy vylučuje existenci A−1. Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Předpokládejme nyní, že A−1 existuje. Podle předchozího, nalezneme řádkově schodovitý tvar bez nulového řádku, tzn. že všechny diagonální prvky v P · A jsou nenulové. Pak ovšem pokračováním eliminace od pravého dolního rohu zpět a vynormováním diagonálních prvků na jedničky získáme jednotkovou matici E. Jinými slovy, najdeme další invertibilní matici P takovou, že pro P = P · P platí P · A = E. Výměnou řádkových a sloupcových transformací lze za předpokladu existence A−1 stejným postupem najít Q takovou, že A · Q = E. Odtud P = P · E = P · (A · Q) = (P · A) · Q = Q. To ale znamená, že jsme nalezli hledanou inverzní matici A−1 = P = Q k A. Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Prakticky tedy můžeme postupovat tak, že vedle sebe napíšeme původní matici A a jednotkovou matici E, matici A upravujeme řádkovými elementárními úpravami nejprve na schodovitý tvar, potom tzv. zpětnou eliminací na diagonální matici a v té násobíme řádky inverzními prvky z K. Tytéž úpravy postupně prováděné s E vedou právě k matici P = P · P z předchozích úvah, tedy z ní získáme právě hledanou inverzi. Pokud tento algoritmus narazí na vynulování celého řádku v původní matici, znamená to, že matice inverzní neexistuje. Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost V předchozích úvahách a počtech s maticemi jsme stále pracovali se sčítáním řádků nebo sloupců coby vektorů, spolu s jejich násobením skaláry. Takové operaci říkáme lineární kombinace. V abstraktním pojetí se k operacím s vektory vrátíme později, bude ale užitečné pochopit podstatu už nyní. Lineární kombinací řádků (nebo sloupců) matice A = (aij ) typu m/n rozumíme výraz a1ui1 + · · · + akuik , kde ai jsou skaláry, uj = (aj1, . . . , ajn) jsou řádky (nebo uj = (a1j , . . . , amj ) jsou sloupce) matice A. Jestliže existuje lineární kombinace daných řádků s alespoň jedním nenulovým skalárním koeficientem, jejímž výsledkem je nulový řádek, říkáme, že jsou lineárně závislé. V opačném případě, tj. když jedinou možnost jak získat nulový řádek je vynásobení výhradně nulovými skaláry, jsou lineárně nezávislé. Obdobně definujeme lineárně závislé a nezávislé sloupce matice. Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost Předchozí výsledky o Gausově eliminaci můžeme vnímat takovým způsobem, že počet výsledných nenulových „schodů“ v řádkově nebo sloupcově schodovitém tvaru je vždy roven témuž přirozenému číslu a to počtu lineárně nezávislých řádků matice a témuž počtu lineárně nezávislých sloupců matice. Tomuto číslu říkáme hodnost matice, značíme h(A). Zapamatujme si výsledné tvrzení: Theorem Nechť A je matice typu m/n nad polem skalárů K. Matice A má stejný počet h(A) linárně nezávislých řádků a lineárně nezávislých sloupců. Zejména je hodnost vždy nejvýše rovna menšímu z rozměrů matice A. Algoritmus pro výpočet inverzních matic také říká, že čtvercová matice A dimenze m má inverzi právě, když je její hodnost rovna počtu řádků m. Literatura Vektory Matice nad skaláry Ekvivalentní úpravy matic Lineární závislost řešení systémů rovnic eliminací Jestliže budeme uvažovat matici systému rovnic a přidáme k ní ještě sloupec požadovaných hodnot, hovoříme o rozšířené matici systému. Postup, který jsme předvedli odpovídá postupné eliminaci proměnných v rovnicích a vyškrtání lineárně závislých rovnic. Pokud nám při přechodu na řádkově schodovitý tvar zůstane v rozšířené matici více nenulových řádků než v matici systému, pak žádné řešení nemůže existovat. Pokud je hodnost obou matic stejná, pak nám při zpětném dopočtu řešení zůstane právě tolik volných parametrů, kolik je rozdíl mezi počtem proměnných hodností.