La permutazione su un insieme è la modifica dell’ordine in cui appaiono gli elementi dell’insieme. Si tratta di una funzione biiettiva che dato un insieme otteniamo lo stesso insieme con gli elementi cambiati di posto.
Un insieme è una raccolta di elementi, mentre una funzione è una relazione tra due insiemi diversi o tra lo stesso insieme che dato un elemento del primo insieme, chiamato dominio, ci permette di ottenere un solo elemento del secondo insieme, chiamato codominio. Il simbolo usato per la permutazione è σ. Se chiamiamo l’insieme A e dato K un campo, allora la definizione della permutazione è:
σ: An→An, n ∈ K
σ = n!
\[ n! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot (n – 1) \cdot n = \prod_{z=1}^{n} z \]Notiamo infatti che dato un certo numero elementi di un insieme finito possiamo effettuare tante permutazioni quante sono il fattoriale del numero. La prima permutazione è l’insieme identità, cioè la sequenza ordinata degli elementi; i primi scambi si ottengono lasciando al suo posto uno degli elementi e scambiando gli altri, e poi otteniamo gli altri risultati sommando ciascun elemento di 1, di 2, fino al numero degli elementi. Ovviamente, sommando se il numero ottenuto è maggiore del massimo dell’insieme ricominciamo dal primo.
Ad esempio se abbiamo l’insieme S2 = {1,2} (il numero in pedice indica il numero di elementi), allora possiamo effettuare 2! permutazioni, cioè 2 ∙ 1 = 2 permutazioni. Infatti otteniamo l’insieme {1,2} e {2,1}
Consideriamo adesso l’insieme S3 = {1,2,3}. Il fattoriale di 3 è 6. Quindi abbiamo 6 permutazioni. Chiamiamo con il simbolo Sn, l’insieme di tutte le permutazioni di S3. Otteniamo:
S3 = { {1,2,3} , {1,3,2} , {3,2,1} , {2,1,3}, {2,3,1}, {3,1,2} }
La prima permutazione è l’identità, le successive tre le abbiamo ottenute lasciando un elemento nella sua posizione e scambiando gli altri due; infine, abbiamo avanzato di un posto tutti gli elementi e poi li abbiamo scalati di un posto, in pratica abbiamo sommato 1 (il 3 però diventa 1 perché il 4 non appartiene all’insieme) e poi gli abbiamo sottratto 1 (l’1 però diventa 3 perché lo 0 non appartiene all’insieme).
Permutazioni di classe pari o dispari
Data una qualsiasi permutazione è richiesto un certo numero di scambi per trasformarla in un’identità. Se occorrono un numero di scambi pari allora la permutazione viene chiamata di classe pari, altrimenti viene chiamata di classe dispari.
Da qui possiamo anche definire la funzione segno di una permutazione che vale 1 se la permutazione è di classe pari, -1 se è di classe dispari.
Ad esempio se abbiamo l’insieme S2 = {1,2} la permutazione {1,2} è di classe pari perché non richiede nessuno scambio e rappresenta l’identità mentre la permutazione {2,1} richiede uno scambio per essere trasformata nell’identità, perciò è di classe dispari e il suo segno è -1.
Data una matrice quadrata e una permutazione possiamo definire la funzione prodotto dedotto associato alla permutazione ed è uguale al prodotto di tutti gli elementi della matrice la cui posizione corrisponde a ciascun indice delle righe e come colonne prendiamo la posizione indicata nello stesso indice della permutazione.
\[ \rho_\sigma = \prod_{z=1}^{n} a_{z\,\sigma(z)} \quad \text{dove } A = (a_{ij}) \in \mathbb{K}^{n \times n},\ \sigma \in S_n \]Ecco un esempio usando una matrice generica con 4 righe e 4 colonne e una permutazione σ = {3,2,4,1}:
\[ \sigma(1) = 3,\quad \sigma(2) = 2,\quad \sigma(3) = 4,\quad \sigma(4) = 1 \] \[ \rho_\sigma = a_{1\,3} \cdot a_{2\,2} \cdot a_{3\,4} \cdot a_{4\,1} \]\[ A = \begin{pmatrix} a_{11} & a_{12} & \color{red}{a_{13}} & a_{14} \\ a_{21} & \color{red}{a_{22}} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & \color{red}{a_{34}} \\ \color{red}{a_{41}} & a_{42} & a_{43} & a_{44} \end{pmatrix} \]Da qui possiamo calcolare il determinante di alcune matrici quadrate. Infatti data una matrice A ∈ Kn,n, possiamo stabilire ciascuna permutazione di n, σn. La formula è:
\[ \det A = \prod_{\sigma \in S_n} sgn(\sigma) \rho_\sigma \]- n = 1 => Sn = {1}
- det A = a11
- n = 2 => Sn = {(1,2),(2,1)}
- det A = ρ(1,2) – ρ(2,1) = a12 – a21
- n = 3 => Sn = { {1,2,3} , {1,3,2} , {3,2,1} , {2,1,3}, {2,3,1}, {3,1,2} }
- det A = ρ(1,2,3) + ρ(2,3,1) + ρ(3,1,2) – ρ(1,3,2) – ρ(3,2,1) – ρ(2,1,3)
- det A = a11 a22 a33 + a12 a3 a31 + a13 a21 a32 – a11 a23 a32 – a13 a22 a31 – a12 a21 a32
Nota che abbiamo inserito prima le permutazioni di classe pari e poi quelle di classe dispari. Ecco degli esempi:
\[ A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} \] \[ \det(C) = 1 \cdot 4 – 2 \cdot 3 = -2 \] \[ B = \begin{pmatrix} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 1 & 0 & 6 \end{pmatrix} \] \[ \det(D) = 1 \cdot 4 \cdot 6 + 2 \cdot 5 \cdot 1 + 3 \cdot 0 \cdot 0 – 3 \cdot 4 \cdot 1 – 2 \cdot 0 \cdot 6 – 1 \cdot 5 \cdot 0 = 22 \]