Permutaatiomatriisi

Tämä artikkeli tai sen osa on tuotu vieraskielisestä lähteestä ja käännös on keskeneräinen. Voit auttaa Wikipediaa tekemällä käännöksen loppuun.

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.

Annettu "m":n alkion permutaatio π ,

${\displaystyle \pi :\lbrace 1,\ldots ,m\rbrace \to \lbrace 1,\ldots ,m\rbrace }$

annettu kahden rivin muodossa

${\displaystyle {\begin{pmatrix}1&2&\cdots &m\\\pi (1)&\pi (2)&\cdots &\pi (m)\end{pmatrix}},}$

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

${\displaystyle P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (m)}\end{bmatrix}},}$

jossa ${\displaystyle \mathbf {e} _{j}}$ merkitsee rivivektorin pituutta "m", jolla on 1 js asemassa ja 0 kaikkialla muualla.^[1]

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

Pπ ja Pσ 

${\displaystyle P_{\sigma }P_{\pi }=P_{\pi \,\circ \,\sigma }}$

Tämä jollain tapaa epätoivottu sääntö on seurausta permutaatioiden kertolaskun määritelmästä (bijektioiden rakenne) ja matriiseista ja valinnasta käyttää vektoreita ${\displaystyle \mathbf {e} _{\pi (i)}}$ permutaatiomatriisien riveinä; jos käytetään sarakkeita niin yllä olevasta tulosta tulee ${\displaystyle P_{\sigma \,\circ \,\pi }}$, joke on yhtäsuuri alkuperäisessä järjestyksessä olevien permutaatioiden kanssa.

Koska permutaatiomatriisit ovat ortogonaalisia matriiseja (ts., ${\displaystyle P_{\pi }P_{\pi }^{T}=I}$), käänteismatriisit ovat olemassa ja voidaan kirjoittaa

${\displaystyle P_{\pi }^{-1}=P_{\pi ^{-1}}=P_{\pi }^{T}.}$

Kertomalla ${\displaystyle P_{\pi }}$ kertaa sarakevektorilla (englanniksi column vector) g voidaan permutoidan vektorin rivit:

${\displaystyle P_{\pi }\mathbf {g} ={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (n)}\end{bmatrix}}{\begin{bmatrix}g_{1}\\g_{2}\\\vdots \\g_{n}\end{bmatrix}}={\begin{bmatrix}g_{\pi (1)}\\g_{\pi (2)}\\\vdots \\g_{\pi (n)}\end{bmatrix}}.}$

Käyttämällä ${\displaystyle P_{\sigma }}$ sen jälkeen kun ${\displaystyle P_{\pi }}$ on käytetty, saadaan sama tulos kuin käyttämällä suoraan ${\displaystyle P_{\pi \circ \sigma }}$

yhtäpitävästi yllä olevan kertolaskusäännön kanssa: merkitään ${\displaystyle P_{\pi }\mathbf {g} =\mathbf {g} '}$, toisin sanoen

${\displaystyle g'_{i}=g_{\pi (i)}\,}$

kaikilla i, siten

${\displaystyle P_{\sigma }(P_{\pi }(\mathbf {g} ))=P_{\sigma }(\mathbf {g} ')={\begin{bmatrix}g'_{\sigma (1)}\\g'_{\sigma (2)}\\\vdots \\g'_{\sigma (n)}\end{bmatrix}}={\begin{bmatrix}g_{\pi (\sigma (1))}\\g_{\pi (\sigma (2))}\\\vdots \\g_{\pi (\sigma (n))}\end{bmatrix}}.}$

Kertomalla rivivektoria (englanniksi row vector) h kertaa ${\displaystyle P_{\pi }}$

permutoi vektorin sarakkeet käänteis ${\displaystyle P_{\pi }}$:

${\displaystyle \mathbf {h} P_{\pi }={\begin{bmatrix}h_{1}\;h_{2}\;\dots \;h_{n}\end{bmatrix}}{\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (n)}\end{bmatrix}}={\begin{bmatrix}h_{\pi ^{-1}(1)}\;h_{\pi ^{-1}(2)}\;\dots \;h_{\pi ^{-1}(n)}\end{bmatrix}}}$

Jälleen voidaan tarkistaa, että ${\displaystyle (\mathbf {h} P_{\sigma })P_{\pi }=\mathbf {h} P_{\pi \circ \sigma }}$.

Merkitään S_n: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₍₁₎ on yksikkömatriisi.

Permutaatiomatriisia voidaan tarkastella σ:n permutaationa, kun permutaatio σ on yksikkömatriisin "I" sarakkeina tai "I":n rivien permutaatioina σ⁻¹.

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 S_n → A ⊂ GL(n, Z₂). Siten, |A| = n!.

Permutaatiomatriisin jälki permutaation kiinnitettyjen pisteiden lukumäärä. Jos permutaatiolla on kiinteitä pisteitä, niin se voidaan kirjoittaa rengasmuodossa kuten π = (a₁)(a₂)...(a_k)σ where σ jos sillä ei ole kiinteitä pisteitä, silloin voidaan kirjoittaa e_a1,e_a2,...,e_ak 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.

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

reflections
Nämä matriisien järjestelyt ovat peilauksia yllä olevista. Tämä on seurausta säännöstä ${\displaystyle \left(\mathbf {AB} \right)^{\mathrm {T} }=\mathbf {B} ^{\mathrm {T} }\mathbf {A} ^{\mathrm {T} }\,}$      (Compare: Transpose)

PErmutaatiomatriisi P_π vastaa permutaatiota :${\displaystyle \pi ={\begin{pmatrix}1&2&3&4&5\\1&4&2&5&3\end{pmatrix}},}$ joten

${\displaystyle P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\mathbf {e} _{\pi (3)}\\\mathbf {e} _{\pi (4)}\\\mathbf {e} _{\pi (5)}\end{bmatrix}}={\begin{bmatrix}\mathbf {e} _{1}\\\mathbf {e} _{4}\\\mathbf {e} _{2}\\\mathbf {e} _{5}\\\mathbf {e} _{3}\end{bmatrix}}={\begin{bmatrix}1&0&0&0&0\\0&0&0&1&0\\0&1&0&0&0\\0&0&0&0&1\\0&0&1&0&0\end{bmatrix}}.}$

Annetulle vektorille g,

${\displaystyle P_{\pi }\mathbf {g} ={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\mathbf {e} _{\pi (3)}\\\mathbf {e} _{\pi (4)}\\\mathbf {e} _{\pi (5)}\end{bmatrix}}{\begin{bmatrix}g_{1}\\g_{2}\\g_{3}\\g_{4}\\g_{5}\end{bmatrix}}={\begin{bmatrix}g_{1}\\g_{4}\\g_{2}\\g_{5}\\g_{3}\end{bmatrix}}.}$

Permutaatiomatriisi on aina muotoa

${\displaystyle {\begin{bmatrix}\mathbf {e} _{a_{1}}\\\mathbf {e} _{a_{2}}\\\vdots \\\mathbf {e} _{a_{j}}\\\end{bmatrix}}}$

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

${\displaystyle {\begin{bmatrix}1&2&\ldots &j\\a_{1}&a_{2}&\ldots &a_{j}\end{bmatrix}}}$

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₀,...,g₅)^T,

e_ai·v=g_ai

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

${\displaystyle {\begin{pmatrix}1&2&\ldots &j\\a_{1}&a_{2}&\ldots &a_{j}\end{pmatrix}}.}$

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

• Brualdi, Richard A. (2006). Combinatorial matrix classes, Encyclopedia of Mathematics and Its Applications 108. Cambridge: Cambridge University Press. ISBN 0-521-86565-4.