www.wikidata.de-de.nina.az

Vorzeichenbehaftete Permutationsmatrix Eine vorzeichenbehaftete Permutationsmatrix ist in der Mathematik eine quadratisc

Vorzeichenbehaftete Permutationsmatrix

Eine vorzeichenbehaftete Permutationsmatrix ist in der Mathematik eine quadratische Matrix, bei der in jeder Zeile und jeder Spalte genau ein Eintrag plus oder minus eins ist und alle übrigen Einträge null sind. Vorzeichenbehaftete Permutationsmatrizen stellen damit eine Verallgemeinerung gewöhnlicher Permutationsmatrizen dar und sind ein Spezialfall monomialer Matrizen. Sie sind genau die ganzzahligen orthogonalen Matrizen. Die Gruppe der vorzeichenbehafteten Permutationsmatrizen ist isomorph zur Hyperoktaedergruppe, der Symmetriegruppe eines Hyperwürfels oder Kreuzpolytops.

Definition Bearbeiten

Eine vorzeichenbehaftete Permutationsmatrix ist eine quadratische Matrix, bei der genau ein Eintrag pro Zeile und Spalte oder ist und alle anderen Einträge sind. Hierbei sind im Allgemeinen und das Einselement und Nullelement eines zugrunde liegenden Rings . Jede vorzeichenbehaftete Permutationsmatrix lässt sich als Produkt

aus einer normalen Permutationsmatrix und einer Diagonalmatrix mit Einträgen oder auf der Hauptdiagonalen darstellen. Die beiden Darstellungen sind dabei äquivalent: in der ersten Darstellung entsprechen die Diagonaleinträge von jeweils den Spalteneinträgen ungleich null von , in der zweiten Darstellung jeweils den Zeileneinträgen ungleich null; die beiden Permutationsmatrizen stimmen überein.

Beispiel Bearbeiten

Ein Beispiel für eine vorzeichenbehaftete Permutationsmatrix der Größe ist

denn es gilt

Eigenschaften Bearbeiten

Anzahl Bearbeiten

Die Anzahl verschiedener vorzeichenbehafteter Permutationsmatrizen der Größe ist

wobei die Doppelfakultät bezeichnet. Es gibt nämlich verschiedene Permutationsmatrizen der Größe und mögliche Wahlen für die Vorzeichen.

Produkt Bearbeiten

Das Produkt zweier vorzeichenbehafteter Permutationsmatrizen ist wieder eine vorzeichenbehaftete Permutationsmatrix, denn es gilt

wobei die Diagonalmatrix ist, die aus durch Zeilen- und Spaltenvertauschungen gemäß der zugrunde liegenden Permutation entsteht.

Inverse Bearbeiten

Eine vorzeichenbehaftete Permutationsmatrix ist stets invertierbar. Die Menge der vorzeichenbehafteten Permutationen bildet daher mit der Matrizenmultiplikation als Verknüpfung eine Untergruppe der allgemeinen linearen Gruppe , spezieller eine Untergruppe der monomialen Gruppe . Die Inverse einer vorzeichenbehafteten Permutationsmatrix ergibt sich dabei zu

und ist demnach gleich ihrer Transponierten. Reelle vorzeichenbehaftete Permutationsmatrizen sind daher orthogonal und ihre Matrizengruppe ist eine Untergruppe der orthogonalen Gruppe . Diese Untergruppe besteht genau aus den ganzzahligen orthogonalen Matrizen.

Potenzen Bearbeiten

Ganzzahlige Potenzen vorzeichenbehafteter Permutationsmatrizen sind wieder vorzeichenbehaftete Permutationsmatrizen. Für jede vorzeichenbehaftete 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. Stellt die zu zugehörige Permutation einen einzelnen Zyklus der Länge dar und bezeichnet die Anzahl der Einträge mit Wert in , dann gilt für die Ordnung von

Im Allgemeinfall zerfällt die Permutation in disjunkte Zyklen und die Ordnung von ist dann gleich dem kleinsten gemeinsamen Vielfachen der Ordnungen der zugehörigen Untermatrizen.

Determinante Bearbeiten

Die Determinante einer vorzeichenbehafteten Permutationsmatrix mit Einträgen aus einem kommutativen Ring ergibt sich nach dem Determinantenproduktsatz zu

wobei das Vorzeichen der zu zugehörigen Permutation ist und die Anzahl der Einträge mit Wert in ist. Vorzeichenbehaftete Permutationsmatrizen sind demnach unimodular, denn ihre Determinante kann nur die Werte oder annehmen.

Verwendung Bearbeiten

Vorzeichenbehaftete Permutationen Bearbeiten

Jede vorzeichenbehaftete Permutationsmatrix entspricht genau einer vorzeichenbehafteten Permutation, also einer Permutation der Menge , für die für gilt. Die Einträge der zu der Permutation zugehörigen Matrix sind dabei gegeben als

Die Gruppe der vorzeichenbehafteten Permutationsmatrizen der Größe ist isomorph zur Hyperoktaedergruppe, der Symmetriegruppe eines Hyperwürfels oder Kreuzpolytops im -dimensionalen Raum.

Hadamard-Matrizen Bearbeiten

Eine Hadamard-Matrix ist eine quadratische Matrix mit Einträgen , bei der alle Zeilen und alle Spalten zueinander orthogonal sind. Das Produkt einer Hadamard-Matrix mit einer vorzeichenbehafteten Permutationsmatrix ergibt wieder eine Hadamard-Matrix. Zwei Hadamard-Matrizen und sind dabei äquivalent, wenn es vorzeichenbehaftete Permutationsmatrizen und gibt, sodass

gilt. Die Äquivalenzklasse einer Hadamard-Matrix ist daher der Orbit einer Gruppenoperation, bei der die Transformationsgruppe das direkte Produkt der Gruppe der vorzeichenbehafteten Permutationen mit sich selbst ist.

Literatur Bearbeiten

  • Petteri Kaski, Patric R.J. Östergård: Classification Algorithms for Codes and Designs. Springer, 2006, ISBN 3-540-28991-7.
  • Michael Field: Lectures on Bifurcations, Dynamics and Symmetry. CRC Press, 1996, ISBN 0-582-30346-X.

Einzelnachweise Bearbeiten

  1. ↑ Petteri Kaski, Patric R.J. Östergård: Classification Algorithms for Codes and Designs. Springer, 2006, ISBN 3-540-28991-7, S. 63.
  2. Michael Field: Lectures on Bifurcations, Dynamics and Symmetry. CRC Press, 1996, ISBN 0-582-30346-X, S. 12–13.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Eine vorzeichenbehaftete Permutationsmatrix ist in der Mathematik eine quadratische Matrix bei der in jeder Zeile und jeder Spalte genau ein Eintrag plus oder minus eins ist und alle ubrigen Eintrage null sind Vorzeichenbehaftete Permutationsmatrizen stellen damit eine Verallgemeinerung gewohnlicher Permutationsmatrizen dar und sind ein Spezialfall monomialer Matrizen Sie sind genau die ganzzahligen orthogonalen Matrizen Die Gruppe der vorzeichenbehafteten Permutationsmatrizen ist isomorph zur Hyperoktaedergruppe der Symmetriegruppe eines Hyperwurfels oder Kreuzpolytops Inhaltsverzeichnis 1 Definition 2 Beispiel 3 Eigenschaften 3 1 Anzahl 3 2 Produkt 3 3 Inverse 3 4 Potenzen 3 5 Determinante 4 Verwendung 4 1 Vorzeichenbehaftete Permutationen 4 2 Hadamard Matrizen 5 Literatur 6 EinzelnachweiseDefinition BearbeitenEine vorzeichenbehaftete Permutationsmatrix ist eine quadratische Matrix bei der genau ein Eintrag pro Zeile und Spalte 1 displaystyle 1 nbsp oder 1 displaystyle 1 nbsp ist und alle anderen Eintrage 0 displaystyle 0 nbsp sind Hierbei sind im Allgemeinen 1 displaystyle 1 nbsp und 0 displaystyle 0 nbsp das Einselement und Nullelement eines zugrunde liegenden Rings R displaystyle R nbsp Jede vorzeichenbehaftete Permutationsmatrix S R n n displaystyle S in R n times n nbsp lasst sich als Produkt S P D displaystyle S P cdot D nbsp bzw S D P displaystyle S D cdot P nbsp aus einer normalen Permutationsmatrix P R n n displaystyle P in R n times n nbsp und einer Diagonalmatrix D R n n displaystyle D in R n times n nbsp mit Eintragen 1 displaystyle 1 nbsp oder 1 displaystyle 1 nbsp auf der Hauptdiagonalen darstellen 1 Die beiden Darstellungen sind dabei aquivalent in der ersten Darstellung entsprechen die Diagonaleintrage von D displaystyle D nbsp jeweils den Spalteneintragen ungleich null von S displaystyle S nbsp in der zweiten Darstellung jeweils den Zeileneintragen ungleich null die beiden Permutationsmatrizen stimmen uberein Beispiel BearbeitenEin Beispiel fur eine vorzeichenbehaftete Permutationsmatrix der Grosse 3 3 displaystyle 3 times 3 nbsp ist S 0 1 0 0 0 1 1 0 0 displaystyle S begin pmatrix 0 amp 1 amp 0 0 amp 0 amp 1 1 amp 0 amp 0 end pmatrix nbsp denn es gilt S 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 displaystyle S begin pmatrix 0 amp 1 amp 0 0 amp 0 amp 1 1 amp 0 amp 0 end pmatrix cdot begin pmatrix 1 amp 0 amp 0 0 amp 1 amp 0 0 amp 0 amp 1 end pmatrix begin pmatrix 1 amp 0 amp 0 0 amp 1 amp 0 0 amp 0 amp 1 end pmatrix cdot begin pmatrix 0 amp 1 amp 0 0 amp 0 amp 1 1 amp 0 amp 0 end pmatrix nbsp Eigenschaften BearbeitenAnzahl Bearbeiten Die Anzahl verschiedener vorzeichenbehafteter Permutationsmatrizen der Grosse n n displaystyle n times n nbsp ist 2 n n 2 n 2 4 2 n displaystyle 2 n cdot n 2n 2 cdot 4 cdot ldots cdot 2n nbsp wobei displaystyle nbsp die Doppelfakultat bezeichnet Es gibt namlich n displaystyle n nbsp verschiedene Permutationsmatrizen der Grosse n n displaystyle n times n nbsp und 2 n displaystyle 2 n nbsp mogliche Wahlen fur die n displaystyle n nbsp Vorzeichen Produkt Bearbeiten Das Produkt zweier vorzeichenbehafteter Permutationsmatrizen S S R n n displaystyle S S in R n times n nbsp ist wieder eine vorzeichenbehaftete Permutationsmatrix denn es gilt S S P D P D P P D D displaystyle S cdot S P cdot D cdot P cdot D P cdot P cdot bar D cdot D nbsp wobei D P T D P displaystyle bar D P T cdot D cdot P nbsp die Diagonalmatrix ist die aus D displaystyle D nbsp durch Zeilen und Spaltenvertauschungen gemass der P displaystyle P nbsp zugrunde liegenden Permutation entsteht 1 Inverse Bearbeiten Eine vorzeichenbehaftete Permutationsmatrix S R n n displaystyle S in R n times n nbsp ist stets invertierbar Die Menge der vorzeichenbehafteten Permutationen bildet daher mit der Matrizenmultiplikation als Verknupfung eine Untergruppe der allgemeinen linearen Gruppe GL n R displaystyle operatorname GL n R nbsp spezieller eine Untergruppe der monomialen Gruppe M n R displaystyle operatorname M n R nbsp Die Inverse einer vorzeichenbehafteten Permutationsmatrix ergibt sich dabei zu S 1 P D 1 D 1 P 1 D T P T P D T S T displaystyle S 1 P cdot D 1 D 1 cdot P 1 D T cdot P T P cdot D T S T nbsp und ist demnach gleich ihrer Transponierten Reelle vorzeichenbehaftete Permutationsmatrizen sind daher orthogonal und ihre Matrizengruppe ist eine Untergruppe der orthogonalen Gruppe O n displaystyle operatorname O n nbsp Diese Untergruppe besteht genau aus den ganzzahligen orthogonalen Matrizen Potenzen Bearbeiten Ganzzahlige Potenzen vorzeichenbehafteter Permutationsmatrizen sind wieder vorzeichenbehaftete Permutationsmatrizen Fur jede vorzeichenbehaftete Permutationsmatrix S R n n displaystyle S in R n times n nbsp gibt es dabei eine Potenz k displaystyle k nbsp sodass S k I displaystyle S k I nbsp ergibt wobei I displaystyle I nbsp die Einheitsmatrix ist Das kleinste positive k displaystyle k nbsp mit dieser Eigenschaft ist gleich der Ordnung von S displaystyle S nbsp in der allgemeinen linearen Gruppe Stellt die zu P displaystyle P nbsp zugehorige Permutation p displaystyle pi nbsp einen einzelnen Zyklus der Lange n displaystyle n nbsp dar und bezeichnet m displaystyle m nbsp die Anzahl der Eintrage mit Wert 1 displaystyle 1 nbsp in D displaystyle D nbsp dann gilt fur die Ordnung von S displaystyle S nbsp ord S n falls m gerade ist 2 n falls m ungerade ist displaystyle operatorname ord S begin cases n amp text falls m text gerade ist 2n amp text falls m text ungerade ist end cases nbsp Im Allgemeinfall zerfallt die Permutation p displaystyle pi nbsp in disjunkte Zyklen und die Ordnung von S displaystyle S nbsp ist dann gleich dem kleinsten gemeinsamen Vielfachen der Ordnungen der zugehorigen Untermatrizen Determinante Bearbeiten Die Determinante einer vorzeichenbehafteten Permutationsmatrix S R n n displaystyle S in R n times n nbsp mit Eintragen aus einem kommutativen Ring R displaystyle R nbsp ergibt sich nach dem Determinantenproduktsatz zu det S det P det D sgn p 1 m displaystyle det S det P cdot det D operatorname sgn pi cdot 1 m nbsp wobei sgn p displaystyle operatorname sgn pi nbsp das Vorzeichen der zu P displaystyle P nbsp zugehorigen Permutation p displaystyle pi nbsp ist und m displaystyle m nbsp die Anzahl der Eintrage mit Wert 1 displaystyle 1 nbsp in D displaystyle D nbsp ist Vorzeichenbehaftete Permutationsmatrizen sind demnach unimodular denn ihre Determinante kann nur die Werte 1 displaystyle 1 nbsp oder 1 displaystyle 1 nbsp annehmen Verwendung BearbeitenVorzeichenbehaftete Permutationen Bearbeiten Jede vorzeichenbehaftete Permutationsmatrix S R n n displaystyle S in R n times n nbsp entspricht genau einer vorzeichenbehafteten Permutation also einer Permutation p displaystyle pi nbsp der Menge n n displaystyle n ldots n nbsp fur die p i p i displaystyle pi i pi i nbsp fur i 0 n displaystyle i 0 ldots n nbsp gilt Die Eintrage der zu der Permutation p displaystyle pi nbsp zugehorigen Matrix S p s i j displaystyle S pi s ij nbsp sind dabei gegeben als s i j 1 falls p i j 1 falls p i j 0 sonst displaystyle s ij begin cases 1 amp text falls pi i j 1 amp text falls pi i j 0 amp text sonst end cases nbsp Die Gruppe der vorzeichenbehafteten Permutationsmatrizen der Grosse n n displaystyle n times n nbsp ist isomorph zur Hyperoktaedergruppe der Symmetriegruppe eines Hyperwurfels oder Kreuzpolytops im n displaystyle n nbsp dimensionalen Raum 2 Hadamard Matrizen Bearbeiten Eine Hadamard Matrix ist eine quadratische Matrix mit Eintragen 1 displaystyle pm 1 nbsp bei der alle Zeilen und alle Spalten zueinander orthogonal sind Das Produkt einer Hadamard Matrix mit einer vorzeichenbehafteten Permutationsmatrix ergibt wieder eine Hadamard Matrix Zwei Hadamard Matrizen H 1 displaystyle H 1 nbsp und H 2 displaystyle H 2 nbsp sind dabei aquivalent wenn es vorzeichenbehaftete Permutationsmatrizen S displaystyle S nbsp und T displaystyle T nbsp gibt sodass H 2 S H 1 T 1 displaystyle H 2 S cdot H 1 cdot T 1 nbsp gilt Die Aquivalenzklasse einer Hadamard Matrix ist daher der Orbit einer Gruppenoperation bei der die Transformationsgruppe das direkte Produkt der Gruppe der vorzeichenbehafteten Permutationen mit sich selbst ist 1 Literatur BearbeitenPetteri Kaski Patric R J Ostergard Classification Algorithms for Codes and Designs Springer 2006 ISBN 3 540 28991 7 Michael Field Lectures on Bifurcations Dynamics and Symmetry CRC Press 1996 ISBN 0 582 30346 X Einzelnachweise Bearbeiten a b c Petteri Kaski Patric R J Ostergard Classification Algorithms for Codes and Designs Springer 2006 ISBN 3 540 28991 7 S 63 Michael Field Lectures on Bifurcations Dynamics and Symmetry CRC Press 1996 ISBN 0 582 30346 X S 12 13 Abgerufen von https de wikipedia org w index php title Vorzeichenbehaftete Permutationsmatrix amp oldid 197656169