Mat(n, n) korral XEn = X, EmX = X Tõestus Maatriksite X = (xij ), kus i Nm, j Nn, ja n-järku ühikmaatriksi E1 = (ij) korrutise XE1 = (yij) üldelement avaldub = = , , , =1 mistõttu XE1 = X. Juhul kui E2 on m-järku ühikmaatriks, siis 2 = = = =1 Teoreem 2.2. Kui permutatsioonis omavahel ära vahetada kaks elementi, siis permutatsioon muudab paarsust. Tõestus. Tõestame esmalt teoreemi, kui permutatsioonis vahetatavad arvud on kõrvuti, s.o. permutatsioonist 1 ... +1 ... saame permutatsiooni 1 ... +1 ... Paneme tähele, et kummaski permutatsioonis arvudele i ja i+1 eelnevate ja järgnevate arvudega inversioonid säilusid. Ainus inversiooni muutus tekkis üleminekul paarilt (i, i+1) paarile (i+1, i)
. Arvu Pn(,,..,) leidmiseks üldjuhul arutleme järgmiselt. Varustame elemendid a (neid on tükki) indeksitega 1,2,...,, ele- mendid b indeksitega 1,2,..., jne, elemendid l indeksitega 1,2, ...,. Sel teel saame kunstlikult n elementi, mis kõik erinevad üksteisest kas elemendi enda või vähemalt indeksi poolest: a1, a2,..., a , b1, b2, ..., b, ..., l1,l2, ..., l. Moodustame nendest n erinevast elemendist kõik tavalised Pn = n! permutatsiooni ja vaatleme neist üht konkreetset. Selles permutatsioonis elemendid a1,a2, ..., a esinevad kindlal kohal, elemendid b1,b2,...,b eelmistest erineval kindlal kohal jne, lõpuks elemendid l1, l2,...,l kõigist eelpool nimetatud elementidest erineval kindlal kohal. 5 Teostame meie valitud permutatsioonis elementidega a1,a2,...,a kõik P=! võimalikku omavahelist permutatsiooni. Sel teel saame P permutatsiooni, mis omavahel erinevad elementide a1,a2,...,a indeksite järjekorra poolest. Teostame nüüd igas saadud P permutatsioonis elementidega b1,b2,..
duse kohaselt on selles hulgas (n - 1)! permutatsiooni. Mistahes i, j Nn , (i) (j) kus i = j, korral ei ole hulkadel Pn ja Pn u ¨hiseid permutatsioone, sest erinevus on juba esimeses arvus. Seega hulga Pn permutatsioonide arv (1) (2) (n) v~ordne hulkade Pn , Pn , . . . , Pn permutatsioonide arvu summaga, s.o. (n - 1)!n = n! Definitsioon 2.1. Oeldakse, ¨ et permutatsioonis 1 2 . . . i . . . j . . . n elemendipaar (i , j ) moodustab inversiooni, kui selles paaris esimene arv i on suurem teisest arvust j , s.o. i > j . Vaadeldes permutatsioonis (2.1) k~oiki arvupaare (1 , 2 ), (1 , 3 ), . . . , (1 , n ), (2 , 3 ), . . . , (2 , n ), . . . , (n-1 , n ), saame kokku lugeda inversioonide arvu antud permutatsioonis. Inversiooni- de arvu permutatsioonis (2.1) t¨ahistame I (1 , 2 , . .
permutatsiooni. Mistahes i, j ∈ Nn , (i) (j) kus i = j, korral ei ole hulkadel Pn ja Pn u ¨hiseid permutatsioone, sest erinevus on juba esimeses arvus. Seega hulga Pn permutatsioonide arv (1) (2) (n) v˜ordne hulkade Pn , Pn , . . . , Pn permutatsioonide arvu summaga, s.o. (n − 1)!n = n! ♠ Definitsioon 2.1. Oeldakse, ¨ et permutatsioonis α1 α2 . . . αi . . . αj . . . αn elemendipaar (αi , αj ) moodustab inversiooni, kui selles paaris esimene arv αi on suurem teisest arvust αj , s.o. αi > αj . Vaadeldes permutatsioonis (2.1) k˜oiki arvupaare (α1 , α2 ), (α1 , α3 ), . . . , (α1 , αn ), (α2 , α3 ), . . . , (α2 , αn ), . . . , (αn−1 , αn ), saame kokku lugeda inversioonide arvu antud permutatsioonis. Inversiooni-
1 2 n |a1 a1 ... a1 | |a21 a22 ... a2n| d = |.....................| = (-1) a11 a22 a33 ... ann permutatsioonid |an1 an2 ... ann| Selgitus: determinandi väärtust arvutav summa on võetud üle kõigi permutatsioonide, millised saab moodustada numbritest 1, 2, 3 ... n ( seega on liidetavaid n! tükki), sümbol summa avaldises tähistab inversioonide koguarvu permutatsioonis 1; 2;....; n. Permutatsioon on teatava hulga kõikidest elementidest moodustatud ning konkreetne järjestus. Pn = n! Öeldakse, et kui väiksem indeks asetseb suurema ees, siis nad moodustavad loomuliku järjestuse, vastasel juhul kui suurem väiksema ees, siis räägitakse, et nad moodustavad inversiooni. Determinant on arv, mis seatakse vastavusse igale ruutmaatriksile ja selle arvu väärtus leitakse
DETERMINANDIKS ja mis on sobivalt valitud märgiga kõikvõimalike niisuguste n teguri korrutiste summa, kus tegurid on valitud maatriksi erinevatest ridadest ja erinevatest veergudest. Tähistades maatriksi A determinandi | A |, võib eelöeldu kirja panna järgmiselt: A |A| = (-1) a1 i a2 j . . . an k , (i, j,...,k) kus (i, j,...,k) on n-elemendiline permutatsioon arvudest 1, 2, . . . ,n ja on inversioonide arv selles permutatsioonis. Permutatsioonid erinevad üksteisest ainult elementide järjekorra poolest ja n-elemendiliste permutatsioonide arv on n-faktoriaal, st neid on n! = 1 2 . . . n tükki. Öeldakse, et kaks arvu k ja l moodustavad permutatsioonis inversiooni, kui suurem arv asetseb väiksema ees. St kui ( . . . k . . . l . . .) ja k > l, siis nad moodustavad inversiooni, vastasel korral aga mitte. NÄITEID 1) TEIST JÄRKU DETERMINANT (n = 2). Teist järku ruutmaatriksi determinant sisaldab 2
DETERMINANDIKS ja mis on sobivalt valitud märgiga kõikvõimalike niisuguste n teguri korrutiste summa, kus tegurid on valitud maatriksi erinevatest ridadest ja erinevatest veergudest. Tähistades maatriksi A determinandi | A |, võib eelöeldu kirja panna järgmiselt: A |A| = (-1) a1 i a2 j . . . an k , (i, j,...,k) kus (i, j,...,k) on n-elemendiline permutatsioon arvudest 1, 2, . . . ,n ja on inversioonide arv selles permutatsioonis. Permutatsioonid erinevad üksteisest ainult elementide järjekorra poolest ja n-elemendiliste permutatsioonide arv on n-faktoriaal, st neid on n! = 1 2 . . . n tükki. Öeldakse, et kaks arvu k ja l moodustavad permutatsioonis inversiooni, kui suurem arv asetseb väiksema ees. St kui ( . . . k . . . l . . .) ja k > l, siis nad moodustavad inversiooni, vastasel korral aga mitte. NÄITEID 1) TEIST JÄRKU DETERMINANT (n = 2). Teist järku ruutmaatriksi determinant sisaldab 2
..xn). Hulga n kõigi permutatsioonide hulga tähiseks on Pn või P(1, 2, . . . , n). Permutatsioon Hulga H = {x1, x2, x3...xn}(Näiteks H = n) elementide ümberjärjestust, milles hulga H iga element esineb täpselt 1 kord, nim hulga H permutatsiooniks Loomulik permutatsioon permutatsioon 1,2,3,...,n hulgas Nn Inversioon Öeldakse, et elemendipaar (ai, aj) moodustab inversiooni, kui selles paaris esimene arv ai on suurem kui aj. Inversioonide arvu tähiseks permutatsioonis _1, _2, . . . , _n on I (_1, _2, . . . , _n). Paaritu permutatsioon permutatsiooni nimetatakse paarituks permutatsiooniks, kui tema inversioonide arv on paaritu Paaris permutatsioon - permutatsiooni nimetatakse paaris permutatsiooniks, kui tema inversioonide arv on paaris OMADUSED: 1) Hulga n elementidest saab moodustada n! permutatsiooni 2) Kui permutatsioonis omavahel ära vahetada 2 elementi, siis permutatsioon muudab paarsust
Arvu n=3 korral on 6=3! permutatsiooni: (1,2,3); (2,3,1); (3,1,2); (2,1,3); (3,2,1); (1,3,2). Teoreem. Permutastoonide arv n elemendist on Pn=n! Tõestus. Permutatsiooni esimese elemendi valimiseks on n võimalust. Teise elemendi valikuks jääb n 1 võimalust. Seega esimese kahe elemendi valikuks on n(n 1) võimalust. Analoogiliselt jätkates saame, et n elemetide ümberjärjestamiseks n(n 1)(n 2) ... 2 1 = n! võimalust. Definitsioon. Öeldakse, et permutatsioonis elemendipaar ( , ) moodustab inversiooni, kui selles paaris esimene arv on suurem teisest arvust , s.o. . Inversioonide arvu permutatsioonis tähistatakse Koostame järgmised tabelid n = 2; 3 korral. Märk (i1,i2) (i1,i2) a1i1 a 2 i2
annaabi.ee 
