Permutationsmatris

I matematik , särskilt i matristeori , är en permutationsmatris en kvadratisk binär matris som har exakt en post på 1 i varje rad och varje kolumn och nollor någon annanstans. Varje sådan matris, säg P , representerar en permutation av m element och, när den används för att multiplicera en annan matris, säg A , resulterar i permutering av raderna (vid förmultiplikering, för att bilda PA ) eller kolumner (vid eftermultiplikering, för att bilda AP ) av matrisen A.

Definition

Givet en permutation π av m element,

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

representeras i tvåradsform av

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

det finns två naturliga sätt att associera permutationen med en permutationsmatris; nämligen att börja med m × m identitetsmatrisen , I _m , antingen permutera kolumnerna eller permutera raderna, enligt π . Båda metoderna för att definiera permutationsmatriser förekommer i litteraturen och egenskaperna uttryckta i en representation kan enkelt omvandlas till den andra representationen. Den här artikeln kommer i första hand att behandla bara en av dessa representationer och den andra kommer endast att nämnas när det finns en skillnad att vara medveten om.

Den m × m permutationsmatris P _π = ( p _ij ) som erhålls genom att permutera kolumnerna i identitetsmatrisen I _m , det vill säga för varje i , p _ij = 1 om j = π ( i ) och p _ij = 0 annars, kommer att kallas kolumnrepresentationen i den här artikeln. Eftersom posterna i rad i alla är 0 förutom att en 1 visas i kolumn π ( i ), kan vi skriva

$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 med längden m med 1 i den j: te positionen och 0 i varannan position.

är permutationsmatrisen P _π som motsvarar permutationen $\pi ={\begin{pmatrix}1&2&3&4&5\\1&4&2&5&3\end{pmatrix}}$

$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 den j: te kolumnen i I _5- identitetsmatrisen nu visas som den π ( j ):e kolumnen i P _π .

_erhållen genom att permutera raderna i identitetsmatrisen Im , det _{annars vill} pij = 0 säga för varje j , pij = 1 om i = π ( j ) och , kommer att hänvisas till som radrepresentationen .

Egenskaper

Kolumnrepresentationen av en permutationsmatris används i hela detta avsnitt, utom när annat anges.

Att multiplicera $P_{\pi }$ gånger en kolumnvektor g kommer att permutera vektorns rader:

$$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 matris av lämplig storlek, är produkten, $P_{\pi }M$ bara en permutation av raderna i M . Men observerar det

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

för varje k visar att permutationen av raderna ges av π ⁻¹ . ( $M^{\mathsf {T}}$ är transponeringen matrisen M. )

Eftersom permutationsmatriser är ortogonala matriser (det vill säga $P_{\pi }P_{\pi }^{\mathsf {T}}=I$ ), finns den inversa matrisen och kan vara skrivet som

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

Att multiplicera en radvektor h gånger $P_{\pi }$ kommer att permutera vektorns kolumner:

$$\mathbf {h} P_{\pi }={\begin{bmatrix}h_{1}&h_{2}&\cdots &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)}&\cdots &h_{\pi ^{-1 }(n)}\end{bmatrix}}$$

Återigen visar upprepad tillämpning av detta resultat att eftermultiplicering av en matris M med permutationsmatrisen P _π , det vill säga MP _π , resulterar i permutering av kolumnerna i M . Lägg också märke till det

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

Givet två permutationer π och σ av m element, är motsvarande permutationsmatriser P _π och P _σ som verkar på kolumnvektorer sammansatta med

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

Samma matriser som verkar på radvektorer (det vill säga efter multiplikation) komponeras enligt samma regel

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

För att vara tydlig använder formlerna ovan prefixnotationen för permutationskomposition, det vill säga

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

Låt $Q_{\pi }$ vara den permutationsmatris som motsvarar π i dess radrepresentation. Egenskaperna för denna representation kan bestämmas från de för kolumnrepresentationen eftersom ${\displaystyle Q_{\pi }=P_{\pi }^{\mathsf {T}}=P_{{\pi }^{-1}}.} I synnerhet$ ,

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

Av detta följer att

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

Liknande,

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

Permutationsmatriser kan karakteriseras som de ortogonala matriserna vars poster alla är icke-negativa .

Matrisgrupp

Om (1) anger identitetspermutationen, så är P ₍₁₎ identitetsmatrisen .

Låt S _n beteckna den symmetriska gruppen , eller gruppen av permutationer , på {1,2,..., n }. Eftersom det finns n ! permutationer, det finns n ! permutationsmatriser. Med formlerna ovan n × n permutationsmatriserna en grupp under matrismultiplikation med identitetsmatrisen som identitetselement .

Kartan S _n → GL( n , Z ₂ ) som skickar en permutation till sin kolumnrepresentation är en trogen representation .

Dubbelstokastiska matriser

En permutationsmatris är i sig en dubbelstokastisk matris , men den spelar också en speciell roll i teorin om dessa matriser. Birkhoff -von Neumann-satsen säger att varje dubbelstokastisk reell matris är en konvex kombination av permutationsmatriser av samma ordning och permutationsmatriserna är precis extrempunkterna i uppsättningen av dubbelstokastiska matriser. Det vill säga, Birkhoff-polytopen , uppsättningen av dubbelstokastiska matriser, är det konvexa skrovet av uppsättningen av permutationsmatriser.

Linjära algebraiska egenskaper

Spåret för en permutationsmatris är antalet fasta punkter för permutationen . Om permutationen har fixpunkter så kan den skrivas i cykelform som π = ( a ₁ )( a ₂ )...( a _k )σ där σ inte har några fixpunkter, då e _{a 1} , e _{a 2} , ..., e _{a k} är egenvektorer för permutationsmatrisen.

För att beräkna egenvärdena för en permutationsmatris $P_{\sigma }$ , skriv $\sigma$ som en produkt av cykler , säg $\sigma =C_{1}C_{2}\cdots C_{t}$ . Låt motsvarande längder av dessa cykler vara $l_{1},l_{2}...l_{t}$ , och låt $R_{i}(1\leq i\leq t)$ vara mängden komplexa lösningar av $x^{l_{i}}=1$ . Unionen av alla $R_{i}$ är uppsättningen av egenvärden för motsvarande permutationsmatris. Den geometriska multipliciteten för varje egenvärde är lika med antalet $R_{i}$ s som innehåller det.

Från gruppteorin vet vi att vilken permutation som helst kan skrivas som en produkt av transponeringar . Därför, alla permutationsmatris P faktorer som en produkt av rad-utbyte elementära matriser , var och en har determinant −1. Således är determinanten för en permutationsmatris P signaturen för motsvarande permutation.

Exempel

Permutation av rader och kolumner

När en matris M multipliceras med en permutationsmatris P till vänster för att göra PM , är produkten resultatet av att raderna av M permuteras . Som ett specialfall, om M är en kolumnvektor, är PM resultatet av att permutera ingångarna i M :

P · (1, 2, 3, 4) T = (4, 1, 3, 2) T

När M istället multipliceras med en permutationsmatris till höger för att göra MP , är produkten resultatet av att kolumnerna i M permuteras . Som ett specialfall, om M är en radvektor, så är MP resultatet av att permutera inmatningarna av M :

(1, 2, 3, 4) · P = (2, 4, 3, 1)

Permutation av rader

Permutationsmatrisen P _π som motsvarar permutationen $\pi ={\begin{pmatrix}1&2&3&4&5\\1&4&2&5&3\end{pmatrix}}$ är

$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 ,

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

Förklaring

En permutationsmatris kommer alltid att vara i formen

${\begin{bmatrix}\mathbf {e} _{a_{1}}\\\mathbf {e} _{a_{2}}\\\ vdots \\\mathbf {e} _{a_{j}}\\\end{bmatrix}}$

där e _{ai Rj} representerar den i :te basvektorn (som en rad) för , ^och där

${\begin{bmatrix}1&2&\ldots &j\\a_{1}&a_{2}&\ldots &a_{j}\end{bmatrix}}$

är permutationsformen för permutationsmatrisen.

₀ När man nu utför matrismultiplikation , bildar man i huvudsak punktprodukten av varje rad i den första matrisen med varje kolumn i den andra. I det här fallet kommer vi att bilda punktprodukten för varje rad i denna matris med vektorn av element som vi vill permutera. Det vill säga till exempel v = ( g ,..., g ₅ ) ^T ,

e _{a i} · v = g _{a i}

Så produkten av permutationsmatrisen med vektorn v ovan kommer att vara en vektor i formen ( g _{a 1} , g _{a 2} , ..., g _{a j} ), och att detta då är en permutation av v eftersom vi har sagt att permutationsformen är

${\begin{pmatrix}1&2&\ldots &j\\a_{1}&a_{2}&\ldots &a_{j}\end{pmatrix}}.$

Så, permutationsmatriser permuterar verkligen ordningen på element i vektorer multiplicerade med dem.

Begränsade former

• Costas array , en permutationsmatris där förskjutningsvektorerna mellan posterna alla är distinkta
• n-queens pussel , en permutationsmatris där det finns högst en post i varje diagonal och antidiagonal

Se även

• Alternerande teckenmatris
• Utbytesmatris
• Generaliserad permutationsmatris
• Rökpolynom
• Permanent

•    Brualdi, Richard A. (2006). Kombinatoriska matrisklasser . Encyclopedia of Mathematics och dess tillämpningar. Vol. 108. Cambridge: Cambridge University Press . ISBN 0-521-86565-4 . Zbl 1106.05001 .
• Joseph, Najnudel; Ashkan, Nikeghbali (2010), The Distribution of Eigenvalues ​​of Randomized Permutation Matrices , arXiv : 1005.0402 , Bibcode : 2010arXiv1005.0402N