Permuta matrico

eta|300px|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 * **e**j* estas la bazaj kolumnaj vektoroj, kaj do * **e**jT* estas liniaj vektoroj de longo *n* kun 1 en la *j*-a pozicio kaj 0 en ĉiuj la aliaj pozicioj.

## Propraĵoj 
Ĉ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π○σ*
: *(**h**Pσ)Pπ = **h**Pπ○σ*

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 * **e**a1, **e**a2, ..., **e**ak* 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 
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* 
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 
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ŭ 
* Alterna signa matrico
* Ĝeneraligita permuta matrico

## Eksteraj ligiloj 
* Permuta matrico je MathWorld

Kategorio:Matricoj
Kategorio:Permutoj