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 $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 $P^{- 1} = P^{T}$ , där T betecknar transponat.

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

Definition

Givet en permutation π av m element,

π : {1, \dots, m} \to {1, \dots, m}

representerad i form av två rader av

(\begin{matrix} 1 & 2 & \dots & m \\ π (1) & π (2) & \dots & π (m) \end{matrix}),

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 Mall:Pi. 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_Mall:Pi = (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 = Mall:Pi(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 Mall:Pi(i), kan vi skriva

P_{π} = [\begin{matrix} 𝐞_{π (1)} \\ 𝐞_{π (2)} \\ ⋮ \\ 𝐞_{π (m)} \end{matrix}],

där $𝐞_{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_Mall:Pi svarande mot permutationen $π = (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 2 & 5 & 3 \end{matrix}),$

P_{π} = [\begin{matrix} 𝐞_{π (1)} \\ 𝐞_{π (2)} \\ 𝐞_{π (3)} \\ 𝐞_{π (4)} \\ 𝐞_{π (5)} \end{matrix}] = [\begin{matrix} 𝐞_{1} \\ 𝐞_{4} \\ 𝐞_{2} \\ 𝐞_{5} \\ 𝐞_{3} \end{matrix}] = [\begin{matrix} 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{matrix}] .

Observera att kolumn j av I₅ i identitetsmatrisen nu uppträder som Mall:Pi(j)-kolumnen hos P_Mall:Pi.

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 = Mall:Pi(j) och 0 i övrigt, refereras till som radrepresentationen.

Egenskaper

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

Att multiplicera $P_{π}$ med en kolumnvektor g permuterar vektors rader:

P_{π} 𝐠 = [\begin{matrix} 𝐞_{π (1)} \\ 𝐞_{π (2)} \\ ⋮ \\ 𝐞_{π (n)} \end{matrix}] [\begin{matrix} g_{1} \\ g_{2} \\ ⋮ \\ g_{n} \end{matrix}] = [\begin{matrix} g_{π (1)} \\ g_{π (2)} \\ ⋮ \\ g_{π (n)} \end{matrix}] .

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

P_{π} 𝐞_{k}^{𝖳} = 𝐞_{π^{- 1} (k)}^{𝖳}

för varje Mall:Mvar visar att permutationer av rader ges av Mall:Pi⁻¹.

Då permutationsmatriserna är ortogonala matriser (exempelvis, $P_{π} P_{π}^{𝖳} = I$ ), existerar den inversa matrisen och kan skrivas som

P_{π}^{- 1} = P_{π^{- 1}} = P_{π}^{𝖳} .

Multiplikation av en radvektor med $P_{π}$ permuterar vektorns kolumner:

𝐡 P_{π} = [\begin{matrix} h_{1} h_{2} \dots h_{n} \end{matrix}] [\begin{matrix} 𝐞_{π (1)} \\ 𝐞_{π (2)} \\ ⋮ \\ 𝐞_{π (n)} \end{matrix}] = [\begin{matrix} h_{π^{- 1} (1)} h_{π^{- 1} (2)} \dots h_{π^{- 1} (n)} \end{matrix}]

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

𝐞_{k} P_{π} = 𝐞_{π (k)} .

Givet två permutationer Mall:Pi and Mall:Math av Mall:Math element, är de motsvarande permutationsmatriserna Mall:Math and Mall:Math som verkar på kolumnvektorer, komponerade enligt

P_{σ} P_{π} 𝐠 = P_{π \circ σ} 𝐠 .

Samma matriser verkande på radvektorer (multiplikation enligt mönstret Mall:Math) är sammansatta enligt samma regel

𝐡 P_{σ} P_{π} = 𝐡 P_{π \circ σ} .

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

π \circ σ (k) = π (σ (k)) .

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

Q_{π} 𝐞_{k}^{𝖳} = P_{π^{- 1}} 𝐞_{k}^{𝖳} = 𝐞_{(π^{- 1})^{- 1} (k)}^{𝖳} = 𝐞_{π (k)}^{𝖳} .

Från detta följer

Q_{σ} Q_{π} 𝐠 = Q_{σ \circ π} 𝐠 .

och på liknande sätt,

𝐡 Q_{σ} Q_{π} = 𝐡 Q_{σ \circ π} .

Exempel

Permutation av rader och kolumner

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):

Permutation av rader

Permutationsmatrisen P_π motsvarande permutationen

π = (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 2 & 5 & 3 \end{matrix}),

är

P_{π} = [\begin{matrix} 𝐞_{π (1)} \\ 𝐞_{π (2)} \\ 𝐞_{π (3)} \\ 𝐞_{π (4)} \\ 𝐞_{π (5)} \end{matrix}] = [\begin{matrix} 𝐞_{1} \\ 𝐞_{4} \\ 𝐞_{2} \\ 𝐞_{5} \\ 𝐞_{3} \end{matrix}] = [\begin{matrix} 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{matrix}] .

Givet en vektor g,

P_{π} 𝐠 = [\begin{matrix} 𝐞_{π (1)} \\ 𝐞_{π (2)} \\ 𝐞_{π (3)} \\ 𝐞_{π (4)} \\ 𝐞_{π (5)} \end{matrix}] [\begin{matrix} g_{1} \\ g_{2} \\ g_{3} \\ g_{4} \\ g_{5} \end{matrix}] = [\begin{matrix} g_{1} \\ g_{4} \\ g_{2} \\ g_{5} \\ g_{3} \end{matrix}] .

Referenser

Noter

↑ Terminologin är inte standard. De flesta författare väljer en notation som är konsistent med övriga notationer som kan ha introducerats så det finns vanligen ingen anledning att tillhandahålla ett specifikt namn.
↑ Brualdi (2006) p.2

Mall:Linjär-algebra

[1] Terminologin är inte standard. De flesta författare väljer en notation som är konsistent med övriga notationer som kan ha introducerats så det finns vanligen ingen anledning att tillhandahålla ett specifikt namn.

[Bru2-2] Brualdi (2006) p.2

[1]

[2]

Permutationsmatris

Innehåll

Definition

Egenskaper

Exempel

Permutation av rader och kolumner

Permutation av rader

Referenser

Noter

Navigeringsmeny

Permutationsmatris

Definition

Egenskaper

Exempel

Permutation av rader och kolumner

Permutation av rader

Referenser

Noter

Navigeringsmeny

Sök