imported>FerdiBf: Änderung 262213184 von ~2025-39146-93 rückgängig gemacht; Die Änderung war leider falsch. Ich mache dazu eine Diskussion "(Anti)homomorphismus" auf.

2025-12-22T09:23:04Z

Änderung 262213184 von ~2025-39146-93 rückgängig gemacht; Die Änderung war leider falsch. Ich mache dazu eine Diskussion "(Anti)homomorphismus" auf.

Neue Seite

[[Datei:HuitRois.png|miniatur|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 (Mathematik)|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 [[Endliche Menge|endlichen Menge]] von Zahlen. Wird eine Permutationsmatrix mit einem [[Vektor]] multipliziert, dann werden die Komponenten des Vektors entsprechend dieser Permutation vertauscht. Permutationsmatrizen sind [[Orthogonale Matrix|orthogonal]], [[Doppelt-stochastische Matrix|doppelt-stochastisch]] und [[Ganzzahlige unimodulare Matrix|ganzzahlig unimodular]]. Die Menge der Permutationsmatrizen fester Größe bildet mit der [[Matrizenmultiplikation]] eine zur [[symmetrische Gruppe]] isomorphe [[Untergruppe]] der [[Allgemeine lineare Gruppe|allgemeinen linearen Gruppe]]. Permutationsmatrizen werden unter anderem in der [[Lineare Algebra|linearen Algebra]], der [[Kombinatorik]] und der [[Kryptographie]] verwendet.

== Definition ==

Eine ''Permutationsmatrix'' ist eine [[quadratische Matrix]], bei der genau ein Eintrag pro Zeile und Spalte gleich <math>1</math> ist und alle anderen Einträge gleich <math>0</math> sind.<ref>{{Literatur|Autor=Jörg Liesen, Volker Mehrmann|Titel=Lineare Algebra|Verlag=Springer|Jahr=2011|Seiten=45}}</ref> Hierbei sind im Allgemeinen <math>1</math> und <math>0</math> das [[Einselement]] und [[Nullelement]] eines zugrunde liegenden [[Ring (Algebra)|Rings]] <math>R</math>. Jede Permutationsmatrix der Größe <math>n \times n</math> entspricht genau einer [[Permutation]] <math>(\pi(1), \ldots , \pi(n))</math> der Zahlen von <math>1</math> bis <math>n</math>. Die zu einer Permutation <math>\pi \in S_n</math> zugehörige Permutationsmatrix

:<math>P_\pi = ( p_{ij} ) \in R^{n \times n}</math>

hat dann als Einträge

:<math>p_{ij} = \delta_{\pi(i),j} = \begin{cases} 1, & \text{falls } \pi(i)=j \\ 0, & \text{sonst,} \end{cases}</math>

wobei <math>\delta_{ij}</math> das [[Kronecker-Delta]] bezeichne. Werden durch die Permutation <math>\pi</math> genau zwei Zahlen miteinander [[Vertauschung|vertauscht]], so bezeichnet man <math>P_\pi</math> auch als Vertauschungsmatrix. Ist <math>e_i</math> der <math>i</math>-te kanonische [[Einheitsvektor]] als Zeilenvektor, dann lässt sich die Permutationsmatrix <math>P_\pi</math> auch durch

:<math>P_\pi = \begin{pmatrix} e_{\pi(1)} \\ \vdots \\ e_{\pi(n)} \end{pmatrix}</math>

darstellen. Gelegentlich findet sich allerdings in der Literatur auch die umgekehrte Variante, bei der die Einheitsvektoren spaltenweise zusammengesetzt werden, wodurch die Permutationsmatrizen entsprechend [[Transponierte Matrix|transponiert]] werden.<ref>{{Literatur|Autor=[[Siegfried Bosch]]|Titel=Lineare Algebra|Verlag=Springer|Jahr=2006|Seiten=275}}</ref> Im Folgenden wird jedoch die gebräuchlichere erste Variante verwendet.

== Beispiel ==

Die zu der Permutation

:<math>\pi =
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
4 & 2 & 1 & 5 & 3 \\
\end{pmatrix} \in S_5
</math>

zugehörige Permutationsmatrix ist

:<math>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}
</math>.

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

== Anwendung ==

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

:<math>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}</math>

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

:<math>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}.
</math>

Wird eine Matrix von links mit einer Permutationsmatrix multipliziert, dann werden die Zeilen der Matrix gemäß der Permutation vertauscht. Umgekehrt ergibt die Multiplikation eines Zeilenvektors mit der transponierten Permutationsmatrix wieder einen Zeilenvektor mit entsprechend der Permutation <math>\pi</math> vertauschten Elementen, also

:<math>v^T \cdot P_\pi^T = \begin{pmatrix} v_1 & \ldots & v_n \end{pmatrix} \cdot \begin{pmatrix} e_{\pi(1)}^T & \ldots & e_{\pi(n)}^T \end{pmatrix} = \begin{pmatrix} v_{\pi(1)} & \ldots & v_{\pi(n)} \end{pmatrix}</math>.

Für obiges Beispiel erhält man somit

:<math>v^T \cdot P_\pi^T =
\begin{pmatrix} v_1 & v_2 & v_3 & v_4 & v_5 \end{pmatrix} \cdot
\begin{pmatrix}
0 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0
\end{pmatrix} =
\begin{pmatrix} v_4 & v_2 & v_1 & v_5 & v_3 \end{pmatrix}.
</math>

Wird eine Matrix von rechts mit der transponierten Permutationsmatrix multipliziert, werden entsprechend die Spalten der Matrix gemäß der Permutation vertauscht.

== Eigenschaften ==
[[Datei:Symmetric group 3; Cayley table; matrices.svg|miniatur|Gruppentafel der 3! = 6 Permutationen einer 3-elementigen Menge. Das Produkt zweier Permutationsmatrizen ist wieder eine Permutationsmatrix.]]
[[Datei:Symmetric group 3; Cayley table; positions.svg|miniatur|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 ===

Permutationsmatrizen sind stets [[Reguläre Matrix|invertierbar]], wobei die [[inverse Matrix|Inverse]] einer Permutationsmatrix gerade ihre Transponierte ist. Die transponierte Matrix ist dabei die Permutationsmatrix der [[Inverse Permutation|inversen Permutation]], es gilt also

:<math>P_{\pi}^{-1} = P_{\pi}^{T} = P_{\pi^{-1}}</math>.

Reelle Permutationsmatrizen sind demnach stets [[Orthogonale Matrix|orthogonal]] und haben vollen [[Rang (Lineare Algebra)|Rang]] <math>n</math>.

=== Produkt ===

Das [[Matrizenmultiplikation|Produkt]] zweier Permutationsmatrizen ist wieder eine Permutationsmatrix, die der [[Komposition (Mathematik)|Hintereinanderausführung]] der zugehörigen Permutationen entspricht. Die Permutationsmatrix der Hintereinanderausführung zweier Permutationen <math>\pi, \sigma \in S_n</math> ergibt sich zu

:<math>P_{\pi \circ \sigma} = P_{\sigma}\cdot P_{\pi} </math>.

Die Abbildung <math>\pi \mapsto P_\pi</math> stellt somit einen [[Antihomomorphismus]] dar. Die Menge der Permutationsmatrizen bildet zusammen mit der Matrizenmultiplikation eine [[Gruppe (Mathematik)|Gruppe]], und zwar eine [[Untergruppe]] der [[Allgemeine lineare Gruppe|allgemeinen linearen Gruppe]] <math>\mathrm{GL}(n,R)</math>. Jede Permutationsmatrix kann dabei als Produkt von elementaren zeilenvertauschenden Matrizen dargestellt werden.

=== Potenzen ===

Ganzzahlige [[Matrixpotenz|Potenzen]] von Permutationsmatrizen sind wieder Permutationsmatrizen. Für jede Permutationsmatrix <math>P_\pi</math> gibt es dabei eine Potenz <math>k</math>, sodass

:<math>P_\pi^{k} = I</math>

ergibt, wobei <math>I</math> die [[Einheitsmatrix]] ist. Das kleinste positive <math>k</math> mit dieser Eigenschaft ist gleich der [[Elementordnung|Ordnung]] von <math>P_\pi</math> in der allgemeinen linearen Gruppe. Diese Ordnung ist gleich dem [[Kleinstes gemeinsames Vielfaches|kleinsten gemeinsamen Vielfachen]] der Längen der [[disjunkt]]en [[Zyklische Permutation|Zyklen]] von <math>\pi</math>.

=== Determinante ===

Die [[Determinante (Mathematik)|Determinante]] einer Permutationsmatrix ist entweder <math>+1</math> oder <math>-1</math> und entspricht dem [[Vorzeichen (Permutation)|Vorzeichen]] der zugehörigen Permutation:

:<math>\det (P_\pi) = \operatorname{sgn}(\pi)</math>.

Eine Permutationsmatrix über den ganzen Zahlen ist damit eine [[ganzzahlige unimodulare Matrix]]. Die [[Spur (Mathematik)|Spur]] einer ganzzahligen Permutationsmatrix entspricht der Anzahl der [[Fixpunkt (Mathematik)|Fixpunkte]] der Permutation.

Die Determinante kann mit dem folgenden Schema ermittelt werden. Dazu wird für jede Spalte der Matrix die Zeilennummer, in der die eins steht, nebeneinander in eine Tabelle geschrieben. Darunter wird für jede Zahl z der ersten Zeile die Anzahl der Zahlen geschrieben, die größer als z sind und in der Tabelle links von z stehen; diese Anzahl heißt Kennmarke. Bei der eingangs angegebenen 8×8-Permutationsmatrix ergibt sich

{| class="wikitable"
! Zeilennummer z
|4||7||1||6||2||8||5||3
|-
!Kennmarke a
|0||0||2||1||3||0||3||5
|}

Ist die Summe der Kennmarken, wie hier, eine [[gerade Zahl]], dann ist die Determinante 1, sonst −1; als Formel bei einer Permutationsmatrix der Größe <math>n\times n</math>:<ref>{{Literatur
| Autor=[[Rudolf Zurmühl|R. Zurmühl]], [[Sigurd Falk|S. Falk]]
| Titel=Matrizen und ihre Anwendungen 1
| TitelErg=Grundlagen, Für Ingenieure, Physiker und Angewandte Mathematiker
| Seiten=57
| Verlag=Springer
| Ort=Berlin u. a.
| Jahr=1997
| ISBN=3-540-61436-2}}</ref>

:<math>\mathrm{det}(P_\pi)=(-1)^\nu</math>  mit  <math>\nu=\sum_{j=1}^n \mathsf{a}_j</math>

=== Eigenwerte ===

Die [[Eigenwert]]e einer reellen Permutationsmatrix sind nicht notwendigerweise alle reell, sie liegen aber auf dem komplexen [[Einheitskreis]]. Sind <math>l_1, \ldots, l_s</math> die Längen der [[Zyklische Permutation|Zyklen]] einer Permutation <math>\pi</math>, dann sind die Eigenwerte der zugehörigen Permutationsmatrix <math>P_\pi</math> die komplexen [[Einheitswurzel]]n

:<math>\lambda_{jk} = e^{2 \pi i k/l_j}</math>

für <math>j=1, \ldots, s</math> und <math>k=1, \ldots, l_j</math>. Eine reelle Permutationsmatrix besitzt demnach genau dann den Eigenwert <math>e^{2 \pi i k/m}</math>, wobei <math>k</math> und <math>m</math> [[teilerfremd]] seien, wenn die zugrunde liegende Permutation mindestens einen Zyklus aufweist, dessen Länge durch <math>m</math> [[teilbar]] ist. Die [[Vielfachheit]] dieses Eigenwerts entspricht dann der Anzahl solcher Zyklen. Eine reelle Permutationsmatrix besitzt daher stets den Eigenwert <math>1</math> mit Vielfachheit gleich der Gesamtzahl der Zyklen <math>s</math> der zugrunde liegenden Permutation.

=== Normen ===

Da reelle Permutationsmatrizen orthogonal sind, gilt für ihre [[Spektralnorm]]

:<math>\|P_\pi\|_2 = 1</math>.

Für die [[Spaltensummennorm|Spalten-]] und [[Zeilensummennorm]] einer reellen Permutationsmatrix ergibt sich ebenfalls

:<math>\| P_\pi \|_1 = \| P_\pi \|_\infty = 1</math>.

Eine reelle Permutationsmatrix 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 ===

* Die Permutationsmatrix der [[Identische Permutation|identischen Permutation]] ist die [[Einheitsmatrix]].
* Eine Permutationsmatrix ist genau dann [[Symmetrische Matrix|symmetrisch]], wenn die zugrunde liegende Permutation [[selbstinverse Permutation|selbstinvers]] ist.
* Weist eine Permutationsmatrix eine [[Blockmatrix|Blockstruktur]] auf, dann lässt sich die zugrunde liegende Permutation als [[Summe von Permutationen]] darstellen.

== Anwendungen ==
{{Schachbrett
| Ausrichtung=rechts
| Titel=

| Z8=--/--/--/--/--/rl/--/--/
| Z7=--/--/rl/--/--/--/--/--/
| Z6=--/--/--/--/--/--/rl/--/
| Z5=--/--/--/--/rl/--/--/--/
| Z4=rl/--/--/--/--/--/--/--/
| Z3=--/--/--/rl/--/--/--/--/
| Z2=--/--/--/--/--/--/--/rl/
| Z1=--/rl/--/--/--/--/--/--/

| center =
| Beschreibung= Acht sich wechselseitig nicht angreifende Türme auf einem Schachbrett
}}
Permutationsmatrizen werden unter anderem verwendet:

* in der linearen Algebra als [[Elementarmatrix|Elementarmatrizen]] bei der [[Gauß-Elimination]] zur Lösung [[Lineares Gleichungssystem|linearer Gleichungssysteme]]
* in der Kombinatorik bei der Matrixdarstellung von [[Permutationsgruppe]]n
* in der Kryptographie als Komponenten von [[Blockverschlüsselung]]sverfahren

In der [[Schachmathematik]] bilden die Permutationsmatrizen gerade die Lösungen des Problems, <math>n</math> [[Turm (Schach)|Türme]] auf ein [[Schachbrett]] der Größe <math>n \times n</math> so zu verteilen, dass sich keine Türme gegenseitig angreifen. Schwieriger zu lösen ist das [[Damenproblem]], bei dem die Türme durch [[Dame (Schach)|Damen]] ersetzt werden, die auch diagonal angreifen können. Die Lösungen des Damenproblems sind ebenfalls Permutationsmatrizen.

== Verallgemeinerung ==
{{Hauptartikel|Monomiale Matrix}}

Eine verallgemeinerte Permutationsmatrix oder monomiale Matrix ist eine quadratische Matrix <math>G \in R^{n \times n}</math>, bei der genau ein Eintrag pro Zeile und Spalte ungleich <math>0</math> ist. Monomiale Matrizen haben die Darstellung

:<math>G = P \cdot D</math>,

wobei <math>P \in R^{n \times n}</math> eine gewöhnliche Permutationsmatrix und <math>D \in R^{n \times n}</math> eine [[Diagonalmatrix]] ist, deren Diagonaleinträge alle ungleich <math>0</math> sind. Die regulären monomialen Matrizen bilden mit der Matrizenmultiplikation als Verknüpfung die [[monomiale Gruppe]] <math>\operatorname{M}(n,R)</math>, eine weitere Untergruppe der allgemeinen linearen Gruppe <math>\operatorname{GL}(n,R)</math>. Spezielle monomiale Matrizen sind [[Vorzeichenbehaftete Permutationsmatrix|vorzeichenbehaftete Permutationsmatrizen]], bei denen in jeder Zeile und jeder Spalte genau ein Eintrag <math>+1</math> oder <math>-1</math> ist und alle übrigen Einträge <math>0</math> sind.

== Siehe auch ==
* [[Levi-Civita-Symbol]]
* [[Rothe-Diagramm]]
* [[Irreduzible Matrix]]
* [[Zyklische Matrix]]

== Literatur ==
* {{Literatur|Autor=Siegfried Bosch|Titel=Lineare Algebra|Verlag=Springer|Jahr=2006|ISBN=3-540-29884-3}}
* {{Literatur |Autor=Jörg Liesen, [[Volker Mehrmann]] |Titel=Lineare Algebra |Auflage=3 |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=2021 |ISBN=978-3-662-62741-9 |DOI=10.1007/978-3-662-62742-6}}

== Einzelnachweise ==
<references />

== Weblinks ==
* {{MathWorld|title=Permutation Matrix|id=PermutationMatrix}}
* {{PlanetMath|title=Permutation Matrix|id=permutationmatrix|author=Wkbj79}}

{{Normdaten|TYP=s|GND=4811820-5}}

[[Kategorie:Matrix]]
[[Kategorie:Permutationstheorie]]

Permutationsmatrix - Versionsgeschichte

imported>FerdiBf: Änderung 262213184 von ~2025-39146-93 rückgängig gemacht; Die Änderung war leider falsch. Ich mache dazu eine Diskussion "(Anti)homomorphismus" auf.