Utente:Grasso Luigi/sandbox4/Gruppo simmetrico

In matematica, il gruppo simmetrico di un insieme è il gruppo formato dall'insieme delle permutazioni dei suoi elementi, cioè dall'insieme delle funzioni biiettive di tale insieme in se stesso, munito dell'operazione binaria di composizione di funzioni. Tutti i gruppi simmetrici di insiemi aventi la stessa cardinalità sono isomorfi. Tra i gruppi simmetrici di un dato numero finito n di oggetti in genere si preferisce considerare quello costituito dalle permutazioni degli interi 1, 2, ..., n e denotarlo con S_n. Questa successione di gruppi è studiata molto approfonditamente e gioca un ruolo di primaria importanza per lo studio delle simmetrie. È facile provare che il gruppo S_n ha ordine n! (si veda la voce permutazione) e che non è abeliano per n > 2.

Struttura di S_n

Gli elementi del gruppo simmetrico di un insieme X = {1, ..., n} sono le permutazioni di X. In genere X è una struttura algebrica (un gruppo, un campo, uno spazio vettoriale ...) oppure una struttura geometrica. Quest'ultima interpretazione è quella che seguiremo nel seguito. Per indicare un elemento generico di $S_{n}$ useremo la notazione 2-linea:

$\alpha ={\begin{pmatrix}1&2&3&\ldots &n\\\alpha (1)&\alpha (2)&\alpha (3)&\ldots &\alpha (n)\end{pmatrix}}=(\,\alpha (1),\alpha (2),\alpha (3),\ldots ,\alpha (n)\,).$

dove la seconda viene detta notazione 2-linea abbreviata. Inoltre useremo la notazione ciclica:

$\alpha =\alpha _{1}\,\alpha _{2}\cdots \alpha _{r}=\prod _{i=1}^{r}\,({a_{1}}^{i}\ {a_{2}}^{i}\ldots {a_{l_{i}}}^{i})=\prod _{i=1}^{r}\,\alpha _{i}\qquad i=1,2...r\quad \sum _{i=1}^{r}\,l_{i}=|S_{n}|=n!$

dove $\alpha _{i}$ è un generico l_i-ciclo di cui più avanti ne diamo la definizione.

Operazione interna

L'operazione di gruppo in S_n è la funzione di composizione, indicata con ∘ detta composizione delle permutazioni. La composizione α ∘ β delle permutazioni α e β, detta "α di β", trasforma un elemento x di X a α(β(x)).

Vediamo un esempio in S₅. (Per la notazione vedi argomento della permutazione):

$\alpha ={\begin{pmatrix}1&2&3&4&5\\3&2&1&5&4\end{pmatrix}}\qquad \beta ={\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}.$

Si applica α dopo β ottenendo le seguenti trasformazioni:

Composizione 2-linea

β	α	γ = α ∘ β
1-2	2-2	2
2-5	5-4	4
3-4	4-5	5
4-3	3-1	1
5-1	1-3	3

Composizione ciclica

β		α		γ = α ∘ β
2-ciclo dx	3-ciclo	2-ciclo	2-ciclo sx
3 → 4	4 → 4	4 → 5	5 → 5	3 → 5
5 → 5	5 → 1	1 → 1	1 → 3	5 → 3
3
4 → 3	3 → 3	3 → 3	3 → 1	4 → 1
1 → 1	1 → 2	2 → 2	2 → 2	1 → 2
2 → 2	2 → 5	5 → 4	4 → 4	2 → 4
4

Quindi la composizione α e β produce nella notazione 2-linea:

$\alpha \beta =\alpha \circ \beta ={\begin{pmatrix}1&2&3&4&5\\2&4&5&1&3\end{pmatrix}}.$

mentre nella rappresentazione ciclica, dalla definizione si ha $\gamma (1)=2\;\gamma (2)=4\;\gamma (4)=1{\text{ e }}\gamma (3)=5\;\gamma (5)=3$ e relazioni simili si possono ottenere per α e β, per cui:

$\alpha =(1\ 3)(2)(4\ 5)=(4\ 5)(1\ 3)(2)\quad \beta =(1\ 2\ 5)(3\ 4)=(3\ 4)(1\ 2\ 5)\qquad \alpha \beta =\alpha \circ \beta =(1\ 3)(4\ 5)(1\ 2\ 5)(3\ 4)=(1\ 2\ 4)(3\ 5)=(3\ 5)(1\ 2\ 4)$

Assiomi del gruppo

Per verificare che il gruppo simmetrico su un insieme X sia effettivamente un gruppo, è necessario verificare gli assioni di chiusura, associatività, identità, e inversa.

$\forall f,g,h\in S_{n}$ si ha

1. L'operazione di composizione è chiusa (legge interna al gruppo) nell'insieme delle permutazioni di un certo insieme X.

   $f\circ g\in S_{n}$

2. La composizione è sempre associativa.

   $f\circ (g\circ h)=(f\circ g)\circ h$

3. La bigezione banale che assegna ad ogni elemento di X lo stesso funge da identità per il gruppo.

   $id={\begin{pmatrix}1&2&3&\cdots &n\\1&2&3&\cdots &n\end{pmatrix}}=(1)(2)\ldots (n)$

   da notare la notazione ciclica interamente costituita da 1-ciclo, di cui daremo la definizione.

4. Ogni biiezione ha una funzione inversa che annulla la sua azione, e quindi ogni elemento di un gruppo simmetrico ha un inverso che è anch'esso una permutazione.

   $g\circ g^{-1}=g^{-1}\circ g=id$

   si ottiene scambiando la coppia della trasformazione, ad esempio si ha
   

   Inversa

   $g$	$g^{-1}$	$g\circ g^{-1}=id$
   1-2	2-1	1
   2-5	5-2	2
   3-4	4-3	3
   4-3	3-4	4
   5-1	1-5	5

   $g^{-1}={\begin{pmatrix}1&2&3&4&5\\5&1&4&3&2\end{pmatrix}}=(1\ 5\ 2)(3\ 4)=(3\ 4)(1\ 5\ 2)$

Rappresentazione ciclica del gruppo

Tra gli elementi di S_n notevole importanza hanno gli l-cicli (con l ≤ n), ossia gli elementi di S_n che hanno ordine l e che hanno esattamente n-l punti fissi. Per ogni l = 2, ..., n si può dimostrare che il numero totale presenti in S_n del tipo l-ciclo è $h_{l}={\frac {n!}{l(n-l)!}}$, mentre per l = 1 abbiamo i punti fissi.

Un ciclo di lunghezza l è una permutazione $\gamma$ per cui si verifica la serie

$x\in X=\{1,\ 2,\ldots ,n\}\ :\ x,\gamma (x),\gamma ^{2}(x),\ldots ,\gamma ^{l}(x)=x$

oppure equivale alla serie

$\gamma (x)=\gamma ^{2}(x),\ldots ,\gamma ^{l-1}(x)=\gamma ^{l}(x)=x$

sono gli unici elementi trasformati da $\gamma$ che riportano all'elemento x di partenza; dev'essere l ≥ 2 poichè quando l = 1 l'elemento x stesso non verrebbe nemmeno spostato. L'ordine del ciclo equivale alla sua lunghezza e viene detto l-ciclo. Un l-ciclo si denota con le l-scritture equivalenti (ogni scrittura parte da un punto diverso dello stesso ciclo):

$(\,x\ \gamma (x)\ \gamma ^{2}(x)\ldots \gamma ^{l-1}(x)\,)=(\;\gamma (x)\ \gamma ^{2}(x)\ldots \gamma ^{l-1}(x)\;x\;)=\cdots =(\;\gamma ^{l-1}(x)\;x\;\gamma (x)\ \ldots \gamma ^{l-2}(x)\;)$

ad esempio per $\gamma =(1\ 2\ 3\ 4\ 5\ )\in S_{5}$ ammette le 5 scritture equivalenti:

$\gamma =(1\ 2\ 3\ 4\ 5\ )=(2\ 3\ 4\ 5\ 1\ )=(3\ 4\ 5\ 1\ 2\ )=(4\ 5\ 1\ 2\ 3\ )=(5\ 1\ 2\ 3\ 4\ )$

Cicli disgiunti

Due cicli sono disgiunti se hanno sottoinsiemi disgiunti di elementi. In altri termini due cicli sono disgiunti se i punti di un ciclo che non sono fissi sono fissi per l'altro ciclo. Fissato un r-ciclo $\alpha$ e un k-ciclo $\beta$ si deve verificare

$\{\alpha _{1},\ldots ,\alpha _{r}\}\cap \{\beta _{1},\ldots \beta _{k}\}\,=\,\{\emptyset \}$

I cicli disgiunti commutano: $\alpha \,\beta \,=\,\beta \,\alpha$. Ad esempio, in S₆ si ha (4 1 3)(2 5 6) = (2 5 6)(4 1 3).

Notazione ciclica, tipo o struttura ciclica, ordine

Adesso consideriamo un generico elemento $\alpha \in S_{n}$ con r cicli distinti e notazione ciclica

$\alpha =\alpha _{1}\,\alpha _{2}\cdots \alpha _{r}=\prod _{i=1}^{r}\,\alpha _{i}\qquad \sum _{i=1}^{r}\,1\cdot l_{i}=n$

dove $\alpha _{i}=(a_{1}^{i}\ a_{2}^{i}\ldots a_{l_{i}}^{i})\quad i=1,2...r$ è un generico l_i-ciclo, nell'ipotesi di cicli disgiunti $\alpha _{i}\cap \alpha _{j}=\{\emptyset \}\quad i\neq j\quad i,j=1...r$. L'ipotesi di cicli disgiunti viene utilizzata anche nel seguito.

La definizione generica del tipo di $\alpha \in Sn$ che si decompone in K_i numero di l_i-cicli, con la notazione $[1^{k_{1}}\ 2^{k_{2}}\ \ldots n^{k_{n}}]$, e dovendo essere ${\textstyle \sum \limits _{i=1}^{r}k_{i}l_{i}=n}$ ci saranno dei termini nulli. Una definizione analoga è quella di struttura ciclica, supponendo di ordinare i cicli con $l_{1}\geq l_{2}\cdots \geq l_{r}$, con la notazione $(l_{1},l_{2}\ldots l_{r})$. La notazione ciclica introdotta ha tipo o struttura ciclica $\left[{l_{1}}^{1}\ {l_{2}}^{1}\ \cdots {l_{r}}^{1}\right]$

La definizione dell'ordine di una permutazione $\alpha$ che denotiamo $o(\alpha )$ è:

${\alpha }^{o(\alpha )}\ =\ \underbrace {\alpha \ \alpha \cdots \alpha } _{o(\alpha )}\ =\ {\alpha }_{I}\ =\ (1)(2)\ldots (n)$

nel caso semplice di notazione ciclica con r cicli distinti vista all'inizio si dimostra essere

$o(\alpha )={\mbox{min }}(l_{1},\ l_{2}\ldots l_{r})$.

Con queste definizioni possiamo dare una rappresentazione estesa o notazione ciclica estesa di $\alpha \in S_{n}$ che ha tipo $\left[{l_{1}}^{k_{1}}\ {l_{2}}^{k_{2}}\ \cdots {l_{r}}^{k_{r}}\right]$:

$\alpha =\prod _{i=1}^{r}\left({\alpha _{1}}^{l_{i}}\cdots {\alpha _{k_{i}}}^{l_{i}}\right)\ =\ \prod _{i=1}^{r}\left(\prod _{j=1}^{k_{i}}\alpha _{j}^{l_{i}}\right)\qquad \sum _{i=1}^{r}\,k_{i}\cdot l_{i}=n$

dove un singolo ciclo ha la notazione ${\alpha _{k_{i}}}^{l_{i}}=({a_{1}}^{k_{i}}\ {a_{2}}^{k_{i}}\ \ldots {a_{l_{i}}}^{k_{i}})$

Esempi

1. I tipi di $S_{3}$ sono: $[1^{3}],\,[1^{1}\ 2^{1}],\,[3^{1}]$ e cioè $(a)(b)(c),\,(a)(b\ c),\,(a\ b\ c)\quad X=\{a,b,c\}$ e l'equazione delle classi $n_{1}+n_{2}+n_{3}=1+3+2=|S_{3}|=3!$ di cui il primo è l'identità.
2. La permutazione α pari ($\operatorname {sgn} (\alpha )\ =\ +1$), cioè decomponibile in un numero pari di 2-ciclo, definita dalla notazione

   $S_{5}\ni \alpha ={\begin{pmatrix}1&2&3&4&5\\4&2&1&3&5\end{pmatrix}}=(2)(5)(4\ 3\ 1)=(2)(5)(1\ 4\ 3)=(2)(5)(1\ 3)(1\ 4)$

   In notazione ciclica ha due 1-ciclo e un 3-ciclo. Il ciclo di lunghezza 3 si ottiene da α(1) = 4, α(4) = 3 e α(3) = 1, mentre i cicli di lunghezza 1 indicano che i punti 2 e 5 restano invariati. I cicli di lunghezza 1 indicano i punti fissi della permutazione f in X e, se non creano problemi d'interpretazione, vengono omessi. Denotiamo il 3-ciclo dalla (1 4 3), scritture equivalenti sono (4 3 1) o (3 1 4) partendo da un punto diverso. Quindi la permutazione α ammette le 3 scritture equivalenti:

   $\alpha =(1\ 4\ 3)=(4\ 3\ 1)=(3\ 1\ 4)$

   con struttura ciclica (3,1,1), ordine $o(\alpha )={\mbox{min }}(3,1,1)=3$ e tipo $[1^{2}\ 2^{0}\ 3^{1}\ 4^{0}\ 5^{0}]=[1^{2}\ 3^{1}]$ e vedremo che il numero dei coniugati o dello stesso tipo ha il valore

   $|Co(\alpha )|={\frac {n!}{\left(1^{k_{1}}\ 3^{k_{3}}\right)\left(k_{1}!\ k_{3}!\right)}}={\frac {5!}{\left(1^{2}\ 3^{1}\right)\left(2!\ 1!\right)}}={\frac {1\ 2\ 3\ 4\ 5\ }{\left(1\cdot 3\right)\left(2\cdot 1\right)}}=4\cdot 5\ =20.$

2-cicli o trasposizioni

I cicli di lunghezza 2 sono di particolare importanza. Il numero dei 2-cicli è esattamente ${\frac {n(n-1)}{2}}$ queste ultime permutazioni sono dette anche trasposizioni o scambi. Per $l\geq 2$ ogni l-ciclo $(a_{1}\cdots a_{l})$ è il prodotto di $(l-1)$ trasposizioni:

$(a_{1}\cdots a_{l})=(a_{1}a_{l})\cdots (a_{1}a_{2})\,\neq \,(a_{1}a_{2})\cdots (a_{1}a_{l})$

ricordo pure che $(a_{i}\ a_{j})=(a_{j}\ a_{i})\quad \forall \,i,j=1...l;\,i\neq j$ cioè commutano sempre.

Ritornando all'esempio si hanno $(l-1)=(3-1)=2$ trasposizioni con scritture equivalenti

${\begin{aligned}h&=(1\ 4\ 3)=(1\ 3)(1\ 4)\neq (1\ 4)(1\ 3)\\&=(4\ 3\ 1)=(1\ 4)(3\ 4)\neq (3\ 4)(1\ 4)\\&=(3\ 1\ 4)=(3\ 4)(1\ 3)\neq (1\ 3)(3\ 4)\\\end{aligned}}$

come si nota i fattori non sono unicamente determinati, ma il numero di fattori è sempre o pari o dispari. Il segno della nostra h è quindi $\epsilon (h)=(-1)^{r}=(-1)^{(l-2)}=(-1)^{1}=-1$ cioè una permutazione dispari, essendovi r=1 sola inversione

Proprietà dei cicli

• Segno (parità) di un elemento
• Potenze di un elemento
  Un ciclo di lunghezza L = k · m, preso alla k-esima potenza, si decomporrà in k cicli di lunghezza m. Per esempio, per (k = 2 ed m = 3),

  $(1~2~3~4~5~6)^{2}=(1~3~5)(2~4~6).$

• Elemento inverso
  Consideriamo un generico l-ciclo

  $\gamma =(m_{1}\cdots m_{l});\quad \gamma (m_{1})=m_{2}\,\gamma (m_{2})=m_{3}\ldots \gamma (m_{l})=m_{1}$

  ammette inverso

  ${\gamma }^{-1}=(m_{l}\cdots m_{1});\quad \gamma (m_{2})=m_{1}\,\gamma (m_{3})=m_{2}\ldots \gamma (m_{1})=m_{l}$

  $\gamma \circ \gamma ^{-1}=\gamma ^{-1}\circ \gamma =id$

  Adesso consideriamo un generico elemento $\alpha \in S_{n}$

  $\alpha =\gamma _{1}\,\gamma _{2}\cdots \gamma _{r}$

  dove $\gamma _{i}=(m_{1}\ m_{2}\ldots m_{i})\quad i=1,2...r$ è un generico i-ciclo, nell'ipotesi di cicli disgiunti $\gamma _{i}\cap \gamma _{j}=\{\emptyset \}\quad i\neq j\quad i,j=1...r$ allora

  $\alpha ^{-1}={\gamma _{1}}^{-1}\,{\gamma _{2}}^{-1}\cdots {\gamma _{r}}^{-1}$

  in particolare se $\alpha$ viene esplicitato con un numero r di 2-cicli
• Elemento coniugato
  Consideriamo un generico l-ciclo ${\textstyle \sigma =(s_{1}\ s_{2}\cdots s_{l})\in S_{n}}$. Un l-ciclo ammette la seguente proprietà di coniugazione con qualsiasi permutazione $\tau \in S_{n}$, questa proprietà è spesso utilizzata per ottenere gli elementi generatori del gruppo. Indichiamo con $\sigma ^{*}$ l-ciclo coniugato di $\sigma$.

  $\sigma ^{*}=\tau {\begin{pmatrix}s_{1}\cdots s_{l}\end{pmatrix}}\tau ^{-1}={\begin{pmatrix}\tau (s_{1})\cdots \tau (s_{l})\end{pmatrix}}$

  Ad esempio in S₃ consideriamo il 3-ciclo ${\textstyle \sigma =(1\ 2\ 3)}$, come τ consideriamo ancora un 3-ciclo cioè con la stessa struttura ciclica di σ, sia ${\textstyle \tau =(1\ 3\ 2)}$. Allora il coniugato σ^* rispetto il τ fissato ha valore:

  $\sigma ^{*}=\tau (\sigma )=(\tau (s_{1})\ \tau (s_{2})\ \tau (s_{3}))=(\tau (1)\ \tau (2)\ \tau (3))=(3\ 1\ 2)=(1\ 2\ 3)=\sigma$

  infatti τ e σ essendo già coniugati si ha $\sigma ^{*}\sigma {\sigma ^{*}}^{-1}=\sigma$. Generalizzando consideriamo s cicli di lunghezza l_i ciascuno, quindi con struttura ciclica $(l_{1},l_{2}\ldots l_{s})$ dove si considerano anche gli 1-ciclo, cioè:

  $\sigma =\prod _{i=1}^{s}\sigma _{i}=\prod _{i=1}^{s}(s_{1}^{i}\ s_{2}^{i}\ \ldots s_{l_{i}}^{i})\quad \sum _{i=1}^{s}l_{i}=|S_{n}|=n!$ essendo cicli disgiunti $\sigma _{i}\cap \sigma _{k}={\emptyset }\quad i\neq k\quad i,k=1,2,\ldots ,s$

  allora si ha per il coniugato rispetto τ, tale coniugato ha stessa struttura ciclica $(l_{1},l_{2}\ldots l_{s})$:

  $\sigma ^{*}=\tau \sigma {\tau }^{-1}=\prod _{i=1}^{s}\tau \sigma _{i}{\tau }^{-1}=\prod _{i=1}^{s}\tau (\sigma _{i})=\prod _{i=1}^{s}(\tau (s_{1}^{i})\ \tau (s_{2}^{i})\ \ldots \tau (s_{l_{i}}^{i}))$

  In notazione ciclica estesa di $\alpha \in S_{n}$ che ha tipo $\left[{l_{1}}^{k_{1}}\ {l_{2}}^{k_{2}}\ \cdots {l_{r}}^{k_{r}}\right]$, il numero dei coniugati o dello stesso tipo di $\alpha$ è:

  $|Co(\alpha )|={\frac {n!}{\left(k_{1}!\ {l_{1}}^{k_{1}}\right)\left(k_{2}!\ {l_{2}}^{k_{2}}\right)\cdots \left(k_{r}!\ {l_{r}}^{k_{r}}\right)}}={\frac {n!}{\left({l_{1}}^{k_{1}}\ {l_{2}}^{k_{2}}\cdots \ {l_{r}}^{k_{r}}\right)\left(k_{1}!\ k_{2}!\ \cdots k_{r}!\ \right)}}.$

  Ad esempio in S₅ consideriamo ${\textstyle \sigma =(1\ 2\ 3)(4\ 5)}$ con la struttura ciclica $(l_{1},l_{2})=(2,3)$ e fissiamo un elemento generico ${\textstyle \tau =(1\ 3\ 5\ 2\ 4)}$. Allora il coniugato σ^* rispetto il τ fissato ha valore:

  $\sigma ^{*}=\prod _{i=1}^{2}\tau (\sigma _{i})=\tau (1\ 2\ 3)\tau (4\ 5)=(\tau (1)\ \tau (2)\ \tau (3))(\tau (4)\ \tau (5))=(3\ 4\ 5)(1\ 2)=(1\ 2)(3\ 4\ 5)$

  variando τ tra i 5! elementi di S₅, si ottengono tutti i coniugati della classe di coniugazione $Co(\sigma )$ che ha ordine $|Co(\sigma )|=20$, cioè ci sono 20 elementi che hanno stessa struttura ciclica $(l_{1},l_{2})=(2,3)$ compresi i due analizzati.
• Decomposizioni di un elemento
  Vediamo i casi di decomposizione possibili.
  1. Ogni elemento di S_n può essere scritto come prodotto di cicli mutuamente disgiunti; questa rappresentazione è unica per qualsiasi ordine dei fattori, con la libertà di rappresentare ogni singolo ciclo scegliendone il punto di partenza. Questo è di facile dimostrazione. Tale decomposizione è commutativa. Ad esempio

     $g={\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}=(1\ 2\ 5)(3\ 4)=(3\ 4)(1\ 2\ 5)$

  2. Inoltre ogni ciclo si può decomporre anche come prodotto di trasposizioni (nella gran parte dei casi non disgiunte). Sebbene la scomposizione di un elemento di S_n in trasposizioni non sia unica e non è commutativa.

     $g=(1\ 5)(1\ 2)(3\ 4)=(1\ 2)(2\ 5)(3\ 4)=\ldots$

     In particolare può essere scritta come prodotto di trasposizioni adiacenti, cioè trasposizioni della forma (a a+1). Ad esempio, la permutazione g si può esplicitare come

     $g=(1\ 2)(2\ 5)(3\ 4)=(4\ 5)(3\ 4)(4\ 5)(1\ 2)(2\ 3)(3\ 4)(4\ 5)=\ldots$

     L'algoritmo di ordinamento bubble sort è un'applicazione di questo fatto. Anche la rappresentazione di una permutazione come prodotto di trasposizioni adiacenti non è univoca.

Trasposizioni, segno e il gruppo alterno

Una trasposizione abbiamo detto è una permutazione che scambia due elementi e mantiene fissi tutti gli altri; per esempio

$f={\begin{pmatrix}1&2&3&4&5\\3&2&1&5&4\end{pmatrix}}=(2)(1\ 3)(4\ 5)=\cdots$

(1 3) e (4 5) sono trasposizioni disgiunte o 2-cicli mentre (2) è 1-ciclo. Ogni permutazione può essere scritta come prodotto di trasposizioni; per esempio, la permutazione g

$g={\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}=(1\ 2\ 5)(3\ 4)=(1\ 2)(2\ 5)(3\ 4)=(1\ 5)(1\ 2)(3\ 4)=\cdots$

può essere scritta come composizione di 3 trasposizioni non disgiunte. Poiché si ha un prodotto di un numero dispari di trasposizioni, viene detta permutazione dispari, mentre f è una permutazione pari. La rappresentazione di una permutazione come prodotto di trasposizioni non è univoca come si nota dai $\cdots$; tuttavia, il numero di trasposizioni necessarie per rappresentare una data permutazione è sempre pari o sempre dispari. L'invarianza di questa parità è dimostrabile.

Il prodotto di due permutazioni pari è pari, il prodotto di due permutazioni dispari è pari e tutti gli altri prodotti sono dispari. Così possiamo definire il segno di una permutazione:

$\operatorname {sgn} f={\begin{cases}+1,&{\text{ }}f{\mbox{ pari}}\\-1,&{\text{ }}f{\text{ dispari}}.\end{cases}}$

Tabella Cayley

	+1	-1
+1	+1	-1
-1	-1	+1

Con questa definizione,

$\operatorname {sgn} \colon \mathrm {S} _{n}\rightarrow \{+1,-1\}\$

l'applicazione di S_n nel gruppo costituito da {+1,-1} munito dell'ordinario prodotto che manda un elemento in 1 se è ottenibile come prodotto di un numero pari di trasposizioni e in -1 se è ottenibile come prodotto di un numero dispari di trasposizioni è ben definita ed è un omomorfismo di gruppi. Le permutazioni la cui immagine è 1 si dicono permutazioni pari, dispari le altre. ({+1, −1} è un gruppo con la normale moltiplicazione, dove $id=+1$, cioè l'elemento neutro).

Il nucleo di tale omomorfismo (o equivalentemente l'insieme delle permutazioni pari) è detto gruppo alterno (o alternante) e si indica con A_n. Tale sottogruppo, avendo indice su S_n e ordine o numero di elementi per il teorema di Lagrange:

$i(An)\ =\ [S_{n}:A_{n}]\ =\ 2\qquad |A_{n}|={\frac {|S_{n}|}{i(A_{n})}}={\frac {n!}{2}}\,(n\geq 2)$

quindi è un sottogruppo normale. Allora ha significato il sottogruppo quoziente S_n / A_n consistente di tutte le permutazioni dispari. Si può dimostrare che il gruppo S_n è isomorfo al prodotto semidiretto di A_n e qualsiasi sottogruppo generato da una singola trasposizione.

Inoltre per n ≥ 5, A_n è un gruppo semplice non abeliano. Un'immediata conseguenza di ciò è che A_n non è risolubile e dunque, dato che un sottogruppo di un gruppo risolubile è risolubile, neanche S_n per n ≥ 5 può essere risolubile (è facile invece mostrare che S_n è risolubile per n ≤ 4).

Elementi speciali

Alcuni elementi del gruppo simmetrico che agisce sull'insieme X sono di particolare interesse (questi possono essere generalizzati al gruppo simmetrico di qualsiasi insieme finito ordinato totalmente, ma non a quello di un insieme non ordinato).

L'elemento di permutazione con inversione dell'ordine nella notazione 2-linea e ciclica:

${\begin{pmatrix}1&2&\cdots &n\\n&n-1&\cdots &1\end{pmatrix}}\ ={\begin{cases}(1\ n)(2\ n-1)\ldots \left({\frac {n+2}{2}}\right),&n{\text{ dispari}}\\(1\ n)(2\ n-1)\ldots \left({\frac {n}{2}}\ {\frac {n+2}{2}}\right),&n{\text{ pari}}\end{cases}}$

questo è l'unico elemento massimale rispetto all'ordine di Bruhat e l'elemento più lungo nel gruppo simmetrico rispetto al gruppo generatore costituito dalle trasposizioni adiacenti (i i+1), 1 ≤ i ≤ n − 1. Tale permutaione è un'involuzione, ed è formata da $\lfloor n/2\rfloor$ trasposizioni non-adiacenti

$(1\,n)(2\,n-1)\cdots ,\qquad {\text{ cioè }}\sum _{k=1}^{n-1}k={\frac {n(n-1)}{2}}{\text{ trasposizioni adiacenti: }}$

$(n\,n-1)(n-1\,n-2)\cdots (2\,1)(n-1\,n-2)(n-2\,n-3)\cdots ,$

quindi ha segno:

$\mathrm {sgn} (\rho _{n})=(-1)^{\lfloor n/2\rfloor }=(-1)^{n(n-1)/2}={\begin{cases}+1&n\equiv 0,1{\pmod {4}}\\-1&n\equiv 2,3{\pmod {4}}\end{cases}}$

che è 4-periodico in n.

In S_2n, l'elemento detto perfect shuffle è la permutazione che divide l'insieme in 2 pile e li interfoglia. Ha segno $(-1)^{\lfloor n/2\rfloor }.$

Da notare che la permutazione d'inversione di n elementi e il perfect shuffle di 2n elementi hanno stesso segno; questi sono importanti per la classificazione delle algebre di Clifford, che sono 8 periodiche.

Classi di coniugio

Le classi di coniugio di S_n corrispondono alle decomposizioni in cicli disgiunti; in altre parole, due elementi di S_n sono coniugati se e solo se le loro decomposizioni in cicli disgiunti consistono dello stesso numero di cicli della stessa lunghezza. Per esempio, tutti i prodotti di due 2-cicli e un 3-ciclo disgiunti sono coniugati, mentre un elemento che si ottiene come prodotto di un 2-ciclo e un 3-ciclo disgiunti non è mai coniugato a un elemento che si ottiene come prodotto di due 2-cicli disgiunti.

Omomorfismi con altri gruppi

I gruppi simmetrici $S_{n}$, per $n\in \mathbb {N}$, sono esempi di gruppi di Coxeter ed esempi di gruppi di riflessioni. Possono essere realizzati come gruppi di riflessioni rispetto agli iperpiani $x_{i}=x_{j},1\leq i<j\leq n$. Inoltre Il gruppo $S_{n}$ si può realizzare come gruppo quoziente del gruppi delle trecce $B_{n}$.

Uno dei motivi per cui sono particolarmente importanti i gruppi simmetrici è dato dal teorema di Cayley che afferma che ogni gruppo finito $G$ di ordine $n$ è isomorfo a un sottogruppo di $S_{n}$.

Esempi

Le tabelle di Cayley sono riferite ad una struttura geometrica. Quindi il simbolo ${C_{n}}^{i}$ indica rotazioni nel piano rispetto un punto fisso di ${\frac {2\pi i}{n}}$, mentre il simbolo $\sigma ^{j}$ indica riflessioni nel piano rispetto una j-retta.

Tabella Cayley 2*2

	${C_{2}}^{2}$	${C_{2}}$
${C_{2}}^{2}$	${C_{2}}^{2}$	${C_{2}}$
${C_{2}}$	${C_{2}}$	${C_{2}}^{2}$

Il gruppo S₂ con soli $2$ elementi (cardinalità $|S_{2}|\,=2!=2$), è isomorfo al gruppo ciclico $C_{2}$con due elementi, mentre A₂ è il sottogruppo composto dalla sola identità.

Il gruppo S₃ con $6$ elementi (cardinalità $|S_{3}|\,=3!=6$). Ha 3 sottogruppi normali: quello banale formato dalla sola identità, l'intero gruppo S₃ ed A₃ che si identifica con le 3 rotazioni di 120° nel piano e comprende l'identità (gruppo ciclico $C_{3}$). I tipi di cicli sono: (1)(2)(3)=e, (a b), (a b c). L'azione di gruppo sull'insieme dei vertici X = {1,2,3} viene detta simmetria e preserva la seguente struttura geometrica:

Triangolo equilatero

è isomorfo al gruppo diedrale di ordine 6 ($D_{3}$), cioè il gruppo delle riflessioni e delle rotazioni simmetriche di un triangolo equilatero, dato che queste simmetrie permutano i 3 vertici del triangolo. I 2-cicli corrispondono alle riflessioni mentre i cicli di lunghezza 3 alle rotazioni. Tale isomorfismo manda A₃ nel gruppo delle rotazioni del triangolo: dato che hanno 3 elementi, entrambi sono isomorfi al gruppo ciclico di 3 elementi.

$D_{3}$	$S_{3}$	rotazione/riflessione
${C_{3}}^{3}=id$	${\begin{pmatrix}1&2&3\\1&2&3\end{pmatrix}}=(1)(2)(3)$	${\frac {2}{3}}\pi \cdot 3$ (identità)
${C_{3}}$	${\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}}=(1\ 2\ 3)=(2\ 3\ 1)=(3\ 1\ 2)$	${\frac {2}{3}}\pi \cdot 1$
${C_{3}}^{2}$	${\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}}=(1\ 3\ 2)=(3\ 2\ 1)=(2\ 1\ 3)$	${\frac {2}{3}}\pi \cdot 2$
${\sigma }^{'''}$	${\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}}=(1)(2\ 3)=(1)(3\ 2)$	asse lato 23
${\sigma }^{''}$	${\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}}=(2)(1\ 3)=(2)(3\ 1)$	asse lato 13
${\sigma }^{'}$	${\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}}=(3)(1\ 2)=(3)(2\ 1)$	asse lato 12

Tabella Cayley per il prodotto o composizione e i sei elementi di simmetria del trinagolo equilatero.

Il gruppo di simmetria $S_{4}$ con $24$ elementi (cardinalità $|S_{4}|\,=4!=24$. Ha 4 sottogruppi normali propri: quello banale formato dalla sola identità, il gruppo di Klein V, vale a dire le trasposizioni pari $\{(1)(2)(3)(4),(1\ 2)(3\ 4),(1\ 3)(2\ 4),(1\ 4)(2\ 3)\}$ con quoziente S₃., l'intero gruppo S₄ ed A₄ che si identifica con le 4 rotazioni di 90° nel piano e comprende l'identità (gruppo ciclico $C_{4}$). I tipi di cicli sono: (1)(2)(3)(4), (a b), (a b c), (a b c d), (a b)(c d).L'azione del gruppo sull'insieme dei vertici X = {1,2,3,4} viene detta simmetria e preserva la seguenti strutture geometriche:

Tetraedro

Coincide con il gruppo di simmetrie del tetraedro ($T_{d}\cong S_{4}$) con $24$ simmetrie: ogni permutazione dei quattro vertici è infatti realizzata da un'unica simmetria. Tra queste, $12$ sono rotazioni intorno ad alcuni assi (cioè il sottogruppo normale $A_{4}\simeq C_{4}$ isomorfo al gruppo ciclico di ordine 4) , mentre le altre $12$ invertono l'orientazione dello spazio.

Cubo

è isomorfo al gruppo formato dalle 24 rotazioni proprie attorno ai $13$ assi di simmetria. Se consideriamo l'insieme dei vertici del tipo X = {1,2,3,4,5,6,7,8 } allora le 24 rotazioni sono sottogruppi di $S_{8}$. Mentre se consideriamo le quattro diagonali del cubo allora l'insieme X = {1,2,3,4 } e le 24 rotazioni sono descritte dal gruppo $S_{4}$. Infine se consideriamo i lati del cubo si ha X = {1,2,3,4,5,6,7,8,9,10,11,12} e le rotazioni sono sottogruppi di $S_{12}$. Il gruppo di simmetrie del cubo ($O_{h}$) è formato da $48$ simmetrie: oltre alle 24 rotazioni viste, vi sono 9 riflessioni essendovi 9 piani di simmetria e infine 15 operazioni di simmetria di roto-riflessione.

Quadrato

Un sottogruppo è costituito dal gruppo diedrale di ordine 8 ($D_{4}\leq S_{4}$), cioè il gruppo delle rotazioni e delle riflessioni simmetriche di un quadrato, infatti tali simmetrie permutano i 4 vertici del quadrato.

$D_{4}$	$S_{4}$	rotazione/riflessione
${C_{4}}^{4}=id$	${\begin{pmatrix}1&2&3&4\\1&2&3&4\end{pmatrix}}=(1)(2)(3)(4)$	${\frac {\pi }{2}}\cdot 4$ (identità)
${C_{4}}$	${\begin{pmatrix}1&2&3&4\\2&3&4&1\end{pmatrix}}=(1\ 2\ 3\ 4)=(2\ 3\ 4\ 1)=...$	${\frac {\pi }{2}}\cdot 1$
${C_{4}}^{2}$	${\begin{pmatrix}1&2&3&4\\3&4&1&2\end{pmatrix}}=(1\ 3)(2\ 4)=(2\ 4)(1\ 3)$	${\frac {\pi }{2}}\cdot 2$
${C_{4}}^{3}$	${\begin{pmatrix}1&2&3&4\\4&1&2&3\end{pmatrix}}=(1\ 4\ 3\ 2)=(4\ 3\ 2\ 1)=...$	${\frac {\pi }{2}}\cdot 3$
${\sigma }^{'}$	${\begin{pmatrix}1&2&3&4\\2&1&4&3\end{pmatrix}}=(1\ 2)(3\ 4)=(3\ 4)(1\ 2)$	asse lato 12,34
${\sigma }^{''}$	${\begin{pmatrix}1&2&3&4\\4&3&2&1\end{pmatrix}}=(1\ 4)(2\ 3)=(2\ 3)(1\ 4)$	asse lato 14,23
${\sigma }^{'''}$	${\begin{pmatrix}1&2&3&4\\3&2&1&4\end{pmatrix}}=(1\ 3)(2)(4)=(3\ 1)(2)(4)$	diagonale 24
${\sigma }^{iv}$	${\begin{pmatrix}1&2&3&4\\1&4&3&2\end{pmatrix}}=(2\ 4)(1)(3)=(4\ 2)(1)(3)$	diagonale 13

Tabella Cayley per la composizione e gli otto elementi di simmetria del quadrato.

Bibliografia

• Michael Artin, Algebra, Bollati Boringhieri, 1997, ISBN 88-339-5586-9.
• Israel Nathan Herstein, Algebra, Editori Riuniti, 2003, ISBN 88-359-5479-7.

Voci correlate

• Permutazione