In der Mathematik, in der Matrixtheorie, ist eine Versetzungsmatrix eine binäre Quadratmatrix, die genau einen Zugang 1 in jeder Reihe und jeder Säule und 0s anderswohin hat. Jede solche Matrix vertritt eine spezifische Versetzung der M Elemente und, wenn verwendet, eine andere Matrix zu multiplizieren, kann diese Versetzung in den Reihen oder Säulen der anderen Matrix erzeugen.

Definition

In Anbetracht einer Versetzung π der M Elemente,

:

gegeben in der Zwei-Linien-Form durch

:

seine Versetzungsmatrix ist die M × M Matrix P, dessen Einträge der ganze 0 außer dass in der Reihe i, der Zugang &pi sind; (i) ist 1 gleich. Wir können schreiben

:

wo einen Zeilenvektoren der Länge M mit 1 in der jth Position und 0 in jeder anderen Position anzeigt.

Eigenschaften

In Anbetracht zwei Versetzungen π und σ der M Elemente und die entsprechende Versetzung matrices P und P

:

Diese etwas unglückliche Regel ist eine Folge der Definitionen der Multiplikation von Versetzungen (Zusammensetzung von Bijektionen) und von matrices, und von der Wahl, die Vektoren als Reihen der Versetzungsmatrix zu verwenden; wenn man Säulen stattdessen dann verwendet hätte, wäre das Produkt oben mit den Versetzungen in ihrer ursprünglichen Ordnung gleich gewesen.

Als Versetzung sind matrices orthogonaler matrices (d. h.,), die umgekehrte Matrix besteht und kann als geschrieben werden

:Wenn er

Zeiten multiplizieren wird, wird ein Spaltenvektor g die Reihen des Vektoren permutieren:

:

\begin {bmatrix }\

\mathbf {e} _ {\\Pi (1)} \\

\mathbf {e} _ {\\Pi (2)} \\

\vdots \\

\mathbf {e} _ {\\Pi (n) }\

\end {bmatrix }\

\begin {bmatrix }\

g_1 \\

g_2 \\

\vdots \\

g_n

\end {bmatrix }\\begin {bmatrix }\

g_ {\\Pi (1)} \\

g_ {\\Pi (2)} \\

\vdots \\

g_ {\\Pi (n) }\

\end {bmatrix}.

</Mathematik>

Jetzt die Verwendung nach der Verwendung gibt dasselbe Ergebnis wie Verwendung direkt in Übereinstimmung mit der obengenannten Multiplikationsregel: Rufen Sie mit anderen Worten

:

für alles ich, dann

:\begin {bmatrix }\

g' _ {\\Sigma (1)} \\

g' _ {\\Sigma (2)} \\

\vdots \\

g' _ {\\Sigma (n) }\

\end {bmatrix }\\begin {bmatrix }\

g_ {\\Pi (\sigma (1))} \\

g_ {\\Pi (\sigma (2))} \\

\vdots \\

g_ {\\Pi (\sigma (n)) }\

\end {bmatrix}.</Mathematik>

Das Multiplizieren eines Zeilenvektoren h Zeiten wird die Säulen des Vektoren durch das Gegenteil permutieren:

:

\begin {bmatrix} h_1 \; h_2 \; \dots \; h_n \end {bmatrix }\

\begin {bmatrix }\\mathbf {e} _ {\\Pi (1)} \\\mathbf {e} _ {\\Pi (2)} \\\vdots \\\mathbf {e} _ {\\Pi (n) }\\end {bmatrix }\

\begin {bmatrix} h_ {\\pi^ {-1} (1)} \; h_ {\\pi^ {-1} (2)} \; \dots \; h_ {\\pi^ {-1} (n)} \end {bmatrix }\

</Mathematik>

Wieder kann es das überprüft werden.

Zeichen

Lassen Sie S die symmetrische Gruppe oder Gruppe von Versetzungen, auf {1,2..., n} anzeigen. Da es n gibt! Versetzungen, es gibt n! Versetzung matrices. Durch die Formeln oben, der n &times; n Versetzung bilden matrices eine Gruppe unter der Matrixmultiplikation mit der Identitätsmatrix als das Identitätselement.

Wenn (1) die Identitätsversetzung anzeigt, dann ist P die Identitätsmatrix.

Man kann die Versetzungsmatrix einer Versetzung &sigma ansehen; als die Versetzung &sigma; der Säulen der Identitätsmatrix I, oder als die Versetzung &sigma; der Reihen von I.

Eine Versetzungsmatrix ist eine doppelt stochastische Matrix. Der Lehrsatz von Birkhoff-Von Neumann sagt, dass jede doppelt stochastische Matrix eine konvexe Kombination der Versetzung matrices derselben Ordnung ist und die Versetzung matrices die äußersten Punkte des Satzes doppelt stochastischen matrices sind. D. h. der Birkhoff polytope, der Satz doppelt stochastischen matrices, ist der konvexe Rumpf des Satzes der Versetzung matrices.

Der Produkt-PREMIERMINISTER, eine MatrixM mit einer Versetzungsmatrix P vormultiplizierend, permutiert die Reihen der M; Reihe i bewegt sich, um sich &pi lautstark zu streiten; (i). Ebenfalls permutiert Abgeordneter die Säulen der M.

Die Karte S &rarr; &sub; GL (n, Z) ist eine treue Darstellung. So, |A | = n!.

Die Spur einer Versetzungsmatrix ist die Zahl von festen Punkten der Versetzung. Wenn die Versetzung Punkte befestigt hat, so kann sie in der Zyklus-Form als &pi geschrieben werden; = (a) (a)... (a) &sigma; wo &sigma; hat keine festen Punkte, dann e, e..., e sind Eigenvektoren der Versetzungsmatrix.

Von der Gruppentheorie wissen wir, dass jede Versetzung als ein Produkt von Umstellungen geschrieben werden kann. Deshalb, jede Versetzungsmatrix P Faktoren als ein Produkt von Reihe auswechselndem elementarem matrices, jeder, Determinante &minus;1 habend. So ist die Determinante einer Versetzungsmatrix P gerade die Unterschrift der entsprechenden Versetzung.

Beispiele

Versetzung von Reihen und Säulen

Wenn eine Versetzungsmatrix P mit einer MatrixM vom links multipliziert wird, wird sie die Reihen der M permutieren (hier die Elemente eines Spaltenvektors), wenn P mit der M vom Recht multipliziert wird, wird sie die Säulen der M (hier die Elemente eines Zeilenvektoren) permutieren:

Diese Maßnahmen von matrices sind Nachdenken von denjenigen direkt oben.

Das folgt aus der Regel (vergleichen Sie Sich: Stellen Sie Um)

| }\

Versetzung von Reihen

Die Versetzungsmatrix P entsprechend der Versetzung: Ist

:\begin {bmatrix }\\mathbf {e} _ {\\Pi (1)} \\\mathbf {e} _ {\\Pi (2)} \\

\mathbf {e} _ {\\Pi (3)} \\

\mathbf {e} _ {\\Pi (4)} \\

\mathbf {e} _ {\\Pi (5)}

\end {bmatrix }\\begin {bmatrix }\

\mathbf {e} _ {1} \\

\mathbf {e} _ {4} \\

\mathbf {e} _ {2} \\

\mathbf {e} _ {5} \\

\mathbf {e} _ {3}

\end {bmatrix }\

\begin {bmatrix}

1 & 0 & 0 & 0 & 0 \\

0 & 0 & 0 & 1 & 0 \\

0 & 1 & 0 & 0 & 0 \\

0 & 0 & 0 & 0 & 1 \\

0 & 0 & 1 & 0 & 0

\end {bmatrix}.</Mathematik>

In Anbetracht eines Vektoren g,

:\begin {bmatrix }\\mathbf {e} _ {\\Pi (1)} \\\mathbf {e} _ {\\Pi (2)} \\\mathbf {e} _ {\\Pi (3)} \\\mathbf {e} _ {\\Pi (4)} \\\mathbf {e} _ {\\Pi (5)}\end {bmatrix }\\begin {bmatrix }\g_1 \\g_2 \\

g_3 \\

g_4 \\

g_5

\end {bmatrix }\\begin {bmatrix }\g_1 \\g_4 \\g_2 \\

g_5 \\

g_3

\end {bmatrix}.</Mathematik>

Das Lösen für P

Wenn uns zwei matrices A und B gegeben werden, die, wie man bekannt, als verbunden sind, aber die Versetzungsmatrix P selbst ist unbekannt, können wir P finden, der eigenvalue Zergliederung verwendet:

::

wo eine Diagonalmatrix von eigenvalues ist, und und der matrices von Eigenvektoren sind. Der eigenvalues dessen und wird immer dasselbe sein, und P kann als geschätzt werden. Mit anderen Worten, was bedeutet, dass die Eigenvektoren von B einfach permutierte Eigenvektoren von A. sind

Beispiel

Lassen Sie und seien Sie zwei solche matrices dass

:

Ein

\begin {bmatrix }\

0 & 1 & 2 \\

1 & 0 & 1.5 \\

2 & 1.5 & 0

\end {bmatrix} \text {und }\

</Mathematik>:

B

\begin {bmatrix }\

0 & 1 & 1.5 \\

1 & 0 & 2 \\

1.5 & 2 & 0

\end {bmatrix}.</Mathematik>

Lassen Sie, das Matrixpermutieren in den solchen dass zu sein

:

P

\begin {bmatrix }\

0 & 1 & 0 \\

1 & 0 & 0 \\

0 & 0 & 1

\end {bmatrix}.</Mathematik>

Das Multiplizieren damit permutiert vom links die Reihen dessen, wohingegen das Multiplizieren vom Recht die Säulen dessen permutiert. Deshalb permutiert die erste und zweite Reihe und die erste und zweite Säule zu erzeugen (wie Sichtprüfung bestätigt). So und Anteil derselbe eigenvalues durch die Diskussion oben. Nach der Entdeckung und diagonalizing diese eigenvalues ist die resultierende Diagonalmatrix

:

\Lambda

\begin {bmatrix }\

- 2.09394 & 0 & 0 \\

0 & 0.9433954 & 0 \\

0 & 0 & 3.037337

\end {bmatrix }\</Mathematik>

und die Matrix von Eigenvektoren dafür ist

:

Q_A

\begin {bmatrix }\

- 0.60130 & 0.54493 & 0.58437 \\

- 0.25523 &-0.82404 & 0.50579 \\

0.75716 & 0.15498 & 0.63458

\end {bmatrix }\</Mathematik>und die Matrix von Eigenvektoren dafür ist:

Q_B

\begin {bmatrix }\

- 0.25523 &-0.82404 &-0.50579 \\

- 0.60130 & 0.54493 &-0.58437 \\

0.75716 & 0.15498 &-0.63458

\end {bmatrix}.</Mathematik>

Den ersten Eigenvektoren (d. h. die erste Säule) beider vergleichend, wessen wir die erste Säule durch die Anmerkung schreiben können, dass das erste Element das zweite Element so vergleicht, stellen wir 1 im zweiten Element der ersten Säule dessen.

Dieses Verfahren wiederholend, vergleichen wir das zweite Element zum ersten Element , so stellen wir 1 im ersten Element der zweiten Säule dessen; und das dritte Element zum dritten Element so stellen wir 1 im dritten Element der dritten Säule dessen.

Die resultierende Matrix ist:

:P\begin {bmatrix }\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end {bmatrix}.</Mathematik>

Und sich mit der Matrix von oben vergleichend, finden wir, dass sie dasselbe sind.

Erklärung

Eine Versetzungsmatrix wird immer in der Form sein

:

\mathbf {e} _ {a_1} \\

\mathbf {e} _ {a_2} \\

\vdots \\

\mathbf {e} _ {a_j} \\

\end {bmatrix} </Mathematik>

wo e den ith Basisvektoren (als eine Reihe) für R, und wo vertritt

:

1 & 2 & \ldots & j \\

a_1 & a_2 & \ldots & a_j\end {bmatrix} </Mathematik>

ist die Versetzungsform der Versetzungsmatrix.

Jetzt, im Durchführen der Matrixmultiplikation, bildet man im Wesentlichen das Punktprodukt jeder Reihe der ersten Matrix mit jeder Säule des zweiten. In diesem Beispiel werden wir das Punktprodukt jeder Reihe dieser Matrix mit dem Vektoren von Elementen bilden, die wir permutieren wollen. D. h. zum Beispiel, v = (g..., g),

:e&middot;v=g

Also, das Produkt der Versetzungsmatrix mit dem Vektoren v oben,

wird ein Vektor in der Form (g, g..., g) sein, und dass das dann eine Versetzung von v ist, seitdem wir gesagt haben, dass die Versetzungsform ist

:1 & 2 & \ldots & j \\

a_1 & a_2 & \ldots & a_j\end {pmatrix}. </Mathematik>

Also, Versetzung matrices permutiert wirklich tatsächlich die Ordnung von Elementen in mit ihnen multiplizierten Vektoren.

Matrices mit unveränderlichen Liniensummen

Die Summe der Werte in jeder Säule oder Reihe in einer Versetzungsmatrix beläuft sich genau 1. Eine mögliche Generalisation der Versetzung matrices ist nichtnegativer integrierter matrices, wo sich die Werte jeder Säule und Reihe auf eine unveränderliche Nummer c belaufen. Wie man bekannt, ist eine Matrix dieser Sorte die Summe der c Versetzung matrices.

Zum Beispiel in der folgenden MatrixM jede Säule oder Reihe beläuft sich 5.

:\begin {bmatrix}

5 & 0 & 0 & 0 & 0 \\

0 & 3 & 2 & 0 & 0 \\

0 & 0 & 0 & 5 & 0 \\

0 & 1 & 2 & 0 & 2 \\

0 & 1 & 1 & 0 & 3

\end {bmatrix}.</Mathematik>

Diese Matrix ist die Summe von 5 Versetzung matrices.

Siehe auch

• Das Wechseln der Zeichen-Matrix
• Verallgemeinerte Versetzungsmatrix