[1]
BI-LIN, determinant, 9, P. Olsˇa´k
[2]
Definice determinantu Definice: Necht’ A = (ai,j ) ∈ Rn,n je cˇtvercova´ matice. Cˇ´ıslo
∑
Determinant
sgn π ⋅ a1,i1 a2,i2 · · · an,in
permutace π =(i1 ,i2 ,...,in )
nazy´va´me determinantem matice A a znacˇ´ıme je det A. Pozna´mka: Abychom tomu vzorci porozumneˇli a doka´zali z neˇj odvodit za´kladnı´ vlastnosti determinantu˚, potrˇebujeme si prˇipomenout vlastnosti permutacı´. . .
• je cˇ´ıslo jisty´m zpu˚sobem charakterizujı´cı´ cˇtvercovou matici • det A = 0 pro singula´rnı´ matici, det A 6= 0 pro regula´rnı´ matici • pouzˇ´ıva´ se prˇi rˇesˇenı´ linea´rnı´ch soustav • . . . a v mnoha dalsˇ´ıch aplikacı´ch
a) determinant, 9, b) P. Olsˇa´k, FEL CˇVUT, c) P. Olsˇa´k 2010, d) BI-LIN, e) L, f) 2009/2010, g)
L
. Viz p. d. 4/2010
BI-LIN, determinant, 9, P. Olsˇa´k
[3]
BI-LIN, determinant, 9, P. Olsˇa´k
Permutace
Permutace, vlastnosti
Permutace n prvku˚ je usporˇa´dana´ n-tice cˇ´ısel z mnozˇiny {1, 2, . . . , n}, prˇitom kazˇde´ cˇ´ıslo je v n-tici zastoupeno pra´veˇ jednou.
• Skla´da´nı´m permutacı´ (jako zobrazenı´) dosta´va´me permutaci.
Prˇ´ıklad: (3, 1, 2, 5, 4) je permutace peˇti prvku˚. (i1, i2 , . . . , in) je permutace z n prvku˚, pokud ij ∈ {1, 2, . . . , n} a ij 6= ik pro j 6= k. Jiny´ pohled: Permutace je bijektivnı´ zobrazenı´ na {1, 2, . . . , n}. Vztah mezi teˇmito pohledy: Je-li da´na n-tice (i1 , i2, . . . , in), pak je da´no zobrazenı´ z : {1, 2, . . . , n} → {1, 2, . . . , n} prˇedpisem z(j) = ij . Je-li da´no zobrazenı´ z, pak lze sestrojit n-tici (z(1), z(2), . . . , z(n)).
• Genericka´ (jednotkova´) permutace je (1, 2, . . . , n). • Kazˇda´ permutace ma´ svou inverznı´ permutaci. • Pocˇet permutacı´ n prvku˚ je n! .
[4]
BI-LIN, determinant, 9, P. Olsˇa´k
[5]
BI-LIN, determinant, 9, P. Olsˇa´k
[6]
Zname´nko permutace
Prˇechod suda´ – licha´
inverze v permutaci (i1 , i2 , . . . , in) je vy´skyt jevu:
Prohozenı´ dvou prvku˚ v permutaci zmeˇnı´ zname´nko permutace.
ij > ik a soucˇasneˇ j < k.
Du˚kaz: V na´sledujı´cı´ permutaci prohodı´m prvky x a y:
Prˇ´ıklad: inverze permutace (3, 1, 2, 5, 4) jsem vyznacˇil pomocı´ obloucˇku˚: zz { { z { (3, 1, 2, 5, 4) Tato permutace ma´ trˇi inverze.
Definice: Ma´-li permutace π sudy´ pocˇet inverzı´, je sgn π = +1, ma´-li π lichy´ pocˇet inverzı´, je sgn π = −1. Cˇ´ıslu sgn π rˇ´ıka´me zname´nko permutace.
(. . . prvky vlevo . . . , x, . . . prvky uvnitrˇ . . . , y, . . . prvky vpravo . . .) Inverze, ktere´ nenavazujı´ na prvek x nebo y zu˚sta´vajı´ nezmeˇneˇny. Inverze mezi prvky vlevo a x nebo y zu˚sta´vajı´ nezmeˇneˇny. Inverze mezi x nebo y a prvky vpravo zu˚sta´vajı´ nezmeˇneˇny. Inverze mezi x nebo y a prvky uvnitrˇ po dvou vznikajı´ nebo zanikajı´ nebo se nemeˇnı´. Inverze mezi x a y vznikne nebo zanikne. Du ˚ sledek: Zname´nko permutace pozna´me podle pocˇtu transpozic (jednoho prohozenı´ dvou prvku˚), ktere´ je potrˇeba na permutaci prove´st, aby byla prˇevedena na generickou permutaci.
Prˇ´ıklad: sgn(3, 1, 2, 5, 4) = −1. Zname´nko genericke´ permutace je +1. Cvicˇenı´: jake´ zname´nko ma´ permutace (n, n − 1, . . . , 3, 2, 1)?
BI-LIN, determinant, 9, P. Olsˇa´k
[7]
Na´vrat k definici deterinantu Definice: Necht’ A = (ai,j ) ∈ Rn,n je cˇtvercova´ matice. Cˇ´ıslo det A =
∑
sgn π ⋅ a1,i1 a2,i2 · · · an,in
permutace π =(i1 ,i2 ,...,in )
• Uzˇitecˇna´ je prˇedstava sˇachovy´ch veˇzˇ´ı.
BI-LIN, determinant, 9, P. Olsˇa´k
Determinant hornı´ troju ´ helnı´kove´ matice
a1,1 , a1,2 , . . . , a1,n−1, 0, a2,2 , . . . , a2,n−1, det 0, 0, . . . , a3,n−1, ... 0, 0, ..., 0,
a1,n a2,n a3,n
an,n
• Prˇ´ıklad pro matice typu (1, 1), (2, 2), (3, 3) . . . Sarrusovo pravidlo.
je roven soucˇinu prvku˚ na diagona´le: a1,1 ⋅ a2,2 ⋅ a3,3 · · · an,n.
• Pozor, pro matice veˇtsˇ´ıch typu˚ Sarrusovo pravidlo nelze pouzˇ´ıt!
Vidı´ vsˇichni procˇ?
[8]
[9]
BI-LIN, determinant, 9, P. Olsˇa´k
BI-LIN, determinant, 9, P. Olsˇa´k
[10]
Za´kladnı´ vlastnosti determinantu
Metoda vy´pocˇtu determinantu
• Prohozenı´ rˇa´dku˚ zmeˇnı´ zname´nko determinantu
Algoritmus: Eliminacı´ prˇevedeme danou matici A na hornı´ troju´helnı´kovou matici U. Pokud beˇhem eliminace pouzˇijeme prvnı´ nebo druhy´ typ kroku eliminace, je potrˇeba si poznamenat, jak se zmeˇnil determinant. Trˇetı´ typ kroku nemeˇnı´ determinant vu˚bec. Konecˇneˇ det U je soucˇin prvku˚ na diagona´le.
• Matice se dveˇma stejny´mi rˇa´dky ma´ nulovy´ determinant • Prona´sobenı´ jedine´ho rˇa´dku α -kra´t zveˇtsˇ´ı α -kra´t i determinant • Je-li jeden rˇa´dek zapsany´ jakou soucˇet dvou cˇa´stı´, pak determinat takove´ matice je roven soucˇtu determinantu˚ matic, ve ktery´ch jsou mı´sto tohoto rˇa´dku jen jeho cˇa´sti: . . ... .. .. − → − → − → − → det a i + det b i = det a i + b i . ... ... ...
Slozˇitost algoritmu: n3. Vy´razna´ u´spora proti vzorci v definici, ktery´ ma slozˇitost n! .
• Trˇetı´ typ kroku eliminacˇnı´ metody nezmeˇnı´ determinant.
BI-LIN, determinant, 9, P. Olsˇa´k
[11]
BI-LIN, determinant, 9, P. Olsˇa´k
[12]
ˇ a´dky a sloupce jedno jest R
Prˇı´klad
Tvrzenı´: det A = det AT . 1 2 4 3
2 3 3 1 2 4 1 4 0 0 = 2 1 2 0 −6 0 −5 1 2 1 1 2 3 1 0 6 11 6 0 0 5 0 30 42 1 2 3 1 1 0 6 11 ⋅ 6 5 0 0 5 0 0 −65
1 3 3 −5 −2 4 0 = (−1) 0 −11 −10 0 −7 −8 1 2 3 3 10 1 0 6 11 = 2 6 0 0 5 0 0 −13 48 1 2 3 3 1 0 6 11 10 = 2 30 0 0 5 0 0 0 −10
2 6 0 5
3 11 5 7
3 10 = 2 8
3 10 = 2 −2 3 10 = 16. 2 16
Za chvı´li uvidı´me, zˇe to lze spocˇ´ıtat jednodusˇeji. . .
Du˚kaz: Ma´m permutaci (i1 , i2 , . . . , in) a podle nı´ provedu sloupcovy´ vy´beˇr prvku˚ matice a vyna´sobı´m mezi sebou: ai1,1 ⋅ ai2,2 · · · ain ,n = a1,j1 ⋅ a2,j2 · · · an,jn Soucˇin rea´lny´ch cˇ´ısel je komutativnı´, tak jsem cˇinitele usporˇa´dal podle velikosti rˇa´dkove´ho indexu. Jaky´ je vztah mezi permutacemi: (i1 , i2, . . . , in) a (j1 , j2 , . . . , jn)? Jsou si vza´jmneˇ inverznı´. A inverznı´ permutace majı´ stejne´ zname´nko. Takzˇe vzorce s rˇa´dkovy´m i sloupcovy´m vy´beˇrem da´vajı´ stejny´ vy´sledek. Du ˚ sledek: Prˇi eliminaci za u´cˇelem vy´pocˇtu determinantu lze libovolneˇ prˇecha´zet mezi rˇa´dkovy´mi a sloupcovy´mi u´pravami.
BI-LIN, determinant, 9, P. Olsˇa´k
[13]
BI-LIN, determinant, 9, P. Olsˇa´k
Regula´rnı´ a singula´rnı´ matice
Determinant soucˇinu matic
Veˇta: Matice A je regula´rnı´, pra´veˇ kdyzˇ det A 6= 0.
Veˇta: Pro dveˇ cˇtvercove´ matice typu (n, n) platı´
Du˚kaz: A je regula´rnı´ pra´veˇ kdyzˇ A ∼ E. Da´le si stacˇ´ı uveˇdomit, zˇe Gaussova eliminace nemeˇnı´ nulovost determinantu.
[14]
det(A ⋅ B) = (det A) ⋅ (det B). Du˚kaz*: Lze prove´st A ∼ U1 rˇa´dkovy´mi eliminacˇnı´mi u´pravami, aby se nezmeˇnil determinant. Da´le lze prˇeve´st B na U2 sloupcovy´mi eliminacˇnı´mi u´pravami tak, zˇe se nezmeˇnı´ determinant. Snadno se uka´zˇe, zˇe det(U1 ⋅ U2) = (det U1) ⋅ (det U2) Existujı´ matice P1 , P2 tak, zˇe U1 = P1 A, U2 = BP2 . Stejne´ rˇa´dkove´ i sloupcove´ u´pravy provedeme na A ⋅ B, tedy P1 A ⋅ BP2 = U1 ⋅ U2 . ´ pravy nemeˇnı´ determinant, takzˇe U det(A ⋅ B) = det(P1A ⋅ BP2 ) = det(U1 ⋅ U2) = = (det U1) ⋅ (det U2 ) = (det A) ⋅ (det B).
BI-LIN, determinant, 9, P. Olsˇa´k
[15]
BI-LIN, determinant, 9, P. Olsˇa´k
[16]
Du ˚ sledky veˇty o determinantu soucˇinu
Rozvoj determinantu podle rˇa´dku
• det A−1 = 1/ det A
Terminologie: Vyrˇadı´me-li ze cˇtvercove´ matice A ∈ Rn,n i-ty´ rˇa´dek a j-ty´ sloupec, dosta´va´me matici Ai,j ∈ Rn−1,n−1. Cˇ´ıslo
• Je-li A = LU rozklad matice A, pak det A = det U, tedy det A je roven soucˇinu diagona´lnı´ch prvku˚ v matici U. (prˇipomı´na´m, zˇe matice L ma´ na diagona´le jednicˇky).
Di,j = (−1)i+j det Ai,j se nazy´va´ doplneˇk matice A v pozici (i, j). Veˇta o rozvoji: Necht’ Di,j jsou doplnˇky cˇtvercove´ matice A = (ai,j ). Pak platı´ det A = ar,1 Dr,1 + ar,2 Dr,2 + · · · + ar,n Dr,n. Na´znak du˚kazu: vytkneˇte ze soucˇtu z definice determinantu ar,1 (jen z teˇch scˇ´ıtancu˚, kde se ar,1 vyskytuje), da´le vytkneˇte ar,2 atd. azˇ ar,n. V za´vorka´ch po vytknutı´ dostanete Dr,i.
BI-LIN, determinant, 9, P. Olsˇa´k
[17]
Rozjı´ma´nı´ nad veˇtou o rozvoji
BI-LIN, determinant, 9, P. Olsˇa´k
Prˇı´klad
• Protozˇe det A = det AT , platı´ analogicka´ veˇta o rozvoji podle sloupce
1 2 4 3
• Je-li v rˇa´dku/sloupci hodneˇ nul, je v soucˇtu podle veˇty o rozvoji hodneˇ nulovy´ch scˇ´ıtancu˚. Stacˇ´ı zapsat jen ty nenulove´ a redukovat vy´pocˇet determinantu matice typu (n, n) na neˇkolik (ma´lo) determinantu˚ matic typu (n − 1, n − 1). • Pozor: rekurzivnı´ vola´nı´ vy´pocˇtu determinantu podle veˇty o rozvoji ma´ slozˇitost n!, takzˇe tento algoritmus je nepouzˇitelny´. • Du˚sledkem veˇty o rozvoji je tvrzenı´: 0 = ar,1 Dk,1 + ar,2 Dk,2 + · · · + ar,n Dk,n
[18]
2 3 4 1 2 1 1 2 2 − 2 −1
3 1 2 3 1 2 4 1 4 2 4 1 0 = = − 4 2 1 = 2 4 2 1 0 3 1 2 1 3 1 2 0 4 1 1 −1 = 2 ⋅ 8 = 16. −2 0 = 2 1 7 −7 0
pro r 6= k.
Stacˇ´ı prove´st veˇtu o rozvoji na matici se dveˇma stejny´mi rˇa´dky. • Veˇta o rozvoji ma´ rˇadu dalsˇ´ıch teoreticky´ch du˚sledku˚, neˇktere´ se dozvı´me pozdeˇji. . .
BI-LIN, determinant, 9, P. Olsˇa´k
[19]
BI-LIN, determinant, 9, P. Olsˇa´k
Inverznı´ matice pomocı´ dopln ˇ ku ˚
Prˇı´klad: inverze k matici typu (2, 2)
Je-li A ∈ Rn,n regula´rnı´, pak
Je da´na matice
A−1
1 = DT , det A
kde D = (Di,j) je matice doplnˇku˚ A v pozicı´ch (i, j). Du˚kaz: Oveˇrˇ´ıme, zˇe AA−1 = E. Oznacˇ´ıme A = (ai,j ), DT = (Dk,j ), E = (ei,k). n
ei,k = ∑ ai,j j=1
1 1 Dk,j = (ai,1Dk,1 + ai,2Dk,2 + · · · + ai,nDk,n) = det A det A
1 det A = 1 pro i = k, det A = 1 ⋅0=0 pro i 6= k. det A
Vyuzˇili jsme veˇtu o rozvoji determinantu podle i-te´ho rˇa´dku.
A=
a c
Matice doplnˇku˚ k te´to matici je d D= −b Takzˇe A−1 =
b d
−c a
1 1 DT = det A ad − bc
d −c
−b a
.
[20]
BI-LIN, determinant, 9, P. Olsˇa´k
Prˇı´klad: inverze matice pomocı´ dopln ˇ ku ˚
1 Je da´na matice A = −1 2 Matice doplnˇku˚ je: −1 0 1 + − 2 1 2 2 3 1 D= − 2 1 + 2 2 3 − 1 + −1 0 1
takzˇe:
det A = −2,
3 1. 1
2 0 2
−1 0 + 2 2 −2 3 −2 1 2 = 4 −5 − 2, 2 2 2 −4 2 1 2 + −1 0 −2 4 2 1 1 DT = − 3 −5 −4 . = det A 2 −2 2 2
1 1 3 1 3 1
A−1
[21]
