Permutace a pořadí Determinanty Determinant a inverzní matice Drsná matematika I ­ 6. praktická přednáška Determinanty Jan Slovák Masarykova univerzita Fakulta informatiky 29. 3. 2010 Permutace a pořadí Determinanty Determinant a inverzní matice Plán přednášky 1 Permutace a pořadí 2 Determinanty 3 Determinant a inverzní matice Permutace a pořadí Determinanty Determinant a inverzní matice Pro R2 je determinant matice A zobrazení det A = a b c d = ad - bc. Prozrazuje např., jestli umíme najít inverzi k A. Vzorec lze číst tak, že postupně sestavíme pořadí, ve kterém bereme prvky ze sloupců po jednotlivých řádcích, opatříme znaménkem a vše sečteme. Stejně budeme činit pro vyšší dimenze. Permutace a pořadí Determinanty Determinant a inverzní matice Bijektivní zobrazení množiny X na sebe se nazývá permutace množiny X. Berme X = {1, 2, . . . , n} a pišme permutace pomocí výsledného pořadí ve formě tabulky: 1 2 . . . n (1) (2) . . . (n) . Permutace a pořadí Determinanty Determinant a inverzní matice Bijektivní zobrazení množiny X na sebe se nazývá permutace množiny X. Berme X = {1, 2, . . . , n} a pišme permutace pomocí výsledného pořadí ve formě tabulky: 1 2 . . . n (1) (2) . . . (n) . Transpozice je taková permutace, že existují právě dva různé prvky x, y X s (x) = y a (z) = z pro všechna ostatní z X. Cyklus je permutace, ve které se jejím opakováním každý prvek postupně dostane na všechny pozice. Každá permutace je složením cyklů, každý cyklus je složením transpozic. Permutace a pořadí Determinanty Determinant a inverzní matice Bijektivní zobrazení množiny X na sebe se nazývá permutace množiny X. Berme X = {1, 2, . . . , n} a pišme permutace pomocí výsledného pořadí ve formě tabulky: 1 2 . . . n (1) (2) . . . (n) . Transpozice je taková permutace, že existují právě dva různé prvky x, y X s (x) = y a (z) = z pro všechna ostatní z X. Cyklus je permutace, ve které se jejím opakováním každý prvek postupně dostane na všechny pozice. Každá permutace je složením cyklů, každý cyklus je složením transpozic. Parita (znaménko) permutace je dána sudým nebo lichým počtem transpozic, ze kterých se skládá. Permutace a pořadí Determinanty Determinant a inverzní matice Příklad 1. Napište permutaci P = 1 2 3 4 5 3 1 2 5 4 jako složení transpozic. Je tato permutace sudá nebo lichá? Permutace a pořadí Determinanty Determinant a inverzní matice Plán přednášky 1 Permutace a pořadí 2 Determinanty 3 Determinant a inverzní matice Permutace a pořadí Determinanty Determinant a inverzní matice Pro matici A = (aij ) dimenze n nad K je její determinant skalár det A = |A| |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 je její paritou. Permutace a pořadí Determinanty Determinant a inverzní matice Pro matici A = (aij ) dimenze n nad K je její determinant skalár det A = |A| |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 je její paritou. Každý z výrazů sgn()a1(1) a2(2) an(n) nazýváme člen determinantu |A|. Permutace a pořadí Determinanty Determinant a inverzní matice 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. Permutace a pořadí Determinanty Determinant a inverzní matice 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. Permutace a pořadí Determinanty Determinant a inverzní matice 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á. Permutace a pořadí Determinanty Determinant a 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ů. Permutace a pořadí Determinanty Determinant a 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: |A| = a11 a22 ann. To dává efektivní metodu výpočtu determinantů pomocí Gaussovy eliminační metody. Příklad 2. Spočtěte několik determinantů volně zvolených matic metodou převedení na schodovitý tvar. Permutace a pořadí Determinanty Determinant a inverzní matice Cauchyova věta Theorem Nechť A = (aij ), B = (bij ) jsou čtvercové matice dimenze n nad okruhem skalárů K. Pak |A B| = |A| |B|. Příklad 3. Spočtěte pomocí Cauchyovy věty, jak mění hodnotu determinantu elementární úpravy matic. Příklad 4. Spočtěte bez Caychyovy věty i s ní determinant součinu dvou volně vybraných matic 3x3. Permutace a pořadí Determinanty Determinant a 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 . Permutace a pořadí Determinanty Determinant a 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. Permutace a pořadí Determinanty Determinant a 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. Permutace a pořadí Determinanty Determinant a 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. Permutace a pořadí Determinanty Determinant a inverzní matice Laplaceova věta Theorem 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. Permutace a pořadí Determinanty Determinant a 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ů. Permutace a pořadí Determinanty Determinant a inverzní matice Příklad 5. Spočtěte několik determintů matic metodou Laplaceova rozvoje, resp. kombinací s eliminací. Permutace a pořadí Determinanty Determinant a inverzní matice Plán přednášky 1 Permutace a pořadí 2 Determinanty 3 Determinant a inverzní matice Permutace a pořadí Determinanty Determinant a inverzní matice 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. Permutace a pořadí Determinanty Determinant a inverzní matice 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. Permutace a pořadí Determinanty Determinant a inverzní matice Příklad 6. Ověřte existenci inverzní matice pro konkrétní příklady nad okruhy skalárů Zp a Z.