Matrice de permutare

În matematică, o matrice de permutare , sau matrice permutativă , este o matrice care se obține prin schimbul unor rânduri sau coloane ale matricei de identitate . Ele sunt utilizate în principal pentru a reprezenta permutări și de aici și numele lor.

Definiție

Având în vedere o permutare $\pi$ ${\ displaystyle \ pi}$ $\ pi$ din $n$ ${\ displaystyle n}$ $n$ elemente

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

{\ displaystyle \ pi: \ lbrace 1, \ ldots, n \ rbrace \ to \ lbrace 1, \ ldots, n \ rbrace}

{\ displaystyle \ pi: \ lbrace 1, \ ldots, n \ rbrace \ to \ lbrace 1, \ ldots, n \ rbrace}

matricea de permutare $P_{\pi }$ ${\ displaystyle P _ {\ pi}}$ ${\ displaystyle P _ {\ pi}}$ cu $n$ ${\ displaystyle n}$ $n$ elemente este definit ca

P_{\pi }:={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\vdots \\\mathbf {e} _{\pi (n)}\\\end{bmatrix}}~,

{\ displaystyle P _ {\ pi}: = {\ begin {bmatrix} \ mathbf {e} _ {\ pi (1)} \\\ vdots \\\ mathbf {e} _ {\ pi (n)} \ \ \ end {bmatrix}} ~,}

{\ displaystyle P _ {\ pi}: = {\ begin {bmatrix} \ mathbf {e} _ {\ pi (1)} \\\ vdots \\\ mathbf {e} _ {\ pi (n)} \ \ \ end {bmatrix}} ~,}

unde este $e_{i}$ ${\ displaystyle e_ {i}}$ $e_ {i}$ denotă $the$ ${\ displaystyle i}$ $the$ -al rândul matricei de identitate $n\times n$ ${\ displaystyle n \ times n}$ $n \ ori n$ .

Dacă o matrice $M.$ ${\ displaystyle M}$ $M.$ este înmulțit la dreapta (postmultiplicat) cu o matrice de permutare $P_{\pi }$ ${\ displaystyle P _ {\ pi}}$ ${\ displaystyle P _ {\ pi}}$ (de exemplu $M. P.$ ${\ displaystyle MP}$ ${\ displaystyle MP}$ ), vectorii săi de coloană permutează în al doilea rând $\pi ^{T}$ ${\ displaystyle \ pi ^ {T}}$ ${\ displaystyle \ pi ^ {T}}$ .

Dacă o matrice $M.$ ${\ displaystyle M}$ $M.$ este înmulțit la stânga (premultiplicat) cu o matrice de permutare $P.$ ${\ displaystyle P}$ $P.$ (de exemplu $P. M.$ ${\ displaystyle PM}$ ${\ displaystyle PM}$ ), vectorii săi de rând permit două $\pi$ ${\ displaystyle \ pi}$ $\ pi$ .

Deci, de exemplu $\pi (i)=j$ ${\ displaystyle \ pi (i) = j}$ ${\ displaystyle \ pi (i) = j}$ , apoi matricea de permutare $P_{\pi }$ ${\ displaystyle P _ {\ pi}}$ ${\ displaystyle P _ {\ pi}}$ are termenul $p_{ij}$ ${\ displaystyle p_ {ij}}$ $p _ {{ij}}$ egal cu unul, deci rândul $the$ ${\ displaystyle i}$ $the$ din $P. M.$ ${\ displaystyle PM}$ ${\ displaystyle PM}$ se potrivește rândului $j$ ${\ displaystyle j}$ $j$ din $M.$ ${\ displaystyle M}$ $M.$ , în timp ce coloana $j$ ${\ displaystyle j}$ $j$ din $M. P.$ ${\ displaystyle MP}$ ${\ displaystyle MP}$ corespunde coloanei $the$ ${\ displaystyle i}$ $the$ din $M.$ ${\ displaystyle M}$ $M.$ .

Proprietate

Matricile de permutare sunt matrice binare care au exact 1 în fiecare rând și coloană și zero în altă parte, dând astfel exact 1 ca suma fiecărui rând sau coloană.

Sunt matrici non-singulare , deci inversabile . Determinantul lor este întotdeauna ± 1 și este exact semnul permutării corespunzătoare. Rezultă că, dacă o matrice este înmulțită cu o matrice de permutare, matricea rezultată va avea totuși același determinant ca matricea inițială, dar va avea semnul opus dacă permutația este impară.

O matrice de permutare $P.$ ${\ displaystyle P}$ $P.$ înmulțit cu propria sa transpunere $P^{T}$ ${\ displaystyle P ^ {T}}$ ${\ displaystyle P ^ {T}}$ returnează matricea de identitate: $PP^{T}=I$ ${\ displaystyle PP ^ {T} = I}$ ${\ displaystyle PP ^ {T} = I}$ .

Dă două permutări $\pi$ ${\ displaystyle \ pi}$ $\ pi$ Și $\sigma$ ${\ displaystyle \ sigma}$ $\ sigma$ dintre cele dintâi $n$ ${\ displaystyle n}$ $n$ numere întregi și matricile de permutare corespunzătoare $P_{\pi }$ ${\ displaystyle P _ {\ pi}}$ ${\ displaystyle P _ {\ pi}}$ Și $P_{\sigma }$ ${\ displaystyle P _ {\ sigma}}$ ${\ displaystyle P _ {\ sigma}}$

P_{\sigma }P_{\pi }=P_{\pi \circ \sigma }

{\ displaystyle P _ {\ sigma} P _ {\ pi} = P _ {\ pi \ circ \ sigma}}

{\ displaystyle P _ {\ sigma} P _ {\ pi} = P _ {\ pi \ circ \ sigma}}

Deoarece matricile de permutare sunt matrice ortogonale , ele posedă o matrice inversă care poate fi scrisă ca

P_{\pi }^{-1}=P_{\pi ^{-1}}

{\ displaystyle P _ {\ pi} ^ {- 1} = P _ {\ pi ^ {- 1}}}

{\ displaystyle P _ {\ pi} ^ {- 1} = P _ {\ pi ^ {- 1}}}

Înmulțirea unei matrice de permutare $P_{\pi }$ ${\ displaystyle P _ {\ pi}}$ ${\ displaystyle P _ {\ pi}}$ cu un vector $g$ ${\ displaystyle g}$ $g$ face ca componentele vectorului să permute corespunzător.

P_{\pi }\mathbf {g} ={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\vdots \\\mathbf {e} _{\pi (n)}\end{bmatrix}}{\begin{bmatrix}g_{1}\\\vdots \\g_{n}\end{bmatrix}}={\begin{bmatrix}g_{\pi (1)}\\\vdots \\g_{\pi (n)}\end{bmatrix}}

{\ displaystyle P _ {\ pi} \ mathbf {g} = {\ begin {bmatrix} \ mathbf {e} _ {\ pi (1)} \\\ vdots \\\ mathbf {e} _ {\ pi ( n)} \ end {bmatrix}} {\ begin {bmatrix} g_ {1} \\\ vdots \\ g_ {n} \ end {bmatrix}} = {\ begin {bmatrix} g _ {\ pi (1) } \ \\ vdots \\ g _ {\ pi (n)} \ end {bmatrix}}}

{\ displaystyle P _ {\ pi} \ mathbf {g} = {\ begin {bmatrix} \ mathbf {e} _ {\ pi (1)} \\\ vdots \\\ mathbf {e} _ {\ pi ( n)} \ end {bmatrix}} {\ begin {bmatrix} g_ {1} \\\ vdots \\ g_ {n} \ end {bmatrix}} = {\ begin {bmatrix} g _ {\ pi (1) } \ \\ vdots \\ g _ {\ pi (n)} \ end {bmatrix}}}

Observații

$P_{(1)}$ ${\ displaystyle P _ {(1)}}$ ${\ displaystyle P _ {(1)}}$ este matricea identității .

O matrice de permutare este un caz particular al unei matrice stocastice sau mai exact un caz particular al unei matrici dublu stochastice .

Se poate arăta că toate matricile pătrate ale unui aspect dat dublu stochastic sunt combinații liniare convexe ale matricilor de permutare; mulțimea matricilor permutative constituie deci un set de puncte extreme ale mulțimii de matrici dublu stochastice.

Sunt $n!$ ${\ displaystyle n!}$ $n!$ (vezi factorial ) matrici de permutare $n\times n$ ${\ displaystyle n \ times n}$ $n \ ori n$ .

Matricile de permutare $n\times n$ ${\ displaystyle n \ times n}$ $n \ ori n$ echipate cu operația de multiplicare formează un grup ; aceasta prezintă matricea de identitate ca un element unitar și constituie o reprezentare liniară a grupului simetric al $n$ ${\ displaystyle n}$ $n$ obiecte.

Matricile de permutare sunt utilizate pentru blocarea partițiilor matrice reductibile .

Exemple

Matricea de permutare $P_{\pi }$ ${\ displaystyle P _ {\ pi}}$ ${\ displaystyle P _ {\ pi}}$ corespunzător permutării $\pi ={\begin{pmatrix}1&2&3&4&5\\1&4&2&5&3\end{pmatrix}}$ ${\ displaystyle \ pi = {\ begin {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 2 & 5 & 3 \ end {pmatrix}}}$ ${\ displaystyle \ pi = {\ begin {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 2 & 5 & 3 \ end {pmatrix}}}$ , Și

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

{\ displaystyle P _ {\ pi} = {\ 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}}}

{\ displaystyle P _ {\ pi} = {\ 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}}}

și acționând asupra unui vector $g$ ${\ displaystyle g}$ $g$ oferă:

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

{\ displaystyle P _ {\ pi} \ mathbf {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}}}

{\ displaystyle P _ {\ pi} \ mathbf {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}}}

Explicaţie

O matrice de permutare va fi întotdeauna în formă

{\begin{bmatrix}\mathbf {e} _{a_{1}}\\\mathbf {e} _{a_{2}}\\\vdots \\\mathbf {e} _{a_{n}}\\\end{bmatrix}}

{\ displaystyle {\ begin {bmatrix} \ mathbf {e} _ {a_ {1}} \\\ mathbf {e} _ {a_ {2}} \\\ vdots \\\ mathbf {e} _ {a_ { n}} \\\ end {bmatrix}}}

{\ displaystyle {\ begin {bmatrix} \ mathbf {e} _ {a_ {1}} \\\ mathbf {e} _ {a_ {2}} \\\ vdots \\\ mathbf {e} _ {a_ { n}} \\\ end {bmatrix}}}

unde, pentru fiecare $the$ ${\ displaystyle i}$ $the$ , $e_{a_{i}}$ ${\ displaystyle e_ {a_ {i}}}$ ${\ displaystyle e_ {a_ {i}}}$ reprezentați-l $the$ ${\ displaystyle i}$ $the$ -al vectorul de bază (ca rând) pentru $\mathbb {R} ^{n}$ ${\ displaystyle \ mathbb {R} ^ {n}}$ $\ mathbb {R} ^ {n}$ , si unde

{\begin{bmatrix}1&2&\ldots &n\\a_{1}&a_{2}&\ldots &a_{n}\end{bmatrix}}

{\ displaystyle {\ begin {bmatrix} 1 & 2 & \ ldots & n \\ a_ {1} & a_ {2} & \ ldots & a_ {n} \ end {bmatrix}}}

{\ displaystyle {\ begin {bmatrix} 1 & 2 & \ ldots & n \\ a_ {1} & a_ {2} & \ ldots & a_ {n} \ end {bmatrix}}}

este permutația care caracterizează matricea permutației.

În termeni concreți, în efectuarea multiplicării matricei, produsul interior al fiecărui rând al primei matrice se formează în esență cu fiecare coloană a celei de-a doua.

În acest exemplu, formăm produsul interior al fiecărei coloane din această matrice cu vectorul cu elemente pe care dorim să le permutăm. Asta este, de exemplu, dacă numim vectorul $v=(g_{0},\dots ,g_{5})^{T}$ ${\ displaystyle v = (g_ {0}, \ dots, g_ {5}) ^ {T}}$ ${\ displaystyle v = (g_ {0}, \ dots, g_ {5}) ^ {T}}$ ,

e_{a_{i}}\cdot v=g_{a_{i}}

{\ displaystyle e_ {a_ {i}} \ cdot v = g_ {a_ {i}}}

{\ displaystyle e_ {a_ {i}} \ cdot v = g_ {a_ {i}}}

Prin urmare, produsul matricei de permutare cu vectorul $v$ ${\ displaystyle v}$ $v$ mai sus, este un vector al formei $(g_{a_{1}},g_{a_{2}},\dots ,g_{a_{n}})$ ${\ displaystyle (g_ {a_ {1}}, g_ {a_ {2}}, \ dots, g_ {a_ {n}})}$ ${\ displaystyle (g_ {a_ {1}}, g_ {a_ {2}}, \ dots, g_ {a_ {n}})}$ , și deci aceasta este o permutare a $v$ ${\ displaystyle v}$ $v$ întrucât am spus că permutarea care se formează este

{\begin{bmatrix}1&2&\ldots &n\\a_{1}&a_{2}&\ldots &a_{n}\end{bmatrix}}

{\ displaystyle {\ begin {bmatrix} 1 & 2 & \ ldots & n \\ a_ {1} & a_ {2} & \ ldots & a_ {n} \ end {bmatrix}}}

{\ displaystyle {\ begin {bmatrix} 1 & 2 & \ ldots & n \\ a_ {1} & a_ {2} & \ ldots & a_ {n} \ end {bmatrix}}}

Prin urmare, matricile de permutare aplicate unui vector permit de fapt componentele sale.

Generalizare

O posibilă generalizare a matricilor de permutare sunt matricile în care valorile fiecărei coloane și rânduri au suma unui anumit număr $c$ ${\ displaystyle c}$ $c$ . De exemplu în următoarea matrice $M.$ ${\ displaystyle M}$ $M.$ fiecare coloană sau rând are suma 5.