Permutacijska matrika

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
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[uredi | uredi kodo]

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[uredi | uredi kodo]

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}

Lastnosti[uredi | uredi kodo]

  • 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[uredi | uredi kodo]

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[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]