Permutacijska matrika

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

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 :\{1,\dots ,m\}\to \{1,\dots ,m\}$

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

$\left(\begin{array}{cccc}1& 2& \cdots & m\\ \pi (1)& \pi (2)& \cdots & \pi (m)\end{array}\right)$

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 }=\left[\begin{array}{c}{𝐞}_{\pi (1)}\\ {𝐞}_{\pi (2)}\\ ⋮\\ {𝐞}_{\pi (m)}\end{array}\right],$

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 =\left(\begin{array}{ccccccc}1& & 2& & 3& & 4\\ 4& & 2& & 1& & 3\end{array}\right)$

Pripadajoča matrika pa je:

$P=\left(\begin{array}{ccccccc}0& & 0& & 0& & 1\\ 0& & 1& & 0& & 0\\ 1& & 0& & 0& & 0\\ 0& & 0& & 1& & 0\end{array}\right)$.

Permutacijski matriki $2\times 2$ (dva elementa, ki permutirata) sta $\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$ in $\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$

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

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=\left[\begin{array}{ccccc}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{array}\right].$.

Glej tudi

• seznam vrst matrik

Zunanje povezave

• Predloga:MathWorld
• Značilnosti permutacijske matrikePredloga:Slepa povezava Predloga:Ikona en