1. Gauss-, Gauss-Jordan elimin´ aci´ o. El˝osz¨ or az Ax = b line´ aris egyenletrendszerekkel foglalkozunk. Itt teh´at adott egy A ∈ Rm×n (p´eld´ aul val´os elem˝ u, m-szer n-es) m´atrix tov´abb´a egy b ∈ Rm (val´os, m-elem˝ u) vektor ´es olyan x ∈ Rn vektort keres¨ unk, amely megold´asa a fenti egyenletrendszernek, vagyis amelyre Ax = b teljes¨ ul. M´ ar az m = n = 1 eset is “bonyolultnak” t˝ unik: a 0x = 0, 0x = 1, 1x = 0 egyenletrendszerek megold´ashalmaza rendre R, ∅, {0}. A megold´ashalmaz teh´at ezekben az esetekben v´egtelen sok elemet tartalmaz, vagy u ¨ res, vagy pontosan egy elem˝ u. (L´atni fogjuk, hogy ´altal´ aban is ez a helyzet.) Ennek a “bonyolults´agnak” k¨osz¨ onhet˝oen, ellent´etben p´eld´ aul az egyv´ altoz´ os, komplex egy¨ utthat´os m´asodfok´ u egyenletekkel, ´ altal´ aban nem ismeretes olyan k´eplet, amely az A, b elemeinek f¨ uggv´eny´eben fejezn´e ki az x megold´as(oka)t. Az x megold´asok meghat´aroz´as´ara algoritmusokat terveztek. Itt k´et algoritmussal ismerked¨ unk meg, a Gauss-, illetve a Gauss-Jordan elimin´ aci´ oval. Mindk´et m´odszer az al´abbi ´eszrev´etelen alapszik: 1. Ha az (A, b) m´ atrixon v´egrehajtjuk az al´ abbi transzform´ aci´ ok egyik´et ´es az ´ıgy kapott m´ atrix (A′ , b′ ), akkor ′ ′ az Ax = b ´es az A x = b egyenletrendszerek megold´ ashalmaza megegyezik: T1 : A m´ atrix egyik sor´ at egy nemnulla λ val´ os sz´ ammal szorozzuk. T2 : A m´ atrix egyik sor´ ahoz hozz´ aadjuk egy m´ asik sor´ anak λ-szoros´ at, ahol λ tetsz˝ oleges val´ os sz´ am. Term´eszetesen a fenti tulajdons´ aggal rendelkezik az a transzform´ aci´ o, hogy a m´atrix k´et sor´at felcser´elj¨ uk. (Ezt jel¨olj¨ uk T0 -lal.) A T0 , T1 , T2 transzform´ aci´ okat elemi sortranszform´ aci´ oknak nevezz¨ uk. Hasonl´oan defini´alhat´ok az elemi oszloptranszform´ aci´ ok is. 2. Az elemi sortranszform´ aci´ ok egyen´ert´ek˝ uek a m´ atrix egy u ´n. elemi m´ atrixszal val´ o balr´ ol szorz´ as´ aval, ahol az elemi m´ atrixot u ´gy kapjuk, hogy a megfelel˝ o transzform´ aci´ ot az egys´egm´ atrixon hajtjuk v´egre. 2.-h¨oz hasonl´ o´ all´ıt´ as mondhat´o ki az elemi oszloptranszform´aci´ ok eset´en is, csak itt az elemi m´atrixszal jobbr´ ol kell szorozni. Ennek az ´ all´ıt´ asnak a megjegyz´es´et seg´ıtheti az angol “jobs=munk´ ak” sz´o: Jobbr´ol Oszlopot, Balr´ ol Sort transzform´ al az elemi m´atrixszal val´o szorz´ as. 3. Az egyetlen egyenletb˝ ol a ´ll´ o Ax = b rendszernek pontosan akkor nincs megold´ asa, ha A = 0 ´es b 6= 0. A Gauss(-Jordan) elimin´ aci´ o sor´an (T1 ´es) T2 t´ıpus´ u sortranszform´aci´ okkal olyan alakra hozzuk a megoldhat´o egyenletrendszert, amelynek megold´asa(i) m´ar k¨onnyen kiolvashat´o(k). Ha az egyenletrendszernek nincs megold´asa, akkor az egyik ´ atalak´ıtott rendszernek lesz egy ellentmond´o (0x = (6= 0) alak´ u) egyenlete. A k¨ovetkez˝okben a Gauss elimin´ aci´ ot ´ırjuk le form´alisabban. Az algoritmusban szerepl˝ o egyes v´altoz´ ok jelent´ese: i k A(k) x = b(k)
jel¨ oli, hogy h´ anyadik sorban ´all az ´eppen vizsg´alt egyenlet. jel¨ oli az eddig tal´ alt nemnulla sorok sz´am´ at. a k-szor transzform´ alt, Ax = b-vel azonos megold´ashalmaz´ u rendszer.
Gauss elimin´ aci´ o: Be: m, n, A, b [m, n ∈ N , A ∈ Rm×n , b ∈ Rm ] i := 1 : k := 0 : A(0) := A : b(0) := b 1. f´ azis [(A, b) ´ atalak´ıt´ asa sortranszform´aci´ okkal] Ha i ≤ m, akkor Ax = b megoldhatatlan k¨ ul¨onben r := k : 2. f´ azis [Visszahelyettes´ıt´es] : Ki: p, q (j) (j ∈ {1, . . . , n} \ {j1 , . . . , jr }) Program v´ege. 1. f´ azis Ciklus, am´ıg i ≤ m ´es az A(k) x = b(k) rendszer i-edik egyenlete megoldhat´o Ha A(k) i-edik sor´anak van nemnulla eleme, akkor k := k + 1 : Sortranszform´ aci´ o i := i + 1 Ciklus v´ege Elj´ar´as v´ege.
1
Sortranszform´ aci´ o ik := i [Az i1 , . . . , ik sz´ amsorozat n¨ ovekszik] V´ alasszunk jk oszlopindexet u ´ gy, hogy az A(k−1) m´atrix (ik , jk ) poz´ıci´oj´ an ´all´o eleme nemnulla legyen. [A j1 , . . . , jk sz´ amok k¨ ul¨onb¨ oz˝oek] Az (A(k−1) , b(k−1) ) m´atrix i-edik sor´anak megfelel˝o sz´am´ u t¨ obbsz¨or¨oseit vonjuk ki az ik -n´al nagyobb index˝ u sorokb´ ol u ´ gy, hogy a jk -adik oszlopban az ik -n´al nagyobb index˝ u elemek lenull´ az´odjanak. Az ´ıgy kapott m´atrix legyen (A(k) , b(k) ). Elj´ar´as v´ege. 2. f´ azis okat az Ax = b rendszer egy megold´as´aban Nevezz¨ uk a r¨ovids´eg kedv´e´ert az xj1 , . . . , xjr v´altoz´ b´ azisv´ altoz´ oknak. ok Tekints¨ uk az A(r) x = b(r) egyenletrendszert. Ennek ir -edik egyenlet´eben az xj1 , . . . , xjr−1 v´altoz´ azisv´altoz´ ok f¨ uggv´enyek´ent. egy¨ utthat´ oja nulla, ´ıgy xjr kifejezhet˝o a nem b´ ok egy¨ utthat´oja nulla, ´ıgy Ezut´ an az ir−1 -edik egyenletet tekintj¨ uk. Ebben az xj1 , . . . , xjr−2 v´altoz´ azisv´altoz´ ok f¨ uggv´enyek´ent. xjr ismeret´eben xjr−1 kifejezhet˝o a nem b´ ´ ´ıgy tov´abb eg´eszen addig, m´ıg az xj1 -et ki nem fejezt¨ uk a nem b´ azisv´altoz´ ok f¨ uggv´enyek´ent. Es Mivel a nem b´ azisv´altoz´ ok term´eszetesen kifejezhet˝oek a nem b´ azisv´altoz´ ok f¨ uggv´enyek´ent, az´ert az Ax = b rendszer tetsz˝ oleges megold´as´at kifejezt¨ uk nem b´ azisv´altoz´ oinak f¨ uggv´enyek´ent. K¨onnyen bel´ aP that´o, hogy ez a f¨ ugg´es line´aris, vagyis l´eteznek olyan p, q (j) ∈ Rn vektorok u ´ gy, hogy x = p + {q (j) xj : xj nem b´ azisv´altoz´ o} alak´ u. (A nemb´ azisv´altoz´ oknak megfelel˝o helyeken p-ben nincs nemnulla elem, q (j) -ben is csak a j-edik poz´ıci´on, ahol egy egyes ´all.) Az Ax = b rendszer megold´asait ´eppen az ilyen alakban el˝oa´ll´o x vektorok adj´ak. A p vektorra teljes¨ ul, hogy Ap = b, a q (j) vektorokra Aq (j) = 0. Elj´ar´as v´ege. P´ elda:
1∗ 1
1 2 1 2 1 2 , (A(1) , b(1) ) = = (A(2) , b(2) ) 0 3 0 −1∗ −1 1 −x2 − x3 = 1 → x2 = −1 − x3 x1 + 2x2 + x3 = 2 → x1 = 2 − 2x2 − x3 = 2 − 2(−1 − x3 ) − x3 = 4 + x3 x = p + q (3) x3 = (4, −1, 0)T + (1, −1, 1)T x3 .
(A(0) , b(0) ) =
2 1
V´ altoztassuk meg most a Sortranszform´aci´ o elj´ar´ast a k¨ovetkez˝o m´odon: Az ik , jk indexek v´alaszt´asa ut´an el˝ osz¨ or osszuk le az ik -adik sort az jk -adik elem´evel, majd a sor megfelel˝o sz´am´ u t¨ obbsz¨or¨ oseit vonjuk le a t¨ obbi sorb´ol u ´ gy, hogy a jk -adik oszlop ik -t´ol k¨ ul¨onb¨ oz˝o index˝ u elemei lenull´ az´odjanak. Ily m´odon az A(r) x = b(r) egyenletrendszerben az i1 -edik, i2 -edik, ... , ir -edik egyenletben a b´ azisv´altoz´ ok osen megk¨ onny´ıti k¨oz¨ ul csak egynek nemnulla az egy¨ utthat´ oja (rendre xj1 -nek, ... , xjr -nek ´es egyes), ami jelent˝ a 2. f´azist, a visszahelyettes´ıt´est. Az ´ıgy nyert m´odszert h´ıvjuk Gauss-Jordan elimin´ aci´ onak. P´ elda: (A(0) , b(0) ), (A(1) , b(1) ) = mint fent, (A(2) , b(2) ) =
1 0
0 −1 4 1 1 −1
x2 + x3 = −1 → x2 = −1 − x3 x1 − x3 = 4 → x1 = 4 + x3 x = p + q (3) x3 = (4, −1, 0)T + (1, −1, 1)T x3 .
A p vektor, mint egy speci´ alis megold´as j´o bizony´ıt´eka az Ax = b rendszer megoldhat´os´ag´anak. Van-e hasonl´ o t¨ om¨ or bizony´ıt´eka az Ax = b rendszer megoldhatatlans´ ag´anak? Ilyen bizony´ıt´ekot ad a k¨ovetkez˝o t´etel (Fredholm alternat´ıva t´ etele): Az Ax = b rendszer pontosan akkor megoldhatatlan, ha l´etezik y ∈ Rm vektor u ´gy, hogy AT y = 0 ´es bT y 6= 0.
2
A t´etel “akkor” ir´ anya k¨onnyen bel´ athat´o: Ha l´etezne a t´etelben le´ırt tulajdons´ ag´ u x ´es y vektor is, akkor az 0 = 0T x = (AT y)T x = y T Ax = y T (Ax) = y T b 6= 0 ellentmond´ashoz jutn´ank. A t´etel m´asik ir´ any´at a fenti elimin´ aci´ ok b´ armelyik´evel bizony´ıthatjuk konstrukt´ıvan: Ha az Ax = b rendszer nem megoldhat´o, akkor az elimin´ aci´ o sor´an valamikor ellentmond´o egyenletre bukkanunk, vagyis az aktu´alis A(k) x = b(k) rendszer i-edik egyenlete 0T x = (6= 0) alak´ u lesz. A 2. feladatb´ol k¨ovetkezik, hogy l´etezik E ∈ Rm×m m´atrix u ´ gy, hogy A(k) = EA, b(k) = Eb. Az E m´atrix az elemi sortranszform´ aci´ oknak megfelel˝o m´atrixok szorzatak´ent ´all el˝o. Az E m´atrixot a k¨ovetkez˝o m´odon sz´amolhatjuk ki: az m × m-es egys´egm´atrixon hajtsuk v´egre ugyanazokat a sortranszform´aci´ okat, amiket az (A, b) m´atrixon v´egrehajtottunk. Jel¨olje ei a i-edik egys´egvektort: ennek minden eleme nulla, lesz´am´ıtva az i-ediket, ami egyes. A fentiek szerint eTi A(k) = eTi EA = 0, eTi b(k) = eTi Eb 6= 0. Legyen y az E m´atrix i-edik sorvektor´anak, eTi E-nek a transzpon´altja. Erre az y vektorra teljes¨ ul, hogy AT y = 0, bT y 6= 0, mint azt az el˝ oz˝o egyenletek ´eppen kimondj´ak. P´ elda: (0)
(A
1∗ 2
2 1 2 1 2 1 2 (1) (1) ,b ) = , (A , b ) = 4 2 5 0 0 0 1 1 0 1 0 → E= 0 1 −2 1 1 0 y T = eT2 E = 0 1 = −2 1 −2 1 (0)
4. Oldd meg a Gauss-, vagy a Gauss-Jordan elimin´ aci´ o seg´ıts´eg´evel az Ai x = bi (i szereket, ahol 1 1 3 1 5 1 1 −3 −1 0 1 1 5 −7 2 1 −2 1 , (A3 , b3 ) := , (A2 , b2 ) := (A1 , b1 ) := 1 2 1 1 2 1 1 1 3 0 2 3 −3 14 1 2 −3 1
= 1, 2, 3) egyenletrend −2 3 −4 4 1 −1 1 −3 . 3 0 −3 1 −7 3 1 −3
Ha a rendszer megoldhatatlan, akkor hat´ arozd meg az ezt tan´ us´ıt´ o y vektort is! 5. Azt mondjuk, hogy a H ∈ Rm×n m´ atrix Hermite-f´ ele norm´ alalak´ u, ha kiv´ alaszthat´ ok i1 , . . . , ir sorindexek ´es j1 , . . . , jr oszlopindexek u ´gy, hogy a) Ha az i sorindex az i1 , . . . , ir sorindexek mindegyik´et˝ ol k¨ ul¨ onb¨ ozik, akkor a H m´ atrix i-edik sora csupa null´ ab´ ol a ´ll. b) B´ armely k ∈ {1, . . . , r} eset´en a H m´ atrix jk -adik oszlop´ anak minden eleme nulla, lesz´ am´ıtva az ik -adikat, ami egyes. Bizony´ıtsd be, hogy minden A ∈ Rm×n m´ atrix Hermite-f´ele norm´ alalakra hozhat´ o T1 ´es T2 t´ıpus´ u elemi sortranszform´ aci´ okkal! Hozd H Hermite-f´ele norm´ alalakra az al´ abbi A m´ atrixokat! Sz´ amolj ki egy E m´ atrixot is, amelyre H = EA! 1 0 0 1 4 2 0 2 0 2 0 1 0 2 5 0 1 0 1 0 A= 0 0 1 3 6 , illetve A = 2 1 0 2 1 1 2 3 14 32 0 1 0 1 0 4 5 6 32 77 6. Bizony´ıtsd be, hogy ha az Ax = b rendszer megoldhat´ o ´es A ´es b is racion´ alis elem˝ u, akkor a rendszernek van racion´ alis megold´ asa is! (Ellent´etben p´eld´ aul az egyv´ altoz´ os x2 = 2 nemline´ aris egyenlettel.)
3
2. Permut´ aci´ o, determin´ ans. Vizsg´ aljuk most az m = n esetet ´es legyen el˝osz¨ or n = 2. Kisz´amolhat´ o, hogy ha a d := a11 a22 − a12 a21 mennyis´eg nem nulla (aij term´eszetesen az A m´atrix i-edik sor´aban ´es j-edik oszlop´aban ´all´o elem´et jel¨oli), akkor az Ax = b rendszernek pontosan egy megold´asa l´etezik, amelynek koordin´at´ait az al´abbi k´eplettel sz´amolhatjuk ki: x1 = (b1 a22 − a12 b2 )/d, x2 = (a11 b2 − b1 a21 )/d. Hasonl´o t´etel mondhat´o ki az n = 3 esetben is: Ha d := a11 a22 a33 + a12 a23 a31 + a13 a21 a32 − a13 a22 a31 − a11 a23 a32 − a12 a21 a33 nem nulla, akkor az Ax = b rendszer egy´ertelm˝ u megold´as´anak koordin´at´ai: x1 x2 x3
= (b1 a22 a33 + a12 a23 b3 + a13 b2 a32 − a13 a22 b3 − b1 a23 a32 − a12 b2 a33 )/d, = (a11 b2 a33 + b1 a23 a31 + a13 a21 b3 − a13 b2 a31 − a11 a23 b3 − b1 a21 a33 )/d, = (a11 a22 b3 + a12 b2 a31 + b1 a21 a32 − b1 a22 a31 − a11 b2 a32 − a12 a21 b3 )/d.
Hogyan ´altal´ anos´ıthat´ oak ezek a t´etelek tetsz˝ oleges n eset´ere? ´ Eszrevett´ ek, hogy a kulcsszerepet j´ atsz´o d mennyis´egek n! = 1 ·2 ·. . .·n tag ¨osszegek´ent ´allnak el˝o. Az egyes tagokat u ´ gy kapjuk, hogy az A m´atrixb´ ol kiv´ alasztunk n elemet, melyeknek sorai ´es oszlopai is k¨ ul¨onb¨ oz˝oek, ´es ezeket ¨osszeszorozzuk. A tagok el˝ ojele plusz, vagy m´ınusz aszerint, hogy p´ aros, vagy p´ aratlan az olyan i, j oszlopindexp´arok sz´ ama, amelyre i < j ´es az i-edik oszlopb´ol kiv´ alasztott elem sorindexe nagyobb, mint a j-edik oszlopb´ol kiv´ alasztott elem sorindexe. Az ´ıgy nyert ¨osszeg az A ∈ Rn×n m´atrix determin´ ansa, jele det A, vagy |A|. A fenti, az n = 2, illetve az n = 3 esetre vonatkoz´o t´etelek ´altal´ anos´ıt´asa, a Cramer szab´ aly ezek ut´an: Ha det A 6= 0, akkor az Ax = b rendszernek pontosan egy megold´asa l´etezik, melynek xi koordin´at´aj´ at u ´ gy kapjuk, hogy az A m´atrix i-edik oszlop´at b-vel helyettes´ıtj¨ uk ´es az ´ıgy nyert m´atrix determin´ans´ at leosztjuk det A-val. Ebben a fejezetben a determin´ans tulajdons´ agait vizsg´aljuk, a k¨ovetkez˝o fejezetben pedig bebizony´ıtjuk a Cramer szab´alyt. Az {1, 2, . . . , n} halmaz ¨ onmag´ ara t¨ ort´en˝o k¨olcs¨on¨osen egy´ertelm˝ u lek´epez´es´et permut´ aci´ onak nevezz¨ uk. A P ∈ Rn×n m´atrixot permut´ aci´ o m´ atrixnak h´ıvjuk, ha minden sor´aban ´es minden oszlop´aban pontosan egy darab egyes van, a t¨ obbi elem nulla. Minden π permut´aci´ ohoz hozz´ arendelhet˝o a Pπ :=
n X
eπ(j) eTj
j=1
permut´aci´ o m´atrix ´es megford´ıtva minden P permut´aci´ o m´atrixhoz l´etezik egy´ertelm˝ uen π permut´aci´ ou ´ gy, hogy P = Pπ legyen. K¨onnyen bel´ athat´o, hogy a permut´aci´ ok (´es ´ıgy a permut´aci´ o m´atrixok) sz´ama n! = 1 · 2 · . . . · n. A permut´aci´ okon a szok´ asos f¨ uggv´eny¨osszet´etel m˝ uvelet egyfajta szorz´ ast defini´al. Ha π, σ permut´aci´ ok, akkor a (π ◦ σ)(i) := π(σ(i)) (i = 1, . . . , n) k´eplettel defini´alt π ◦ σ lek´epez´es is permut´aci´ o. Teljes¨ ul, hogy Pπ◦σ = Pπ · Pσ . Ennek az azonoss´agnak a seg´ıts´eg´evel a “◦” szorz´ as sz´ amos tulajdons´ ag´at bizony´ıthatjuk a “·” szorz´ as tulajdons´ agaib´ol: – A “◦” szorz´ as nem kommutat´ıv (vagyis π ◦ σ 0 1 0 1 0 0 0 0 1 0 0 · 0 0 1 = 1 0 0 0 1 0 1 0 0 1
nem felt´etlen¨ ul egyezik meg 1 0 1 0 0 6= 0 0 1 = 0 1 0 0
σ ◦ π-vel): 1 0 0 0 1 0 0 1 · 1 0 0 1 0 0 0
0 0 . 1
– A “◦” szorz´ as asszociat´ıv (´ atz´ ar´ ojelezhet˝ o), hiszen l´enyeg´eben m´atrixszorz´ as. – van egys´egelem: az egys´egm´atrixnak megfelel˝o, mindent helybenhagy´ o ε permut´aci´ ora teljes¨ ul, hogy π ◦ ε = ε ◦ π = π. 4
– van inverz elem: a PπT -nak megfelel˝o π −1 permut´aci´ ora teljes¨ ul, hogy π ◦ π −1 = π −1 ◦ π = ε, hiszen T T Pπ Pπ = Pπ Pπ = I, az egys´egm´atrix. Transzpoz´ıci´ onak nevez¨ unk egy τ permut´aci´ ot, ha a neki megfelel˝o permut´aci´ om´ atrix az egys´egm´atrixb´ol k´et sor´anak felcser´el´es´evel keletkezik. Egy τ transzpoz´ıci´o ¨onmaga inverze, vagyis τ −1 = τ , ugyanis PτT = Pτ . Az n szerinti teljes indukci´ oval k¨onnyen bel´athat´o, hogy a permut´aci´ ok π1 , π2 , . . . , πn! sorrendbe ´all´ıthat´ok u ´ gy, hogy πi+1 = τi ◦ πi valamely τi transzpoz´ıci´okkal, ´es π1 -nek tetsz˝ oleges permut´aci´ ot v´alaszthatunk. Adott π permut´aci´ o eset´en azt mondjuk, hogy i ´es j inverzi´ ot alkotnak π-ben, ha i < j, de π(i) > π(j). A π permut´aci´ o p´ aros, illetve p´ aratlan aszerint, hogy p´ aros, illetve p´ aratlan a benne l´ev˝ o inverzi´ok sz´ama. K¨onnyen bel´athat´o, hogy π ´es τ ◦ π parit´ asa ellent´etes, ha τ transzpoz´ıci´o. 1. A p´ aros ´es a p´ aratlan permut´ aci´ ok sz´ ama is
1 2 n!.
2. Egy π permut´ aci´ o v´egtelenf´elek´eppen bomlik fel transzpoz´ıci´ ok szorzat´ ara, de egy-egy ilyen felbont´ asban a transzpoz´ıci´ ok sz´ am´ anak parit´ asa megegyezik π parit´ as´ aval. 3. K´et permut´ aci´ o szorzata pontosan akkor p´ aros, ha a permut´ aci´ ok parit´ asa megegyezik. Speci´ alisan π ´es π −1 egyszerre p´ aros, vagy p´ aratlan. Egy A m´atrix determin´ans´ anak defin´ıci´oja ezek ut´an t¨ om¨ oren: X (−1)π mod2 aπ(1)1 · . . . · aπ(n)n : π permut´aci´ o , det A :=
ahol “π mod 2” nulla, vagy egy aszerint, hogy π p´ aros, vagy p´ aratlan.
Els˝o fontos ´eszrev´etel¨ unk a determin´anssal kapcsolatban, hogy egy m´atrix, ´es transzpon´altj´ anak determin´ansa megegyezik. R¨ oviden v´azoljuk a bizony´ıt´ast: o Pn −1 (−1)π mod2 aπ−1 (1)1 · . . . · aπ−1 (n)n : π permut´aci´ o = det A = P π mod2 = (−1) a1π(1) · . . . · anπ(n) : π permut´aci´ o = det (AT ). Emiatt az al´ abbi ´ all´ıt´ asok ´erv´enyben maradnak akkor is, ha a “sor” ´es az “oszlop” szavakat felcser´elj¨ uk. A defin´ıci´ob´ol k¨onnyen ad´odik, hogy a determin´ans a sorvektorok multiline´aris f¨ uggv´enye, vagyis: a) Ha az A m´atrix i-edik sora egy b vektor λ konstansszorosa, akkor det A = λdet B, ahol B az A m´atrixb´ol keletkezik u ´ gy, hogy i-edik sor´at b-vel helyettes´ıtj¨ uk. b) Ha az A m´atrix i-edik sora egy b ´es egy c vektor ¨osszege, akkor det A = det B + det C, ahol B ´es C az A m´atrixb´ol keletkezik u ´ gy, hogy i-edik sor´at b-vel, illetve c-vel helyettes´ıtj¨ uk. Ebb˝ol m´ar k¨onnyen ad´odik a determin´ans azon tulajdons´ aga, hogy a T0 , T1 , T2 sortranszform´aci´ ok ut´an az u ´ j m´atrix (A′ ) determin´ansa a r´egi m´atrix (A) determin´ans´ anak (−1)-szerese, λ-szorosa, illetve 1-szerese. A T0 sortranszform´ aci´ o eset´eben ez abb´ol ad´odik, hogy P τ ◦π mod2 (−1) a(τ ◦π)(1)1 · . . . · a(τ ◦π)(n)n : π permut´ aci´ o = det A = n o P π mod2 ′ ′ (−1) aπ(1)1 · . . . · aπ(n)n : π permut´aci´ o = −det (A′ ). = −
a megfelel˝o τ transzpoz´ıci´oval. A T1 , T2 transzform´ aci´ okra vonatkoz´o ´ all´ıt´as a determin´ans multilinearit´as´anak k¨ovetkezm´enye, figyelembe v´eve m´eg azt is, hogy ha a m´atrix k´et sora megegyezik, akkor a determin´ans ¨onmaga (−1)-szeresek´ent null´ aval egyenl˝ o.
A determin´anst mechanikusan a Gauss elimin´ aci´ o seg´ıts´eg´evel sz´amolhatjuk ki, a jobb oldal vektort (b) a nullvektornak k´epzelve. A Gauss elimin´ aci´ o sor´an v´egig T2 t´ıpus´ u sortranszform´aci´ okkal dolgozunk, ´ıgy a determin´ans nem v´altozik. Ha az elj´ ar´ as sor´an tal´ alunk csupa null´ ab´ol ´all´o sort, akkor a determin´ans nulla, ellenkez˝o esetben a kiv´ alasztott n¨ ovekv˝ o sorindexsorozat i1 = 1, i2 = 2, . . ., in = n. Ekkor legyen π az a permut´aci´ o, amelynek k helyen felvett ´ert´eke ´eppen jk . (n) (n) Megmutatjuk, hogy ekkor det A = (−1)π mod2 ai1 j1 · . . . · ain jn . (n)
(n)
Az A(n) m´atrix determin´ans´ aban szerepl˝ o (−1)σmod2 aσ(1)1 ·. . .·aσ(n)n tag csak akkor nem nulla, ha σ(jk ) ≤ ik (k = 1, . . . , n), egy´ebk´ent ugyanis a szorzatnak van nulla tagja. Eszerint σ ◦ π ≤ ε, amib˝ol σ ◦ π = ε, vagyis σ = π −1 ´es ´ıgy det A = (−1)π
−1
mod2 (n) aπ−1 (1)1
(n)
(n)
(n)
· . . . · aπ−1 (n)n = (−1)π mod2 a1π(1) · . . . · anπ(n) , 5
ami ´eppen a bizony´ıtand´o ´ all´ıt´ as. 4. Sz´ am´ıtsd ki az al´ abbi determin´ ansokat a defin´ıci´ o 2 3 2 1 1 4 , −1 2 ,
szerint, illetve Gauss elimin´ aci´ oval! 1 1 1 0 1 1 −1 0 1 , 1 0 1 . −1 −1 0 1 1 0
5. Antiszimmetrikusnak nevez¨ unk egy m´ atrixot ha a transzpon´ altja (−1)-szerese. Mutasd meg, hogy egy p´ aratlan rend˝ u antiszimmetrikus m´ atrix determin´ ansa nulla! 6. Tegy¨ uk fel, hogy az A ∈ Rn×n m´ atrix nulla sor- ´es oszlop¨ osszeg˝ u, vagyis Ae = AT e = 0, ahol e az (1, . . . , 1)T vektort jel¨ oli. Az A m´ atrixb´ ol i-edik sor´ anak ´es j-edik oszlop´ anak elhagy´ as´ aval keletkez˝ o m´ atrixot jel¨ olje Aij . Bizony´ıtsd be, hogy ekkor (−1)i+j det (Aij ) az i, j-t˝ ol f¨ uggetlen konstans! ´ [Utmutat´ as: Adjuk Aij l-edik oszlop´ ahoz a t¨ obbi oszlop´ at, majd k-adik sor´ ahoz a t¨ obbi sor´ at. Sor- ´es oszlopcser´ek ut´ an Akl -et kapjuk.] A determin´ansok nem mechanikus sz´ am´ıt´as´an´al hasznos lehet m´eg Laplace t´etele, melynek seg´ıts´eg´evel a determin´ans kisz´ am´ıt´ as´ at vissza lehet vezetni kisebb rend˝ u determin´ansok kisz´ am´ıt´as´ara. Laplace t´ etele: V´ alasszuk ki A tetsz˝ oleges k darab sor´at, ahol 1 ≤ k ≤ n − 1. Az A m´atrix determin´ans´ at megkapjuk, ha a kiv´ alasztott sorokban szerepl˝ o mindegyik k-adrend˝ u aldetermin´anst megszorozzuk az adjung´altj´ aval ´es ezeket a szorzatokat ¨ osszeadjuk. (Egy k-adrend˝ u aldetermin´ ans az A m´atrixb´ol valamely k sor´anak ´es oszlop´anak meghagy´ as´ aval keletkez˝o r´eszm´ atrix´anak a determin´ansa. Tegy¨ uk fel, hogy az aldetermin´ans sor-, illetve oszlopindexei i1 , . . . , ik , illetve j1 , . . . , jk . Az aldetermin´ ans adjung´ altj´ at u ´ gy kapjuk, hogy elhagyjuk az A m´atrixb´ ol ezeket a sorokat ´es oszlopokat, k´epezz¨ uk az ´ıgy kapott m´atrix determin´ans´ at ´es megszorozzuk (−1)i1 +...+ik +j1 +...+jk -vel.) Laplace t´etel´enek speci´ alis esete a kifejt´ esi t´ etel, ez a k = 1 eset. Laplace t´etel´enek k¨ovetkezm´enye a determin´ ansok szorz´ ast´ etele, mely szerint det (AB) = (det A) · (det B). A bizony´ıt´ ashoz vegy¨ uk ´eszre, hogy 0 A AB 0 a m´atrix T2 -kel ´atvihet˝ oa m´atrixba, B −I B −I 2
´ıgy a k´et m´atrix determin´ansa megegyezik. Az els˝o m´atrix determin´ansa (−1)n (det A)(det B) (alkalmazzuk a Laplace t´etelt az els˝o n oszlopra!), m´ıg a m´asodik´e (−1)n det (AB) (alkalmazzuk a Laplace t´etelt az utols´ o n oszlopra!), amib˝ ol ad´odik a k´ıv´ ant egyenl˝ os´eg. (Hasonl´o a bizony´ıt´asmenet, mikor A ∈ Rm×n , B ∈ Rn×m nem felt´etlen¨ ul n´egyzetes m´atrixok, ez vezet a Cauchy-Binet formul´ ahoz.) 7. Sz´ am´ıtsd ki az al´ abbi m´ atrixok x y ··· y . y x . . . .. . . .. ... y .. y ··· y x a) kombinatorikus
determin´ ans´ at!
1 2 n 1 .. .. . . 2 3
··· ··· .. .
n n−1 .. .
···
1
b) ciklikus
(xj−1 )i,j=1,...,n i
1 )i,j=1,...,n ( xi +y j
c) Vandermonde
d) Cauchy m´ atrix
8. Legyenek x1 , . . . , xn tetsz˝ oleges sz´ amok, tov´ abb´ a s1 := x1 , s2 := x1 + x2 , . . . sn := x1 + . . . + xn . Bizony´ıtsd be, hogy az (smin {i,j} )i,j=1,...,n m´ atrix determin´ ansa x1 · . . . · xn . ´ 9. Alljon a 2n × 2n-es m´ atrix f˝ oa ´tl´ oj´ aban csupa x, mell´ek´ atl´ oj´ aban csupa y, m´ asutt null´ ak. Mennyi a m´ atrix determin´ ansa?
6
3. Inverz, Cramer szab´ aly. Egy A ∈ Rn×n m´atrixot invert´ alhat´ onak nevez¨ unk, ha l´etezik olyan B ∈ Rn×n m´atrix, amelyre AB ´es BA is az egys´egm´atrix. A B m´atrixot ekkor az A m´atrix inverz´enek nevezz¨ uk. A determin´ansok szorz´ ast´etel´eb˝ol k¨ovetkezik, hogy egy invert´ alhat´o m´atrix determin´ansa nem lehet nulla. (Ha det A = 0, akkor az A m´atrixot szingul´ arisnak, ellenkez˝o esetben regul´ arisnak, vagy nemszingul´ arisnak h´ıvjuk.) Megford´ıtva egy nemszingul´ aris m´atrix invert´ alhat´o: Jel¨olje Aij az A m´atrixb´ol i-edik sor´anak ´es j-edik oszlop´anak elhagy´as´ aval keletkez˝o r´eszm´ atrix´at. Legyen A−1 :=
1 (((−1)i+j det Aij )i,j=1,...,n )T , det A
ekkor A−1 az A m´atrix inverze. Ez k¨onnyen k¨ovetkezik a kifejt´esi t´etelb˝ol ´es abb´ol, hogy ha egy m´atrix k´et sora, vagy k´et oszlopa megegyezik, akkor determin´ansa nulla. Ha az A m´atrix invert´ alhat´ o, akkor inverze nem is lehet m´as, mint az A−1 , s˝ot ha egy B m´atrix teljes´ıti az inverz defin´ıci´oj´ aban l´ev˝ o azonoss´ agok egyik´et, vagyis AB = I, vagy BA = I, akkor A invert´ alhat´o ´es B = A−1 . Legyen ugyanis p´eld´ aul AB = I. Ekkor a determin´ansok szorz´ ast´etele szerint A nemszingul´ aris, ´ıgy l´etezik A−1 . Szorozzuk meg az AB = I egyenl˝ os´eget balr´ol az A−1 m´atrixszal ´es m´aris megkapjuk, hogy B = A−1 . Ebb˝ol az ´eszrev´etelb˝ ol m´ar k¨onnyen ad´odik, hogy ha A, B ∈ Rn×n invert´ alhat´o m´atrixok, akkor A−1 , AT −1 T −1 −1 ´es AB is invert´ alhat´ oak ´es inverzeik rendre A, (A ) ´es B A . Ha az A m´atrix invert´ alhat´ o, akkor az Ax = b rendszernek pontosan egy megold´asa l´etezik, x = A−1 b. (Vil´agos, hogy ez megold´as, ´es megford´ıtva, ha Ax = b, akkor ezt a rendszert balr´ol A−1 -gyel szorozva kapjuk, hogy x = A−1 b.) Az x = A−1 b vektor i-edik koordin´ at´aja n
xi =
1 X (−1)j+i (det Aji )bj , det A j=1
ahol a szumma ´ert´eke a kifejt´esi t´etel szerint ´eppen azon m´atrix determin´ansa, amelyet u ´ gy kapunk A-b´ol, hogy i-edik oszlop´aba a b vektort ´ırjuk. Ezzel bel´attuk Cramer szab´aly´at. Megjegyezz¨ uk, hogy az egyenletrendszer megold´as´anak kisz´ am´ıt´asa szempontj´ ab´ol a Cramer szab´alynak ink´abb csak elm´eleti haszna van, hiszen alkalmaz´as´ahoz n + 1 darab n-edrend˝ u determin´anst kell kisz´ amolni, m´ıg a Gauss(-Jordan) elimin´ aci´ o ugyanerre a feladatra l´enyeg´eben egyetlen n-edrend˝ u determin´ans kisz´ am´ıt´as´aval egyen´ert´ek˝ u. Az inverz mechanikus sz´ am´ıt´ asa a Gauss-Jordan elimin´ aci´ o seg´ıts´eg´evel t¨ ort´enhet. Ha az elimin´ aci´ o sor´an tal´ alunk csupa nulla sort, akkor a m´atrix szingul´aris, teh´at nem invert´ alhat´o. Ellenkez˝o esetben a m´atrix Hermite f´ele norm´alalakja az A(n) = PπT permut´aci´ om´ atrix, ahol i1 = 1, . . . , in = n ´es π(1) := j1 , . . . , π(n) := jn . Tudjuk, hogy egy E m´atrixot is kisz´ am´ıthatunk, amelyre A(n) = EA. (Az A-hoz jobbr´ ol egy egys´egm´atrixot toldva ´es u ´ gy hajtva v´egre az elimin´ aci´ os l´ep´eseket az egys´egm´atrix hely´en v´eg¨ ul a megfelel˝o E m´atrix ´ all majd.) Ekkor teh´at EA = PπT , vagyis A nemszingul´ aris, l´etezik az inverze. Az EA = PπT egyenl˝ os´egb˝ ol azt balr´ol Pπ -vel, jobbr´ ol A−1 -gyel szorozva kapjuk, hogy Pπ E = A−1 . 1. Legyenek
1 1 (A, b) = 2 −1 4 1
2 −1 3 2 2 −4 illetve (A, b) = 2 3 4 −2 2 1
1 1 3
5 1 11
a) Sz´ amold ki az A m´ atrix inverz´et a defin´ıci´ ob´ ol, illetve Gauss-Jordan elimin´ aci´ oval! b) Hat´ arozd meg az Ax = b rendszer egyetlen megold´ as´ at az x = A−1 b k´epletb˝ ol, illetve Cramer szab´ aly´ anak seg´ıts´eg´evel! 2. Az A ∈ Rn×n m´ atrixot als´ o h´ aromsz¨ og m´ atrixnak nevezz¨ uk, ha a f˝ oa ´tl´ o feletti elemei null´ ak. Bizony´ıtsd be, hogy egy als´ o h´ aromsz¨ og m´ atrix inverze is als´ o h´ aromsz¨ og m´ atrix! 3. Egy eg´esz elem˝ u m´ atrixnak milyen felt´eteleket kell kiel´eg´ıtenie, hogy inverz m´ atrix´ anak elemei is eg´eszek legyenek?
7
4. Bizony´ıtsd be, hogy hat´ arozd meg a 1 0 0 . .. 0
(I − A)(I + A + A2 + . . . + Ak−1 ) = I − Ak . Ennek az ´eszrev´etelnek a seg´ıts´eg´evel −x
0
1
−x
0 .. .
1 .. .
···
0
··· .. . .. . .. . 0
1 0 n−1 .. x . ´ e s a xn−2 0 . .. −x x 1
x
x2
1
x
xn−1 .. . ···
1 ..
xn−1 .. . 2 x x 1
··· .. . .. . .. . xn−1
. xn−2
m´ atrixok inverz´et! 5. Tegy¨ uk fel, hogy az M ∈ R(m+n)×(m+n) m´ atrix M=
A C
B D
alak´ u, ahol A ∈ Rn×n , B ∈ Rn×m , C ∈ Rm×n , D ∈ Rm×m . a) Ha A invert´ alhat´ o, akkor M=
I CA−1
0 I
A 0 0 D − CA−1 B
I 0
A−1 B I
´es M pontosan akkor invert´ alhat´ o, ha D − CA−1 B, az A Schur komplemense M -ben invert´ alhat´ o. Ut´ obbi esetben M inverze −1 I −A−1 B A 0 I 0 M −1 = . 0 I 0 (D − CA−1 B)−1 −CA−1 I b) Hasonl´ oan ha D invert´ alhat´ o, akkor I BD−1 A − BD−1 C M= 0 I 0
0 D
I D−1 C
0 I
´es M pontosan akkor invert´ alhat´ o, ha A − BD−1 C, az D Schur komplemense M -ben invert´ alhat´ o. Ut´ obbi esetben M inverze I 0 (A − BD−1 C)−1 0 I −BD−1 −1 M = . −D−1 C I 0 D−1 0 I 6. Legyen A ∈ Rn×n invert´ alhat´ o m´ atrix, u, v ∈ Rn adott vektorok. Bizony´ıtsd be, hogy A + uv T pontosan T −1 akkor invert´ alhat´ o, ha 1 + v A u 6= 0 ´es ekkor (A + uv T )−1 = A−1 −
A−1 uv T A−1 . 1 + v T A−1 u
Ezt az o ¨sszef¨ ugg´est Sherman-Morrison formul´ anak nevezik. Alkalmaz´ asak´ent hat´ arozd meg a kombinatorikus m´ atrix invert´ alhat´ os´ ag´ anak a felt´etel´et ´es az inverz´et! ´ anos´ıtsd az el˝ 7. Altal´ oz˝ o feladatot: u, v ∈ Rn vektorok helyett szerepeljenek U, V ∈ Rn×r m´ atrixok ´es keresd T az A + U V m´ atrix invert´ alhat´ os´ ag´ anak felt´etel´et ´es inverz´et! (Woodbury t´ etele)
8
4. Line´ aris f¨ uggetlens´ eg, rang. P A v1 , . . . , vk ∈ Rd vektorok line´ aris kombin´ aci´ oi a ki=1 λi vi vektorok, ahol λ1 , . . . , λk ∈ R. A v1 , . . . , vk ∈ Rd vektorok line´ arisan f¨ uggetlenek, ha csak trivi´alis m´odon lehet bel˝ol¨ uk kikombin´alni P k a 0 vektort, vagyis λ1 , . . . , λk ∈ R, i=1 λi vi = 0 eset´en λ1 = . . . = λk = 0. 1. A v1 , . . . , vk ∈ Rd vektorok pontosan akkor line´ arisan f¨ uggetlenek, ha egyik¨ uk sem a ´ll el˝ o a t¨ obbiek line´ aris kombin´ aci´ ojak´ent.
2. Tegy¨ uk fel, hogy a v1 , . . . , vk ∈ Rd vektorok line´ arisan f¨ uggetlenek. F¨ uggetlenek-e ekkor az al´ abbi vektorrendszerek is: a) v1 , v1 + v2 , . . . , v1 + . . . + vk , b) v1 − v2 , v2 − v3 , . . . , vn − v1 , c) v1 + v2 , v2 + v3 , . . . , vn + v1 ? Ha a v1 , . . . , vk ∈ Rd vektorok nem line´arisan f¨ uggetlenek, akkor line´ arisan ¨ osszef¨ ugg˝ onek mondjuk ˝oket. Ez a helyzet p´eld´ aul, ha egyik¨ uk a 0 vektor, vagy ha van k¨ozt¨ uk k´et egyforma vektor. Hogy egy vektorrendszer line´arisan f¨ uggetlen, vagy ¨osszef¨ ugg˝o, azt mechanikusan az al´abbi m´odon d¨ onthetj¨ uk el: Alkossunk a vektorokb´ ol, mint oszlopvektorokb´ol egy A m´atrixot ´es Gauss-, vagy Gauss-Jordan elimin´ aci´ oval vizsg´aljuk meg, hogy az Ax = 0 homog´en egyenletrendszernek van-e null´ at´ol k¨ ul¨onb¨ oz˝o megold´ asa. Ha van ilyen megold´as, akkor a vektorok line´arisan ¨osszef¨ ugg˝oek, k¨ ul¨onben f¨ uggetlenek. 3. F¨ uggetlenek-e az al´ abbi vektorok? Ha nem, ´ırd fel a 0 vektort line´ aris kombin´ aci´ ojukk´ent! (2, 5, 1, −1)T , (1, 3, 6, 5)T , (−1, 4, 1, 2)T 4. Bizony´ıtsd be, hogy d-n´el t¨ obb Rd -beli vektor m´ ar line´ arisan o ¨sszef¨ ugg˝ o!
A v1 , . . . , vk ∈ Rd vektorrendszer legt¨obb elemb˝ ol ´all´o line´arisan f¨ uggetlen r´eszrendszer´et a vektorrendszer b´ azis´anak nevezz¨ uk. A b´ azis elemsz´ ama a vektorrendszer rangja. A 4. feladat szerint a v1 , . . . , vk ∈ Rd vektorrendszer rangja legfeljebb d (´es persze legfeljebb k). 5. Egy b´ azisb´ ol a vektorrendszer minden eleme kikombin´ alhat´ o, m´eghozz´ a egyf´elek´eppen. 6. a) b) c) d)
Egy vektorrendszer rangja nem v´ altozik, ha k´et vektor´ at felcser´elj¨ uk; egyik vektor´ at egy λ 6= 0 sz´ ammal megszorozzuk; egyik vektor´ ahoz hozz´ aadjuk egy m´ asik vektor´ anak λ-szoros´ at, ahol λ ∈ R; elhagyunk bel˝ ole egy nulla vektort.
Adott A ∈ Rm×n eset´en sorvektorai rendszer´enek rangja a m´atrix sorrangja, oszlopvektorai rendszer´enek rangja a m´atrix oszloprangja, jel¨ uk sr (A), illetve or (A). Nyilv´ an sr (A) = or (AT ) ´es or (A) = sr (AT ). Tudjuk tov´abb´a, hogy max{sr (A), or (A)} ≤ min {m, n}. El˝osz¨ or megmutatjuk, hogy a k´etf´ele m´atrixrang megegyezik. 7. Ha E ∈ Rm×m ´es F ∈ Rn×n invert´ alhat´ o m´ atrixok, akkor or (EA) = or (A) ´es sr (AF ) = sr (A). 8. Az A m´ atrix sor- ´es oszloprangja sem v´ altozik, ha a) a m´ atrixon elemi sor-, vagy oszloptranszform´ aci´ okat hajtunk v´egre, illetve b) a m´ atrix egy csupa nulla sor´ at, vagy oszlop´ at elhagyjuk. 9. Az A m´ atrix sor- ´es oszloprangja is a Gauss-, vagy Gauss-Jordan elimin´ aci´ o sor´ an b = 0 mellett kisz´ amolt r sz´ am. Az A oszlopvektorainak egy b´ azisa a j1 -edik, . . ., jr -edik oszlop. Az A sorvektorainak egy b´ azisa az i1 -edik, . . ., ir -edik sor. [Az ut´ obbi a ´ll´ıt´ ashoz u ´tmutat´ ask´ent: Azt kell megmutatnunk, hogy ha y T A = 0 ´es yi = 0 (i 6∈ {i1 , . . . , ir }), akkor y = 0. P´eld´ aul a Gauss-Jordan elimin´ aci´ o alkalmaz´ asakor 0 = y T Aejk = y T E −1 eik (k = 1, . . . , r) ´es T T −1 T −1 0 = y ei = y E ei (i 6∈ {i1 , . . . , ir }). Ebb˝ ol y E = 0 ´es ´ıgy y = 0 ad´ odik.] Eszerint az A m´atrix sor ´es oszloprangja megegyezik. Ezt a k¨oz¨os ´ert´eket a m´atrix rangj´anak nevezz¨ uk ´es r (A)-val jel¨olj¨ uk. A m´atrixrangnak m´eg k´et jellemz´es´et adjuk a fejezet h´ atral´ev˝ o r´esz´eben. 10. Az A m´ atrix sorainak (oszlopainak) b´ armely line´ arisan f¨ uggetlen r´eszrendszer´et kieg´esz´ıthetj¨ uk a sorok (oszlopok) egy b´ azis´ av´ a. ´ [Utmutat´ as: El´eg sorokra bizony´ıtani az a ´ll´ıt´ ast. Feltehet˝ o, hogy a m´ atrix els˝ o s sora line´ arisan f¨ uggetlen, ezt a rendszert akarjuk b´ aziss´ a b˝ ov´ıteni. E c´elb´ ol hajtsunk v´egre Gauss(-Jordan) elimin´ aci´ ot b = 0 v´ alaszt´ assal. El´eg megmutatnunk, hogy ekkor i1 = 1, . . . , is = s lesz. Tegy¨ uk fel indirekt, hogy i1 = 1, . . . , ik = k, de az 9
aktu´ alis m´ atrix k + 1-edik sora 0. Ekkor l´etezik E m´ atrix, amelyre Eei = ei (i > k), ´es eTk+1 EA = 0. Az T ek+1 E vektor mutatja, hogy ekkor A els˝ o k + 1 sora line´ arisan o ¨sszef¨ ugg˝ o lenne, ami ellentmond´ as.] Ez´ert nem csak a legt¨obb elem˝ u, hanem a legb˝ovebb (tov´abb nem b˝ ov´ıthet˝o) line´arisan f¨ uggetlen rendszerek is b´ azisok. 11. N´egyzetes m´ atrixra ekvivalensek: a) nemszingul´ aris (vagyis invert´ alhat´ o); b) sorai line´ arisan f¨ uggetlenek; c) oszlopai line´ arisan f¨ uggetlenek. 12. Az A m´ atrix r (A) darab line´ arisan f¨ uggetlen sor´ anak ´es r (A) darab line´ arisan f¨ uggetlen oszlop´ anak keresztez˝ od´es´eben lev˝ o r´eszm´ atrix nemszingul´ aris. A rang k¨ovetkez˝o jellemz´es´et adja az al´ abbi feladat: 13. Az A m´ atrix rangja a legnagyobb p sz´ am, amelyre A-nak l´etezik p × p-es nemszingul´ aris r´eszm´ atrixa.
14. Ha az A m´ atrixnak van p×p-es nemszingul´ aris A′ r´eszm´ atrixa ´es teljes¨ ul, hogy az A m´ atrix A′ -t tartalmaz´ o (p + 1) × (p + 1)-es r´eszm´ atrixai m´ ar szingul´ arisak, akkor r (A) = p. 15. Ha az A m´ atrix szimmetrikus (vagyis megegyezik a transzpon´ altj´ aval), akkor a 13. feladatban el´eg a f˝ oa ´tl´ obeli f˝ oa ´tl´ oj´ u r´eszm´ atrixokat figyelni. Most a rang ´es a k¨ ul¨onb¨ oz˝o m´atrixm˝ uveletek k¨ozti ¨osszef¨ ugg´eseket vizsg´aljuk. ´ 16. r (AB) ≤ min {r (A), r (B)}. [Utmutat´ as: or (AB) ≤ or (B) ´es sr (AB) ≤ sr (A).]
´ 17. r (A + B) ≤ r (A) + r (B). [Utmutat´ as: A + B = (A, B)(I, I)T .]
18. r (AB) ≥ r (A) + r (B) − (A oszlopsz´ ama). ´ [Utmutat´ as: L´eteznek E ∈ Rm×m ´es F ∈ Rn×n invert´ alhat´ o m´ atrixok u ´gy, hogy az EAF m´ atrix bal fels˝ o sark´ aban egy r (A) × r (A)-s egys´egm´ atrix a ´ll, m´ asutt null´ ak. Ekkor r (AB) = r (EAF F −1 B) = r (F −1 B els˝ o r sora) ≥ r (B) − ((A oszlopsz´ ama) − r (A)). Eg´esz´ıts¨ uk ki ugyanis F −1 B els˝ o r sor´ anak b´ azis´ at F −1 B sorainak b´ azis´ av´ a...] A m´atrixrang ebben a fejezetben utols´ o jellemz´es´et adja a k¨ovetkez˝o feladat: 19. Az A ∈ Rm×n nemnulla m´ atrix rangja a legkisebb q sz´ am, amelyre tal´ alhat´ ok ui ∈ Rm , vi ∈ Rn (i = P q T atrix egy ilyen felbont´ as´ at diadikus felbont´ asnak 1, . . . , q) vektorok u ´gy, hogy A = i=1 ui vi legyen. Az A m´ nevezz¨ uk. A q = r (A) esetben (minim´ alis diadikus felbont´ as) az ui vektorok ´es a vi vektorok is line´ arisan f¨ uggetlenek. ´ [Utmutat´ as: Tudjuk, hogy l´etezik E ∈ Rm×m invert´ alhat´ o m´ atrix u ´gy, hogy EAejkP= eik (k = 1, . . . , r) ´es P r r T ei EA = 0 (i 6∈ {i1 , . . . , ir }), ahol r = r (A). Ekkor EA = k=1 eik (eTik EA), ´ıgy A = k=1 (E −1 eik )(eTik EA) = Pr T k=1 (Aejk )(eik EA).] 20. Sz´ am´ıtsd ki az al´ abbi m´ atrixok rangj´ at, a) soraiknak egy-egy b´ azis´ at; b) oszlopaiknak egy-egy b´ azis´ at; c) egy-egy r (A) × r (A)-s nemszingul´ aris r´eszm´ atrixukat; d) egy-egy minim´ alis diadikus felbont´ asukat! 2 −4 3 1 0 2 1 −2 3 1 −2 1 −4 2 −2 9 4 7 , 0 1 −1 3 1 −4 3 1 −1 4 −7 4 −4 5 21. A 2. fejezet 6. feladat´ at a ´ltal´ anos´ıtva mutasd meg, hogy ha A ∈ Rn×n , akkor a ((−1)i+j det Aij )i,j=1,...,n m´ atrix rangja csak 0, 1, vagy n lehet! V´eg¨ ul a line´aris egyenletrendszerek megoldhat´os´aga ´es a rang k¨ozti ¨osszef¨ ugg´esr˝ol sz´ol a KroneckerCapelli t´ etel: 22. Ha az Ax = b rendszer megoldhat´ o, akkor r (A, b) = r (A), k¨ ul¨ onben pedig r (A, b) = r (A) + 1.
10
5. Alterek, affin halmazok. Ebben a fejezetben a homog´en, illetve inhomog´en egyenletrendszerek megold´ashalmazainak szerkezet´et vizsg´aljuk. Ez vezet a c´ımben eml´ıtett fogalmakhoz. Az L ⊆ Rd halmazt alt´ ernek nevezz¨ uk, ha nem¨ ures ´es b´ armely k´et eleme ´es az orig´o ´altal meghat´arozott s´ıkot is tartalmazza, vagyis x, y ∈ L, λ, µ ∈ R eset´en λx + µy ∈ L. K´etf´ele alapvet˝o konstrukci´ o van, amelyekkel egy adott S ⊆ Rd halmazb´ol altereket gy´ arthatunk. Az els˝o a line´aris burok, a m´asodik az ortogon´alis kieg´esz´ıt˝ o alt´er k´epz´ese. Alterek tetsz˝ oleges rendszer´enek metszete nyilv´an alt´er, ´ıgy egy adott S ⊆ Rd halmaz eset´en l´etezik egy´ertelm˝ uen az S-t tartalmaz´ o legsz˝ ukebb alt´er, S line´ aris burka, lin S := ∩{L : S ⊆ L, L alt´er}. 1. Bizony´ıtsd be, hogy lin S = {
k X i=1
λi xi : k ∈ N , λi ∈ R, xi ∈ S (i = 1, . . . , k)}.
Adott A ∈ Rm×n m´atrix eset´en az A k´ eptere Im A := {Ax : x ∈ Rn }. Az 1. feladat szerint a k´ept´er ´eppen egy v´eges vektorrendszer (A oszlopvektorai) line´aris burka. Adott S ⊆ Rd halmaz eset´en S ortogon´ alis kieg´ esz´ıt˝ o altere az ¨osszes S-beli vektorra mer˝oleges vektorok halmaza. (K´et vektor, x ´es y mer˝ oleges, vagy ortogon´ alis, ha xT y = 0.) Az S halmaz ortogon´alis kieg´esz´ıt˝o alter´enek jele S ⊥ , eszerint S ⊥ := {x ∈ Rd : xT y = 0 (y ∈ S)}. A v´eges S eset´enek most a nullt´er felel meg: Adott A ∈ Rm×n m´atrix eset´en az A nulltere Ker A := {x ∈ Rn : Ax = 0}. Egy m´atrix nulltere teh´ at ´eppen a megfelel˝o homog´en line´aris egyenletrendszer megold´ashalmaza. 2. Bizony´ıtsd be, hogy a) lin (S1 ∪ S2 ) = (lin S1 ) + (lin S2 ); b) (S1 ∪ S2 )⊥ = S1⊥ ∩ S2⊥ . Hogyan alakulnak ezek az egyenl˝ os´egek, mikor S1 , S2 alterek? 3. Bizony´ıtsd be, hogy (Im A)⊥ = Ker (AT ). A k´epterek ´es nullterek alterek. Megford´ıtva igaz-e, hogy minden alt´er el˝oa´ll k´ept´erk´ent ´es nullt´erk´ent is? Az els˝o k´erd´es megv´ alaszol´ as´ ahoz ´erdemes az alterek minim´alis (nem sz˝ uk´ıthet˝o) gener´al´o rendszereit vizsg´alni. (Egy S ⊆ L halmazt az L alt´er gener´ al´ o rendszer´enek h´ıvunk, ha lin S = L. Ilyen p´eld´ aul az eg´esz L.) 4. a) b) c)
Adott S ⊆ Rd halmaz eset´en az al´ abbi a ´ll´ıt´ asok ekvivalensek: Minden S ′ ⊂ S eset´en lin S ′ ⊂ lin S; Minden s ∈ S eset´en s 6∈ lin (S \ {s}); Pk Ha k ∈ N , λ1 , . . . , λk ∈ R, x1 , . . . , xk ∈ S, tov´ abb´ a i=1 λi xi = 0, akkor λ1 = . . . = λk = 0.
Ha az a), b), vagy c) ´ all´ıt´ asok egyike (´es akkor mindegyike) teljes¨ ul, akkor az S halmazt line´ arisan f¨ uggetlennek nevezz¨ uk, k¨ ul¨onben pedig line´ arisan ¨ osszef¨ ugg˝ onek. A line´aris f¨ uggetlens´eg fogalma nyilv´an az el˝oz˝o fejezetben szerepl˝ o defin´ıci´o ´ altal´ anos´ıt´asa, hiszen egy line´arisan f¨ uggetlen vektorrendszer nem tartalmazhat egyforma elemeket. Line´arisan f¨ uggetlen p´eld´ aul az u ¨ res halmaz. Egy line´arisan f¨ uggetlen halmaz legfeljebb d elem˝ u lehet.
11
5. Adott L ⊆ Rd alt´er ´es S ⊆ Rd halmaz eset´en az al´ abbi a ´ll´ıt´ asok ekvivalensek: a) S minim´ alis gener´ al´ o rendszere L-nek, vagyis lin S = L, de S ′ ⊂ S eset´en lin S ′ ⊂ L; b) S line´ arisan f¨ uggetlen gener´ al´ o rendszere L-nek; c) S maxim´ alis (nem b˝ ov´ıthet˝ o) L-beli line´ arisan f¨ uggetlen rendszer, vagyis S ⊆ L line´ arisan f¨ uggetlen, de S ⊂ S˜ ⊆ L eset´en S˜ m´ ar line´ arisan o ¨sszef¨ ugg˝ o. Ha az a), b), vagy c) ´ all´ıt´ asok egyike (´es akkor mindegyike) teljes¨ ul, akkor az S halmazt az L alt´er b´ azis´anak nevezz¨ uk. A fejezet elej´en feltett els˝o k´erd´es¨ unk ´ıgy fogalmazhat´ o: L´etezik-e minden alt´ernek b´ azisa? Ezt a k´erd´est (´ altal´ anosabban) v´alaszolja meg a k¨ovetkez˝o feladat. 6. Legyen L ⊆ Rd alt´er, Sf line´ arisan f¨ uggetlen, Sg az L gener´ al´ o rendszere. Tegy¨ uk fel, hogy Sf ⊆ Sg . Ekkor l´etezik az L-nek olyan Sb b´ azisa, amelyre Sf ⊆ Sb ⊆ Sg . Speci´ alisan minden f¨ uggetlen b´ aziss´ a b˝ ov´ıthet˝ o ´es minden gener´ al´ o rendszer b´ aziss´ a sz˝ uk´ıthet˝ o. ´ [Utmutat´ as: Sb legyen az Sf -et tartalmaz´ o Sg -beli line´ arisan f¨ uggetlenek k¨ oz¨ ul egy maxim´ alis elemsz´ am´ u.] 7. Legyen L ⊆ Rd alt´er. Ha Sf ⊆ L line´ arisan f¨ uggetlen rendszer, tov´ abb´ a Sg az L gener´ al´ o rendszere, akkor Sf elemsz´ ama kevesebb, mint Sg -´e. ´ [Utmutat´ as: Feltehet˝ o, hogy Sg -nek v´eges sok eleme van. Bel˝ ol¨ uk mint oszlopvektorokb´ ol a ´ll´ıtsunk o ¨ssze egy G m´ atrixot, hasonl´ oan Sf -b˝ ol egy F m´ atrixot. Ekkor l´etezik X m´ atrix u ´gy, hogy F = GX. Vizsg´ aljuk meg az F = GX m´ atrix rangj´ at.] A 7. feladatb´ol azonnal k¨ovetkezik, hogy L minden b´ azisa azonos elemsz´ am´ u. Ezt a k¨oz¨os elemsz´ amot (v´egtelen halmazr´ ol l´ev´en sz´ o nem rangnak, hanem) az L alt´er dimenzi´ oj´anak nevezz¨ uk. 8. Az Sb halmaz pontosan akkor b´ azisa az L alt´ernek, ha az L-beli line´ arisan f¨ uggetlenek (gener´ al´ o rendszerek) k¨ ozt a legnagyobb (legkisebb) elemsz´ am´ u. 9. Az Sb ⊆ L halmaz pontosan akkor b´ azisa az L alt´ernek, ha minden L-beli elemet pontosan egyf´elek´eppen lehet kikombin´ alni Sb elemeib˝ ol. Ezzel a b´ azisok sokf´ele jellemz´es´et ismert¨ uk meg. Bizony´ıt´as n´elk¨ ul megjegyezz¨ uk, hogy alkalmasan defini´alva a gener´ al´ o rendszer fogalm´at a t´etelek hasonl´ oan sz´eles spektrum´ at nyerhetj¨ uk v´eges vektorrendszerek eset´en is (egy r´esz¨ uket bizony´ıtottuk az el˝oz˝o fejezetben). A k´et t´etelk¨or k¨ozti kapcsolatr´ ol sz´ol a k¨ovetkez˝o feladat: 10. Egy v´eges vektorrendszer gener´ al´ o rendszer´enek nevezz¨ uk azt a r´esz´et, amelyb˝ ol a rendszer minden eleme kikombin´ alhat´ o. Alkossunk a vektorrendszer elemeib˝ ol, mint oszlopvektorokb´ ol egy m´ atrixot. Ekkor a vektorrendszer b´ azisai (gener´ al´ o rendszerei) ´eppen a m´ atrix k´epter´enek vektorrendszerbeli b´ azisai (gener´ al´ o rendszerei). A m´asodik k´erd´es megv´ alaszol´ asa el˝ ott n´eh´any ´eszrev´etel: 11. Alkalmazzuk a Gauss-Jordan elimin´ aci´ ot az Ax = 0 rendszer megold´ asainak megkeres´es´ere. Ekkor az A m´ atrix j1 -edik, ..., jr -edik oszlopa A k´epter´enek a b´ azisa, a q (j) vektorok pedig A nullter´enek b´ azis´ at alkotj´ ak. Speci´ alisan dim (Im A) = r (A) ´es dim (Ker A) = n − r (A). 12. Ha L ⊆ Rd alt´er, akkor dim (L⊥ ) = d − dim L. 13. Ha L ⊆ Rd alt´er, akkor L⊥⊥ = L.
A fejezet elej´en feltett¨ uk azt a k´erd´est is, hogy egy L ⊆ Rd alt´er el˝oa´ll-e egy m´atrix nullterek´ent. Most m´ar l´atjuk, hogy igen: legyen ugyanis L⊥ = Im AT , akkor L = L⊥⊥ = Ker A.
⊥ ⊥ ⊥ ⊥ 14. Bizony´ıtsd be, hogy ha L1 , L2 ⊆ Rd alterek, akkor a) (L1 + L2 )⊥ = L⊥ 1 ∩ L2 ; b) (L1 ∩ L2 ) = L1 + L2 . ´ [Utmutat´ as: b)-hez haszn´ ald a)-t ´es a 13. feladatot!]
15. Legyenek L1 illetve L2 az x1 , x2 , illetve az y1 , y2 vektorok a ´ltal kifesz´ıtett alterek. Hat´ arozd meg az L1 + L2 , L1 ∩ L2 , (L1 + L2 )⊥ ´es az (L1 ∩ L2 )⊥ alterek egy b´ azis´ at ´es dimenzi´ oj´ at! x1 := (1, 2, 1, 0)T , x2 := (−1, 1, 1, 1)T , y1 := (2, −1, 0, 1)T , y2 := (1, −1, 3, 7)T 16. Bizony´ıtsd be, hogy dim (L1 + L2 ) + dim (L1 ∩ L2 ) = dim L1 + dim L2 , ha L1 , L2 alterek! ´ [Utmutat´ as: Eg´esz´ıts¨ uk ki L1 ∩ L2 egy b´ azis´ at L1 , illetve L2 egy-egy b´ azis´ av´ a. A k´et b´ azis u ´ni´ oja L1 + L2 b´ azisa lesz.] 12
17. Tetsz˝ oleges L ⊆ Rd alt´er eset´en minden Rd -beli vektor pontosan egyf´elek´eppen a ´ll el˝ o, mint egy L-beli ´es ⊥ egy L -beli vektor o ¨sszege. ´ [Utmutat´ as: Haszn´ aljuk az el˝ oz˝ o feladatot!] A 17. feladatban szerepl˝ o´ all´ıt´ asra konstrukt´ıv bizony´ıt´ast is adhatunk. Ehhez el˝osz¨ or is vegy¨ uk ´eszre, hogy 18. Ha az A m´ atrix oszlopvektorai line´ arisan f¨ uggetlenek, akkor AT A invert´ alhat´ o. T ´ [Utmutat´ as: Ker (A A) = Ker A = {0}.]
Ha most az A m´atrix oszlopvektorai az L alt´er b´ azis´at alkotj´ak, akkor adott x ∈ Rd eset´en olyan x = x1 +x2 felbont´ ast keres¨ unk, amelyre x1 ∈ Im A ´es x2 ∈ Ker AT , vagyis x1 = Ay1 valamely y1 vektorral ´es AT x2 = 0. ¨ Osszefoglalva az x2 + Ay1 = x, AT x2 = 0 egyenletrendszert kell megoldanunk. Ennek egy¨ utthat´ om´ atrixa invert´ alhat´o, inverze −1 I A I −A I 0 I 0 I − A(AT A)−1 AT A(AT A)−1 = = . AT 0 0 I 0 −(AT A)−1 −AT I (AT A)−1 AT −(AT A)−1 Ebb˝ol ad´odik, hogy x1 = A(AT A)−1 AT x ´es x2 = x − x1 . Egyszer˝ us¨odne a k´eplet, ha feltehetn´enk, hogy AT A = I. (Nem kellene invert´ alni.) De vajon l´etezike minden Im A-k´ent adott alt´erhez (ahol A oszlopvektorai line´arisan f¨ uggetlenek) olyan B m´atrix, amelyre B T B = I ´es Im B = Im A? Az al´ abbiakban l´atni fogjuk, alni. √ hogy hogyan kell egy ilyen B-t konstru´ Az x ∈ Rd vektor hossza (euklideszi norm´aja) az xT x ´ert´ek. Jele ||x||. Az, hogy egy B m´atrixra B T B = I ezek ut´an u ´ gy fogalmazhat´ o, hogy a B oszlopvektorai p´ aronk´ent mer˝oleges egys´egnyi hossz´ u vektorok. 19. Bizony´ıtsd be, hogy a ||.|| norm´ ara fenn´ allnak: a) ||x|| ≥ 0, ´es ||x|| = 0 pontosan akkor, ha x = 0; b) ||λx|| = |λ|·||x|| tetsz˝ oleges λ ∈ R eset´en; c) (Cauchy-Schwarz-Bunyakovszkij egyenl˝ otlens´eg) |xT y| ≤ ||x||·||y||; d) (h´ aromsz¨ og-egyenl˝ otlens´eg) ||x + y|| ≤ ||x|| + ||y||; e) c)-ben (d)-ben) pontosan akkor van egyenl˝ os´eg, ha az x, y vektorok line´ arisan o ¨sszef¨ ugg˝ ok (´es xT y ≥ 0). ´ [Utmutat´ as c)-hez: Feltehet˝ o, hogy x 6= 0. Ekkor ((−xT y/||x||2 )x + y)T ((−xT y/||x||2 )x + y) ≥ 0.]
20. Bizony´ıtsd be, hogy ha 0 6= b1 , . . . , bk ∈ Rd p´ aronk´ent mer˝ oleges vektorok, akkor line´ arisan f¨ uggetlenek.
21. Bizony´ıtsd be, az al´ abbi ortogonaliz´ aci´ os elj´ ar´ as helyess´eg´et: a) bi ∈ lin {a1 , . . . , ai } (i = 1, . . . , k); b) bi 6= 0 (i = 1, . . . , k); c) bi mer˝ oleges a b1 , . . . , bi−1 vektorokra; d) a bi vektorok p´ aronk´ent mer˝ oleges egys´egvektorok ´es lin {a1 , . . . , ak } = lin {b1 , . . . , bk }. Gram-Schmidt ortogonaliz´ aci´ os elj´ ar´ as Be: a1 , . . . , ak [line´ arisan f¨ uggetlen vektorok] b1 := a1 , i := 1 Ciklus, am´ıg i < k bT a
bT a
b1 − . . . − ibT i+1 bi + ai+1 bi+1 := − 1bT i+1 b 1 b1 i i i := i + 1 Ciklus v´ege b1 := b1 /||b1 ||, . . . , bk := bk /||bk || Ki: b1 , . . . , bk Program v´ege. 22. Az x vektort bontsuk k´et olyan vektor o ¨sszeg´ere, melyek k¨ oz¨ ul az egyik az a1 , a2 vektorok a ´ltal kifesz´ıtett alt´erben fekszik, a m´ asik pedig mer˝ oleges erre az alt´erre. x = (5, 2, −2, 2)T , a1 = (2, 1, 1, −1)T , a2 = (1, 1, 3, 0)T 23. Legyen az x vektor az x1 ∈ L ´es x2 ∈ L⊥ vektorok o ¨sszege. Mutassuk meg, hogy ||x − x1 ||2 ≤ ||x − y||2 b´ armely y ∈ L eset´en! ´ [Utmutat´ as: Ha L = Im X, X T X = I, akkor x1 = XX T x, y = Xy ′ .] Az x, y ∈ Rd nemnulla vektorok sz¨ oge radi´anban az a 0 ´es π k¨oz´e es˝o ´ert´ek, amelynek koszinusza xT y/(||x||· ||y||).
24. Legyenek x, y nemnulla vektorok, tov´ abb´ a x = x1 + x2 , ahol x1 ∈ {λy : λ ∈ R}, x2 ∈ {λy : λ ∈ R}⊥ . Mutassuk meg, hogy x, y sz¨ og´enek koszinusza megegyezik az ||x1 ||/||x|| ´ert´ekkel plusz, vagy m´ınusz el˝ ojellel aszerint, hogy x1 az y-nak pozit´ıv, vagy negat´ıv sz´ amszorosa. 13
25. Legyenek x1 , x2 mint a 22. feladatban. Mutassuk meg, hogy az L-beli vektorok k¨ oz¨ ul x az x1 -gyel z´ arja be a legkisebb sz¨ oget! 26. Hat´ arozzuk meg a legkisebb sz¨ oget, amelyet az a1 , a2 vektorok a ´ltal kifesz´ıtett t´er bez´ ar az x vektorral! x := (1, 3, −1, 3)T , a1 := (1, −1, 1, 1)T , a2 := (5, 1, −3, 3)T Most r´at´er¨ unk a nem felt´etlen¨ ul homog´en line´aris egyenletrendszerek megold´ashalmazainak vizsg´alat´ara. Az M ⊆ Rd halmazt affin halmaznak nevezz¨ uk, ha b´ armely k´et eleme ´altal meghat´arozott egyenest is tartalmazza, vagyis x, y ∈ M, λ ∈ R eset´en λx + (1 − λ)y ∈ M . Affin halmazra p´elda az eltolt alterek ´es a line´aris egyenletrendszerek megold´ashalmazai, vagyis a p + Im B ´es az {x : Ax = b} alak´ u halmazok. Az affin halmazokra hasonl´ o elm´elet ´ep´ıthet˝o ki, mint alterekre. Ebben a line´aris burok szerep´et az affin burok veszi ´at, a line´aris kombin´ aci´ o szerep´et az affin kombin´aci´ o. Defini´alhat´o az affin gener´al´o rendszer, az affin f¨ uggetlen rendszer, az affin b´ azis ´es az affin dimenzi´ o is. A megfelel˝o t´etelek felsorol´asa helyett itt csak a szoros kapcsolat okait magyar´az´o t´eteleket eml´ıtj¨ uk: 27. A nem¨ ures affin halmazok ´eppen az eltolt alterek. Minden affin halmaz pontosan egy alt´er eltoltjak´ent a ´ll el˝ o, amely alteret u ´gy kapjuk, hogy az affin halmazb´ ol kivonjuk egy tetsz˝ oleges elem´et. A p + Im B affin halmazzal p´ arhuzamos alt´er term´eszetesen Im B. Az {x : Ax = b} affin halmazzal p´ arhuzamos alt´er Ker A, mint azt a k¨ovetkez˝o feladat mutatja: 28. Ha az Ax = b rendszer megoldhat´ o ´es p egy tetsz˝ oleges megold´ asa, akkor {x : Ax = b} = p + Ker A. A 27. feladat szerint minden affin halmaz el˝oa´ll p + Im B alakban. A p + Im B affin halmaz pedig el˝oa´ll {x : Ax = b} alakban, csak v´alasszuk A-t u ´ gy, hogy Im B = Ker A legyen (vagyis Ker (B T ) = Im (AT )), ´es legyen b = Ap. Ekkor a 28. feladat szerint {x : Ax = b} = p + Ker A = p + Im B lesz. A fentiek ismeret´eben k¨onnyen ellen˝ orizhet˝o a k¨ovetkez˝o feladatban le´ırt du´ al Gauss-Jordan elimin´ aci´ o helyess´ege. 29. Adott A ∈ Rm×n , c ∈ Rn eset´en az AT y = c rendszert az al´ abbi m´ odon oldhatjuk meg: Hozzuk az A m´ atrixot Hermite-f´ele norm´ alalakra az E transzform´ aci´ o m´ atrixszal. Ekkor a megoldhat´ o (EA)T y ′ = c rendszer megold´ asai ´eppen azok a vektorok, amelyeknek ik -adik elemei cjk -val egyeznek meg, ahol k = 1, . . . , r. A megoldhat´ o AT y = c rendszer megold´ asai pedig az y = E T y ′ alak´ u vektorok, ahol y ′ az (EA)T y ′ = c rendszer megold´ asain fut. Ha a fenti vektorok egyike (´es akkor mindegyike) nem lenne megold´ as, p´eld´ aul az AT y j-edik (j) (j) eleme nem cj , akkor q a megoldhatatlans´ ag tan´ uja, vagyis olyan vektor, amelyre Aq = 0, de cT q (j) 6= 0.
K´erdezhet˝o, hogy mi sz¨ uks´eg van a du´ al m´odszerre, mikor AT y = c is csak egy egyenletrendszer, amit megoldhatn´ank Gauss-Jordan elimin´ aci´ oval. A v´alasz, hogy vannak a Gauss-Jordan ´es a du´ al Gauss-Jordan elimin´ aci´ onak u ´ n. m´ odos´ıtott v´ altozatai, amelyben az eg´esz A egy¨ utthat´om´ atrix helyett csak az E transzform´aci´ o m´atrixszal sz´ amolunk, t´ artakar´ekoss´agi okokb´ ol. Tegy¨ uk fel, hogy A ∈ Rm×n , ahol m j´oval kisebb, T mint az n. Ekkor az A y = c megold´as´ ahoz a m´odos´ıtott Gauss-Jordan elimin´ aci´ oval n × n-es transzform´ aci´ o m´atrixszal kellene sz´ amolni, m´ıg a m´odos´ıtott du´ al Gauss-Jordan elimin´ aci´ on´al csak m × m-esek a transzform´aci´ o m´atrixok. 30. Tervezd meg a m´ odos´ıtott Gauss-Jordan ´es du´ al Gauss-Jordan elimin´ aci´ okat!
14
6. Saj´ at´ ert´ ekek, definit m´ atrixok. Adott M ∈ C n×n eset´en a µ ∈ C sz´ amot az M m´atrix saj´ at´ ert´ ek´enek nevezz¨ uk, ha l´etezik nemnulla u ∈ C n vektor u ´ gy, hogy M u = µu. Az u vektort ekkor az M m´atrix µ saj´at´ert´ek´ehez tartoz´o saj´ atvektor´anak nevezz¨ uk. Ha µ ∈ C az M m´atrix saj´ at´ert´eke, akkor a (µI − M )u = 0 rendszernek van nemtrivi´alis megold´asa, ekkor teh´at a rendszer egy¨ utthat´ om´ atrixa szingul´ aris, vagyis det (µI − M ) = 0. Megford´ıtva ha valamely µ ∈ C eset´en det (µI − M ) = 0, akkor a (µI − M )u = 0 rendszernek van nemtrivi´alis megold´asa, vagyis µ az M m´atrix saj´at´ert´eke. Ha µ-t v´altoz´ onak tekintj¨ uk, akkor det (µI − M ) ennek polinomja lesz: Pn P 1. det (µI − M ) = k=0 cn−k µn−k , ahol cn = 1 ´es cn−k = (−1)k · {det M ′ : M ′ k-rend˝ u, szimmetrikus minorja M -nek} (k = 1, . . . , n). (M ′ az M szimmetrikus minorja, ha M -b˝ ol n´eh´ any sor ´es a megfelel˝ o oszlopok elhagy´ as´ aval keletkezik.) A c(µ) := det (µI − M ) polinomot az M m´atrix karakterisztikus polinomj´anak nevezz¨ uk. A fentiek szerint M saj´at´ert´ekei ´eppen az c(µ) komplex gy¨ okei. Az, hogy minden m´atrixnak van saj´ at´ert´eke Gauss t´etel´eb˝ol k¨ovetkezik, mely szerint minden komplex egy¨ utthat´os polinomnak van komplex gy¨ oke. A saj´at´ert´ekeket elm´eletileg az al´abbi algoritmus seg´ıts´eg´evel kereshetj¨ uk meg: Kezdetben legyen f1 (µ) := c(µ). Keress¨ uk meg az aktu´alis fi (µ) polinom egy komplex gy¨ ok´et (legyen ez µi ) ´es osszuk le az fi (µ) polinomot a µ − µi line´aris polinommal. Az ´ıgy kapott polinom legyen fi+1 (µ). Ezt ism´etelj¨ uk addig, m´ıg v´eg¨ ul az fn+1 (µ) nulladfok´ u polinomhoz jutunk. (Mivel az elj´ar´ast 1 f˝oegy¨ utthat´os (´ un. f˝ o-) polinomra alkalmaztuk, fn+1 (µ) sz¨ uks´egk´eppen az 1 polinom lesz.) Az elj´ar´as helyess´eg´enek bizony´ıt´ as´ ahoz vegy¨ uk ´eszre, hogy 2. Ha µ0 az f (µ) polinom gy¨ oke, akkor µ − µ0 oszt´ oja az f (µ) polinomnak. ´ [Utmutat´ as: f (µ) = f (µ) − f (µ0 ) ´es µ − µ0 oszt´ oja µk − µk0 -nak (k = 1, . . . , n).] A fenti algoritmus sor´an a c(µ) polinom egy (µ − µ1 ) · . . . · (µ − µn ) felbont´ as´at kaptuk line´aris polinomok szorzat´ ara, ahol µ1 , . . . , µn (nem felt´etlen¨ ul p´ aronk´ent k¨ ul¨onb¨ oz˝o) komplex sz´amok. 3. A µ1 , . . . , µn sz´ amok ´eppen a c(µ) polinom gy¨ okei. 4. Ha az f (µ) ´es g(µ) n-edfok´ u polinomok a µ v´ altoz´ o legal´ abb n + 1 ´ert´eke mellett megegyeznek, akkor a k´et polinom megegyezik, vagyis egy¨ utthat´ oik megegyeznek. 5. aris t´enyez˝ ok szorzat´ ara val´ o felbont´ as a t´enyez˝ ok sorrendj´et˝ ol eltekintve egy´ertelm˝ u: Ha Q Qn A fenti line´ n ′ ′ ′ ), akkor (µ , . . . , µ ) = (µ , . . . , µ )P valamely P permut´ a ci´ o m´ a trixszal. (µ − µ (µ − µ ) = 1 n i 1 n i i=1 i=1
A (µ1 , . . . , µn ) (a fentiek szerint egy´ertelm˝ uen meghat´arozott) sz´am n-est az M spektrum´anak nevezz¨ uk. Az M egy saj´at´ert´ek´enek (azaz c(µ) egy gy¨ ok´enek) multiplicit´ asa az a sz´am, ah´anyszor a saj´at´ert´ek a spektrumban szerepel. (Egy polinom µ0 gy¨ oke multiplicit´as´anak m´eg sz´amos a felbont´ ast´ ol f¨ uggetlen ekvivalens defin´ıci´oja l´etezik, p´eld´ aul a multiplicit´as a legnagyobb k sz´am, amelyre (µ − µ0 )k oszt´oja a polinomnak, de a polinom deriv´altjainak ismeret´eben is meghat´arozhat´ o.) P´eld´ aul egy (fels˝ o, vagy als´o) h´ aromsz¨ og m´atrix spektruma a diagon´ alisa. A spektrum meghat´arozza a karakterisztikus polinomot (viszont mag´at a m´atrixot nem, l´asd 0, e1 eT2 ): 6. A karakterisztikus P polinom cn−k egy¨ utthat´ oi a spektrum µi elemeinek f¨ uggv´eny´eben az al´ abbi m´ odon adhat´ ok meg: cn−k = (−1)k · 1≤i1 <...
15
9. Ha E ∈ Rn×n invert´ alhat´ o m´ atrix, M ∈ Rn×n , akkor M ´es E −1 M E karakterisztikus polinomja ´es ´ıgy spektruma is megegyezik. ˜ ∈ Rn×n m´atrixok hasonl´ Az M ∈ Rn×n ´es az M oak, ha l´etezik E ∈ Rn×n invert´ alhat´o m´atrix u ´ gy, hogy ˜ = E −1 M E. K¨ M onnyen bel´ athat´o, hogy a hasonl´ os´ag ekvivalenciarel´aci´ o a val´os m´atrixok halmaz´an. Ennek az ekvivalenciarel´aci´ onak a finom´ıt´ asa lesz az ortogon´alis hasonl´ os´ag. Az U ∈ Rn×n m´atrix ortogon´ alis, ha invert´ alhat´o ´es inverze megegyezik a transzpon´altj´ aval. (Ortogon´alis m´atrix p´eld´ aul minden permut´aci´ o m´atrix.) Tudjuk hogy az U T = U −1 felt´etel ekvivalens azzal is, hogy az U oszlopvektorai p´ aronk´ent mer˝oleges egys´egvektorok (vagyis U T U = I) ´es azzal is, hogy az U sorvektorai p´ aronk´ent mer˝oleges egys´egvektorok (vagyis U U T = I). Ortogon´ alis m´atrix transzpon´altja ´es ortogon´alis m´atrixok szorzata is ortogon´alis m´atrix. 10. Ha u1 , . . . , uk p´ aronk´ent mer˝ oleges egys´egvektorok, akkor l´etezik U ortogon´ alis m´ atrix u ´gy, hogy U e1 = u 1 , . . . , U ek = u k . ˜ ∈ Rn×n m´atrixok ortogon´ Az M ∈ Rn×n ´es az M alisan hasonl´ oak, ha l´etezik U ∈ Rn×n ortogon´alis T ˜ m´atrix u ´ gy, hogy M = U M U . Az ortogon´alis hasonl´ os´ag is ekvivalenciarel´aci´ o a val´os m´atrixok halmaz´an. 11. (Schur t´ etele) Minden M v.s.v. m´ atrix ortogon´ alisan hasonl´ o egy F fels˝ o h´ aromsz¨ og m´ atrixhoz. Az F m´ atrix f˝ oa ´tl´ oj´ aban az M spektrum´ anak elemei a ´llnak. Speci´ alisan egy M val´ os, szimmetrikus m´ atrix ortogon´ alisan hasonl´ o egy D diagon´ alis m´ atrixhoz, melynek f˝ oa ´tl´ oj´ aban az M spektrum´ anak elemei a ´llnak. ´ [Utmutat´ as: k szerinti teljes indukci´ oval mutassuk meg, hogy l´etezik Uk ortogon´ alis m´ atrix u ´gy, hogy UkT M Uk a jobb als´ o (n − k) × (n − k)-as r´eszm´ atrix´ at lesz´ am´ıtva fels˝ o h´ aromsz¨ og m´ atrix. A k = 1 esetr˝ ol: Egy v.s.v. m´ atrixnak minden saj´ at´ert´ek´ehez tartozik val´ os saj´ atvektor is. Egy ilyet norm´ aljunk le ´es eg´esz´ıts¨ uk ki U1 ortogon´ alis m´ atrixsz´ a. Ekkor U1 megfelel.] 12. Ha M v.s.v. (µ1 , . . . , µn ) spektrummal, akkor M −1 is v.s.v. (1/µ1 , . . . , 1/µn ) spektrummal. 13. Ha f (µ) polinom, M v.s.v. (µ1 , . . . , µn ) spektrummal, akkor f (M ) is v.s.v. (f (µ1 ), . . . , f (µn )) spektrummal. A k¨ovetkez˝okben feltessz¨ uk, hogy M ∈ Rn×n val´os, szimmetrikus m´atrix, U ortogon´alis m´atrix u ´ gy, hogy U M U =: D diagon´ alis m´atrix, tov´abb´a D f˝oa´tl´ oj´ aban M spektrum´ anak elemei ´allnak n¨ ovekv˝o sorrendben, vagyis d11 = µ1 ≤ . . . ≤ dnn = µn . (A n¨ ovekv˝o sorrendet el´erhetj¨ uk u ´ gy, hogy U -t jobbr´ ol szorozzuk egy megfelel˝o permut´aci´ o m´atrixszal.) M U = U D miatt M ui = µi ui (1 ≤ i ≤ n), teh´at az U i-edik oszlopa a µi -nek megfelel˝o saj´atvektor. E jel¨ol´esekkel T
14. Legyen µ az M saj´ at´ert´eke ´es tegy¨ uk fel, hogy µk−1 < µ = µk = . . . = µl < µl+1 . Ekkor az M µ-h¨ oz tartoz´ o saj´ atvektorai ´eppen az uk , . . . , ul vektorok line´ aris kombin´ aci´ oi, lesz´ am´ıtva a 0 vektort. 15. Felcser´elhet˝ o val´ os szimmetrikus m´ atrixok egyszerre ortogon´ alisan diagonaliz´ alhat´ ok, vagyis ha A, B ∈ Rn×n szimmetrikus m´ atrixok ´es AB = BA (vagy m´ ask´eppen AB szimmetrikus), akkor l´etezik X ortogon´ alis m´ atrix u ´gy, hogy X T AX ´es X T BX is diagon´ alis m´ atrixok. ´ [Utmutat´ as: Legyen Y az A-t diagonaliz´ al´ o ortogon´ alis m´ atrix, ekkor yi ´es Byi is saj´ atvektorai A-nak egyenl˝ o saj´ at´ert´ekkel. Ez´ert BY = Y C, ahol C szimmetrikus blokkdiagon´ alis m´ atrix. Diagonaliz´ aljuk C-t egy hasonl´ o szerkezet˝ u Z ortogon´ alis m´ atrixszal, ekkor X := Y Z megfelel.] 16. (Rayleigh t´ etele) µ1 = min {xT M x : ||x|| = 1} ´es µn = max{xT M x : ||x|| = 1}. A sz´els˝ o´ert´ekhelyek ´eppen a megfelel˝ o saj´ atvektorok. 17. Legyen M ′ az M szimmetrikus minorja. Ekkor µ1 ≤ µ′1 ´es µ′n′ ≤ µn . 18. Bizony´ıtsd be, hogy ha a val´ os, szimmetrikus A m´ atrix valamennyi saj´ at´ert´eke az [a, c] z´ art intervallum eleme, ´es a val´ os, szimmetrikus B m´ atrix valamennyi saj´ at´ert´eke a [b, d] z´ art intervallum eleme, akkor az A+B m´ atrix valamennyi saj´ at´ert´eke az [a + c, b + d] z´ art intervallumhoz tartozik. Az M val´os szimmetrikus m´atrixot pozit´ıv szemidefinitnek nevezz¨ uk, ha tetsz˝ oleges x ∈ Rn eset´en xT M x ≥ 0. Az M val´ os szimmetrikus m´atrixot pozit´ıv definitnek nevezz¨ uk, ha tetsz˝ oleges 0 6= x ∈ Rn eset´en xT M x > 0. A pozit´ıv szemidefinit, illetve pozit´ıv definit m´atrixok halmaz´at jel¨olje PSD, illetve PD. Ezek a definit´ asi tulajdons´ agok szoros kapcsolatban vannak a saj´at´ert´ekek el˝ojel´evel: 19. Legyen M val´ os, szimmetrikus m´ atrix. Ekkor a k¨ ovetkez˝ oa ´ll´ıt´ asok ekvivalensek: a) M pozit´ıv szemidefinit; b) M saj´ at´ert´ekei nemnegat´ıvak; c) M = V V T valamely V ∈ Rn×r eset´en. (A legkisebb ilyen r sz´ am az M m´ atrix rangja.) 16
20. Legyen M val´ os, szimmetrikus m´ atrix. Ekkor a k¨ ovetkez˝ oa ´ll´ıt´ asok ekvivalensek: a) M pozit´ıv definit; b) M saj´ at´ert´ekei pozit´ıvak; c) M = V V T valamely V ∈ Rn×n nemszingul´ aris m´ atrix eset´en. Egy el´egs´eges felt´etelt szolg´ altat a definit´ asra a k¨ovetkez˝o feladat: 21. (Gersgorin ok) Legyen M val´ os, szimmetrikus m´ atrix, µ az M saj´ at´ert´eke. P Ekkor l´etezik 1 ≤ i ≤ n P k¨or¨ alisan, ha i = 1, . . . , n eset´en mii > (≥) j6=i |mij |, akkor M pozit´ıv u ´gy, hogy j6=i |mij | ≥ |µ − mii |. Speci´ (szemi)definit. Sz´amos m˝ uvelet nem vezet ki a definit m´atrixok k¨or´eb˝ol, p´eld´ aul a nemnegat´ıv skal´arral val´o szorz´ as, az ¨sszead´as, tov´abb´a a hatv´anyoz´as. Az invert´ o al´as nem vezet ki az invert´ alhat´o pozit´ıv szemidefinit m´atrixok, vagyis a pozit´ıv definit m´atrixok k¨or´eb˝ol. Az A, B ∈ Rn×n m´atrixok Hadamard szorzata az a C = A ◦ B ∈ Rn×n m´atrix, amelynek (i, j)-edik eleme, cij = aij · bij (i, j = 1, . . . , n). Nevezik “lusta di´ak szorzatnak” is, ´erthet˝ o okokb´ ol.
22. Ha A, B ∈ PSD, akkor A ◦ B ∈ PSD. Ha A, B ∈ PD, akkor A ◦ B ∈ PD.
Az A ∈ Ra×c ´es a B ∈ Rb×d m´atrixok Kronecker szorzata az a C = A ⊗ B ∈ (Rb×d )a×c hiperm´atrix, amelynek (i, j)-edik blokkja Cij = aij B 1 ≤ i ≤ a, 1 ≤ j ≤ c). Ut´anasz´amolhatunk, hogy a) (A1 ⊗ A2 )T = AT1 ⊗ AT2 ´es b) (A1 ⊗ A2 )(A3 ⊗ A4 ) = (A1 A3 ) ⊗ (A2 A4 ). 23. Ha A, B ∈ PSD, akkor A ⊗ B ∈ PSD. Ha A, B ∈ PD, akkor A ⊗ B ∈ PD.
24. Ha A, B ∈ PSD felcser´elhet˝ oek, akkor A · B ∈ PSD. Ha A, B ∈ PD felcser´elhet˝ oek, akkor A · B ∈ PD.
25. Legyen A ∈ PSD, tov´ abb´ a k ≥ 1 eg´esz sz´ am. Ekkor l´etezik egy´ertelm˝ uen egy B pozit´ atrix, √ıv szemidefinit m´ amelyre B k = A. Ez a B felcser´elhet˝ o A-val ´es rangja megegyezik A rangj´ aval. Jele: k A. ´ [Utmutat´ as: Egy´ertelm˝ us´egr˝ ol: Tegy¨ uk fel, hogy B1k = B2k , ahol B1 , B2 0. Legyen Bi =: Qi Di′ QTi , ahol k k −1 T ′ ol Q := QT2 Q1 jel¨ ol´es Qi = Qi ´es Di ≥ 0 (i = 1, 2) diagon´ alis m´ atrix. Ekkor Q1 D1′ QT1 = Q2 D2′ QT2 , amib˝ ′k ′k ′ ′ mellett QD1 = D2 Q ´es ´ıgy QD1 = D2 Q, vagyis B1 = B2 k¨ ovetkezik.] A val´os n-vektorok hossz´ anak ´es sz¨ og´enek mint´ ara ´ertelmezhet˝o val´os, szimmetrikus m´atrixok hossza Pn aj´ n T x arszorzatot a A • B := tr (A · B T ) = (Frobenius norm´ a ja) ´ e s sz¨ o ge is, ha az x y = i yi (x, y ∈ R ) skal´ i=1 Pn n×n szimmetrikus m´atrixok) skal´arszorzat helyettes´ıti. i,j=1 aij bij (A, B ∈ R 26. K´et pozit´ıv szemidefinit m´ atrix legfeljebb 90◦ -os sz¨ oget z´ ar be. Megford´ıtva ha egy val´ os szimmetrikus m´ atrix minden m´ as pozit´ıv szemidefinit m´ atrixszal legfeljebb 90◦ -os sz¨ oget z´ ar be, akkor maga is pozit´ıv szemidefinit. K´et pozit´ıv szemidefinit m´ atrix pontosan akkor mer˝ oleges egym´ asra, ha (m´ atrix)szorzatuk a nulla m´ atrix.
Jel¨olje A B, ha A − B ∈ PSD, hasonl´ oan A ≻ B, ha A − B ∈ PD (A, B ∈ Rn×n szimmetrikus m´atrixok).
27. A r´eszbenrendez´es a val´ os szimmetrikus m´ atrixok halmaz´ an, vagyis reflex´ıv, szimmetrikus ´es tranzit´ıv.
28. Ha A B, akkor a f˝ oa ´tl´ obeli elemekre aii ≥ bii (i = 1, . . . , n). Ha A B ´es valamely 1 ≤ i ≤ n eset´en aii = bii , akkor Aei = Bei is teljes¨ ul. 29. Ha A ∈ Rn×n szimmetrikus m´ atrix ´es A = A2 , akkor az I A 0, speci´ alisan az A m´ atrix f˝ oa ´tl´ obeli elemeire 1 ≥ aii ≥ 0 (i = 1, . . . , n). Most m´ar r´at´erhet¨ unk arra a feladatra, amely miatt ezt a fejezetet a line´aris egyenletrendszerek t´emak¨ orben t´ argyaljuk. (Amellett, hogy a saj´ atvektorok is line´aris egyenletrendszerek megold´asai.) 30. Ha l´etezik λ > 0 konstans u ´gy, hogy M λbbT , akkor az M x = b rendszer megoldhat´ o. ´ [Utmutat´ as: Haszn´ aljuk Fredholm alternat´ıva t´etel´et!] 31. Az el˝ oz˝ o t´etel felt´etele azzal ekvivalens, hogy b benne van az M pozit´ıv saj´ at´ert´ekeihez tartoz´ o saj´ atvektorai a ´ltal fesz´ıtett alt´erben. Adjunk meg min´el nagyobb megfelel˝ o λ-t! ´ [Utmutat´ as: M λbbT ⇐⇒ D λ(U T b)(U T b)T . A m´ asodik r´eszhez: λ := µn−r (M)+1 /(bT b).] 32. Ha A pozit´ıv definit m´ atrix, akkor minden B val´ os, szimmetrikus m´ atrix eset´en l´etezik λ > 0 konstans u ´gy, hogy λA B. K¨ovetkez˝o c´elunk a pozit´ıv szemidefinit´as gyakorlati szempontb´ol is hasznos krit´eriumainak bizony´ıt´asa. Kisrend˝ u p´eld´ ak eset´en hasznos az al´ abbi ´eszrev´etel: 33. Egy val´ os, szimmetrikus m´ atrix pontosan akkor pozit´ıv szemidefinit, ha szimmetrikus minorjai determin´ ansai nemnegat´ıvak. Egy val´ os, szimmetrikus m´ atrix pontosan akkor pozit´ıv definit, ha szimmetrikus minorjai determin´ ansai pozit´ıvak. 17
Magasabbrend˝ u p´eld´ ak eset´eben a definit´as eld¨ ont´es´et kisebbrend˝ u feladatra vezethetj¨ uk vissza a Schur komplemens seg´ıts´eg´evel: 34. Tegy¨ uk fel, hogy egy A val´ os szimmetrikus m´ atrix egy A′ szimmetrikus minorja pozit´ıv definit. Ekkor az A ′ pontosan akkor pozit´ıv (szemi)definit, ha A Schur komplemense pozit´ıv (szemi)definit. Ennek az ´eszrev´etelnek a seg´ıts´eg´evel k¨onnyen tervezhet¨ unk algoritmust annak eld¨ ont´es´ere, hogy egy adott val´os szimmetrikus m´atrix pozit´ıv (szemi)definit-e. P´eld´ aul a pozit´ıv szemidefinit´ast eld¨ ont˝ o algoritmus: Vizsg´ aljuk meg a m´atrix f˝ oa´tl´ oj´ anak bal f¨ ols˝o elem´et. Ha ez negat´ıv, akkor a m´atrix nem pozit´ıv szemidefinit. Ha nulla, akkor sor´anak ´es oszlop´anak is null´ anak kell lenni, hagyjuk el a sor´at ´es oszlop´at ´es vizsg´aljuk a marad´ek m´atrix pozit´ıv szemidefinit´as´ at. Ha az elem pozit´ıv, vizsg´aljuk Schur komplemens´enek pozit´ıv szemidefinit´as´at. Ily m´odon minden l´ep´esben eggyel reduk´ altuk a vizsg´aland´o m´atrix rendj´et, kisrend˝ u m´atrixok eset´en pedig k¨onny˝ u eld¨ onteni, hogy a m´atrix pozit´ıv szemidefinit-e. Az algoritmus val´ oj´ aban egy Gauss-elimin´aci´ oval egyen´ert´ek˝ u ´es a megfelel˝o E m´atrix olyan invert´ alhat´o m´atrix, amelyre EM E T diagon´ alis lesz. 35. Tervezz¨ unk algoritmust, amely adott M val´ os, szimmetrikus m´ atrix eset´en kisz´ amol egy olyan E invert´ alhat´ o m´ atrixot, amelyre EM E T diagon´ alis. Mutassuk meg, hogy ha E a fenti tulajdons´ ag´ u, akkor az EM E T f˝ oa ´tl´ oj´ aban lev˝ o pozit´ıv, negat´ıv ´es nulla elemek sz´ ama csak az M -t˝ ol f¨ ugg.(Sylvester tehetetlens´ egi t´ etele) T (1 − b)/(2a) 1 0 a (1 − b)/(2a) 1 1 0 ´ [Utmutat´ as: P´eld´ aul = ha a 6= 0.] (1 + b)/(2a) −1 a b (1 + b)/(2a) −1 0 −1 36. Egy M val´ os szimmetrikus m´ atrix pozit´ıv definit´ as´ ahoz elegend˝ o f˝ ominorai determin´ ansainak pozitivit´ asa. (Az M f˝ ominorai azok a szimmetrikus minorok, amelyek az utols´ o n´eh´ any oszlop ´es sor elhagy´ as´ aval keletkeznek M -b˝ ol.) A −e2 eT2 m´ atrix mutatja, hogy hasonl´ o a ´ll´ıt´ as pozit´ıv szemidefinit m´ atrixokra nem teljes¨ ul. V´eg¨ ul p´ aronk´ent mer˝oleges egys´egnyi hossz´ u oszlopvektorokkal rendelkez˝o m´atrix teljes oszloprang´ u m´atrixb´ ol t¨ ort´en˝o kiemel´es´er˝ ol: 37. Legyen A ∈ Rn×r teljes oszloprang´ u m´ atrix. Ekkor l´eteznek egy´ertelm˝ uen Q ∈ Rn×r ´es F ∈ Rr×r m´ atrixok T u ´gy, hogy Q Q = I, F pozit´ıv diagon´ alis´ u fels˝ o h´ aromsz¨ og m´ atrix, tov´ abb´ a A = QF . ´ [Utmutat´ A l´etez´esr˝ ol: AT A ≻ 0, legyen E olyan, hogy EAT AE T = D diagon´ alis m´ atrix. Ekkor Q := √ √ as: −1 T us´egr˝ ol: Q1 F1 = Q2 F2 eset´en Q1 = Q2 F , ahol F AE ( D) ´es F := ( D)−1 EAT A megfelel. Az egy´ertelm˝ fels˝ o h´ aromsz¨ og m´ atrix, tov´ abb´ a QT1 Q1 = I-b˝ ol ad´ od´ oan ortogon´ alis is, ´ıgy csak az egys´egm´ atrix lehet.] Megjegyezz¨ uk, hogy ´ıgy egy m´asik ortogonaliz´aci´ os elj´ar´ashoz jutottunk, ami persze a fenti egy´ertelm˝ us´egb˝ ol ad´od´oan ugyanazt a Q ortogon´alis m´atrixot sz´amolja ki, mint a Gram-Schmidt f´ele. 38. Legyen A ∈ Rn×r teljes oszloprang´ u m´ atrix. Ekkor l´eteznek Q ∈ Rn×r ´es B ∈ Rr×r m´ atrixok u ´gy, hogy T Q Q = I, B pozit´ı√ v definit m´ atrix,√tov´ abb´ a A = QB. ´ [Utmutat´ as: B := AT A, Q := A( AT A)−1 megfelel.] Irodalom. D. K. Fagyejev ´es I. Sz. Szominszkij: Fels˝ ofok´ u algebrai feladatok, M˝ uszaki K¨onyvkiad´o, Budapest, 1973 Fried Ervin: Klasszikus ´es line´ aris algebra, Tank¨ onyvkiad´o, Budapest, 1991 G´asp´ ar L´ aszl´o: M´ atrixaritmetikai gyakorlatok, Tank¨ onyvkiad´o, Budapest, 1990 P. R. Halmos: V´eges dimenzi´ os vektorterek, M˝ uszaki K¨onyvkiad´o, Budapest, 1984 Kov´acs Margit: A nemline´ aris programoz´ as elm´elete, Typotex Kft., Budapest, 1997 A. G. Kuros: Fels˝ obb algebra, Tank¨ onyvkiad´o, Budapest, 1968 R´ ozsa P´ al: Line´ aris algebra ´es alkalmaz´ asai, Tank¨ onyvkiad´o, Budapest, 1991 Szele Tibor: Bevezet´es az algebr´ aba, Tank¨ onyvkiad´o, Budapest, 1953 Szendrei J´anos: Algebra ´es sz´ amelm´elet, Tank¨ onyvkiad´o, Budapest, 1989 Ujv´ ari Mikl´ os: A szemidefinit programoz´ as alkalmaz´ asai a kombinatorikus optimaliz´ al´ asban, ELTE Kiad´ o, Budapest, 2001
18
