Permutationsmatris

En permutationsmatris är en kvadratisk matris som har precis en etta i varje rad och varje kolumn och vars övriga element är noll.

Permutationsmatriser är ortogonalmatriser, eftersom deras rader är omkastningar av raderna i en enhetsmatris och matriserna är således inverterbara.

Om en permutationsmatris multipliceras med en vektor permuteras vektorns rader eller kolumner beroende på om matrisen står till vänster eller höger om multiplikationstecknet.

Alla permutationer i den symmetriska gruppen ${\displaystyle S_{n}}$ kan skrivas som en n × n-permutationsmatris och dessa matriser bildar en grupp under matrismultiplikation, med enhetsmatrisen som neutralt element. Inversen till en permutation med matrisen P ges av ${\displaystyle P^{-1}=P^{T}}$, där T betecknar transponat.

Matrisspåret av en permutationsmatris är antalet fixpunkter för permutationen.

Givet en permutation π av m element,

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

representerad i form av två rader av

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

finns det två naturliga sätt att associera permutationen med en permutationsmatris, nämligen att starta med en m × m enhetsmatris, I_m och endera permutera kolumnerna eller raderna i I_m i enlighet med π. Båda sätten att definiera en permutationsmatris förekommer i litteraturen och egenskaperna uttryckta i den ena representationen kan enkelt översättas till den andra representationen. Denna artikel behandlar blott den ena representationen med undantag av när det finns särskilda skäl för att uppmärksamma skillnaden.

m × m-permutationsmatrisen P_π = (p_ij) erhållen genom permutation av kolumnerna av idetitetsmatrisen I_m, det vill säga, för varje i är p_ij = 1 om j = π(i) eller 0 i övriga fall, kommer att refereras till som kolumnrepresentation i denna artikel.^[1] Då elementen i rad i är alla 0 med undantag för en 1:a som förekommer i π(i), kan vi skriva

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

där ${\displaystyle \mathbf {e} _{j}}$, en standardbasvektor, betecknar en radvektor av längden m med 1 i position j och 0 i övriga positioner.^[2]

Exempelvis är, permutationsmatrisen P_π svarande mot permutationen ${\displaystyle \pi ={\begin{pmatrix}1&2&3&4&5\\1&4&2&5&3\end{pmatrix}},}$

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

Observera att kolumn j av I₅ i identitetsmatrisen nu uppträder som π(j)-kolumnen hos P_π.

Den andra representationen, erhållen genom permutering av raderna hos identitetsmatrisen I_m, det vill säga, för varje j, är p_ij = 1 om i = π(j) och 0 i övrigt, refereras till som radrepresentationen.

Kolumnrepresentationen av en permutationsmatris används genomgående i detta avsnitt om inte annat anges.

Att multiplicera ${\displaystyle P_{\pi }}$ med en kolumnvektor g permuterar vektors rader:

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

Upprepad användning av detta resultat visar att om M är en korrekt dimensionerad matris, är produkten, ${\displaystyle P_{\pi }M}$ en permutation av raderna i M. Emellertid, observationen att

${\displaystyle P_{\pi }\mathbf {e} _{k}^{\mathsf {T}}=\mathbf {e} _{\pi ^{-1}(k)}^{\mathsf {T}}}$

för varje k visar att permutationer av rader ges av π⁻¹.

Då permutationsmatriserna är ortogonala matriser (exempelvis, ${\displaystyle P_{\pi }P_{\pi }^{\mathsf {T}}=I}$), existerar den inversa matrisen och kan skrivas som

${\displaystyle P_{\pi }^{-1}=P_{\pi ^{-1}}=P_{\pi }^{\mathsf {T}}.}$

Multiplikation av en radvektor med ${\displaystyle P_{\pi }}$ permuterar vektorns kolumner:

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

Återigen, upprepad tillämpning av detta resultat, det vill säga, multiplikation av en matris M med permutationsmatrisen P_π, enligt M P_π, resulterar i en permutation av M:s kolumner. Notera också att

${\displaystyle \mathbf {e} _{k}P_{\pi }=\mathbf {e} _{\pi (k)}.}$

Givet två permutationer π and σ av m element, är de motsvarande permutationsmatriserna P_π and P_σ som verkar på kolumnvektorer, komponerade enligt

${\displaystyle P_{\sigma }P_{\pi }\,\mathbf {g} =P_{\pi \,\circ \,\sigma }\,\mathbf {g} .}$

Samma matriser verkande på radvektorer (multiplikation enligt mönstret M P_π) är sammansatta enligt samma regel

${\displaystyle \mathbf {h} P_{\sigma }P_{\pi }=\mathbf {h} P_{\pi \,\circ \,\sigma }.}$

För klarhets skull, ovanstående uttryck använder prefixnotation för permutationssammansättningar, det vill säga

${\displaystyle \pi \,\circ \,\sigma (k)=\pi \left(\sigma (k)\right).}$

Låt ${\displaystyle Q_{\pi }}$ vara permutationsmatrisen som svarar mot π i dess radrepresentation. Egenskaperna hos denna representation kan bestämmas från de med kolumnrepresentation då ${\displaystyle Q_{\pi }=P_{\pi }^{\mathsf {T}}=P_{{\pi }^{-1}}.}$ Speciellt,

${\displaystyle Q_{\pi }\mathbf {e} _{k}^{\mathsf {T}}=P_{{\pi }^{-1}}\mathbf {e} _{k}^{\mathsf {T}}=\mathbf {e} _{(\pi ^{-1})^{-1}(k)}^{\mathsf {T}}=\mathbf {e} _{\pi (k)}^{\mathsf {T}}.}$

Från detta följer

${\displaystyle Q_{\sigma }Q_{\pi }\,\mathbf {g} =Q_{\sigma \,\circ \,\pi }\,\mathbf {g} .}$

och på liknande sätt,

${\displaystyle \mathbf {h} \,Q_{\sigma }Q_{\pi }=\mathbf {h} \,Q_{\sigma \,\circ \,\pi }.}$

När en permutationsmatris P multipliceras från vänster med en matris M (PM) permuterar den M:s rader (här, en kolumnvektors element),

när P multipliceras från höger med M (MP) kommer den att permutera M:s kolumner (här, en radvektors element):

Permutationsmatrisen P_π motsvarande permutationen

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

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

Givet en vektor g,

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

v • r Linjär algebra Grundläggande begrepp Skalär · Vektor · Noll · Ortogonalitet · Ekvationssystem · Rum · Linjärkombination · Inre produkt · Oberoende · Bas · Radrum · Kolonnrum · Nollrum · Gram-Schimdt · Egenvärde · Hölje · Linjäritet Vektoralgebra Kryssprodukt · Trippelprodukt Matriser Elementär · Block · Enhet · Determinant · Norm · Rang · Transformation · Rotation · Invers · Cramers regel · Trappstegsform · Spår · Transponat · Gausselimination · Symmetri · Addition Multilinjär algebra Geometrisk algebra · Yttre algebra · Bivektor · Multivektor · Tensor Konstruktioner Delrum · Dualrum · Funktionsrum · Kvotrum · Tensorprodukt Numerik Flyttal · Gles matris Kategori