1
Diszkrét matematika I., 11. el˝oadás Dr. Takách Géza NyME FMK Informatikai Intézet
[email protected] http://inf.nyme.hu/˜takach 2005. november 22.
Permutációk Definíció. Permutáción n különböz˝o elem valamely sorrendjét értjük. Az n elem átltalában 1, 2, . . . , n. Másképpen: egy permutáció egy σ : {1, 2, . . . , n} → {1, 2, . . . , n} kölcsönösen egyértelm˝u leképezés: σ(1) = az els˝o helyen álló szám, σ(2) = a második helyen álló szám, . . . Például az 52314 permutáció esetén σ(1) = 5, σ(2) = 2, σ(3) = 3, σ(4) = 1, σ(5) = 4. Definíció. Az 1, 2, . . . , n elemek egy permutációjában két elem inverzióban áll, ha közülük a nagyobbik megel˝ozi a kisebbiket. Azaz σ(i) > σ(j) valamely i < j-re. A permutáció inverziószáma az inverzióban álló párok száma. Jele I(σ). Például a fenti permutációban inverzióban áll: 5-2, 5-3, 5-1, 5-4, 2-1, 3-1. Definíció. Egy permutáció páros, ha az inverziószáma páros, páratlan, ha az inverziószáma páratlan. Például az 52314 permutáció páros, mert I(σ) = 6. Tétel. I. Ha egy permutációban két szomszédos elemet felcserélünk, akkor az inverziószám eggyel változik. II. Ha egy permutációban két tetsz˝oleges elemet felcserélünk, az inverziószám páratlannal változik. Bizonyítás. I. A két felcserélt elem viszonya megváltozik. Más elemekhez való viszonyuk nem. II. Tfh. k darab elem áll a felcserélend˝o két elem (b és c) között, és tfh. b van el˝obb a sorban. Mozgassuk b-t c mellé, hogy sorban felcseréljük a köztük álló k elemmel
k darab csere
Cseréljük fel b-t és c-t
1 darab csere
Mozgassuk c-t b eredeti helyére, hogy sorban felcseréljük az eredetileg köztük álló k elemmel
k darab csere
Összesen Azaz az inverziószám egy −(2k + 1) és 2k + 1 közé es˝o páratlan számmal változik.
2k + 1 darab csere ♦
Az alábbi tételre nem lesz szükségünk determinánsok számolásánál, de második félévben majd kell. Tétel. Ha n > 1, akkor n elemnek ugyanannyi páros és páratlan permutációja van. Bizonyítás. Egy permutációban az els˝o és a második elem felcserélése párosból páratlant, illetve páratlanból párosat gyárt, különböz˝oekb˝ol különböz˝oeket. ♦
2
Determinánsok mátrix — táblázat determináns — egyetlen szám, amivel a mátrixot valamilyen szempontból jellemezzük Négyzetes mátrix elemeib˝ol képzett szorzatok ±1 együtthatós összegeit vesszük. A szorzatok minden sorból és oszlopból pontosan egy elemet tartalmaznak. X X X X Az els˝o sorból a σ(1) oszlopbeli, a második sorból a σ(2) oszlopbeli,. . ., az n-ik sorból a σ(n) oszlopbeli elemet vesszük. Mivel minden oszlopból pontosan egy elemet veszünk, ezért σ(1), σ(2), . . . , σ(n) az 1, 2, . . . , n számok egy sorrendje, azaz permutációja.
Példa
a11 x1 a21 x1
+ a12 x2 + a22 x2
= b1 = b2
Egyenl˝o együtthatók elve: a11 a22 x1 a21 a12 x1 a11 a22 − a21 a12 x1
+ a12 a22 x2 + a22 a12 x2 + 0x2
b1 a22 − a12 b2 a11 a22 − a12 a21
és hasonlóan
= b1 a22 = b2 a12 = b1 a22 − b2 a12
Tfh. a11 a22 − a12 a21 6= 0. Ekkor x1 =
x2 =
Itt pont az alábbi négyzetes mátrixok determinánsai szerepelnek: a11 a12 b1 a12 a21 a22 b2 a22
b1 a22 − a12 b2 a11 a22 − a12 a21
a11 a21
b1 b2
Determináns definíciója Definíció. Az
a11 a21 .. . an1
a12 . . . a22 . . . .. . . . . an2 . . .
a1n a2n .. .
ann
négyzetes mátrix determinánsa a11 a12 . . . a1n a21 a22 . . . a2n det A = |A| = .. .. . . .. . . . . an1 an2 . . . ann
X (−1)I(σ) a1σ(1) a2σ(2) . . . anσ(n) , = σ
ahol az összegzést az 1, 2, . . . , n számok minden lehetséges permutációjára el kell végezni. n! tag, fele +, fele - el˝ojel˝u.
2 × 2-es és 3 × 3-as determináns TÁBLÁN
3
Determináns definíciója (folyt.) A determináns definíciójánál a szorzatok tényez˝oit sorok szerint rendeztük. Ha tetsz˝oleges sorrendben írjuk o˝ ket, akkor az alábbi tétel alapján számolhatunk. Tétel. Legyen aρ(1)σ(1) aρ(2)σ(2) . . . aρ(n)σ(n) egy szorzat a determináns definíciójából, melynek n tényez˝ojét tetsz˝oleges sorrendben írtuk fel. (ρ a sorindexeknek, σ az oszlopindexeknek megfelel˝o permutáció.) Ekkor a szorzat el˝ojele (−1)I(ρ)+I(σ) . Bizonyítás. Ha ρ(i) = i, azaz ρ a sorok természetes sorrendjének megfelel˝o identikus permutáció, akkor I(ρ) = 0 és az el˝ojel pont a definíció szerinti. Tényez˝ok egy tetsz˝oleges sorrendje ebb˝ol cserék egymásutánjával kapható. Egy cserére az I(ρ) és I(σ) is páratlannal változik, azaz az összegük párossal.
♦
Ezzel a sorok és oszlopok szerepe szimmetrikussá vált. Azaz minden amit sorokra kimondunk, oszlopokra is igaz, a bizonyításban csak a sor és oszlop szavakat kell következetesen felcserélni.
A determináns tulajdonságai I-III. Tétel. I. Ha a f˝oátló alatt vagy fölött minden elem 0, akkor a determináns a f˝oátlóbeli elemek szorzata. II. Ha valamely sor, vagy oszlop minden eleme 0, akkor a determináns is 0. III. Ha valamelyik sor minden elemét λ-val szorozzuk, akkor a determináns értéke is λ-val szorzódik. Bizonyítás. I. Ha egy szozat a definícióban tartalmaz f˝oátló feletti elemet, akkor f˝oátló alattit is, és viszont. Így a definícióbeli n! tag (szorzat) közül egy kivételével mind 0. II. Következik III-ból. III. Minden egyes szorzatban pontosan egy tényez˝o lesz λ-szoros, ezek a λ-k kiemelhet˝ok az összeg elé.
♦
A determináns tulajdonságai IV. Tétel. IV. Ha valamelyik sor (oszlop) minden eleme egy kéttagú összeg, akkor a determináns is két determináns összege: 0 a11 + a0011 a012 + a0012 . . . a01n + a001n a21 a22 . . . a2n .. .. . . .. = . . . . an1 an2 . . . ann 0 a11 a012 . . . a01n a0011 a0012 . . . a001n a21 a22 . . . a2n a21 a22 . . . a2n .. .. . . .. + .. .. . . .. . . . . . . . . an1 an2 . . . ann an1 an2 . . . ann
Bizonyítás. Minden szorzat pont egy elemet tartalmaz az els˝o sorból...
A determináns tulajdonságai V. Tétel. V. Ha egy determináns két sora (oszlopa) egyenl˝o, akkor a determináns értéke 0. Bizonyítás. Tfh. az els˝o két sor egyezik meg, azaz a1j = a2j minden j-re. A determináns egy tagja: S = a1σ(1) a2σ(2) a3σ(3) . . . anσ(n) .
♦
4 Ugyanez a szorzat el˝ofordul mint S 0 = a1σ(2) a2σ(1) a3σ(3) . . . anσ(n) , mert (RAJZ!) a1σ(1) = a2σ(1)
és
a2σ(2) = a1σ(2) .
S el˝ojelét az σ(1)σ(2)σ(3) . . . σ(n) permutáció paritása határozza meg, S 0 -ét pedig a σ(2)σ(1)σ(3) . . . σ(n) permutáció paritása: a kett˝o pont ellenkez˝o. Azaz a definícióban szerepl˝o szorzatok párba állíthatók úgy, hogy a párok kiejtsék egymást. ♦
A determináns tulajdonságai VI. KövetkezményVI. Ha valamelyik sor egy másik λ-szorosa, akkor a determináns értéke 0. Bizonyítás. A III. és az V. tulajdonságokból következik. (λ kiemelése után két azonos sor lesz.)
♦
A determináns tulajdonságai VII. Tétel. VII. Ha egy sorhoz hozzáadjuk egy másik sor λ-szorosát, akkor a determináns értéke nem változik. Bizonyítás. Tfh. a második sor λ-szorosát adtuk az els˝o sorhoz. Ekkor a IV. tulajdonság szerint: a11 + λa21 a12 + λa22 . . . a1n + λa2n a21 a22 . . . a2n .. .. . . .. = . . . . an1 an2 . . . ann a11 a12 . . . a1n λa21 λa22 . . . λa2n a21 a22 . . . a2n a21 a22 . . . a2n .. .. . . .. + .. .. . . .. , . . . . . . . . an1 an2 . . . ann an1 an2 . . . ann az utóbbi pedig 0 a VI. tulajdonság szerint.
♦
A determináns tulajdonságai VIII. Tétel. VIII. Ha két sort felcserélünk, akkor a determináns értéke az ellentettjére változik. Bizonyítás. A 4. Tételt alkalmazzuk többször. El˝oször a j-ik sort kivonjuk az i-ikb˝ol, majd az új i-ik sort hozzáadjuk a j-ikhez, végül az új j-ik sort kivonjuk az új i-ikb˝ol: aik aik − ajk aik − ajk −ajk 7→ 7→ 7→ ajk ajk aik aik Eközben a determináns értéke nem változott. Végül az i-ik sorból −1-et kiemelve a kapott determináns az eredeti −1-szerese, ugyanakkor az eredetib˝ol pont az i-ik és j-ik sorok felcserélésével keletkezett. ♦
A determináns tulajdonságai IX. Tétel. IX. Ha az elemeket a f˝oátlóra tükrözzük, akkor a determináns értéke nem változik. Újabb bizonyíték arra, hogy a tételekben a sor és oszlop szavak felcserélhet˝oek. Bizonyítás. Legyenek az eredeti determináns elemei aij , a tükrözötté bij , aij = bji . Egy szorzat az eredetiben: aρ(1)σ(1) aρ(2)σ(2) . . . aρ(n)σ(n) .
5 Ugyanez szerepel a tükrözöttben is: bσ(1)ρ(1) bσ(2)ρ(2) . . . bσ(n)ρ(n) . El˝ojelük: (−1)I(ρ)+I(σ) illetve (−1)I(σ)+I(ρ) , ami egyenl˝o.
♦
Determinánsszámítás Gauss-eliminációval. Hogyan változik a determináns értéke elemi ekvivalens átalakításkor? Sorcsere esetén: −1-szeresére változik. Leosztok egy sort egy számmal: a számot ki kelle emelni a determináns elé. Kivonom egy sor számszorosát egy másikból: nem változik. Ha az eljárás közben csupa 0 sort találunk: a determináns értéke 0. Ha ez utóbbi nem következik be, akkor elérhet˝o, hogy a f˝oátló alatt vagy fölött minden elem 0 legyen, ekkor a determináns a f˝oátlóbeli elemek szorzata.
Példa
1 5 1 1
2 6 2 3 = −4 ·
3 7 4 9 1 0 0 0
=
4 8 8 27 2 1 0 0
3 2 1 4
1 2 3 0 −4 −8 0 0 1 0 1 6 1 = −4 · 0 0 0
4 3 4 20
4 −12 4 23 2 1 0 0
3 2 1 0
1 2 3 4 3 = −4 · 0 1 2 = 0 0 1 4 0 1 6 23 4 3 = −4 · 1 · 1 · 1 · 4 = −16 4 4
Determinánsok kifejtése Létezik egy olyan kiszámítási mód is, amellyel az n × n-es determináns n darab (n − 1) × (n − 1)-es kiszámítására vezethet˝o vissza: kifejtés. Ebben a témakörben feltesszük, hogy n > 1. Definíció. Egy n-ed rend˝u determinánsból hagyjuk el az i-ik sort és a j-ik oszlopot. Az aij elemhez tartozó Aij el˝ojeles aldeterminánson ennek a determinánsnak a (−1)i+j -szeresét értjük. Példa.
1 2 4 5 7 8
3 6 9
esetén
2+3
A23 = (−1)
1 · 7
1 2 ∼ ∼ ∼ ∼ −→ 1 7 7 8 ∼ 2 = −1 · (1 · 8 − 2 · 7) = 6. 8
2 . 8
6
Sakktáblaszabály az el˝ojelezésre + − + − .. .
− + − + .. .
+ − + − .. .
− + − + .. .
... ... ... ... .. .
Kifejtési tétel és ferde kifejtés Tétel. Ha egy sor (oszlop) minden elemét megszorozzuk a hozzátartozó el˝ojeles aldeterminánssal, akkor az így kapott szorzatok összege a determináns értéke: n X det A = ai1 Ai1 + ai2 Ai2 + . . . + ain Ain = aij Aij . j=1
♦
Bizonyítás. Nem kell.
Tétel. (Ferde kifejtés) Ha egy sor elemeit rendre egy másik sorhoz tartozó el˝ojeles aldeterminánsokkal szorozzuk meg, az így kapott szorzatok összege mindig 0: k 6= r ⇒ 0 = ar1 Ak1 + ar2 Ak2 + . . . + arn Akn =
n X
arj Akj .
j=1
♦
Bizonyítás. Nem kell.
Vandermonde-determináns Definíció. Legyenek γ1 , γ2 , . . . , γn tetsz˝oleges számok. Az általuk generált Vandermonde-determináns 1 γ1 γ12 . . . γ1n−1 1 γ2 γ22 . . . γ2n−1 n−1 2 V (γ1 , γ2 , . . . , γn ) = 1 γ3 γ3 . . . γ3 . . .. .. . . .. .. . . . . 1 γn γ 2 . . . γ n−1 n n Q Tétel. V (γ1 , γ2 , . . . , γn ) = 1≤j≤i≤n (γi − γj ). Azaz a Vandermonde-determináns akkor és csak akkor nem nulla, ha generátorelemei páronként különböz˝oek. Bizonyítás. Teljes indukcióval. n = 2 esetén: 1 γ1 1 γ2
= γ2 − γ1 .
Tegyük fel, hogy az állítás igaz minden (n − 1)-edrend˝u Vandermonde-determinánsra, és igazoljuk, hogy ekkor igaz minden n-edrend˝ure is. Vonjuk ki minden oszlopból jobbról balfelé haladva az el˝oz˝o oszlop γ1 -szeresét: 1 γ1 γ12 . . . γ1n−1 1 0 0 0 0 1 γ2 γ22 . . . γ2n−1 1 γ2 − γ1 γ22 − γ1 γ2 . . . γ2n−1 − γ1 γ2n−2 1 γ3 γ 2 . . . γ n−1 1 γ3 − γ1 γ32 − γ1 γ3 . . . γ n−1 − γ1 γ n−2 3 3 3 3 = . .. .. . . .. .. .. . . .. .. .. . . . . . . . . . 1 γn γ 2 . . . γ n−1 1 γn − γ1 γ 2 − γ1 γn . . . γ n−1 − γ1 γ n−2 n n n n n
.
7 Most vonjuk le minden sorból az els˝o sort: , ezzel kinullázzuk az els˝o oszlopot, a többi oszlop nem változik.
1 0 0 .. .
0 γ2 − γ1 γ3 − γ1 .. .
0 γn − γ1
0 0 0 n−1 n−2 2 γ2 − γ1 γ2 . . . γ2 − γ1 γ2 γ32 − γ1 γ3 . . . γ3n−1 − γ1 γ3n−2 .. . . .. . . . γn2 − γ1 γn . . . γnn−1 − γ1 γnn−2
Emeljük ki a a második, harmadik stb. sorból rendre γ2 − γ1 -et, γ3 − γ1 -et, stb.: 1 0 0 0 0 0 1 γ2 . . . γ2n−2 n−2 (γ2 − γ1 )(γ3 − γ1 ) . . . (γn − γ1 ) 0 1 γ3 . . . γ3 . . .. . . .. .. .. . . . 0 1 γn . . . γ n−2 n
.
=
= (γ2 − γ1 )(γ3 − γ1 ) . . . (γn − γ1 )V (γ2 , . . . , γn ). Ezzel a feladatot eggyel kisebb rend˝u Vandermonde-determinánsra vezettük vissza. Az indukciós feltevés miatt (γ2 − γ1 )(γ3 − γ1 ) . . . (γn − γ1 )V (γ2 , . . . , γn ) = Y Y (γ2 − γ1 )(γ3 − γ1 ) . . . (γn − γ1 ) (γi − γj ) = (γi − γj ) 2≤j≤i≤n
1≤j≤i≤n
♦
Ellen˝orz˝o kérdések 1. Mi a paritása a 352461, a 654321 és az 123456 permutációknak? 2. Rajzoljon fel egy 4 × 4-es determinánst, és rajzolja bele, hogy mely elemeket jelöli ki a 4231 permutáció! Milyen el˝ojelet kap ez a szorzat a determináns kiszámításakor? 3. Írja fel a determináns definícióját! 4. Mely esetekben lesz 0 egy determináns értéke? (3 eset) 5. Mikor nem változik a determináns értéke? (2 eset) 6. Mikor változik a determináns értéke konstansszorosára? (2 eset) 7. Írjon fel egy 3 × 3-as determinánst és számítsa ki az értékét (a) definíció szerint; (b) kifejtési tétel szerint; (c) Sarrus-szabállyal!
