5.7 Die Permutationsmatrizen

Definition (Permutationsmatrix, Transpositionsmatrix)

Seien K ein Körper, n ≥ 1 und π  ∈  S_n = { σ | σ : { 1, …, n } → { 1, …, n } ist bijektiv }. Dann heißt die Matrix

P_π = $( \begin{matrix} e_{π (1)} & … & e_{π (n)} \end{matrix} )$   ∈  K^{n × n}

die zu π gehörige Permutationsmatrix. Ist π eine Transposition, so heißt P_π eine Transpositionsmatrix. Vertauscht eine Transposition π die Zahlen i ≠ j, so schreiben wir auch kurz P_ij für die zugehörige Transpositionsmatrix.

Die Spalten der Permutationsmatrix P_π sind die gemäß π = (π(1), …, π(n)) umgeordneten kanonischen Einheitsvektoren e₁, …, e_n. Jede Zeile und jede Spalte von P_π hat genau einen Eins-Eintrag und sonst nur Nullen. Jede Permutationsmatrix geht aus E_n durch Vertauschung von Spalten hervor. Bei den spezielleren Transpositionsmatrizen werden genau zwei verschiedene Spalten ausgetauscht. Für alle i ≠ j gilt P_ij = P_ji.

Beispiele

(1)	Für n = 2 gibt es neben E₂ nur noch die Permutationsmatrix P₁₂ = $( \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} )$ , die zudem eine Transpositionsmatrix ist. Es gilt P₁₂² = E₂.

(2)

Für n = 3 gibt es neben E₃ noch die fünf Permutationsmatrizen

$( \begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix} )$ , $( \begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix} )$ , $( \begin{matrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix} )$ , $( \begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix} )$ , $( \begin{matrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix} )$ .

Für alle n gibt es genau n! = |S_n| viele Permutationsmatrizen und genau n(n − 1)/2 Transpositionsmatrizen („2 aus n“). Die Transpositionsmatrizen sind durch genau zwei Null-Einträge auf der Diagonale charakterisiert.

Es gilt P_π(i, j) = 1 genau dann, wenn π(j) = i. Dies ist äquivalent zu π⁻¹(i) = j. Damit sind die Zeilen von P_π die gemäß π⁻¹ angeordneten Einheitsvektoren e₁, …, e_n:

P_π = $( \begin{matrix} e_{π (1)} & … & e_{π (n)} \end{matrix} )$ = $( \begin{matrix} e_{π^{- 1} (1)} \\ … \\ e_{π^{- 1} (n)} \end{matrix} )$ .

Man rechnet nach, dass für alle π, σ  ∈  S_n gilt:

P_π P_σ = P_π ∘ σ, P⁻¹_π = P_π⁻¹. (Kompositions- und Invertierungsregel)

Permutationsmatrizen wirken auf Vektoren und andere Matrizen wie folgt.

Matrix-Vektor-Produkt

Für alle π  ∈  S_n und alle x  ∈  Kⁿ gilt

P_πx = $( \begin{matrix} e_{π (1)} & … & e_{π (n)} \end{matrix} )$ x = x₁e_π(1) + … + x_ne_π(n) = (x_π⁻¹(1), …, x_π⁻¹(n)).

Die i-te Komponente von x sitzt in y = P_πx an der Stelle j = π(i). Damit sitzt an der j-ten Stelle von y die i = π⁻¹(j)-te Komponente von x.

Matrizenprodukt von links und rechts

Für alle A  ∈  K^{m × n}, π  ∈  S_n und σ  ∈  S_m gilt

A P_π = $( \begin{matrix} {Ae}_{π (1)} & … & {Ae}_{π (n)} \end{matrix} )$ = $( \begin{matrix} a_{π (1)} & … & a_{π (n)} \end{matrix} )$ mit den Spalten a₁, …, a_n von A,

P_σ A = $( \begin{matrix} a_{σ^{- 1} (1)} \\ … \\ a_{σ^{- 1} (m)} \end{matrix} )$ mit den Zeilen a₁, …, a_m von A.

Die Multiplikation mit P_π von rechts vertauscht also die Spalten von A, während die Multiplikation mit P_σ von links die Zeilen von A vertauscht. Speziell sind in AP_ij die Spalten i und j vertauscht und in P_ij A die Zeilen i und j.

Wie jede invertierbare Matrix lässt sich eine Permutationsmatrix als Produkt von Elementarmatrizen darstellen. Dies lässt sich aber auch leicht direkt einsehen. Für die Transpositionen gilt

P_ij = W_jj(−1) W_ij(1) W_ji(−1) W_ij(1) für alle i ≠ j.

Stellt man nun ein π  ∈  S_n als Komposition von Transpositionen dar, so ergibt sich eine Darstellung von P_π als Produkt von Transpositionsmatrizen.

Da das Vertauschen von Zeilen und Spalten speziell beim Umgang mit Gleichungssystemen als elementare Operation angesehen wird, werden die Transpositionsmatrizen oft als weiterer Typ von Elementarmatrizen zugelassen.