Permutationsmatrix

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Permutationsmatrix der Permutation (3,5,8,1,7,4,2,6). Die roten Punkte zeigen die Einseinträge an.

Eine Permutationsmatrix oder auch Vertauschungsmatrix ist in der Mathematik eine Matrix, bei der in jeder Zeile und in jeder Spalte genau ein Eintrag eins ist und alle anderen Einträge null sind. Jede Permutationsmatrix entspricht genau einer Permutation einer endlichen Menge von Zahlen. Wird eine Permutationsmatrix mit einem Vektor multipliziert, dann werden die Komponenten des Vektors entsprechend dieser Permutation vertauscht. Permutationsmatrizen sind orthogonal, doppelt-stochastisch und ganzzahlig unimodular. Die Menge der Permutationsmatrizen fester Größe bildet mit der Matrizenmultiplikation eine Untergruppe der allgemeinen linearen Gruppe. Permutationsmatrizen werden unter anderem in der linearen Algebra, der Kombinatorik und der Kryptographie verwendet.

Definition[Bearbeiten]

Eine Permutationsmatrix ist eine quadratische Matrix, bei der genau ein Eintrag pro Zeile und Spalte gleich 1 ist und alle anderen Einträge gleich 0 sind.[1] Hierbei sind im Allgemeinen 1 und 0 das Einselement und Nullelement eines zugrunde liegenden Rings R (in der Praxis meist die reellen Zahlen). Jede Permutationsmatrix der Größe n \times n entspricht genau einer Permutation (\pi(1), \ldots , \pi(n)) der Zahlen von 1 bis n. Die zu einer Permutation \pi \in S_n zugehörige Permutationsmatrix

P_\pi = ( p_{ij} ) \in R^{n \times n}

hat dann als Einträge

p_{ij} = \begin{cases} 1, & \text{falls } \pi(i)=j \\ 0, & \text{sonst.} \end{cases}

Werden durch die Permutation \pi genau zwei Zahlen miteinander vertauscht, so bezeichnet man P_\pi auch als Vertauschungsmatrix. Ist e_i der i-te kanonische Einheitsvektor als Zeilenvektor, dann lässt sich die Permutationsmatrix P_\pi auch durch

P_\pi = \begin{pmatrix} e_{\pi(1)} \\ \vdots \\ e_{\pi(n)} \end{pmatrix}

darstellen. Gelegentlich findet sich allerdings in der Literatur auch die umgekehrte Variante, bei der die Einheitsvektoren spaltenweise zusammengesetzt werden, wodurch die Permutationsmatrizen entsprechend transponiert werden.[2] Im Folgenden wird jedoch die gebräuchlichere erste Variante verwendet.

Beispiel[Bearbeiten]

Die zu der Permutation

\pi =
\begin{pmatrix} 
1 & 2 & 3 & 4 & 5 \\
4 & 2 & 1 & 5 & 3 \\
\end{pmatrix} \in S_5

zugehörige Permutationsmatrix ist

P_{\pi} =
\begin{pmatrix} e_4 \\ e_2 \\ e_1 \\ e_5 \\ e_3 \end{pmatrix} =
\begin{pmatrix} 
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 
\end{pmatrix} \in R^{5 \times 5}
.

Nachdem durch die Permutation \pi beispielsweise die Zahl 5 auf die Zahl 3 abgebildet wird, findet sich in der fünften Zeile von P_\pi die 1 in der dritten Spalte.

Anwendung[Bearbeiten]

Wird eine Permutationsmatrix mit einem gegebenen Spaltenvektor v = (v_1, \ldots , v_n)^T multipliziert, dann ergibt das Matrix-Vektor-Produkt

P_{\pi} \cdot v = \begin{pmatrix} e_{\pi(1)} \\ \vdots \\ e_{\pi(n)} \end{pmatrix} \cdot \begin{pmatrix} v_1 \\ \vdots \\ v_n \end{pmatrix} = \begin{pmatrix} v_{\pi(1)} \\ \vdots \\ v_{\pi(n)} \end{pmatrix}

einen neuen Spaltenvektor, dessen Einträge entsprechend der Permutation \pi vertauscht wurden. Ist beispielsweise v = (v_1,v_2,v_3,v_4,v_5)^T, dann ergibt das Matrix-Vektor-Produkt mit der obigen Beispiel-Permutationsmatrix den Spaltenvektor

P_\pi \cdot v =
\begin{pmatrix} 
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 
\end{pmatrix} \cdot
\begin{pmatrix} v_1 \\ v_2 \\ v_3 \\ v_4 \\ v_5 \end{pmatrix} =
\begin{pmatrix} v_4 \\ v_2 \\ v_1 \\ v_5 \\ v_3 \end{pmatrix}.

Analog dazu ergibt die Multiplikation eines Zeilenvektors mit einer Permutationsmatrix wieder einen Zeilenvektor mit entsprechend vertauschten Elementen. Wird eine Permutationsmatrix von links mit einer anderen Matrix multipliziert, dann werden die Zeilen der Matrix gemäß der Permutation vertauscht. Wird eine Permutationsmatrix von rechts mit einer Matrix multipliziert, werden stattdessen die Spalten der Matrix vertauscht.

Eigenschaften[Bearbeiten]

Gruppentafel der 3! = 6 Permutationen einer 3-elementigen Menge. Das Produkt zweier Permutationsmatrizen ist wieder eine Permutationsmatrix.
Positionen der 6 Matrizen in obiger Gruppentafel. Nur die Einheitsmatrizen liegen symmetrisch zur Hauptdiagonalen, also ist die symmetrische Gruppe nicht abelsch. Das sind auch Permutationsmatrizen, daher die eingezeichneten Zykel.

Inverse[Bearbeiten]

Permutationsmatrizen sind orthogonale Matrizen, daher existiert eine eindeutige Inverse, nämlich die Permutationsmatrix der inversen Permutation, und es gilt:

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

Permutationsmatrizen haben demnach immer vollen Rang n.

Produkt[Bearbeiten]

Die Permutationsmatrix der Hintereinanderausführung zweier Permutationen \pi, \sigma \in S_n ergibt sich zu

P_{\pi \circ \sigma} = P_{\sigma} \cdot P_{\pi}.

Die Menge der Permutationsmatrizen bildet damit zusammen mit der Matrizenmultiplikation eine Gruppe, und zwar eine Untergruppe der allgemeinen linearen Gruppe \mathrm{GL}(n,R). Jede Permutationsmatrix kann dabei als Produkt von elementaren zeilenvertauschenden Matrizen dargestellt werden.

Determinante[Bearbeiten]

Die Determinante einer Permutationsmatrix ist entweder +1 oder -1 und entspricht dem Vorzeichen der zugehörigen Permutation:

\det (P_\pi) = \operatorname{sgn}(\pi).

Eine Permutationsmatrix über den ganzen Zahlen ist damit eine ganzzahlige unimodulare Matrix. Die Spur einer Permutationsmatrix entspricht der Anzahl der Fixpunkte der Permutation.

Normen[Bearbeiten]

Für die Spalten- und Zeilensummennorm einer Permutationsmatrix erhält man

\| P_\pi \|_1 = \| P_\pi \|_\infty = 1.

Eine Permutionsmatrix ist damit eine doppelt-stochastische Matrix. 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[Bearbeiten]

Verwendung[Bearbeiten]

Solid white.svg a b c d e f g h Solid white.svg
8 a8 b8 c8 d8 e8 f8 g8 h8 8
7 a7 b7 c7 d7 e7 f7 g7 h7 7
6 a6 b6 c6 d6 e6 f6 g6 h6 6
5 a5 b5 c5 d5 e5 f5 g5 h5 5
4 a4 b4 c4 d4 e4 f4 g4 h4 4
3 a3 b3 c3 d3 e3 f3 g3 h3 3
2 a2 b2 c2 d2 e2 f2 g2 h2 2
1 a1 b1 c1 d1 e1 f1 g1 h1 1
a b c d e f g h
Acht sich wechselseitig nicht angreifende Türme auf einem Schachbrett

Permutationsmatrizen werden unter anderem verwendet:

In der Schachmathematik bilden die Permutationsmatrizen gerade die Lösungen des Problems, n Türme auf ein Schachbrett der Größe n \times n so zu verteilen, dass sich keine Türme gegenseitig angreifen. Schwieriger zu lösen ist das Damenproblem, bei dem die Türme durch Damen ersetzt werden und dessen Lösungen ebenfalls Permutationsmatrizen sind.

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1.  Jörg Liesen, Volker Mehrmann: Lineare Algebra. Springer, 2011, S. 45.
  2.  Siegfried Bosch: Lineare Algebra. Springer, 2006, S. 275.

Weblinks[Bearbeiten]