Matrice di permutazione

In matematica una matrice di permutazione, o matrice permutativa, è una matrice che si ottiene scambiando alcune righe o colonne della matrice identità. Vengono utilizzate principalmente per rappresentare permutazioni e da ciò deriva il loro nome.

Data una permutazione ${\displaystyle \pi }$ di ${\displaystyle n}$ elementi

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

la matrice di permutazione ${\displaystyle P_{\pi }}$ con ${\displaystyle n}$ elementi è definita come

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

dove ${\displaystyle e_{i}}$ denota la ${\displaystyle i}$-esima riga della matrice identità ${\displaystyle n\times n}$.

Se una matrice ${\displaystyle M}$ viene moltiplicata a destra (postmoltiplicata) per una matrice di permutazione ${\displaystyle P_{\pi }}$ (per esempio ${\displaystyle MP}$), i suoi vettori colonna permutano secondo ${\displaystyle \pi ^{T}}$.

Se una matrice ${\displaystyle M}$ è moltiplicata a sinistra (premoltiplicata) per una matrice di permutazione ${\displaystyle P}$ (per esempio ${\displaystyle PM}$), i suoi vettori riga permutano secondo ${\displaystyle \pi }$.

Perciò se per esempio ${\displaystyle \pi (i)=j}$, allora la matrice di permutazione ${\displaystyle P_{\pi }}$ ha il termine ${\displaystyle p_{ij}}$ uguale ad uno, dunque la riga ${\displaystyle i}$ di ${\displaystyle PM}$ corrisponde alla riga ${\displaystyle j}$ di ${\displaystyle M}$, mentre la colonna ${\displaystyle j}$ di ${\displaystyle MP}$ corrisponde alla colonna ${\displaystyle i}$ di ${\displaystyle M}$.

Le matrici di permutazione sono matrici binarie che hanno esattamente un 1 in ogni riga e in ogni colonna e zeri altrove, dando quindi come somma di ogni riga o colonna esattamente 1.

Sono matrici non singolari, quindi invertibili. Il loro determinante vale sempre ±1 e precisamente è il segno della permutazione corrispondente. Segue che se una matrice viene moltiplicata per una matrice di permutazione, la matrice risultante avrà ancora lo stesso determinante della matrice iniziale ma sarà di segno opposto se la permutazione è dispari.

Una matrice di permutazione ${\displaystyle P}$ moltiplicata per la propria trasposta ${\displaystyle P^{T}}$ restituisce la matrice identità: ${\displaystyle PP^{T}=I}$.

Date due permutazioni ${\displaystyle \pi }$ e ${\displaystyle \sigma }$ dei primi ${\displaystyle n}$ interi e le corrispondenti matrici di permutazione ${\displaystyle P_{\pi }}$ e ${\displaystyle P_{\sigma }}$

${\displaystyle P_{\sigma }P_{\pi }=P_{\pi \circ \sigma }.}$

Poiché le matrici di permutazione sono matrici ortogonali, possiedono matrice inversa che può essere scritta come

${\displaystyle P_{\pi }^{-1}=P_{\pi ^{-1}}.}$

La moltiplicazione di una matrice di permutazione ${\displaystyle P_{\pi }}$ con un vettore ${\displaystyle g}$ fa permutare di conseguenza le componenti del vettore.

${\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_{(1)}}$ è la matrice identità.

Una matrice di permutazione è un caso particolare di matrice stocastica o più precisamente un caso particolare di matrice doppiamente stocastica.

Si può mostrare che tutte le matrici quadrate di un dato aspetto doppiamente stocastiche sono combinazioni lineari convesse di matrici di permutazione; l'insieme delle matrici permutative costituisce quindi un insieme di punti estremi dell'insieme delle matrici doppiamente stocastiche.

Vi sono ${\displaystyle n!}$ (vedi fattoriale) matrici di permutazione ${\displaystyle n\times n}$.

Le matrici di permutazione ${\displaystyle n\times n}$ munite dell'operazione di moltiplicazione formano un gruppo; questo presenta la matrice identità come elemento unità e costituisce una rappresentazione lineare del gruppo simmetrico di ${\displaystyle n}$ oggetti.

Le matrici di permutazione vengono impiegate per partizionare a blocchi le matrici riducibili.

La matrice di permutazione ${\displaystyle P_{\pi }}$ corrispondente alla permutazione ${\displaystyle \pi ={\begin{pmatrix}1&2&3&4&5\\1&4&2&5&3\end{pmatrix}}}$, è

${\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}}}$

e agendo su un vettore ${\displaystyle g}$ fornisce:

${\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}}.}$

Una matrice di permutazione sarà sempre nella forma

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

dove, per ogni ${\displaystyle i}$, ${\displaystyle e_{a_{i}}}$ rappresenta l'${\displaystyle i}$-esimo vettore di base (come una riga) per ${\displaystyle \mathbb {R} ^{n}}$, e dove

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

è la permutazione caratterizzante la matrice di permutazione.

In concreto, nell'eseguire la moltiplicazione di matrice, si forma essenzialmente il prodotto interno di ogni riga della prima matrice con ogni colonna della seconda.

In questo esempio, si forma il prodotto interno di ogni colonna di questa matrice con il vettore con elementi che vogliamo permutare. Cioè, per esempio, se chiamiamo il vettore ${\displaystyle v=(g_{0},\dots ,g_{5})^{T}}$,

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

Quindi, il prodotto della matrice di permutazione con il vettore ${\displaystyle v}$ precedente, è un vettore della forma ${\displaystyle (g_{a_{1}},g_{a_{2}},\dots ,g_{a_{n}})}$, e quindi questa è una permutazione di ${\displaystyle v}$ poiché abbiamo detto che la permutazione che si forma è

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

Quindi, le matrici di permutazione applicate a un vettore effettivamente permutano le sue componenti.

Una possibile generalizzazione di matrici di permutazione sono le matrici dove i valori di ogni colonna e riga hanno somma un certo numero ${\displaystyle c}$. Per esempio nella seguente matrice ${\displaystyle M}$ ogni colonna o riga ha somma 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}}.}$

Una matrice di questo tipo può essere scomposta in matrici di permutazione come

${\displaystyle M=c_{1}P_{1}+\ldots +c_{t}P_{t},}$

con

${\displaystyle \sum _{i=1}^{t}c_{i}=c.}$

• Glossario sulle matrici
• Matrice delle adiacenze
• Matrice permutativa generalizzata
• Gruppo simmetrico

• Wikimedia Commons contiene immagini o altri file su matrice di permutazione

• (EN) Pagina su Wolfram MathWorld, su mathworld.wolfram.com.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica