Permutationsmatrix

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.

DefinitionBearbeiten

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

 

hat dann als Einträge

 

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

 

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.

BeispielBearbeiten

Die zu der Permutation

 

zugehörige Permutationsmatrix ist

 .

Nachdem durch die Permutation   beispielsweise die Zahl   auf die Zahl   abgebildet wird, findet sich in der fünften Zeile von   die   in der dritten Spalte.

AnwendungBearbeiten

Wird eine Permutationsmatrix mit einem gegebenen Spaltenvektor   multipliziert, dann ergibt das Matrix-Vektor-Produkt

 

einen neuen Spaltenvektor, dessen Einträge entsprechend der Permutation   vertauscht wurden. Ist beispielsweise  , dann ergibt das Matrix-Vektor-Produkt mit der obigen Beispiel-Permutationsmatrix den Spaltenvektor

 

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   vertauschten Elementen, also

 .

Für obiges Beispiel erhält man somit

 

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

EigenschaftenBearbeiten

 
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.

InverseBearbeiten

Permutationsmatrizen sind stets invertierbar, wobei die Inverse einer Permutationsmatrix gerade ihre Transponierte ist. Die transponierte Matrix ist dabei die Permutationsmatrix der inversen Permutation, es gilt also

 .

Reelle Permutationsmatrizen sind demnach stets orthogonal und haben vollen Rang  .

ProduktBearbeiten

Das Produkt zweier Permutationsmatrizen ist wieder eine Permutationsmatrix, die der Hintereinanderausführung der zugehörigen Permutationen entspricht. Die Permutationsmatrix der Hintereinanderausführung zweier Permutationen   ergibt sich zu

 .

Die Abbildung   stellt somit einen Antihomomorphismus dar. Die Menge der Permutationsmatrizen bildet zusammen mit der Matrizenmultiplikation eine Gruppe, und zwar eine Untergruppe der allgemeinen linearen Gruppe  . Jede Permutationsmatrix kann dabei als Produkt von elementaren zeilenvertauschenden Matrizen dargestellt werden.

PotenzenBearbeiten

Ganzzahlige Potenzen von Permutationsmatrizen sind wieder Permutationsmatrizen. Für jede Permutationsmatrix   gibt es dabei eine Potenz  , sodass

 

ergibt, wobei   die Einheitsmatrix ist. Das kleinste positive   mit dieser Eigenschaft ist gleich der Ordnung von   in der allgemeinen linearen Gruppe. Diese Ordnung ist gleich dem kleinsten gemeinsamen Vielfachen der Längen der disjunkten Zyklen von  .

DeterminanteBearbeiten

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

 .

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

EigenwerteBearbeiten

Die Eigenwerte einer reellen Permutationsmatrix sind nicht notwendigerweise alle reell, sie liegen aber auf dem komplexen Einheitskreis. Sind   die Längen der Zyklen einer Permutation  , dann sind die Eigenwerte der zugehörigen Permutationsmatrix   die komplexen Einheitswurzeln

 

für   und  . Eine reelle Permutationsmatrix besitzt demnach genau dann den Eigenwert  , wobei   und   teilerfremd seien, wenn die zugrunde liegende Permutation mindestens einen Zyklus aufweist, dessen Länge durch   teilbar ist. Die Vielfachheit dieses Eigenwerts entspricht dann der Anzahl solcher Zyklen. Eine reelle Permutationsmatrix besitzt daher stets den Eigenwert   mit Vielfachheit gleich der Gesamtzahl der Zyklen   der zugrunde liegenden Permutation.

NormenBearbeiten

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

 .

Für die Spalten- und Zeilensummennorm einer reellen Permutationsmatrix ergibt sich ebenfalls

 .

Eine reelle 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älleBearbeiten

VerwendungBearbeiten

  a b c d e f g h  
8                 8
7                 7
6                 6
5                 5
4                 4
3                 3
2                 2
1                 1
  a b c d e f g h  

Acht sich wechselseitig nicht angreifende Türme auf einem Schachbrett

Vorlage:Schachbrett/Wartung/Alt

Permutationsmatrizen werden unter anderem verwendet:

In der Schachmathematik bilden die Permutationsmatrizen gerade die Lösungen des Problems,   Türme auf ein Schachbrett der Größe   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, die auch diagonal angreifen können. Die Lösungen des Damenproblems sind ebenfalls Permutationsmatrizen.

VerallgemeinerungBearbeiten

Eine verallgemeinerte Permutationsmatrix oder monomiale Matrix ist eine quadratische Matrix  , bei der genau ein Eintrag pro Zeile und Spalte ungleich   ist. Monomiale Matrizen haben die Darstellung

 ,

wobei   eine gewöhnliche Permutationsmatrix und   eine Diagonalmatrix ist, deren Diagonaleinträge alle ungleich   sind. Die regulären monomialen Matrizen bilden mit der Matrizenmultiplikation als Verknüpfung die monomiale Gruppe  , eine weitere Untergruppe der allgemeinen linearen Gruppe  . Spezielle monomiale Matrizen sind vorzeichenbehaftete Permutationsmatrizen, bei denen in jeder Zeile und jeder Spalte genau ein Eintrag   oder   ist und alle übrigen Einträge   sind

Siehe auchBearbeiten

LiteraturBearbeiten

EinzelnachweiseBearbeiten

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

WeblinksBearbeiten