Matematick´y ustav ´ Slezske´ univerzity v Opaveˇ Uˇcebn´ı texty k pˇrednaˇ ´ sce ALGEBRA I, zimní semestr 2000/2001 Michal Marvan
6. Matice. Algebraick´e vlastnosti 1. Algebraick´e operace s maticemi Definice. Bud’te A, B matice jednoho a t´ehoˇz typu r/s nad polem P. Jejich souˇcet je matice A + B t´ehoˇz typu r/s, dan´a pˇredpisem (A + B)i j = Ai j + Bi j pro kaˇzd´e i = 1, . . . , r a j = 1, . . . , s. D´ale definujeme c-n´asobek matice A, kde c je libovoln´y prvek pole P, jako matici c A typu r/s danou pˇredpisem (c A)i j = c Ai j pro kaˇzd´e i = 1, . . . , r a j = 1, . . . , s. Pˇr´ıklad. Necht’ A=
1
−3
4 −1
2
Pak
A+B =
2
1
8
4 −1
,
B= 4
−2
11
2
2
−5
−1
,
2B =
0
.
0
22
4
4
−10
−2
.
Definice. Nulov´a matice je matice 0 sloˇzen´a ze sam´ych nul. Matice (−1)A se znaˇc´ı −A a naz´yv´a se matice opaˇcn´a k matici A. Tvrzen´ı. Necht’ jsou A, B, C matice nad polem P. Pak plat´ı (1)
A + B = B + A,
(5) 1A = A,
(2)
A + (B + C) = (A + B) + C,
(6) c(A + B) = c A + cB,
(3)
A + 0 = A,
(7) (c + k)A = c A + k A,
(4)
A + (−A) = 0,
(8) c(k A) = (ck)A,
pokud jsou vˇsechny naznaˇcen´e operace definov´any. Dukaz. ˚ (1) (A + B)i j = Ai j + Bi j = Bi j + Ai j = (B + A)i j . (2) – (8) Cviˇcen´ı.
6. Matice. Algebraick´e vlastnosti
Mnoˇzinu vˇsech matic typu r/s nad polem P oznaˇcme Mr s (P). Podle (1) – (4) z pˇredchoz´ıho tvrzen´ı, Mr s (P) je abelovsk´a grupa. [Jak uvid´ıme pozdˇeji, axiomy (1) – (8) ˇr´ıkaj´ı, zˇ e Mr s (P) je vektorov´y prostor nad polem P.] Zav´ad´ıme i souˇcin A · B dvou matic, m´a-li matice A pr´avˇe tolik sloupc˚u, kolik m´a B ˇra´ dk˚u. V´ysledkem je matice C = A · B, kter´a m´a stejn´y poˇcet ˇra´ dk˚u jako matice A a stejn´y poˇcet sloupc˚u jako matice B. Prvek Ckl na pr˚useˇc´ıku k-t´eho ˇra´ dku a l-t´eho sloupce dostaneme tak, zˇ e po ˇradˇe n´asob´ıme mezi sebou prvky k-t´eho ˇra´ dku matice A a prvky l-t´eho sloupce matice B a vznikl´e souˇciny (v poˇctu s) seˇcteme: Definice. Bud’ A matice typu r/s, bud’ B matice typu s/t nad polem P, Jejich souˇcin je matice A · B typu r/t dan´a pˇredpisem (A · B)kl
=
Ak1 B1l + Ak2 B2l + · · · + Aks Bsl
s
=
Aki Bil .
i=1
Znam´enko ,, · “ cˇ asto vynech´av´ame a p´ısˇeme jednoduˇse AB. Souˇcin matic pˇredstavuje zobrazen´ı Mr s × Mst → Mr t . Pˇr´ıklad. Necht’ A=
1
1
0
0
Pak C = AB =
,
B=
0
2
0
0
0
1
0
1
.
,
protoˇze C11 = A11 B11 + A12 B21 = 1·0+1·0 = 0, podobnˇe C12 = A11 B12 + A12 B22 = 1·1+1·1 = 2, atd. V obr´acen´em poˇrad´ı BA =
0
0
0
0
.
M˚uzˇ e se tedy st´at, zˇ e oba souˇciny AB a B A existuj´ı, a pˇresto si nejsou rovny. Tud´ızˇ , n´asoben´ı matic obecnˇe nen´ı komutativn´ı. D´ale je vidˇet, zˇ e souˇcin nenulov´ych matic m˚uzˇ e b´yt nulov´a matice. ˇ Definice. Ctvercov´ a matice je matice typu n/n, tj. matice, kter´a m´a stejn´y poˇcet ˇra´ dk˚u jako sloupc˚u. Souˇcin takov´ych matic je zase cˇ tvercov´a matice typu n/n. Tud´ızˇ , n´asoben´ı cˇ tvercov´ych matic je bin´arn´ı operace. 2
6. Matice. Algebraick´e vlastnosti
Definice. Jednotkov´a matice je cˇ tvercov´a matice tvaru
1 0 ··· 0
0 1 E =
Ei j =
.
· · · 0 ···
0 0 ··· 1
To jest,
1
kdyˇz i = j,
0
kdyˇz i = j.
Tvrzen´ı. Necht’ jsou A, B, C matice nad polem P. Pak plat´ı (9)
A(BC) = (AB)C,
(10)
AE = E A = A,
(11)
A(B + C) = AB + AC,
(12) (A + B)C = AC + BC, pokud jsou vˇsechny naznaˇcen´e operace definov´any. Podle (9) a (10) je Mnn (P) monoid vzhledem k operaci n´asoben´ı matic. Neutr´aln´ım prvkem je jednotkov´a matice. Dukaz. ˚ Dokaˇzme napˇr´ıklad identitu (11) za pˇredpokladu, zˇ e A je matice typu r/s a B, C jsou matice typu s/t. Matici na lev´e stranˇe oznaˇcme U , matici na prav´e stranˇe oznaˇcme V . Pak U i V jsou shodnˇe typu r/t a plat´ı Ukl =
s
Aki (B + C)il =
i=1
=
s
s
Aki (Bil + Cil ) =
i=1
Aki Bil +
i=1
s
s
(Aki Bil + Aki Cil )
i=1
Aki Cil = (AB)kl + (AC)kl = Vkl .
i=1
Ostatn´ı identity se dokazuj´ı analogicky. Jde o dobr´e cviˇcen´ı. 2. Inverzn´ı matice Budeme ˇreˇsit probl´em rozpozn´an´ı invertibiln´ıch prvk˚u v monoidu Mnn (P). ˇ Definice. Bud’ A cˇ tvercov´a matice typu n/n. Rekneme, zˇ e matice X je inverzn´ı k matici A, je-li t´ehoˇz typu n/n a plat´ı AX = X A = E. Znaˇc´ı se X = A−1 . Matice A se naz´yv´a invertibiln´ı, existuje-li matice k n´ı inverzn´ı. 3
6. Matice. Algebraick´e vlastnosti
K dan´e cˇ tvercov´e matici A existuje nejv´ysˇe jedna inverzn´ı matice [v libovoln´em monoidu existuje k dan´emu prvku nejv´ysˇe jeden prvek inverzn´ı]. Pˇr´ıklad: kaˇzd´a jednotkov´a matice je invertibiln´ı a plat´ı E −1 = E. Neinvertibiln´ı je napˇr´ıklad nulov´a matice (dokaˇzte). Invertibiln´ı nejsou ani matice A, B z posledn´ıho pˇr´ıkladu: Kdyby matice A mˇela inverzn´ı matici A−1 , pak bychom mˇeli B = B E = B(A A−1 ) = (B A)A−1 = 0A−1 = 0, spor. Podobnˇe pro B. Tvrzen´ı. Necht’ jsou A, B invertibiln´ı matice. (1) Pak je invertibiln´ı i matice AB a plat´ı (AB)−1 = B −1 A−1 ; (2) Invertibiln´ı je i matice A−1 a plat´ı (A−1 )−1 = A. Dukaz. ˚ Tvrzen´ı plat´ı v libovoln´em monoidu a byla jiˇz dok´az´ana. Dusledek. ˚ Invertibiln´ı matice tvoˇr´ı podgrupu v monoidu Mnn (P). Definice. Grupa invertibiln´ıch cˇ tvercov´ych matic se znaˇc´ı GLn (P). Naz´yv´a se obecn´a line´arn´ı grupa. Potˇrebujeme praktick´a kriteria pro invertibilitu matic. Jedno z nich je nalezeno n´ızˇ e, pˇritom tak´e dost´av´ame algoritmus, kter´y invertuje zadanou matici, pokud je invertibiln´ı. Kl´ıcˇ em k u´ spˇechu je Gauss˚uv–Jordan˚uv tvar a tzv. element´arn´ı matice. Definice. Element´arn´ı matice jsou cˇ tvercov´e matice jednoho z n´asleduj´ıc´ıch tvar˚u:
1 ··· 0 ··· 0 ··· 0
(i)
0 E i j (c) = 0
···
···
···
··· 1 ··· c ··· ···
···
···
··· 0 ··· 1 ··· ···
···
···
0 0
i
j
0 ··· 0 ··· 0 ··· 1
kde i = j, c = 0. Matice E i j (c) se od jednotkov´e matice liˇs´ı t´ım, zˇ e prvek E i j je roven c.
(ii)
1 ··· 0 ··· 0
··· E i (c) = 0 · · · ···
· · · 0 ···
···
c
i
0 ··· 0 ··· 1
kde c = 0. Matice E i (c) se od jednotkov´e matice liˇs´ı t´ım, zˇ e prvek E ii je roven c. 4
6. Matice. Algebraick´e vlastnosti
1 ··· 0 ··· 0 ··· 0
(iii)
0 Ei j = 0
···
···
···
··· 0 ··· 1 ··· ···
···
···
··· 1 ··· 0 ··· ···
···
···
0 0
i
j
0 ··· 0 ··· 0 ··· 1
kde i = j. Matice E i j se od jednotkov´e matice liˇs´ı t´ım, zˇ e i-t´y a j-t´y ˇra´ dek jsou vymˇenˇeny. Vˇsimnˇete si, zˇ e kaˇzd´a z element´arn´ıch matic E i j (c), E i (c), E i j vznikne z jednotkov´e matice E aplikac´ı jedn´e ze tˇr´ı element´arn´ıch ˇra´ dkov´ych u´ prav, popsan´ych v minul´e pˇredn´asˇce. Lemma. Bud’te A, A dvˇe matice t´ehoˇz typu. N´asleduj´ıc´ı v´yroky jsou ekvivalentn´ı: 1◦ matice A vznikne z A jednou z element´arn´ıch rˇa´ dkov´ych u´ prav; 2◦ existuje element´arn´ı matice Q takov´a, zˇe A = Q A. Dukaz. ˚ Element´arn´ı matice odpov´ıdaj´ı po ˇradˇe element´arn´ım u´ prav´am (i) pˇriˇcten´ı k i-t´emu ˇra´ dku c-n´asobku j-t´eho ˇra´ dku; (ii) vyn´asoben´ı i-t´eho ˇra´ dku prvkem c ∈ P \ {0}; (iii) v´ymˇena i-t´eho a j-t´eho ˇra´ dku. D˚ukaz se ve vˇsech tˇrech pˇr´ıpadech snadno provede pˇr´ım´ym v´ypoˇctem. Lemma. Element´arn´ı matice jsou vesmˇes invertibiln´ı a plat´ı (i) (E i (c))−1 = E i (c−1 ), (ii) (E i j (c))−1 = E i j (−c), (iii) (E i j )−1 = E i j . Dukaz. ˚ Cviˇcen´ı. Opˇet se vˇse snadno ovˇeˇr´ı pˇr´ım´ym v´ypoˇctem. Nyn´ı zformulujeme d˚uleˇzit´e kriterium invertibility ˇ Tvrzen´ı. Ctvercov´ a matice A je invertibiln´ı pr´avˇe tehdy, kdyˇz je rˇa´ dkovˇe ekvivalentn´ı s jednotkovou matic´ı. Dukaz. ˚ ,,⇒“: Bud’ A matice, ˇra´ dkovˇe ekvivalentn´ı s jednotkovou matic´ı E. Pak existuje koneˇcn´a posloupnost ˇra´ dkov´ych u´ prav, kter´a pˇrevede A na E. Oznaˇcme Q 1 , Q 2 , . . . , Q k element´arn´ı matice, odpov´ıdaj´ıc´ı jednotliv´ym u´ prav´am. Pak Q k · · · Q 2 Q 1 A = E (v tomto poˇrad´ı!). Oznaˇcme Q = Q k · · · Q 2 Q 1 , m´ame pak Q A = E. Ovˇsem kaˇzd´a z matic Q 1 , Q 2 , . . . , Q k je invertibiln´ı, a proto je invertibiln´ı i jejich souˇcin (a plat´ı −1 −1 Q −1 = Q −1 uzˇ eme na obou stran´ach vyn´asobit zleva 1 Q 2 · · · Q k ). Rovnost Q A = E proto m˚ matic´ı Q −1 . Dost´av´ame A = Q −1 Q A = Q −1 E = Q −1 . Tud´ızˇ , A−1 = (Q −1 )−1 = Q a A je invertibiln´ı. 5
6. Matice. Algebraick´e vlastnosti
,,⇐“: Necht’je, naopak, A invertibiln´ı cˇ tvercov´a matice typu n/n. Pˇreved’me A ˇra´ dkov´ymi u´ pravami na Gauss˚uv–Jordan˚uv tvar B, takˇze A ∼ B. Rozezn´avejme dva pˇr´ıpady. 1. Necht’ bˇehem algoritmu nalezneme pr´avˇe n hlavn´ıch prvk˚u; ty pak nutnˇe vyplˇnuj´ı u´ hlopˇr´ıcˇ ku, jsou rovny 1 a nad nimi i pod nimi leˇz´ı nuly. To ovˇsem znamen´a, zˇ e B = E, takˇze A ∼ E, coˇz se mˇelo dok´azat. 2. Necht’ bylo nalezeno m´enˇe neˇz n hlavn´ıch prvk˚u, pak B je matice s nulov´ym posledn´ım ˇra´ dkem (proˇc?), naˇceˇz pro kaˇzdou matici X typu n/n je souˇcin B X zase matice s nulov´ym posledn´ım ˇra´ dkem (ovˇeˇrte). Nicm´enˇe, B = Q A, kde Q je souˇcin element´arn´ıch matic, a tedy B je t´ezˇ invertibiln´ı (je souˇcinem invertibiln´ıch matic), tj. existuje B −1 . Volba X = B −1 pak vede ke sporu, protoˇze B B −1 = E, ale E nem´a nulov´y posledn´ı ˇra´ dek. Navrhnˇeme postup, jak matici A−1 spoˇc´ıtat. Podle d˚ukazu pˇredchoz´ıho tvrzen´ı A−1 = Q = Q k · · · Q 2 Q 1 = Q k · · · Q 2 Q 1 E, coˇz je matice, kter´a vznikne z jednotkov´e matice E posloupnost´ı element´arn´ıch ˇra´ dkov´ych u´ prav, pˇr´ısluˇsn´ych element´arn´ım matic´ım Q 1 , Q 2 , . . . , Q k . Tedy tout´ezˇ posloupnost´ı, kter´a pˇrevedla A na E: A→E E → A−1 . Staˇc´ı tedy, aby se ˇra´ dkov´e u´ pravy, prov´adˇen´e s matic´ı A pˇri pˇrevodu na E, prov´adˇely souˇcasnˇe i s matic´ı E, a ta pak pˇrejde v Q = A−1 : Algoritmus (v´ypoˇcet inverzn´ı matice). Bud’ A cˇ tvercov´a matice typu n/n. Pˇripojme k A z prav´e strany jednotkovou matici E:
A11
A21
Ar 1
A12 · · ·
A1s
1 0 ··· 0
A22 · · ·
A2s
0 1 · · · 0
··· Ar 2 · · ·
··· Ar s
0 0 ··· 1
,
a v takto vznikl´e matici typu n/2n prov´adˇejme ˇra´ dkov´e u´ pravy, kter´e levou cˇ a´ st (tj. matici A) pˇrevedou na Gauss˚uv–Jordan˚uv tvar B. Potom: – jestliˇze B = E, pak A je invertibiln´ı a na prav´e stranˇe vyjde inverzn´ı matice A−1 ; – jestliˇze B obsahuje nulov´y ˇra´ dek, pak A nen´ı invertibiln´ı. Pˇr´ıklad. V´ypoˇcet inverzn´ı matice: 1 2 1 0 1 2 1 2 1 0 ∼ ∼ 3 4 0 1 0 −2 −3 1 0 1 Pˇr´ıklad. Neinvertibiln´ı pˇr´ıpad: 1 2 1 0 1 2 1 0 ∼ . 3 6 0 1 0 0 −3 1
6
1
0
3 2
− 12
∼
1
0
−2
1
0
1
3 2
− 12
.
6. Matice. Algebraick´e vlastnosti
Cviˇcen´ı. Invertujte matice i 1 , 2i i + 1 resp.
[2]5
[1]5
[3]5
[2]5
.
Cviˇcen´ı. P´ısmena ABCDEFGHIJKLMNOPQRSTUVWXYZ necht’maj´ı po ˇradˇe k´ody [1]31 aˇz [26]31 . K´od [0]31 necht’ oznaˇcuje mezeru. K´ody [27]31 aˇz [30]31 pˇriˇrad’me znak˚um ,,ˇca´ rka“, ,,teˇcka“, ,,vykˇriˇcn´ık“ a ,,otazn´ık“. Napˇr´ıklad zpr´avˇe ,,HIC SUNT LEONES!“ odpov´ıd´a posloupnost [8]31 [9]31 [3]31 [0]31 [19]31 [21]31 [14]31 [20]31 [0]31 [12]31 [5]31 [15]31 [14]31 [5]31 [19]31 [29]31 . Jiˇz Jules Verne sezn´amil svˇetovou ml´adeˇz se zp˚usobem, jak podobn´e zpr´avy dek´odovat, jsou-li dostateˇcnˇe dlouh´e a zn´ame-li pr˚umˇernou cˇ etnost v´yskytu jednotliv´ych p´ısmen v jazyce zpr´avy. Dek´odov´an´ı se zt´ızˇ´ı, k´odujeme-li n-tice znak˚u. Necht’pro jednoduchost n = 2. Posloupnost rozdˇelme na dvojice prvk˚u ze Z31 (poˇc´ınaje zleva) a kaˇzdou dvojici, povaˇzovanou za matici typu 2/1, vyn´asobme zleva matic´ı [12]31 [10]31 A= . [13]31 [11]31 Vznikne posloupnost [0]31 [17]31 [5]31 [8]31 [4]31 [13]31 [27]31 [30]31 [27]31 [8]31 [24]31 [13]31 [1]31 [20]31 [22]31 [8]31 , kter´e odpov´ıd´a posloupnost znak˚u k odesl´an´ı: ,, QEHDM,?,HXMATVH“. P˚uvodn´ı text pak zjist´ıme pouˇzit´ım inverzn´ı matice [26] [21] 31 31 A−1 = [9]31 [6]31 analogick´ym zp˚usobem (cviˇcen´ı). Probl´em k rˇ eˇsen´ı. Dek´odujte ,,KRRWZ WRNC.LENANADFOWOTU?BZPKA WC EUZPCQ,?YDP?!AQXBB“
3. Transponovan´a matice Definice. Transponovan´a matice k matici A ∈ Mr s (P) je matice A ∈ Msr (P), splˇnuj´ıc´ı Aij = A ji . Pˇr´ıklad.
1
2
3
4
5
6
1
= 2 3
4 5 6
Vˇsimnˇete si, zˇ e ˇra´ dky se zamˇenily za sloupce a naopak.
7
6. Matice. Algebraick´e vlastnosti
Pˇredpisem A → A je zad´ano zobrazen´ı ( · ) : Mr s (P) → Msr (P). Cviˇcen´ı. Ukaˇzte, zˇ e ( · ) : Mr s (P) → Msr (P) je homomorfismus aditivn´ıch grup. Cviˇcen´ı. (AB) = B A pro libovoln´e matice A ∈ Mr s (P) a B ∈ Mst (P). Dokaˇzte. Cviˇcen´ı. Necht’ A ∈ GLn (P). Dokaˇzte, zˇ e A ∈ GLn (P) a zˇ e plat´ı (A )−1 = (A−1 ) .
V´ıme jiˇz, zˇ e element´arn´ı ˇra´ dkov´a u´ prava je tot´ezˇ , co n´asoben´ı element´arn´ı matic´ı zleva. Element´arn´ı sloupcov´a u´ prava se zav´ad´ı analogicky jako ˇra´ dkov´a, pouze slovo ˇra´ dek se v definici vˇsude nahrad´ı slovem sloupec. Protoˇze transponov´an´ı matic vede k vz´ajemn´e z´amˇenˇe ˇra´ dk˚u za sloupce, libovoln´a element´arn´ı sloupcov´a u´ prava matice A se z´ısk´a kombinac´ı transpozice → element´arn´ı ˇra´ dkov´a u´ prava → transpozice. Je-li Q matice pˇr´ısluˇsn´a element´arn´ı ˇra´ dkov´e u´ pravˇe, pak pr´avˇe naznaˇcen´ym postupem pˇrevedeme matici A na matici A → A → Q A → (Q A ) = (A ) Q = AQ . Vid´ıme, zˇ e element´arn´ı sloupcov´a u´ prava je tot´ezˇ , co n´asoben´ı matic´ı Q zprava. Pˇritom matice transponovan´a k element´arn´ı matici je opˇet element´arn´ı matice: E i (c) = E i (c),
E i j (c) = E ji (c),
E ij = E ji = E i j .
O sloupcov´ych u´ prav´ach matic plat´ı analogick´a tvrzen´ı jako o ˇra´ dkov´ych u´ prav´ach. Pozor je tˇreba d´avat pˇri ˇreˇsen´ı soustav line´arn´ıch rovnic. Sloupcov´e u´ pravy matice soustavy mˇen´ı ˇreˇsen´ı rovnice. (Napˇr´ıklad z´amˇena sloupc˚u = z´amˇena nezn´am´ych.) Tak´e ve v´ysˇe uveden´em algoritmu pro v´ypoˇcet inverzn´ı matice nelze prov´adˇet sloupcov´e u´ pravy souˇcasnˇe s ˇra´ dkov´ymi, ani za pˇredpokladu, zˇ e je provedeme v obou polovin´ach matice n/2n. To lze ovˇeˇrit na prakticky libovoln´em pˇr´ıkladˇe v´ypoˇctu inverzn´ı matice.
8
