Gruppo simmetrico

Un gruppo simmetrico $ S_n $ è composto da tutte le possibili permutazioni (modi di riordinare) degli $ n $ oggetti dell'insieme $ X $ e da tutte le composizioni possibili delle permutazioni. $$ S_n = ( X , \cdot ) $$

Dove il simbolo ( $ \cdot $ ) è usato per indicare la composizione di due permutazioni.

E' detto di grado $ n $ quando l'insieme è finito ed è composto da $ n $ elementi.

Una permutazione è un riarrangiamento degli elementi di un insieme in un ordine diverso. In matematica, una permutazione è una funzione biunivoca che mappa un insieme ordinato su se stesso.

Ad esempio, consideriamo l'insieme:

$$ X = \{1, 2, 3, 4, 5, 6 \} $$

Una permutazione potrebbe essere $ \{3, 5, 1, 2, 6, 4\} $, dove l'ordine originale degli elementi è stato cambiato.

$$ \tau: X \to X \\ 1 ⟶ 3 \\ 2 ⟶ 5 \\ 3 ⟶ 1 \\ 4 ⟶ 2 \\ 5 ⟶ 6 \\ 6 ⟶ 4 $$

I numeri sono stati riordinati in un certo modo. Ogni numero appare esattamente una volta, e nessun numero si ripete.

Per scrivere questa corrispondenza biunivoca $ \tau $ dell'insieme in se stesso si usa scrivere la disposizione iniziale su una prima linea e le immagini sulla seconda linea di una matrice.

$$ \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 5 & 1 & 2 & 6 & 4 \end{pmatrix} $$

Questo è il concetto di base delle permutazioni in un gruppo simmetrico.

Ad esempio, nella prima colonna 1 diventa 3, la seconda colonna 2 diventa 5, ecc. $$ \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow \\ 3 & 5 & 1 & 2 & 6 & 4 \end{pmatrix} $$ In alcune rappresentazioni, la permutazione può essere semplificata omettendo la prima riga, presupponendo che sia ordinata implicitamente in modo crescente, come $ (1,2,3,4,5,6) $. Quindi, possiamo rappresentare la permutazione precedente anche in questo modo più sintetico. $$ \tau = ( 3, 5, 1, 2, 6, 4 ) $$

L'insieme di tutte le permutazioni possibili forma un gruppo simmetrico che si indica S(X) oppure S_n rispetto all'operazione di composizione ( $ \cdot $ ) .

$$ S_n = ( X , \cdot ) $$

Si tratta di un'operazione interna al gruppo. Quindi, il risultato di ogni composizione fa ancora parte del gruppo S_n.

Esempio

Il gruppo simmetrico $ S_6=(X, \cdot) $ è formato dall'insieme finito $ X=\{ 1, 2, 3, 4, 5, 6 \} $ e dall'operazione di composizione ( $ \cdot $ ).

$$ S_6 = \{ \tau_1 , \tau_2 , ... , \tau_{n!} \} $$

$$ S_6 = \{ (1,2,3,4,5,6) \ , \ (3,5,1,2,6,4) \ , \ (4,1,6,3,2,5) \ , \ ... \} $$

In questo caso l'insieme $ X = \{1, 2, 3, 4, 5, 6 \} $ è composto da n=6 elementi, quindi si possono formare in tutto 720 permutazioni.

$$ |S_n| = 6!=6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720 $$

La notazione $ |S_n| = n! $ è la cardinalità del gruppo, significa che il numero di queste permutazioni è $ n! $ (fattoriale di $ n $), che è il prodotto di tutti i numeri interi positivi fino a $ n $.

La composizione delle permutazioni

Il gruppo simmetrico S_n è composto dalle permutazioni dell'insieme X e dall'operazione di composizione delle permutazioni che indichiamo con il simbolo $ \cdot $

La composizione di due permutazioni è un'operazione in cui si applica una permutazione e poi un'altra, seguendo l'ordine in cui vengono scritte.

Il risultato è una nuova permutazione che combina le modifiche di entrambe. In sostanza, ciò che la prima permutazione sceglie come output diventa l'input per la seconda permutazione.

Esempio

Consideriamo due permutazioni del gruppo S₆

$$ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 6 & 2 & 3 & 5 & 1 \end{pmatrix} $$

$$ \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 5 & 1 & 2 & 6 & 4 \end{pmatrix} $$

La composizione delle permutazioni è un'altra permutazione appartenente al gruppo S₆

$$ \sigma \cdot \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 6 & 2 & 3 & 5 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 5 & 1 & 2 & 6 & 4 \end{pmatrix} $$

Per calcolare la composizione delle permutazioni $ \sigma $ e $ \tau $, applicheremo prima $ \tau $ e poi $ \sigma $.

Cioè, per ogni elemento $ i $, troveremo $ \tau(i) $, e poi applicheremo $ \sigma $ a quel risultato per ottenere $ \sigma(\tau(i)) $.

Questo accade perché in una funzione composta $ \sigma ( \tau () ) $ si calcola prima la funzione più interna $ \tau() $ e poi quella più esterna $ \sigma() $ . Pertanto, la composizione va sempre eseguita da destra verso sinistra.

Prendiamo l'output di $ \tau $ e lo usiamo come input per $ \sigma $:

$ \tau(1) = 3 $ e $ \sigma(3) = 2 $, quindi $ \sigma(\tau(1)) = 2 $
$ \tau(2) = 5 $ e $ \sigma(5) = 5 $, quindi $ \sigma(\tau(2)) = 5 $
$ \tau(3) = 1 $ e $ \sigma(1) = 4 $, quindi $ \sigma(\tau(3)) = 4 $
$ \tau(4) = 2 $ e $ \sigma(2) = 6 $, quindi $ \sigma(\tau(4)) = 6 $
$ \tau(5) = 6 $ e $ \sigma(6) = 1 $, quindi $ \sigma(\tau(5)) = 1 $
$ \tau(6) = 4 $ e $ \sigma(4) = 3 $, quindi $ \sigma(\tau(6)) = 3 $

Mettendo tutto insieme, la composizione $ \sigma \cdot \tau $ è:

$$
\sigma \cdot \tau = \begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 \\
2 & 5 & 4 & 6 & 1 & 3
\end{pmatrix}
$$

Questa è la permutazione risultante dalla composizione delle due permutazioni date.

L'operazione inversa di una permutazione

Nel gruppo simmetrico l'operazione inversa di una permutazione si ottiene semplicemente scambiando la prima e la seconda riga tra loro.

Ad esempio, la permutazione $ \sigma $ è la seguente:

$$ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 6 & 2 & 3 & 5 & 1 \end{pmatrix} $$

L'operazione inversa $ \sigma^{-1} $ è la permutazione:

$$ \sigma^{-1} = \begin{pmatrix} 4 & 6 & 2 & 3 & 5 & 1 \\ 1 & 2 & 3 & 4 & 5 & 6 \end{pmatrix} $$

La permutazione identità di una permutazione

La permutazione identità $ \epsilon $ in un gruppo simmetrico è una permutazione che lascia ogni elemento nella sua posizione originale.

È l'elemento neutro del gruppo, il che significa che la composizione della permutazione identità con qualsiasi altra permutazione del gruppo dà quella permutazione stessa come risultato.

Ad esempio, nel caso del gruppo simmetrico di sei elementi la permutazione identità è rappresentata come:

$$ \epsilon = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 2 & 3 & 4 & 5 & 6 \end{pmatrix} $$

Questa rappresentazione mostra che ogni elemento $ i $ viene mappato a se stesso, $ i \to i $, per tutti gli elementi dell'insieme $ X = \{1, 2, 3, 4, 5, 6\} $.

Il gruppo simmetrico è un gruppo non abeliano

In generale i gruppi simmetrici sono gruppi non abeliani perché non soddisfano la proprietà commutativa.

Per $ n > 2 $ i gruppi simmetrici non sono abeliani.

Questo significa che l'ordine in cui si applicano due permutazioni può influenzare il risultato.

Ad esempio, la composizione $ \sigma \cdot \tau $ restituisce come risultato la permutazione $ (2,5,4,6,1,3) $

$$ \sigma \cdot \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 6 & 2 & 3 & 5 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 5 & 1 & 2 & 6 & 4 \end{pmatrix} $$

$$ \sigma \cdot \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 4 & 6 & 1 & 3 \end{pmatrix} $$

Se applichiamo la composizione in ordini diverso, si ottengono risultati differenti:

La composizione $ \tau \cdot \sigma $ restituisce come risultato la permutazione $ (2,4,5,1,6,3) $

$$ \tau \cdot \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 5 & 1 & 2 & 6 & 4 \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 6 & 2 & 3 & 5 & 1 \end{pmatrix} $$

$$ \tau \cdot \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 4 & 5 & 1 & 6 & 3 \end{pmatrix} $$

I risultati $ \sigma \tau = (2,5,4,6,1,3) $ e $ \tau \sigma = (2,4,5,1,6,3) $ sono chiaramente diversi , mostrando che $ S_6 $ non è abeliano.

Questa proprietà vale per tutti i gruppi simmetrici di grado maggiore di 2.

Il gruppo simmetrico è un gruppo abeliano (commutativo) solo quando $ n = 1 $ o $ n = 2 $. In questi casi, le permutazioni possono essere scambiate senza cambiare il risultato, perché per $ n = 1 $ c'è solo un elemento (e quindi solo una permutazione possibile, l'identità), e per $ n = 2 $ ci sono solo due permutazioni: l'identità e lo scambio dei due elementi, che sono inverse di se stesse. Ad esempio, se l'insieme $ X= \{ 1,2 \} $ ha solo due elementi, le permutazioni possibili sono due $$ \epsilon = \begin{pmatrix} 1 & 2 \\ 1 & 2 \end{pmatrix} $$ $$ \tau = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix} $$ In questo caso la composizione del gruppo simmetrico $ S_2 $ è commutativa $$ \epsilon \cdot \tau = \begin{pmatrix} 1 & 2 \\ 1 & 2 \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix} $$ $$ \tau \cdot \epsilon = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 \\ 1 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix} $$ Il risultato finale è lo stesso.