Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty Matematika I – 5a Vektory, matice, determinanty Jan Slovák Masarykova univerzita, Fakulta informatiky 15. 10. 2012 Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty Definition Symbolem K budeme nadále značit nějakou množinu skalárů. 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). Jako skaláry budeme uvažovat číslené obory Z, Q, R, C, případně i zbytkové třídy Zk. Pro sčítání vektorů v Kn zjevně platí (KG1)–(KG4) s nulovým prvkem 0 = (0, . . . , 0) ∈ Kn . Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty Konvence značení Schválně používáme pro nulový prvek stejný symbol jako u skalárů. 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 často žádné speciální značení, a ponechá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). Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty 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, . . .. Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty 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. Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty 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. Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty 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). Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty 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. Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty 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í. Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty 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 Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty Č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). Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty 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 Ekvivalentní úpravy matic Determinanty 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. Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty 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. Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty 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 Ekvivalentní úpravy matic Determinanty 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á Gaussova eliminace proměnných. Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty 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 Ekvivalentní úpravy matic Determinanty 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. Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty Algoritmus 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ů. 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 hledané inverzi. Pokud tento algoritmus narazí na vynulování celého řádku v původní matici, znamená to, že matice inverzní neexistuje. Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty 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 Ekvivalentní úpravy matic Determinanty 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 Ekvivalentní úpravy matic Determinanty ř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í. Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty V rovině R2 jsme pracovali s maticemi lineárních zobrazení a determinant matice A det A = a b c d = ad − bc prozrazoval, jestli umíme najít inverzi k A. Determinant byl užitečný i jinak: obsah rovnoběžníka by měl být lineárně závislý na každém ze dvou vektorů definujících rovnoběžník a je užitečné zároveň požadovat změnu znaménka při změně pořadí těchto vektorů. Protože tyto vlastnosti měl, až na pevný skalární násobek, jedině determinant, odvodili jsme, že je obsah dán právě takto. Nyní uvidíme, že podobně lze se skalárními funkcemi z matic do skalárů postupovat v každé konečné dimenzi. Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty Budeme pracovat s libovolnými skaláry K a maticemi nad těmito skaláry (např. Z, Q, R, C, Zk). Připomeňme, že bijektivní zobrazení množiny X na sebe se nazývá permutace množiny X. Je-li X = {1, 2, . . . , n}, lze permutace zapsat pomocí výsledného pořadí ve formě tabulky: 1 2 . . . n σ(1) σ(2) . . . σ(n) . Prvek x ∈ X se nazývá samodružným bodem permutace σ, je-li σ(x) = x. Permutace σ taková, že existují právě dva různé prvky x, y ∈ X s σ(x) = y a σ(z) = z pro všechna ostatní z ∈ X se nazývá transpozice, značíme ji (x, y). Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty V dimenzi dva byl vzorec pro determinant jednoduchý – vezmeme všechny možné součiny dvou prvků, po jednom z každého sloupce a řádku matice, opatříme je znaménkem tak, aby při přehození dvou sloupců došlo ke změně celkového znaménka, a výrazy všechny sečteme: A = a b c d , det A = ad − bc. 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 Ekvivalentní úpravy matic Determinanty Jednoduché příklady už umíme: je-li n = 1, pak |a11| = a11 ∈ K, a pro n = 2 je a11 a12 a21 a22 = +a11a22 − a12a21. Podobně pro n = 3 se dá uhodnout (chceme linearitu v každém sloupci a antisymetrii) a11 a12 a13 a21 a22 a23 a31 a32 a33 = + a11a22a33 − a13a22a31 + a13a21a32 − a11a23a32 + a12a23a31 − a12a21a33. Tomuto vzorci se říká Saarusovo pravidlo. Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty 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 Ekvivalentní úpravy matic Determinanty 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 2n! sudých a 1 2n! 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 Ekvivalentní úpravy matic Determinanty 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 Ekvivalentní úpravy matic Determinanty 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 Ekvivalentní úpravy matic Determinanty Výpočet determinantů Metoda Gaussovy eliminace 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. Pozor jen, že se smí pouze k nepozměněnému řádku přičítat lineární kombinace ostatních! Vektory Matice nad skaláry Ekvivalentní úpravy matic Determinanty Výpočet determinantů Rozvoj podle řádku či sloupce Algebraickým doplňkem Aij prvku aij matice A = (aij ) rozumíme determinant matice vzniklé z A vypuštěním i–tého řádku a j–tého sloupce, opatřený znaménkem (−1)i+j . Laplaceův rozvoj podle zvoleného i-tého řádku nebo i-tého sloupce je |A| = n j=1 aij Aij = n j=1 aji Aji . Cauchyova věta Nechť A = (aij ), B = (bij ) jsou čtvercové matice dimenze n nad okruhem skalárů K. Pak |A · B| = |A| · |B|.