Permuta matrico

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo
Ekzistas 6 malsamaj permutaj 3×3 matricoj (montritaj supre kaj la samaj maldekstre). Ĉiu el 36 iliaj produtoj estas denove permuta 3×3 matrico (montritaj en 6×6 kvadrato pli malsupre pli dekstre)

En matematiko, permuta matrico estas kvadrata duuma matrico kiu havas akurate po unu elementon 1 en ĉiu linio kaj en ĉiu kolumno kaj 0 aliloke. Ĉiu ĉi tia matrico prezentas specifan permuto de m eroj kaj, kiam uzata por multipliki alia matrico, povas produkti permuton de la linioj aŭ kolumnoj de la alia matrico.

Por donita permuto π de n eroj,

\pi : \lbrace 1, \ldots, n \rbrace \to \lbrace 1, \ldots, n \rbrace

donita en du-linia formo per

\begin{pmatrix} 1 & 2 & \cdots & n \\ \pi(1) & \pi(2) & \cdots & \pi(n) \end{pmatrix}

ĝia permuta matrico estas la n×n matrico Pπ kies elementoj estas ĉiuj 0 escepte de tio ke en ĉiu linio i, elemento en kolumno π(i) egalas al 1. Eblas skribi ĝin kiel

P_\pi = \begin{bmatrix} \mathbf e_{\pi(1)}^T \\ \mathbf e_{\pi(2)}^T \\ \vdots \\ \mathbf e_{\pi(m)}^T \end{bmatrix}

kie ej estas la bazaj kolumnaj vektoroj, kaj do ejT estas liniaj vektoroj de longo n kun 1 en la j-a pozicio kaj 0 en ĉiuj la aliaj pozicioj.

Propraĵoj[redakti | redakti fonton]

Ĉiu permuta matrico estas ortonormala matrico, ĉar skalara produto de ĉiu linio aŭ kolumno je si egalas al 1, skalara produto de ĉiu linio je ĉiu la alia linio estas 0, skalara produto de ĉiu kolumno je ĉiu la alia kolumno estas 0. Tiel

(Pπ)TPπ = Pπ(Pπ)T = I

Pro tio ke ĉiu permuta matrico estas ortonormala matrico, ĝia inversa matrico ekzistas kaj egalas al transpono de la originala matrico:

(Pπ)-1 = P-1) = (Pπ)T

Por donitaj du permutoj π kaj σ de m eroj kaj la respektivaj permutaj matricoj Pπ kaj Pσ

PσPπ = Pπ○σ

Ĉi tiu bedaŭrinda regulo estas konsekvenco de la difinoj de multipliko de permutoj (ĉi tie multipliko kiel komponaĵo de reciproke unuvaloraj surĵetoj) kaj de multipliko de matricoj, kaj de la elekto de uzo de la vektoroj eπ(i) kiel linioj de la permuta matrico. Tamen ĉi tiu regulo estas konsekvenca al tio ke multipliko de matrico je kolumna vektoro priskribas linearan transformon de la vektora spaco, kiu estas permuto de la komponantoj de la vektoro (vidu sube).

Multipliko de Pπ je matrico N rezultas je permuto de la linioj de la matrico N;

P_\pi N
=
\begin{bmatrix}
\mathbf{e}_{\pi(1)}^T \\
\mathbf{e}_{\pi(2)}^T \\
\vdots \\
\mathbf{e}_{\pi(n)}^T
\end{bmatrix}
\begin{bmatrix}
N_{1, 1} & N_{1, 2} & \dots & N_{1, m} \\
N_{2, 1} & N_{2, 2} & \dots & N_{2, m} \\
\vdots & \vdots & & \vdots \\
N_{n, 1} & N_{n, 2} & \dots & N_{n, m} \\
\end{bmatrix}
=
\begin{bmatrix}
N_{\pi(1), 1} & N_{\pi(1), 2} & \dots & N_{\pi(1), m} \\
N_{\pi(2), 1} & N_{\pi(2), 2} & \dots & N_{\pi(2), m} \\
\vdots & \vdots & & \vdots \\
N_{\pi(n), 1} & N_{\pi(n), 2} & \dots & N_{\pi(n), m} \\
\end{bmatrix}

Simile, multipliko de Pπ je kolumna vektoro g rezultas je permuto de la komponantoj de la vektoro:

P_\pi \mathbf{g}
=
\begin{bmatrix}
\mathbf{e}_{\pi(1)}^T \\
\mathbf{e}_{\pi(2)}^T \\
\vdots \\
\mathbf{e}_{\pi(n)}^T
\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}

Nun apliko de Pσ post apliko de Pπ donas la saman rezulton kiel apliko de Pπ○σ senpere. Estu

g'_i=g_{\pi(i)}

por ĉiuj i, tiam

P_\sigma(P_\pi \mathbf{g}) = P_\sigma \mathbf{g}'
=
\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}

kaj ankaŭ por la matrico N

Pσ(PπN) = Pπ○σN

Multipliko de matrico M je Pπ donas permuton de la kolumnoj de la matrico M per la inverso de Pπ.

MP_\pi
=
\begin{bmatrix}
M_{1, 1} & M_{1, 2} & \dots & M_{1, n} \\
M_{2, 1} & M_{2, 2} & \dots & M_{2, n} \\
\vdots & \vdots & & \vdots \\
M_{m, 1} & M_{m, 2} & \dots & M_{m, n} \\
\end{bmatrix}
\begin{bmatrix}
\mathbf{e}_{\pi(1)}^T \\
\mathbf{e}_{\pi(2)}^T \\
\vdots \\
\mathbf{e}_{\pi(n)}^T
\end{bmatrix}
=
\begin{bmatrix}
M_{1, \pi^{-1}(1)} & M_{1, \pi^{-1}(2)} & \dots & M_{1, \pi^{-1}(n)} \\
M_{2, \pi^{-1}(1)} & M_{2, \pi^{-1}(2)} & \dots & M_{2, \pi^{-1}(n)} \\
\vdots & \vdots & & \vdots \\
M_{m, \pi^{-1}(1)} & M_{m, \pi^{-1}(2)} & \dots & M_{m, \pi^{-1}(n)} \\
\end{bmatrix}

Simile, multipliko de linia vektoro h je Pπ donas permuton de la eroj de la vektoro per la inverso de Pπ:

\mathbf{h}P_\pi
=
\begin{bmatrix} h_1 & h_2 & \dots & h_n \end{bmatrix}
\begin{bmatrix}
\mathbf{e}_{\pi(1)}^T \\
\mathbf{e}_{\pi(2)}^T \\
\vdots \\
\mathbf{e}_{\pi(n)}^T
\end{bmatrix}
=
\begin{bmatrix} h_{\pi^{-1}(1)} & h_{\pi^{-1}(2)} & \dots & h_{\pi^{-1}(n)} \end{bmatrix}

kaj simile

(MPσ)Pπ = MPπ○σ
(hPσ)Pπ = hPπ○σ

Estu Sn la simetria grupo, aŭ grupo de permutoj, sur {1, 2, ..., n}. Pro tio ke estas n! permutoj, estas n! permutaj matricoj. Per la formuloj pli supre, la n×n permutaj matricoj formas grupon sub matrica multipliko kun la identa matrico kiel la neŭtra elemento.

Se (1) estas la identa permuto, do P(1) estas la identa matrico.

Oni povas konsideri ĉiun permutan matricon de permuto σ kiel la permuto σ de la kolumnoj de la identa matrico I, aŭ kiel la permuto σ-1 de la linioj de I.

Permuta matrico estas duoble stokasta matrico. La teoremo de Birkhoff-von Neumann diras ke ĉiu duoble stokasta matrico estas konveksa kombinaĵo de permutaj matricoj de la sama ordo kaj la permutaj matricoj estas la ekstremumaj punktoj de la aro de duoble stokastaj matricoj. Tio estas, la hiperpluredro de Birkhoff, la aro de duoble stokastaj matricoj, estas la konveksa koverto de la aro de permutaj matricoj.

La spuro de permuta matrico egalas al la kvanto de fiksaj punktoj de la permuto. Se la permuto havas fiksajn punktojn, do ĝi povas esti skribita en cikla formo kiel π = (a1)(a2)...(ak kie σ ne havas fiksajn punktojn, tiam ea1, ea2, ..., eak estas ajgenvektoroj de la permuta matrico.

Ĉiu permuto povas esti prezentita kiel produto de interŝanĝoj. Pro tio, ĉiu permuta matrico povas esti prezentita kiel produto de linio-interŝanĝantaj rudimentaj matricoj, ĉiu havanta determinanton -1. Tial la determinanto de permuta matrico P egalas al signumo de la respektiva permuto.

Ekzemploj[redakti | redakti fonton]

La permuta matrico Pπ respektiva al la permuto \pi=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 2 & 5 & 3 \end{pmatrix} estas

P_\pi
=
\begin{bmatrix}
\mathbf{e}_{\pi(1)}^T \\
\mathbf{e}_{\pi(2)}^T \\
\mathbf{e}_{\pi(3)}^T \\
\mathbf{e}_{\pi(4)}^T \\
\mathbf{e}_{\pi(5)}^T
\end{bmatrix}
=
\begin{bmatrix}
\mathbf{e}_{1}^T \\
\mathbf{e}_{4}^T \\
\mathbf{e}_{2}^T \\
\mathbf{e}_{5}^T \\
\mathbf{e}_{3}^T
\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}

Por ĉiu kolumna vektoro g,

P_\pi \mathbf{g}
=
\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}
\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}

Solvado por P[redakti | redakti fonton]

Se estas donitaj du matricoj A kaj B pri kiuj estas sciate ke estas rilato B=PAP-1, sed la permuta matrico P estas nekonata, oni povas trovi P uzante ajgenan malkomponaĵon. La ajgenoj de A kaj B estas ĉiam la samaj, do ekzistas ajgenaj malkomponaĵoj de ambaŭ matricoj A kaj B kun la sama jordana matrico (plejofte diagonala matrico) de ajgenoj Λ:

A = QΛQ-1
B = SΛS-1

kie Q kaj S estas la matricoj de ajgenvektoroj. Tiam P povas esti komputita kiel P = SQ-1. Ĉi tio signifas ke, PQ = S, kio signifas ke la ajgenvektoroj la matrico de B estas permutita matrico de ajgenvektoroj de A.

Matricoj kun konstantaj kolumnaj kaj liniaj sumoj[redakti | redakti fonton]

La sumo de eroj en ĉiu kolumno aŭ linio de permuta matrico egalas al 1. Ebla ĝeneraligo de permutaj matricoj estas nenegativaj entjeraj matricoj kie la sumoj de eroj de ĉiu kolumno kaj linio egalas al konstanta nombro c. Matrico de ĉi tiu speco estas sumoj de c permutaj matricoj.

Ekzemple en jena matrico M sumo de ĉiu kolumno aŭ linio egalas al 5:

M =\begin{bmatrix}
5 & 0 & 0 & 0 & 0 \\
0 & 1 & 2 & 0 & 2 \\
0 & 3 & 2 & 0 & 0 \\
0 & 0 & 0 & 5 & 0 \\
0 & 1 & 1 & 0 & 3
\end{bmatrix}

Vidu ankaŭ[redakti | redakti fonton]

Eksteraj ligiloj[redakti | redakti fonton]