Permutatiematrix

In de lineaire algebra, een onderdeel van de wiskunde, is een permutatiematrix een vierkante matrix, die in iedere rij en in iedere kolom één waarde 1 heeft en waar alle andere waarden in diezelfde rijen en kolommen gelijk zijn aan 0. Een permutatiematrix is dus behalve een vierkante ook een binaire matrix. Een permutatiematrix ontstaat door de rijen of door de kolommen van een eenheidsmatrix te permuteren.

Iedere ${\displaystyle m\times m}$-permutatiematrix ${\displaystyle \mathbf {P} }$ vermenigvuldigd met een m-vector ${\displaystyle \mathbf {x} }$ stelt een specifieke permutatie van de ${\displaystyle m}$ elementen van ${\displaystyle \mathbf {x} }$ voor. Indien ${\displaystyle \mathbf {P} }$ met een andere matrix wordt vermenigvuldigd permuteert ${\displaystyle \mathbf {P} }$ de rijen of de kolommen van de andere matrix produceren. De eenheidsmatrix is ook een permutatiematrix, maar dat is evident. Het product van twee willekeurige permutatiematrices is opnieuw een permutatiematrix. Iedere permutatiematrix is een orthogonale matrix, dus is de inverse matrix van een permutatiematrix ${\displaystyle \mathbf {P} }$ de getransponeerde matrix ${\displaystyle \mathbf {P} ^{T}}$ van ${\displaystyle \mathbf {P} }$.

Twee matrices ${\displaystyle \mathbf {A} }$ en ${\displaystyle \mathbf {B} }$ worden gelijksoortige matrices genoemd, wanneer er een permutatiematrix ${\displaystyle \mathbf {P} }$ is, zodat ${\displaystyle \mathbf {B} =\mathbf {P} ^{-1}\mathbf {AP} }$.

Definitie

Gegeven een permutatie ${\displaystyle \pi }$ van ${\displaystyle m}$ elementen,

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

De bijbehorende permutatiematrix ${\displaystyle \mathbf {P} _{\pi }}$ is

${\displaystyle \mathbf {P} _{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (m)}\end{bmatrix}}={\begin{pmatrix}0&0&\cdots &1&0\\0&1&\cdots &0&0\\\vdots &\vdots &&&\vdots \\0&0&\cdots &0&1\end{pmatrix}}}$

De invoerwaarden van ${\displaystyle \mathbf {P} _{\pi }}$ zijn allemaal gelijk zijn 0, behalve dat in rij ${\displaystyle i}$ de waarde ${\displaystyle \pi (i)}$ gelijk is aan 1.

${\displaystyle \mathbf {e} _{i}}$ is dus voor iedere ${\displaystyle i}$ een rijvector van lengte ${\displaystyle m}$ met een 1 op de ${\displaystyle i}$-de plaats en een 0 op alle andere plaatsen.

De gegeven permutatie ${\displaystyle \pi }$ wordt ook geschreven als

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

Eigenschappen

Gegeven twee permutaties ${\displaystyle \pi }$ en ${\displaystyle \sigma }$ van ${\displaystyle m}$ elementen en de corresponderende permutatiematrices ${\displaystyle \mathbf {P} _{\pi }}$ en ${\displaystyle \mathbf {P} _{\sigma }}$. Dan geldt voor de functiecompositie van de twee permutaties dat

${\displaystyle \mathbf {P} _{\pi }\mathbf {P} _{\sigma }=\mathbf {P} _{\pi \circ \sigma }}$

Aangezien permutatiematrices orthogonale matrices zijn, bestaat de inverse matrix ervan en kan deze worden geschreven als

${\displaystyle \mathbf {P} _{\pi }^{-1}=\mathbf {P} _{\pi ^{-1}}=\mathbf {P} _{\pi }^{T}}$

${\displaystyle \mathbf {P} _{\pi }}$ vermenigvuldigen met de kolomvector ${\displaystyle \mathbf {g} }$ permuteert de rijen van ${\displaystyle \mathbf {g} }$:

${\displaystyle \mathbf {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}}.}$

${\displaystyle \mathbf {P} _{\pi }}$ vermenigvuldigen van een rijvector ${\displaystyle \mathbf {h} }$ permuteert de kolommen van ${\displaystyle \mathbf {h} }$:

${\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)}\;h_{\pi (2)}\;\dots \;h_{\pi (n)}\end{bmatrix}}}$

Voorbeelden

Definieer de permutatiematrix ${\displaystyle \mathbf {P} _{\pi }}$

${\displaystyle \mathbf {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 ${\displaystyle \mathbf {g} }$, dan is

${\displaystyle \mathbf {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}}}$

waarin de elementen van ${\displaystyle \mathbf {g} }$ zijn gepermuteerd.

${\displaystyle \mathbf {P} _{\pi }}$ wordt in dit geval ook geschreven als

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