Permutaatiomatriisi

Permutaatiomatriisi on matematiikan matriisiteoriassa eliöllinen yksikkömatriisi, jolla on täsmälleen yksi johtava alkio 1 jokaisella rivillä ja sarakkeessa ja kaikkialla muualla 0. Jokainen sellainen matriisi esittää tiettyä permutaatiota, jossa on m alkiota ja kerrottaessa toisella matriisilla, se voi tuottaa uuden matriisin, jolla on toisen matriisin rivit ja sarakkeet.
Määritelmä.
Annettu "m":n alkion permutaatio π ,
formula_1
annettu kahden rivin muodossa
formula_2
sen permutaatiomatriisi on "m × m" matriisi "P"π, jonka johtavat alkiot ovate kaikkialla 0, paitsi rivillä "i", johtava alkio π("i") on 1. Voidaan kirjoittaa
formula_3
jossa formula_4 merkitsee rivivektorin pituutta "m", jolla on 1 "j"s asemassa ja 0 kaikkialla muualla.
Ominaisuudet.
Annetut kaiksi permutaatiota π ja σ, joilla on "m" alkiota ja vastaavat permutaatiomatriisit 
 "P"π ja "P"σ &lt;br&gt;
formula_5
Tämä jollain tapaa epätoivottu sääntö on seurausta permutaatioiden kertolaskun määritelmästä (bijektioiden rakenne) ja matriiseista ja valinnasta käyttää vektoreita formula_6 permutaatiomatriisien riveinä; jos käytetään sarakkeita niin yllä olevasta tulosta tulee 
formula_7, joke on yhtäsuuri alkuperäisessä järjestyksessä olevien permutaatioiden kanssa.
Koska permutaatiomatriisit ovat ortogonaalisia matriiseja
(ts., formula_8), käänteismatriisit ovat olemassa ja voidaan kirjoittaa
formula_9
Kertomalla formula_10 kertaa sarakevektorilla (englanniksi column vector) g voidaan permutoidan vektorin rivit:
formula_11
Käyttämällä formula_12 sen jälkeen kun formula_13 on käytetty, saadaan sama tulos kuin käyttämällä suoraan formula_14
yhtäpitävästi yllä olevan kertolaskusäännön kanssa:
merkitään
formula_15, toisin sanoen 
formula_16
kaikilla "i", siten 
formula_17
Kertomalla rivivektoria (englanniksi row vector) h kertaa formula_10
permutoi vektorin sarakkeet käänteis formula_10:
formula_20
Jälleen voidaan tarkistaa, että formula_21.
Notes.
Merkitään "Sn":lla symmetristä ryhmää (engl. symmetric group), 
tai permutaatioiden ryhmää {1,2...,"n"}. Koska nyt on "n"! permutaatioita, on olemassa "n"! permutaatiomatriiseja. Yllä olevien kaavojen perusteella "n" × "n" permutaatiomatriisit muodostavat ryhmän (engl. group) yksikkömatriisin kertolaskulla.
Jos (1) viittaa identiteetti permutaatioon (yksikkö permutaatio), niin "P"(1) on yksikkömatriisi.
Permutaatiomatriisia voidaan tarkastella σ:n permutaationa, kun permutaatio σ on yksikkömatriisin "I" sarakkeina tai "I":n rivien permutaatioina σ−1.
Permutaatiomatriisi on stokastinen neliömatriisi.
Tulo "PM" saadaan kertomalla matriisia "M" permutaatiomatriisilla "P", permutoimalla "M"n rivit "i" liikkuvat riveiksi π("i"). Päinvastoin tulo "MP" permutoi "M":n sarakkeita.
Kuvaus "S""n" → A ⊂ GL("n", Z2). Siten, |A| = "n"!.
Permutaatiomatriisin jälki permutaation kiinnitettyjen pisteiden lukumäärä. Jos permutaatiolla on kiinteitä pisteitä, niin se voidaan kirjoittaa rengasmuodossa kuten π = ("a"1)("a"2)...("a""k")σ where σ jos sillä ei ole kiinteitä pisteitä, silloin voidaan kirjoittaa e"a"1,e"a"2...,e"a""k" jotka ovat permutaatiomatriisin ominaisarvot.
Ryhmäteorian pohjalta tiedetään että mikä tahansa permutaatio voidaan kirjoittaa transpoosin tulona. Sen tähden minkä tahansa permutaatiomatriisin "P" tekijät saadaan Alkeismatriisin rivitoimituksilla, jossa jokaisella on determinantti -1. Siten permutaatiomatriisin "P" determinatti on vastaavan permutaation merkki.
Esimerkkejä.
Rivien ja sarakkeiden permutaatiot.
Kun permutaatiomatriisia "P" kerrotaan matriisilla "M" vasemmalta "PM" permutoi "M":n rivit (sarakevektorin alkioilla), kun "P" kerrotaan "M":llä oikealta "MP" permutoi "M":n sarakkeet (rivivektorin alkiot):
Rivien ja sarakkeiden permutaatiot ovat esimerkkejä peilauksesta (katso alla) ja syklisistä permutaatioista (engl. cyclic permutation matrix).
Rivien permutaatio.
PErmutaatiomatriisi "P"π vastaa permutaatiota :formula_22 joten
formula_23
&lt;br&gt;
Annetulle vektorille g,
formula_24
Selitys.
Permutaatiomatriisi on aina muotoa
formula_25
jossa e"a""i" esittää "i":ttä basis alkeisvektoria (kuten riviä) R:lle '"j", missä
formula_26
on permutaatio muoto permutaatiomatriisista.
Suorittamalla matriisikertolaskun, erityisesti muodostamalla pistetulo ensimmäisen matriisin jokaisen rivin toisen matriisin jokaisen sarakkeen kanssa. Tässä esimerkissä muodostetaan pistetulo jokaisen tämän matriisin rivin ja halutun vektorin alkioiden välille. Joka on esimerkiksi v= ("g"0...,"g"5)T, 
e"a""i"·v="g""a""i"
Siten permutaatiomatriisin tulo vektorin v kanssa (yllä), 
muodostaa vektorin muotoa ("g""a"1, "g""a"2, ..., "g""a""j"), ja tämä on siten v:n permutaatio kun sanotaan, että permutaatio on muotoa
formula_27
Siten permutaatiomatriisit itse asiassa permutoivat vektorin alkioiden järjestyksessä kerrottaessa permutaatiomatriisit niillä.