Î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 {\ displaystyle \ pi} din {\ displaystyle n} elemente
- {\ displaystyle \ pi: \ lbrace 1, \ ldots, n \ rbrace \ to \ lbrace 1, \ ldots, n \ rbrace}
matricea de permutare {\ displaystyle P _ {\ pi}} cu {\ displaystyle n} elemente este definit ca
- {\ displaystyle P _ {\ pi}: = {\ begin {bmatrix} \ mathbf {e} _ {\ pi (1)} \\\ vdots \\\ mathbf {e} _ {\ pi (n)} \ \ \ end {bmatrix}} ~,}
unde este {\ displaystyle e_ {i}} denotă {\ displaystyle i} -al doilea rând al matricei de identitate {\ displaystyle n \ times n} .
Dacă o matrice {\ displaystyle M} este înmulțit la dreapta (postmultiplicat) cu o matrice de permutare {\ displaystyle P _ {\ pi}} (de exemplu {\ displaystyle MP} ), vectorii săi de coloană permutează în al doilea rând {\ displaystyle \ pi ^ {T}} .
Dacă o matrice {\ displaystyle M} este înmulțit la stânga (premultiplicat) cu o matrice de permutare {\ displaystyle P} (de exemplu {\ displaystyle PM} ), vectorii săi de rând permutează în al doilea rând {\ displaystyle \ pi} .
Deci, de exemplu {\ displaystyle \ pi (i) = j} , apoi matricea de permutare {\ displaystyle P _ {\ pi}} are termenul {\ displaystyle p_ {ij}} egal cu unul, deci rândul {\ displaystyle i} din {\ displaystyle PM} se potrivește rândului {\ displaystyle j} din {\ displaystyle M} , în timp ce coloana {\ displaystyle j} din {\ displaystyle MP} corespunde coloanei {\ displaystyle i} din {\ displaystyle 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 {\ displaystyle P} înmulțit cu propria sa transpunere {\ displaystyle P ^ {T}} returnează matricea de identitate: {\ displaystyle PP ^ {T} = I} .
Dă două permutări {\ displaystyle \ pi} Și {\ displaystyle \ sigma} dintre cele dintâi {\ displaystyle n} numere întregi și matricile de permutare corespunzătoare {\ displaystyle P _ {\ pi}} Și {\ displaystyle P _ {\ 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
- {\ displaystyle P _ {\ pi} ^ {- 1} = P _ {\ pi ^ {- 1}}}
Înmulțirea unei matrice de permutare {\ displaystyle P _ {\ pi}} cu un vector {\ displaystyle g} face ca componentele vectorului să permute corespunzător.
- {\ 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
{\ 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 de matrice de permutare; mulțimea matricilor permutative constituie deci un set de puncte extreme ale mulțimii de matrici dublu stochastice.
Sunt {\ displaystyle n!} (vezi factorial ) matrici de permutare {\ displaystyle n \ times n} .
Matricile de permutare {\ displaystyle n \ times 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 {\ displaystyle n} obiecte.
Matricile de permutare sunt utilizate pentru blocarea partițiilor matrice reductibile .
Exemple
Matricea de permutare {\ displaystyle P _ {\ pi}} corespunzător permutării {\ displaystyle \ pi = {\ begin {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 2 & 5 & 3 \ end {pmatrix}}} , Și
- {\ 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 {\ displaystyle g} oferă:
- {\ 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ă
- {\ displaystyle {\ begin {bmatrix} \ mathbf {e} _ {a_ {1}} \\\ mathbf {e} _ {a_ {2}} \\\ vdots \\\ mathbf {e} _ {a_ { n}} \\\ end {bmatrix}}}
unde, pentru fiecare {\ displaystyle i} , {\ displaystyle e_ {a_ {i}}} reprezentați-l {\ displaystyle i} -al vectorul de bază (ca rând) pentru {\ displaystyle \ mathbb {R} ^ {n}} , si unde
- {\ 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 {\ displaystyle v = (g_ {0}, \ dots, g_ {5}) ^ {T}} ,
- {\ displaystyle e_ {a_ {i}} \ cdot v = g_ {a_ {i}}}
Prin urmare, produsul matricei de permutare cu vectorul {\ displaystyle v} mai sus, este un vector al formei {\ displaystyle (g_ {a_ {1}}, g_ {a_ {2}}, \ dots, g_ {a_ {n}})} , și deci aceasta este o permutare a {\ displaystyle v} întrucât am spus că permutarea care se formează este
- {\ 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 {\ displaystyle c} . De exemplu în următoarea matrice {\ displaystyle M} fiecare coloană sau rând are suma 5.
- {\ displaystyle M = {\ 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}}}
O matrice de acest tip poate fi descompusă în matrici de permutare cum ar fi
- {\ displaystyle M = c_ {1} P_ {1} + \ ldots + c_ {t} P_ {t}}
cu
- {\ displaystyle \ sum _ {i = 1} ^ {t} c_ {i} = c}
Elemente conexe
Alte proiecte
linkuri externe