Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice Matematika I – 5b Vektory, matice, determinanty Jan Slovák Masarykova univerzita, Fakulta informatiky 17. 10. 2011 Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice Obsah přednášky 1 Vektory 2 Matice nad skaláry 3 Lineární závislost 4 Determinanty 5 Věty Cauchyova a Laplaceova 6 Inverzní matice Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice 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ě z oboru integrity. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice 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. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice 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 ). 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). Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní 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). Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice 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. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice 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í. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice 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. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice 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. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice 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               Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice realizace pomocí elementárních matic Vynásobení i-tého řádku (resp. sloupce) skalárem a:             1 ... 1 a 1 ... 1             ← i Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice 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 Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice 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: Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice 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 ...           . Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice 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. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice 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. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice 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. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice 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. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice Obecně, nechť A = (aij ) je čtvercová matice dimenze n nad K. Determinant matice A je skalár det A = |A| definovaný vztahem |A| = σ∈Σn sgn(σ)a1σ(1) · a2σ(2) · · · anσ(n) kde Σn je množina všech možných permutací na {1, . . . , n} a znaménko sgn pro každou permutaci ještě musíme popsat. Každý z výrazů sgn(σ)a1σ(1) · a2σ(2) · · · anσ(n) nazýváme člen determinantu |A|. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice Jak tedy najít správná znaménka? Říkáme, že dvojice prvků a, b ∈ X = {1, . . . , n} tvoří inverzi v permutaci σ, je-li a < b a σ(a) > σ(b). Permutace σ se nazývá sudá (resp. lichá), obsahuje-li sudý (resp. lichý) počet inverzí. Parita permutace σ je (−1)počet inverzí a značíme ji právě sgn(σ). Tolik definice, chceme ale vědět, jak s paritou počítat. Z následujícího tvrzení už je jasně vidět, že Saarusovo pravidlo skutečně počítá determinant v dimenzi 3. Theorem Na množině X = {1, 2, . . . , n} je právě n! různých permutací. Tyto lze seřadit do posloupnosti tak, že každé dvě po sobě jdoucí se liší právě jednou transpozicí. Lze při tom začít libovolnou permutací a každá transpozice mění paritu. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice Zjistili jsme, že provedení libovolné transpozice změní paritu permutace a že každé pořadí čísel {1, 2, . . . , n} lze získat postupnými transpozicemi sousedních prvků. Důsledkem tohoto popisu je, že na každé množině X = {1, . . . , n}, n > 1, je právě 1 2 n! sudých a 1 2 n! lichých permutací. Jestliže složíme dvě permutace za sebou, znamená to provést napřed všechny transpozice tvořící první a pak druhou. Proto pro libovolné permutace σ, η : X → X platí sgn(σ ◦ η) = sgn(σ) · sgn(η), sgn(σ−1 ) = sgn(σ). Pro každou matici A = (aij ) typu m/n na skaláry z K definujeme matici transponovanou k A. Jde o matici AT = (aij ) s prvky aij = aji typu n/m. Čtvercová matice A s vlastností A = AT se nazývá symetrická. Jestliže platí A = −AT , pak se A nazývá antisymetrická. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice Theorem Pro každou čtvercovou matici A platí 1 |AT | = |A|, 2 Je-li jeden řádek v A tvořen nulovými prvky z K, pak |A| = 0, 3 Jestliže matice B vznikla z A výměnou dvou řádků, pak |A| = −|B|, 4 Jestliže matice B vznikla z A vynásobením řádku skalárem a ∈ K, pak |B| = a|A|, 5 Jsou-li prvky k-tého řádku v A tvaru akj = ckj + bkj a všechny ostatní řádky v maticích A, B = (bij ), C = (cij ) jsou stejné, pak |A| = |B| + |C|, 6 Determinant |A| se nezmění, přičteme-li k libovolnému řádku A lineární kombinaci ostatních řádků. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice Důsledkem prvního tvrzení předchozí věty o rovnosti determinantů matice a matice transponované je, že kdykoliv se nám podaří dokázat nějaké tvrzení o determinantech formulované s využitím řádků příslušné matice, pak analogické tvrzení platí i pro sloupce. Např. tedy můžeme okamžitě všechna tvrzení (2)–(6) této věty přeformulovat i pro přičítání lineárních kombinací ostatních sloupců k vybranému. Vlastnosti (3)–(5) říkají, že determinant jako zobrazení, které n vektorům dimenze n (řádkům nebo sloupcům matice) přiřadí skalár je antisymetrické zobrazení lineární v každém svém argumentu, přesně jak jsme podle analogie z dimenze 2 požadovali. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice Pro matici v řádkovém nebo sloupcovém schodovitém tvaru je jediným nenulovým členem determinantu ten, který odpovídá identické permutaci. Vidíme tedy, že determinant takové matice je |A| = a11 · a22 · · · · ann. Předchozí věta tedy poskytuje velice efektivní metodu výpočtu determinantů pomocí Gaussovy eliminační metody. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice Theorem (Cauchyova věta) Nechť A = (aij ), B = (bij ) jsou čtvercové matice dimenze n nad okruhem skalárů K. Pak |A · B| = |A| · |B|. Časem uvidíme, že skutečně stejně jako v dimenzi dva je determinant matice roven orientovanému objemu rovnoběžnostěnu určeného jejími sloupci. Uvidíme časem také, že když uvážíme zobrazení x → A · x zadané čtvercovou maticí A na Rn, pak můžeme determinant této matice vidět jako vyjádření poměru mezi objemem rovnoběžnostěnů daných vektory x1, . . . xn a jejich obrazy A · x1, . . . , A · xn. Protože skládání zobrazení x → A · x → B · (A · x) odpovídá násobení matic, je Cauchyova věta snad docela pochopitelná. My tuto větu odvodíme ryze algebraicky jako docela jednoduchý důsledek tzv. Laplaceovy věty o rozvoji. Ta bude vyžadovat něco málo přípravy. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice Definition (Minory a algebraické doplňky matice) Nechť A = (aij ) je matice typu m/n a 1 ≤ i1 < . . . < ik ≤ m, 1 ≤ j1 < . . . < jl ≤ n jsou pevně zvolená přirozená čísla. Pak matici M =    ai1j1 ai1j2 . . . ai1j ... ... aik j1 aik j2 . . . aik j    typu k/ nazýváme submaticí matice A určenou řádky i1, . . . , ik a sloupci j1, . . . , j . Zbývajícími (m − k) řádky a (n − l) sloupci je určena matice M∗ typu (m − k)/(n − ), která se nazývá doplňková submatice k M v A. Při k = je definován |M|, který nazýváme subdeterminant nebo minor řádu k matice A. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice Definition (Minory a algebraické doplňky matice - pokračování) Je-li m = n, pak při k = je i M∗ čtvercová a |M∗| se nazývá doplněk minoru |M|, nebo doplňkový minor k submatici M v matici A. Skalár (−1)i1+···+ik +j1+···+jl · |M∗ | se nazývá algebraický doplněk k minoru |M|. Submatice tvořené prvními k řádky a sloupci se nazývají hlavní submatice, jejich determinanty hlavní minory matice A. Při speciální volbě k = = 1, m = n hovoříme o algebraickém doplňku Aij prvku aij matice A. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice Lemma Nechť A je čtvercová matice dimenze n a |M| je její minor řádu k < n. Pak součin libovolného členu |M| s libovolným členem jeho algebraického doplňku je členem |A|. Toto tvrzení už podbízí představu, že by se pomocí takových součinů menších determinantů skutečně mohl determinant matic vyjadřovat. Víme, že |A| obsahuje právě n! různých členů, právě jeden pro každou permutaci. Tyto členy jsou navzájem různé jakožto polynomy v prvcích (neznámé obecné) matice A, přitom lze pro každý z členů zvolit matici A takovou, že pouze tento člen bude nenulový. Uvažované součiny |M| · |M∗| obsahují právě n! různých členů z |A| a proto takto musí být vyjádřen právě det A. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice Tím jsme naznačili důkaz věty: Theorem (Laplaceova věta) Nechť A = (aij ) je čtvercová matice dimenze n nad libovolným okruhem skalárů a nechť je pevně zvoleno k jejích řádků. Pak |A| je součet všech n k součinů (−1)i1+···+ik +j1+···+jl · |M| · |M∗| minorů řádu k vybraných ze zvolených řádků, s jejich algebraickými doplňky. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice Laplaceův rozvoj determinantu Laplaceova věta převádí výpočet |A| na výpočet determinantů nižšího stupně. Této metodě výpočtu se říká Laplaceův rozvoj podle zvolených řádků či sloupců. Např. rozvoj podle i-tého řádku nebo i-tého sloupce: |A| = n j=1 aij Aij = n j=1 aji Aji kde Aij označuje algebraický doplněk k prvku (minoru stupně 1) aij . Při praktickém počítání determinantů bývá výhodné kombinovat Laplaceův rozvoj s přímou metodou přičítání lineárních kombinací řádků či sloupců. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice Důkaz Cauchyovy věty |A · B| = |A| · |B| Uvažme matici H dimenze 2n (používáme tzv. blokovou symboliku, tj. píšeme matici jakoby složenou z matic) H = A 0 −E B = Laplaceovým rozvojem podle prvních n řádků obdržíme |H| = |A| · |B|. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice Důkaz Cauchyovy věty |A · B| = |A| · |B| Nyní budeme k posledním n sloupcům H postupně přičítat lineární kombinace prvních n sloupců tak, abychom obdrželi matici s nulami v pravém dolním rohu. Dostaneme K = A A · B −E 0 . Dostáváme tedy |H| = |K| = (−1)n+1+···+2n |A · B| = (−1)2n·(n+1) · |A · B| = |A · B|. Vektory Matice nad skaláry Lineární závislost Determinanty Věty Cauchyova a Laplaceova Inverzní matice Předpokládejme nejprve, že existuje matice inverzní k matici A, tj. A · A−1 = E. Protože pro jednotkovou matici platí vždy |E| = 1, je pro každou invertibilní matici vždy |A| invertibilní skalár a platí |A|−1 = |A−1|. Pro libovolnou čtvercovou matici A = (aij ) dimenze n definujeme matici A∗ = (a∗ ij ), kde a∗ ij = Aji jsou algebraické doplňky k prvkům aji v A. Nazýváme ji algebraicky adjungovaná matice k matici A. Theorem Pro každou čtvercovou matici A nad okruhem skalárů K platí AA∗ = A∗ A = |A| · E. Zejména tedy 1 A−1 existuje jako matice nad okruhem skalárů K právě, když |A|−1 existuje v K. 2 Pokud existuje A−1, pak platí A−1 = |A|−1 · A∗.