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.

Matriisit kuvaavat 3 alkion permutaatioita
Kahden permutaatiomatriisin matriisitulo on myös permutaatiomatriisi. ( Englanniksi matriisitulosta ).

Nämä ovat kuuden matriisin asemat:

(Ne ovat myös permutaatiomatriiseja.)

Määritelmä

muokkaa

Annettu "m":n alkion permutaatio π ,

 

annettu kahden rivin muodossa

 

sen permutaatiomatriisi on m × m matriisi Pπ, jonka johtavat alkiot ovate kaikkialla 0, paitsi rivillä i, johtava alkio π(i) on 1. Voidaan kirjoittaa

 

jossa   merkitsee rivivektorin pituutta "m", jolla on 1 js asemassa ja 0 kaikkialla muualla.[1]

Ominaisuudet

muokkaa

Annetut kaiksi permutaatiota π ja σ, joilla on "m" alkiota ja vastaavat permutaatiomatriisit

Pπ ja Pσ 
 

Tämä jollain tapaa epätoivottu sääntö on seurausta permutaatioiden kertolaskun määritelmästä (bijektioiden rakenne) ja matriiseista ja valinnasta käyttää vektoreita   permutaatiomatriisien riveinä; jos käytetään sarakkeita niin yllä olevasta tulosta tulee  , joke on yhtäsuuri alkuperäisessä järjestyksessä olevien permutaatioiden kanssa.

Koska permutaatiomatriisit ovat ortogonaalisia matriiseja (ts.,  ), käänteismatriisit ovat olemassa ja voidaan kirjoittaa

 

Kertomalla   kertaa sarakevektorilla (englanniksi column vector) g voidaan permutoidan vektorin rivit:

 

Käyttämällä   sen jälkeen kun   on käytetty, saadaan sama tulos kuin käyttämällä suoraan  

yhtäpitävästi yllä olevan kertolaskusäännön kanssa: merkitään  , toisin sanoen

 

kaikilla i, siten

 

Kertomalla rivivektoria (englanniksi row vector) h kertaa  

permutoi vektorin sarakkeet käänteis  :

 

Jälleen voidaan tarkistaa, että  .

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.[2]

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 Sn → 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 π = (a1)(a2)...(ak)σ where σ jos sillä ei ole kiinteitä pisteitä, silloin voidaan kirjoittaa ea1,ea2,...,eak 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ä

muokkaa

Rivien ja sarakkeiden permutaatiot

muokkaa

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):

 
P * (1,2,3,4)T = (4,1,3,2)T
 
(1,2,3,4) * P = (2,4,3,1)

Rivien ja sarakkeiden permutaatiot ovat esimerkkejä peilauksesta (katso alla) ja syklisistä permutaatioista (engl. cyclic permutation matrix).

Rivien permutaatio

muokkaa

PErmutaatiomatriisi Pπ vastaa permutaatiota :  joten

 


Annetulle vektorille g,

 

Selitys

muokkaa

Permutaatiomatriisi on aina muotoa

 

jossa eai esittää i:ttä basis alkeisvektoria (kuten riviä) R:lle 'j, missä

 

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= (g0,...,g5)T,

eai·v=gai

Siten permutaatiomatriisin tulo vektorin v kanssa (yllä), muodostaa vektorin muotoa (ga1, ga2, ..., gaj), ja tämä on siten v:n permutaatio kun sanotaan, että permutaatio on muotoa

 

Siten permutaatiomatriisit itse asiassa permutoivat vektorin alkioiden järjestyksessä kerrottaessa permutaatiomatriisit niillä.

Lähteet

muokkaa

Viitteet

muokkaa
  1. Brualdi (2006) p.2
  2. Brualdi (2006) p.19