Permutacijska matrika

Permutacijska matrika (oznaka $P_{\pi }\,$) je kvadratna matrika, ki ima v vsaki vrstici samo en element enak 1, na ostalih mestih pa ima ničle. Prav tako ima tudi v vsakem stolpcu samo po en element enak 1, ostali pa so 0. Vsaka takšna matrika predstavlja določeno permutacijo $m\,$ elementov. Vsaka permutacija ima svojo permutacijsko matriko. Če permutacijsko matriko pomnožimo z drugo matriko, dobimo permutacije v vrsticah v drugi matriki. Permutacijska matrika je nesigularna, kar pomeni, da njena determinanta ni nikoli enaka 0 (vedno je +1 ali -1).

Matrike, ki opisujejo permutacije 3 elementov. Skupaj 6 (1.2.3 = 3!) permutacij (v vsaki vrstici).
V vsakem kvadratu je ena izmed permutacij treh elementov.

Permutacijska matrika se vedno dobi s permutacijami enotske matrike. Vsaka enotska matrika je tudi permutacijska matrika.

Definicija

Permutacijo $m\,$ elementov označimo s $\pi \,$

$\pi :\lbrace 1,\ldots ,m\rbrace \to \lbrace 1,\ldots ,m\rbrace \,$

To lahko enakovredno zapišemo v posebni obliki, ki jo imenujemo ciklično označevanje permutacij

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

kjer je

• v prvi vrstici so napisani vsi elementi, ki jih permutiramo
• v drugi vrstici so zapisane posamezne vrednosti permutiranih elementov

$\pi (1)\,$ pomeni permutirani element na prvem mestu

itd.

Permutacijska matrika $P_{\pi }\,$ z razsežnostjo $m\times m\,$ ima povsod 0, razen v vrstici $i\,$, kjer ima vrednost 1. To lahko zapišemo kot

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

kjer je

• $e_{j}\,$ enotski vrstični vektor z dolžino $m\,$, ki ima enico na $j\,$-tem mestu, na vseh ostalih mestih pa ima $0\,$.

Zgled

Ena izmed permutacij štirih elementov je :

$\pi ={\begin{pmatrix}1&&2&&3&&4\\4&&2&&1&&3\end{pmatrix}}$

Pripadajoča matrika pa je:

$P={\begin{pmatrix}0&&0&&0&&1\\0&&1&&0&&0\\1&&0&&0&&0\\0&&0&&1&&0\\\end{pmatrix}}$.

Permutacijski matriki $2\times 2\,$ (dva elementa, ki permutirata) sta ${\begin{bmatrix}1&0\\0&1\\\end{bmatrix}}$ in ${\begin{bmatrix}0&1\\1&0\\\end{bmatrix}}$

Primer permutacijske matrike $4\times 4\,$ (štirje elementi, ki permutirajo): ${\begin{pmatrix}1&0&0&0\\0&0&1&0\\0&0&0&1\\0&1&0&0\end{pmatrix}}$

Značilnosti

• za dve permutaciji $\sigma \,$ in $\pi \,$ velja $P_{\sigma }.P_{\pi }=P_{\sigma \circ \pi }$

kjer je

$\circ \,$ kompozitum permutacij $P_{\sigma }\,$ in $P_{\pi }\,$

• permutacijske matrike so ortogonalne, zanje velja :$P_{\pi }P_{\pi }^{T}=I$
• permutacijska matrika spada med stohastične matrike
• množenje permutacijske matrike $P\,$ s poljubno matriko $A\,$ povzroči permutacijo vrstic v matriki $A\,$ (to je $P.A\,$)
• množenje poljubne matrike $A\,$ s permutacijsko matriko $P\,$ ima za posledico permutacijo stolpcev v matriki $A\,$ (to je $A.P\,$)
• obratna vrednost permutacijske matrike je enaka njeni transponirani $P^{-1}=P^{T}\,$ ali $A.A^{T}=I\,$ ($I\,$ je enotska matrika)

Posplošitev permutacijske matrike

Vsota elementov v vsaki vrstici permutacijske matrike je 1. To lahko posplošimo tako, da dovolimo v vsaki vrstici poljubno vsoto. Takšne matrike so vsote permutacijskih matrik.

Primer: Naslednja matrika ima v vsaki vrstici vsoto elementov enako 5

$M={\begin{bmatrix}5&0&0&0&0\\0&3&2&0&0\\0&0&0&5&0\\0&1&2&0&2\\0&1&1&0&3\end{bmatrix}}.$.

Glej tudi

• seznam vrst matrik

Zunanje povezave

• Weisstein, Eric Wolfgang. »Permutation Matrix«. MathWorld.
• Značilnosti permutacijske matrike (angleško)