Matrice di permutazione

Da Wikipedia, l'enciclopedia libera.

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.

Definizione[modifica | modifica sorgente]

Data una permutazione \pi di n elementi

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

la matrice di permutazione P_\pi con n elementi è definita come

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

dove e_i denota la i-esima riga della matrice identità n \times n.

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

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

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

Proprietà[modifica | modifica sorgente]

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 P moltiplicata per la propria trasposta P^T restituisce la matrice identità: P P^T = I.

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

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

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

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

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

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}

Osservazioni[modifica | modifica sorgente]

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 n! (vedi fattoriale) matrici di permutazione n \times n.

Le matrici di permutazione 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 n oggetti.

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

Esempi[modifica | modifica sorgente]

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

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 g fornisce:

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}

Spiegazione[modifica | modifica sorgente]

Una matrice di permutazione sarà sempre nella forma

\begin{bmatrix}
\mathbf{e}_{a_1} \\
\mathbf{e}_{a_2} \\
\vdots \\
\mathbf{e}_{a_n} \\
\end{bmatrix}

dove, per ogni i, e_{a_i} rappresental'i-esimo vettore di base (come una riga) per \mathbb{R}^n, e dove

\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 v=(g_0,\dots,g_5)^T,

e_{a_i} \cdot v=g_{a_i}

Quindi, il prodotto della matrice di permutazione con il vettore v precedente, è un vettore della forma (g_{a_1},g_{a_2},\dots,g_{a_n}), e quindi questa è una permutazione di v poiché abbiamo detto che la permutazione che si forma è

\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.

Generalizzazione[modifica | modifica sorgente]

Una possibile generalizzazione di matrici di permutazione sono le matrici dove i valori di ogni colonna e riga hanno somma un certo numero c. Per esempio nella seguente matrice M ogni colonna o riga ha somma 5.

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

M = c_1 P_1 + \ldots + c_t P_t

con

\sum_{i=1}^{t} c_i = c

Voci correlate[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

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