permutationsmatris

En permutationsmatris är en kvadratisk matris som används för att representera en permutation av ett ändligt antal element. Den är ofta uppbyggd genom att använda en ordnad uppsättning av standardbasens enhetsvektorer och genom att permutera rader eller kolumner enligt en given permutation. På så sätt beskriver den hur basisvektorerna ändrar position i ett linjärt utbilde.

Formellt: om σ är en permutation av {1, …, n}, så är permutationsmatrisen Pσ en n×n-matris där endast en 1:a finns i varje kolumn och varje rad och övriga element är 0, där positionerna med 1 uppfyller Pσ_{σ(j), j} = 1 för varje j i {1, …, n}. Denna konstruktion innebär att Pσ återspeglar hur kolonnerna eller raderna av en annan matris omordnas.

Egenskaperna hos en permutationsmatris är bland annat att den är ortogonal ( Pσ^T = Pσ^{-1} ), och dess determinan är tecknet för permutationens slag (det vill säga ±1). Egenvärdena är i allmänhet komplexa rotserier av en enhet, särskilt för cykliska permutationer.

Användning: vänstermultiplikation med en permutationsmatris omordnar raderna i en matris, medan högermultiplikation omordnar kolumnerna. Exempelvis, för n = 3 och σ = (2 3 1) är Pσ = [[0, 0, 1], [1, 0, 0], [0, 1, 0]]. Produktregler: Pσ τ motsvarar permutationens sammansättning σ∘τ. Permutationsmatriser används inom linjär algebra, dator-algoritmer och kombinatorik för att formellt representera och manipulera permutationer.