Permutatiematrix

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de lineaire algebra, een onderdeel van de wiskunde, is een permutatie matrix een vierkante (0,1)-matrix die precies één waarde 1 in elke rij en elke kolom heeft en waar alle andere waarde in diezelfde rijen en kolommen gelijk zijn aan 0. Een permutatiematrix kan ook gezien worden als een elementaire matrix waar de rijen zijn gepermuteerd. Elke permutatiematrix stelt een specifieke permutatie van m elementen voor en, indien gebruikt om een andere matrix te vermenigvuldigen, kan de permutatiematrix deze permutatie in de rijen of kolommen van de andere matrix produceren.

Definitie[bewerken]

Gegeven een permutatie π van m elementen,

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

wat in tweeregelige vorm kan worden geschreven als

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

De permutatiematrix is de m × m matrix Pπ, waarvan de invoerwaarden allen gelijk zijn 0, behalve dat in rij i, de invoerwaarde π(i) gelijk is aan 1. Wij mogen schrijven

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

waar \mathbf e_j een rijvector van lengte m met 1 in de j-de positie en 0 in alle andere posities voorstelt.

Eigenschappen[bewerken]

Gegeven twee permutaties π en σ van m elementen en de corresponderende permutatiematrices Pπ en Pσ

P_{\pi} P_{\sigma} = P_{\pi \circ \sigma}

Aangezien permutatiematrices orthogonale matrices zijn (dat wil zeggen, P_{\pi}P_{\pi}^{T} = I), bestaat de inverse matrix en kan deze geschreven worden als

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

Vermenigvuldiging van P_{\pi} maal een kolomvector g zal de rijen van de vector permuteren:

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

Vermenigvuldiging van een rijvector h maal P_{\pi} zal de kolommen van de matrix als volgt permuteren:

\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)} \; h_{\pi(2)} \; \dots \; h_{\pi(n)} \end{bmatrix}
  1. Een permutatiematrix is het product van een eindig aantal elementaire matrices die elk een corresponderen met e 'rij-verwisselende' elementaire rij operatie.
  2. Elke permutatiematrix P is inverteerbaar en P^{-1} = P^T.
  3. Het product van twee willekeurige permutatiematrices is opnieuw een permutatiematrix.
  4. De getransponeerde van een permutatiematrix is ook een permutatiematrix.

Voorbeelden[bewerken]

De permutatiematrix Pπ die correspondeert met de permutatie :\pi=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 2 & 5 & 3 \end{pmatrix}, is

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

Gegeven een vector g,

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


Zie ook[bewerken]