Gruppi di trasformazioni

Definizione di permutazione

Definizione (100)

Sia $X$$X$ un insieme non vuoto e chiamiamo $S_{X}$$S_{X}$ l'insieme di tutte le applicazioni biettive (invertibili) di $X$$X$ in sé stesso, chiamate anche permutazioni o trasformazioni su $X$$X$. Il prodotto di due applicazioni biettive è ancora un'applicazione biettiva, quindi la coppia $(S_{X},\cdot )$$(S_{X},\cdot )$ è un gruppo. Il prodotto di applicazioni ha una legge di composizione interna all'insieme, è associativo e l'unità è l'identità. Questo è il gruppo totale o simmetrico sull'insieme $X$$X$.

 

Supponiamo che $X$$X$ sia finito e supponiamo che la sua cardinalità sia $n$$n$ allora il gruppo simmetrico ha ordine $n!$$n!$. In questo caso $S_{X}$$S_{X}$ si denota anche con $S_{n}$$S_{n}$.

Se chiamo $\sigma$$\sigma$ una permutazione di $S_{X}$$S_{X}$, allora la indico con

$${\begin{array}{cccc}a_{1}&a_{2}&\dots &a_{n}\\\downarrow &\downarrow &\downarrow &\downarrow \\b_{1}&b_{2}&\dots &b_{n}\end{array}}$$

$${\begin{array}{cccc}a_{1}&a_{2}&\dots &a_{n}\\\downarrow &\downarrow &\downarrow &\downarrow \\b_{1}&b_{2}&\dots &b_{n}\end{array}}$$

o anche $\sigma (a_{i})=b_{i}\,\forall i=1,n$$\sigma (a_{i})=b_{i}\,\forall i=1,n$.

Cicli

Consideriamo un tipo particolare di permutazione dette cicli.

Definizione (101)

Per ogni $r\geq 2$$r\geq 2$, si dice ciclo di lunghezza $r$$r$ una permutazione su $X$$X$ del tipo

$$\left({\begin{array}{ccccccc}c_{1}&c_{2}&\dots &c_{r}&c_{r+1}&\dots &c_{n}\\\downarrow &\downarrow &\downarrow &\downarrow &\downarrow &\downarrow &\downarrow \\c_{2}&c_{3}&\dots &c_{r+1}&c_{r+2}&\dots &c_{1}\end{array}}\right)$$

$$\left({\begin{array}{ccccccc}c_{1}&c_{2}&\dots &c_{r}&c_{r+1}&\dots &c_{n}\\\downarrow &\downarrow &\downarrow &\downarrow &\downarrow &\downarrow &\downarrow \\c_{2}&c_{3}&\dots &c_{r+1}&c_{r+2}&\dots &c_{1}\end{array}}\right)$$

.

 

Esempio (102)

$1\to 2,2\to 3,3\to 4,4\to 1,5\to 5$$1\to 2,2\to 3,3\to 4,4\to 1,5\to 5$.

 

Se ho una permutazione $\sigma \in S_{X}$$\sigma \in S_{X}$ e $a\in X$$a\in X$, ho due possibilità: $S(a)\neq a$$S(a)\neq a$ allora $\sigma$$\sigma$ muove $a$$a$, se $\sigma (a)=a$$\sigma (a)=a$ allora $\sigma$$\sigma$ fissa $a$$a$.

Permutazioni disgiunte

Definizione (103)

Due permutazioni $\sigma ,\tau \in S_{X}$$\sigma ,\tau \in S_{X}$ si dicono disgiunte se gli oggetti mossi da $\sigma$$\sigma$ sono fissati da $\tau$$\tau$. In questo caso, $\sigma \circ \tau =\tau \circ \sigma$$\sigma \circ \tau =\tau \circ \sigma$ (le due permutazioni non interferiscono sugli oggetti).

 

Proposizione (104)

Ogni permutazione $\sigma \in S_{n}$$\sigma \in S_{n}$ diversa dall'identità si può scrivere come prodotto di un numero finito di cicli a due a due disgiunti, univocamente determinati dalla permutazione $\sigma$$\sigma$ a meno dell'ordine dei fattori.

 

Dimostrazione

$\sigma \neq id$$\sigma \neq id$, prendo un oggetto $c_{1}$$c_1$ mosso da $\sigma$$\sigma$. Se $\sigma (c_{1})=c_{2}$$\sigma (c_{1})=c_{2}$, allora $c_{2}$$c_{2}$ potrebbe avere come immagine $c_{1}$$c_1$ e chiudere un ciclo di lunghezza $2$$2$, altrimenti potrebbe andare in $c_{3}$$c_{3}$. Poi $c_{3}$$c_{3}$ non può tornare in $c_{2}$$c_{2}$ perché $\sigma$$\sigma$ è biettiva. Allora $c_{3}\to c_{4}$$c_{3}\to c_{4}$. Non posso proseguire all'infinito perché si ha solo un numero finito di oggetti. Non posso tornare in $c_{2},c_{3},\dots ,c_{n-1}$$c_{2},c_{3},\dots ,c_{n-1}$ per la biettività di $\sigma$$\sigma$, allora si torna in $c_{1}$$c_1$ e si chiude un ciclo. Se tutti gli $n$$n$ oggetti sono terminati, la permutazione è un ciclo di lunghezza $n$$n$. Se alcuni oggetti sono rimasti fuori, la permutazione potrebbe fissarli tutti. Quindi gli elementi fissati non compaiono. Se c'è un altro elemento che viene mosso, si ripete il ragionamento e si ha un ciclo disgiunto dal precedente. Posso considerare $\sigma$$\sigma$ come il prodotto di cicli a due a due disgiunti, e gli elementi che non compaiono sono punti fissi.

 

Oltre alla scrittura in tabella, un ciclo di lunghezza $r$$r$, si può indicare come $(c_{1},c_{2},c_{r})$$(c_{1},c_{2},c_{r})$: questa scrittura indica che $\sigma (c_{1})=c_{2},\,\sigma (c_{2})=c_{r},\,\sigma (c_{r})=c_{1}$$\sigma (c_{1})=c_{2},\,\sigma (c_{2})=c_{r},\,\sigma (c_{r})=c_{1}$, cioè a destra di ogni elemento si mette la sua immagine mediante $\sigma$$\sigma$, e l'immagine dell'ultimo elemento scritto è il primo (il ciclo si chiude).

Usando la prima notazione su più righe, è inessenziale l'ordinamento della prima riga, ma è essenziale che sotto a ciascun elemento ci sia l'immagine.

Esempi di permutazioni di X

Per ogni ciclo ci sono $r$$r$ scritture del tipo $(c_{1},c_{2},c_{r})$$(c_{1},c_{2},c_{r})$.

Se $X$$X$ ha almeno due oggetti, le permutazioni sono l'identità $id$$id$ e la permutazione che scambia $1$$1$ con $2$$2$ ($S_{X}$$S_{X}$ ha ordine $2!$$2!$).

Definizione (105)

Un ciclo di lunghezza $2$$2$ si chiama scambio o trasposizione.

 

Esempio (106)

$S_{3}$$S_3$ ha $6$$6$ oggetti ($3!$$3!$): l'identità, tre scambi, un ciclo di lunghezzza 3 $(1,2,3)$$(1,2,3)$ e il suo inverso $(1,3,2)$$(1,3,2)$.

 

Esempio (107)

$S_{4}$$S_{4}$ ha $24$$24$ permutazioni. La struttura ciclica di una permutazione è la decomposizione in cicli disgiunti. Possiamo avere l'identità, $6$$6$ scambi (si calcolano facendo $3*4/2$$3*4/2$, perché ogni scambio ha due scritture possibili), $8$$8$ cicli di lunghezza $3$$3$, prodotti di due cicli disgiunti $(1,2)\circ (3,4)$$(1,2)\circ (3,4)$ che sono $3$$3$. Infine ci sono i cicli di lunghezza $4$$4$ che sono $6$$6$. La somma è $24$$24$.

 

Il risultato si può generalizzare con una formula complessiva.

Segno di una permutazione

Prendiamo una permutazione $\sigma$$\sigma$ e la scriviamo nel modo iniziale:

$$\sigma =\left({\begin{array}{cccc}a_{1}&a_{2}&\dots &a_{n}\\\downarrow &\downarrow &\downarrow &\downarrow \\b_{1}&b_{2}&\dots &b_{n}\end{array}}\right)$$

$$\sigma =\left({\begin{array}{cccc}a_{1}&a_{2}&\dots &a_{n}\\\downarrow &\downarrow &\downarrow &\downarrow \\b_{1}&b_{2}&\dots &b_{n}\end{array}}\right)$$

e definiamo segno di $\sigma$$\sigma$ la quantità $\delta _{\sigma }=\prod _{1\leq i<j\leq n}{\frac {b_{i}-b_{j}}{a_{i}-a_{j}}}$$\delta _{\sigma }=\prod _{1\leq i<j\leq n}{\frac {b_{i}-b_{j}}{a_{i}-a_{j}}}$ (faccio il prodotto di frazioni che hanno al numeratore $\sigma (a_{i})-\sigma (a_{j})$$\sigma (a_{i})-\sigma (a_{j})$ e al denominatore $a_{i}-a_{j}$$a_{i}-a_{j}$ per ogni coppia con $i<j$$i<j$). Ciascuno dei numeratori compare anche al denominatore a meno di un segno (sia gli $a_{i}$$a_{i}$ che i $b_{i}$$b_{i}$ appartengono a $X$$X$), quindi posso semplificare ciascun numeratore con il denominatore corrispondente a meno di un segno.

Definizione (108)

Chiamo $\delta _{s}$$\delta _{s}$ il segno.

 

Permutazioni pari e dispari

Definizione (109)

$\sigma$$\sigma$ è una permutazione pari se $\delta _{\sigma }=1$$\delta _{\sigma }=1$ e si dice dispari se $\delta _{\sigma }=-1$$\delta _{\sigma }=-1$.

 

Presa una qualsiasi permutazione $\tau$$\tau$, scritta come

$$\left({\begin{array}{cccc}b_{1}&b_{2}&\dots &b_{n}\\\downarrow &\downarrow &\downarrow &\downarrow \\c_{1}&c_{2}&\dots &c_{n}\end{array}}\right)$$

$$\left({\begin{array}{cccc}b_{1}&b_{2}&\dots &b_{n}\\\downarrow &\downarrow &\downarrow &\downarrow \\c_{1}&c_{2}&\dots &c_{n}\end{array}}\right)$$

Se considero il prodotto $\tau \circ \sigma$$\tau \circ \sigma$, applico prima $\sigma$$\sigma$ e poi $\tau$$\tau$, quindi $\tau \circ \sigma$$\tau \circ \sigma$ è la permutazione che manda $a_{1},a_{2},\dots ,a_{n}$$a_{1},a_{2},\dots ,a_{n}$ in $c_{1},c_{2},\dots ,c_{n}$$c_{1},c_{2},\dots ,c_{n}$. Il suo segno per definizione è uguale a $\prod _{1\leq i<j\leq n}{\frac {c_{i}-c_{j}}{a_{i}-a_{j}}}$$\prod _{1\leq i<j\leq n}{\frac {c_{i}-c_{j}}{a_{i}-a_{j}}}$

Se calcolo $\delta _{\tau }*\delta _{\sigma }=(\prod _{1\leq i<j\leq n}{\frac {c_{i}-c_{j}}{b_{i}-b_{j}}})*(\prod _{1\leq i<j\leq n}{\frac {b_{i}-b_{j}}{a_{i}-a_{j}}})$$\delta _{\tau }*\delta _{\sigma }=(\prod _{1\leq i<j\leq n}{\frac {c_{i}-c_{j}}{b_{i}-b_{j}}})*(\prod _{1\leq i<j\leq n}{\frac {b_{i}-b_{j}}{a_{i}-a_{j}}})$. Ciascun $b_{i}-b_{j}$$b_{i}-b_{j}$ che compare in $\delta _{\tau }$$\delta _{\tau }$ si semplifica con il corrispondente denominatore in $\delta _{\sigma }$$\delta _{\sigma }$ e il risultato è lo stesso.

Quindi il segno del prodotto $\delta _{\tau *\sigma }$$\delta _{\tau *\sigma }$ è uguale al prodotto dei segni $\delta _{\tau }*\delta _{s}$$\delta _{\tau }*\delta _{s}$.

Sottogruppo delle permutazioni pari

Si deduce immediatamente che l'insieme di tutte le permutazioni di segno $1$$1$ di $S_{n}$$S_{n}$ formano un sottogruppo. L'identità è pari, quindi l'insieme è non vuoto. L'insieme delle permutazioni pari è chiuso rispetto al prodotto, perché il prodotto tra permutazioni pari è pari. L'inverso di $\sigma$$\sigma$, chiamata $\sigma ^{-1}$$\sigma ^{-1}$ è pari. Questo sottogruppo si chiama gruppo alterno su $n$$n$ oggetti e si denota con ${\mathcal {a}}_{n}$${\mathcal {a}}_{n}$.

Il prodotto di due permutazioni dispari è pari, quindi le permutazioni dispari non formano un sottogruppo.

Il gruppo alterno ${\mathcal {a}}_{n}$${\mathcal {a}}_{n}$ ha ordine ${\frac {n!}{2}}$${\frac {n!}{2}}$ e anche le permutazioni dispari sono ${\frac {n!}{2}}$${\frac {n!}{2}}$

Segno di cicli

Osservazione (110)

preso il ciclo di lunghezza $2$$2$, $(c_{1},c_{2})$$(c_{1},c_{2})$ il segno è $-1$$-1$, perché $\delta _{C}={\frac {c_{1}-c_{2}}{c_{2}-c_{1}}}$$\delta _{C}={\frac {c_{1}-c_{2}}{c_{2}-c_{1}}}$.

 

Ogni ciclo di lunghezza $2$$2$ è dispari.

Sia $r\geq 2$$r\geq 2$, sia $C=(c_{1},c_{2},c_{r})$$C=(c_{1},c_{2},c_{r})$. Posso scrivere questo ciclo come prodotto di scambi non disgiunti, cioè come $(c_{1},c_{r})\circ (c_{1},c_{r-1})\circ \circ \circ (c_{1},c_{3})\circ (c_{1},c_{2})$$(c_{1},c_{r})\circ (c_{1},c_{r-1})\circ \circ \circ (c_{1},c_{3})\circ (c_{1},c_{2})$. Ogni termine compare in uno solo degli addendi.

Allora ogni ciclo di lunghezza $r$$r$ è prodotto di $r-1$$r-1$ scambi (non disgiunti) e con segno $-1$$-1$. Se $r-1$$r-1$ è pari, il ciclo è pari (moltiplicando $-1$$-1$ per sé stesso per un numero pari di volte ottengo $1$$1$), altrimenti è dispari.

Osservazione (111)

$\delta _{C}=(-1)^{r_{1}-1}$$\delta _{C}=(-1)^{r_{1}-1}$ se $C=(1,r_{1})$$C=(1,r_{1})$, cioè se il ciclo ha lunghezza $R_{1}$$R_1$.

 

Prendo una generica permutazione $\sigma$$\sigma$, un qualsiasi elemento di $S_{n}$$S_{n}$. Allora $\sigma =\sigma _{r_{1}}\circ \sigma _{r_{2}}\circ \dots \circ \sigma _{r_{t}}$$\sigma =\sigma _{r_{1}}\circ \sigma _{r_{2}}\circ \dots \circ \sigma _{r_{t}}$ per un certo $t$$t$. Sia questa la decomposizione di $\sigma$$\sigma$ nel prodotto di $t$$t$ cicli disgiunti di lunghezza $r_{1},r_{2},\dots ,r_{t}$$r_{1},r_{2},\dots ,r_{t}$. Il segno conserva il prodotto, quindi $\delta _{\sigma }=\delta _{\sigma _{r_{1}}}*\dots *\delta _{\sigma _{r_{t}}}$$\delta _{\sigma }=\delta _{\sigma _{r_{1}}}*\dots *\delta _{\sigma _{r_{t}}}$.

Ogni ciclo è prodotto di scambi e ogni scambio ha segno $-1$$-1$. Il ciclo di lunghezza $r_{1}$$r_1$ ha segno uguale a $(-1)^{r_{1}-1}$$(-1)^{r_{1}-1}$.

$$\delta _{\sigma }=(-1)^{(\sum _{i=1}^{t}r_{i})-t}$$

$$\delta _{\sigma }=(-1)^{(\sum _{i=1}^{t}r_{i})-t}$$

L'esponente è il numero totale di scambi di cui $\sigma$$\sigma$ è prodotto in base a questa formula.

$\delta _{s}=1$$\delta _{s}=1$ se l'esponente è pari, e quindi se è decomponibile in un numero pari di scambi non necessariamente disgiunti. $\sigma$$\sigma$ è dispari se l'esponente è dispari e quindi se è decomponibile nel prodotto di un numero dispari di scambi, non necessariamente disgiunti.

Una permutazione pari si può decomporre in infiniti modi, ma qualunque sia il modo, il numero degli scambi è sempre pari.

Prese tutte le permutazioni pari, se ad ognuna aggiungiamo lo scambio $(1,2)$$(1,2)$ otteniamo tutte permutazioni dispari e se ne ottengono altrettante. Quindi l'ordine del gruppo alterno è ${\frac {n!}{2}}$${\frac {n!}{2}}$