Permutationsmatrix

Begriff und Definition

Eine Permutationsmatrix oder Vertauschungsmatrix ist eine quadratische Matrix, in der in jeder Zeile und jeder Spalte genau eine 1 steht; alle übrigen Einträge sind 0. Dabei können 1 und 0 allgemein das Einselement und das Nullelement eines zugrunde liegenden Rings R sein. Permutationsmatrizen beschreiben Permutationen, also Umordnungen einer endlichen Menge, und vertauschen beim Multiplizieren die Einträge von Vektoren oder die Zeilen und Spalten von Matrizen. Sie werden besonders in der linearen Algebra, Kombinatorik und Kryptographie eingesetzt.

Jede Permutationsmatrix der Größe n×n gehört eindeutig zu einer Permutation π=(π(1),…,π(n)) der Zahlen 1 bis n. Für π∈S_n lautet die zugehörige Matrix P_π=(p_ij)∈R^(n×n) mit

p_ij=δ_{π(i),j}={1, falls π(i)=j; 0 sonst}.

δ_ij bezeichnet das Kronecker-Delta, das für i=j den Wert 1 und sonst 0 besitzt. Ist e_i der i-te kanonische Einheitsvektor als Zeilenvektor, so gilt

P_π=(e_{π(1)}; … ; e_{π(n)}).

Werden durch π genau zwei Zahlen vertauscht, heißt P_π auch Vertauschungsmatrix. Manche Literatur setzt die Einheitsvektoren stattdessen spaltenweise zusammen; dadurch erhält man die transponierte Variante der hier verwendeten Matrix.

Beispiel und Wirkung

Für die Permutation

π=((1,2,3,4,5),(4,2,1,5,3))∈S_5

ist

P_π=((0,0,0,1,0),(0,1,0,0,0),(1,0,0,0,0),(0,0,0,0,1),(0,0,1,0,0)).

Da π beispielsweise die Zahl 5 auf 3 abbildet, steht in der fünften Zeile die 1 in der dritten Spalte.

Für einen Spaltenvektor v=(v_1,…,v_n)^T bewirkt die Multiplikation

P_πv=(v_{π(1)},…,v_{π(n)})^T.

Im Beispiel wird daher (v_1,v_2,v_3,v_4,v_5)^T zu (v_4,v_2,v_1,v_5,v_3)^T. Wird eine Matrix von links mit P_π multipliziert, werden ihre Zeilen gemäß π vertauscht. Für einen Zeilenvektor gilt entsprechend

v^T P_π^T=(v_{π(1)},…,v_{π(n)}).

Wird eine Matrix von rechts mit P_π^T multipliziert, werden ihre Spalten gemäß π vertauscht.

Inverse, Produkt und Potenzen

Jede Permutationsmatrix ist invertierbar. Ihre Inverse ist gleich ihrer Transponierten und gehört zur inversen Permutation:

P_π^−1=P_π^T=P_{π^−1}.

Reelle Permutationsmatrizen sind deshalb orthogonal und besitzen den vollen Rang n.

Das Produkt zweier Permutationsmatrizen ist wieder eine Permutationsmatrix. Es entspricht der Hintereinanderausführung ihrer Permutationen. Für π,σ∈S_n gilt bei der verwendeten Konvention

P_{π∘σ}=P_σ·P_π.

Die Zuordnung π↦P_π ist daher ein Antihomomorphismus: Die Reihenfolge der Faktoren wird gegenüber der Verkettung der Permutationen umgekehrt. Die Permutationsmatrizen fester Größe bilden unter der Matrizenmultiplikation eine Gruppe und eine Untergruppe der allgemeinen linearen Gruppe GL(n,R). Jede Permutationsmatrix lässt sich als Produkt elementarer Matrizen darstellen, die jeweils zwei Zeilen vertauschen.

Auch jede ganzzahlige Potenz einer Permutationsmatrix ist wieder eine Permutationsmatrix. Zu jeder Matrix P_π gibt es eine positive Zahl k mit P_π^k=I, wobei I die Einheitsmatrix ist. Das kleinste solche k ist die Ordnung der Matrix. Sie entspricht dem kleinsten gemeinsamen Vielfachen der Längen der disjunkten Zyklen von π.

Determinante, Eigenwerte und Normen

Die Determinante einer Permutationsmatrix ist das Vorzeichen der zugehörigen Permutation und beträgt immer +1 oder −1:

det(P_π)=sgn(π).

Eine Permutationsmatrix über den ganzen Zahlen ist damit ganzzahlig unimodular, das heißt, sie besitzt ganzzahlige Einträge und die Determinante ±1. Ihre Spur, also die Summe der Hauptdiagonaleinträge, ist gleich der Anzahl der Fixpunkte der Permutation.

Zur Bestimmung der Determinante kann man für jede Spalte die Zeilennummer z notieren, in der die 1 steht. Die Kennmarke a_j einer Zahl z ist die Anzahl der größeren Zahlen, die links von z stehen. Mit ν=∑_{j=1}^n a_j gilt

det(P_π)=(−1)^ν.

Ist die Summe der Kennmarken gerade, ist die Determinante 1, andernfalls −1. Für die im Artikel betrachtete 8×8-Matrix lauten die Zeilennummern 4,7,1,6,2,8,5,3 und die Kennmarken 0,0,2,1,3,0,3,5. Ihre Summe ist gerade, also ist die Determinante 1.

Die Eigenwerte einer reellen Permutationsmatrix müssen nicht reell sein, liegen aber auf dem komplexen Einheitskreis. Haben die disjunkten Zyklen von π die Längen l_1,…,l_s, so sind die Eigenwerte

λ_jk=e^(2πik/l_j)

für j=1,…,s und k=1,…,l_j. Der Eigenwert e^(2πik/m), wobei k und m teilerfremd sind, tritt genau dann auf, wenn mindestens ein Zyklus eine durch m teilbare Länge besitzt. Seine Vielfachheit ist die Anzahl solcher Zyklen. Insbesondere ist 1 stets ein Eigenwert; seine Vielfachheit entspricht der Gesamtzahl s der Zyklen.

Da reelle Permutationsmatrizen orthogonal sind, gelten für Spektralnorm, Spaltensummennorm und Zeilensummennorm

‖P_π‖_2=‖P_π‖1=‖P_π‖∞=1.

Sie sind außerdem doppelt-stochastisch: Alle Einträge sind nichtnegativ, und jede Zeilen- und Spaltensumme ist 1. Nach dem Satz von Birkhoff und von Neumann ist eine quadratische Matrix genau dann doppelt-stochastisch, wenn sie eine Konvexkombination von Permutationsmatrizen ist.

Spezialfälle und Anwendungen

Die identische Permutation gehört zur Einheitsmatrix. Eine Permutationsmatrix ist genau dann symmetrisch, wenn die zugehörige Permutation selbstinvers ist, also mit ihrer eigenen Umkehrung übereinstimmt. Besitzt die Matrix eine Blockstruktur, lässt sich die zugrunde liegende Permutation als Summe von Permutationen darstellen.

Wichtige Anwendungen sind:

• In der linearen Algebra dienen Permutationsmatrizen als Elementarmatrizen bei der Gauß-Elimination zur Lösung linearer Gleichungssysteme.

• In der Kombinatorik werden sie zur Matrixdarstellung von Permutationsgruppen verwendet.

• In der Kryptographie treten sie als Komponenten von Blockverschlüsselungsverfahren auf.

In der Schachmathematik entsprechen Permutationsmatrizen genau den Lösungen des Turmproblems: n Türme werden auf einem n×n-Schachbrett so verteilt, dass keine zwei einander angreifen. Genau eine 1 je Zeile und Spalte bedeutet dabei genau einen Turm je Reihe und Linie. Beim schwierigeren Damenproblem dürfen sich die Figuren zusätzlich diagonal nicht angreifen. Auch dessen Lösungen sind Permutationsmatrizen, erfüllen aber weitere Bedingungen.

Verallgemeinerte Permutationsmatrizen

Eine verallgemeinerte Permutationsmatrix, auch monomiale Matrix genannt, ist eine quadratische Matrix G∈R^(n×n), in der pro Zeile und Spalte genau ein Eintrag ungleich 0 ist. Sie besitzt die Darstellung

G=P·D,

wobei P eine gewöhnliche Permutationsmatrix und D eine Diagonalmatrix mit ausschließlich von 0 verschiedenen Diagonaleinträgen ist. Die regulären monomialen Matrizen bilden unter der Matrizenmultiplikation die monomiale Gruppe M(n,R), eine Untergruppe von GL(n,R).

Ein wichtiger Spezialfall sind vorzeichenbehaftete Permutationsmatrizen. In jeder ihrer Zeilen und Spalten befindet sich genau ein Eintrag +1 oder −1; alle übrigen Einträge sind 0.