Utente:Grasso Luigi/sandbox4/Permutazione ciclica

In matematica, e in particolare nella teoria dei gruppi, una permutazione ciclica è una permutazione formata da un singolo ciclo.In genere, una permutazione ciclica viene detta ciclo; se una permutazione ciclica ha l elementi, viene detta un l-ciclo. Alcuni autori danno una definizione estesa per includere permutazioni con punti fissi oltre al massimo un ciclo non banale (ma si possono avere più cicli non banali e il resto sono cicli banali). In notazione ciclica, le permutazioni sono esplicitate dalla lista dei loro elementi inclusi nelle parentesi, nell'ordine in cui sono permutati.

Ad esempio prendiamo un elemento del gruppo simmetrico $S_{4}$ che agisce su un generico insieme di elementi $X=\{1,\ 2,\ 3,\ 4\}\quad |X|=4$, la permutazione nella notazione ciclica (1 3 2 4) che manda 1→3, 3→2, 2→4 e 4→1 forma un 4-ciclo, mentre la permutazione (1 3 2)(4) che manda 1→3, 3→2, 2→1 e 4→4 forma un 3-ciclo per alcuni autori. D'altra parte, la permutazione (1 3)(2 4) che manda 1→3, 3→1, 2→4 e 4→2 non è una permutazione ciclica in quanto permuta le coppie {1, 3} e {2, 4}.

L'insieme degli elementi che non sono fissati da una permutazione ciclica viene detto orbita. Ogni permutazione su un numero finito di elementi può essere scomposta in permutazioni cicliche su orbite disgiunte.

Le singole parti cicliche di una permutazione vengono detti cicli, ritornando all'esempio abbiamo nel primo caso un 4-ciclo, nel secondo un 3-ciclo e un 1-ciclo (o punto fisso) e nel terzo caso ne abbiamo due del tipo 2-ciclo.

Definizione

Non esiste una definizione univoca di permutazione ciclica. Alcuni definiscono una permutazione $\sigma$ di un certo numero di elementi (insieme permutato ${\textstyle X=\{1,\ 2,\ \ldots n\}{\text{ con }}|X|=n}$) essere ciclica se l'applicazione successiva a ciascun elemento dell'insieme permutato porta alle posizioni di tutti gli altri elementi presenti, o, in modo analogo, se la sua rappresentazione in notazione ciclica consiste di un l-ciclo ($l\leqslant n$). Altri danno una definizione estesa che comprende i punti fissi o anche detti gli 1-ciclo.

Definizione ristretta

Un sottoinsieme non vuoto $S\subseteq X$ è un ciclo della permutazione $\sigma$ se la restrizione di $\sigma$ ad $S$ è una permutazione ciclica degli elementi di $S$. Se $X$ è finito, i suoi cicli sono disgiunti, e l'unione dà $X$. Cioè, formano una partizione, detta decomposizione ciclica di $\sigma .$ Quindi, secondo tale definizione, una permutazione di $\sigma$ è ciclica se e solo se $X$ è il suo unico ciclo.

Permutazione ciclica formata da un 8-ciclo.

Per esempio, la permutazione del gruppo simmetrico S₈, scritta in notazione ciclica e in notazione 2-linea (in due modi tra quelli possibili)

${\begin{aligned}\sigma \ &=(1\ 4\ 6\ 2\ 5\ 8\ 3\ 7)&=\\&={\begin{pmatrix}1&2&3&4&5&6&7&8\\4&5&7&6&8&2&1&3\end{pmatrix}}&=\\&={\begin{pmatrix}1&4&6&2&5&8&3&7\\4&6&2&5&8&3&7&1\end{pmatrix}}\end{aligned}}$

ha un 8-ciclo (vedi a destra).

Permutazione ciclica con definizione estesa:
due punti fissi (1-ciclo) e un 6-ciclo

Mentre nello stesso gruppo vi è l'elemento

${\begin{aligned}\sigma \ &=(1\ 4\ 6\ 8\ 3\ 7)(2)(5)&=\\&={\begin{pmatrix}1&2&3&4&5&6&7&8\\4&2&7&6&5&8&1&3\end{pmatrix}}&=\\&={\begin{pmatrix}1&4&6&8&3&7&2&5\\4&6&8&3&7&1&2&5\end{pmatrix}}\end{aligned}}$

ha un 6-ciclo e due 1-ciclo (vedi a destra). Alcuni autori considerano questa permutazione ciclica mentre altri no. In questo secondo caso si utilizza la definizione detta estesa.

Definizione estesa

Con la definizione estesa, esistono permutazioni cicliche che non consistono in un unico ciclo. Più formalmente, una permutazione $\sigma$ di un insieme di elementi X, è vista come funzione biiettiva

$\sigma \ :\ X\to X$

viene detta un ciclo se l'azione su X del sottogruppo generato da $\sigma$ ($S\subseteq X$), tale sottogruppo viene anche detta orbita, contiene più di un solo elemento. Questa nozione si utilizza di solito per un insieme X finito; quindi l'orbita più grande, S, è anche finita. Vediamo come è fatto $S$.

Sia $s_{0}\in S$, e poniamo $s_{i}\ =\sigma ^{i}(s_{0})$ per ogni $i\in \mathbf {Z}$. Se S è finito, allora si verifica

$\exists \ l\geqslant 1\ :\ s_{l}\ =\ s_{0}$.

Quindi $S=\{s_{0},s_{1},\ldots ,s_{l-1}\}$, e $\sigma$ si definisce come

${\begin{aligned}\sigma (s_{i})&=s_{i+1}&&\forall s_{i}\in S,&&0\leqslant i<l\\\sigma (x)&=x&&\forall x\in X\setminus S&&\\\end{aligned}}$

il secondo caso tiene conto di tutti i punti fissi per tutti gli elementi dell'insieme $X\setminus S$. Gli elementi non fissi per $\sigma$ seguono le relazioni

$s_{0}\mapsto s_{1}\mapsto s_{2}\mapsto \cdots \mapsto s_{l-1}\mapsto s_{l}=s_{0}$.

Una permutazione ciclica si scrive nella notazione ciclica

$\sigma =(s_{0}~s_{1}~\dots ~s_{l-1})$

e tenendo conto di tutto l'insieme $X$

$\sigma =(s_{0}~s_{1}~\dots ~s_{l-1})(x_{l})(x_{l+1})\ldots (x_{n})$

da notare che non vi sono virgole tra gli elementi, per evitare confusione con una l-upla). La lunghezza del ciclo è il numero di elementi della sua orbita maggiore. Un ciclo di lunghezza l viene detto l-ciclo.

L'orbita di un 1-ciclo dicesi punto fisso della permutazione, ma come da definizione estesa ogni 1-ciclo è un particolare caso della funzione detta permutazione identità:

${\begin{aligned}\sigma \colon X&\to X\\x&\mapsto \sigma (x)=x\\\end{aligned}}$

e nelle notazioni usuali

$\sigma _{I}\ =\ (1)(2)\ldots (n)\ =\ {\begin{pmatrix}1&2&3&\ldots &n\\1&2&3&\ldots &n\end{pmatrix}}$

Quando si utilizza la notazione ciclica, gli 1-ciclo vengono spesso omessi per evitare confusione.

Proprietà

Nel resto della pagina viene utilizzata la definizione estesa.

Uno dei risultati di base sui gruppi simmetrici è che qualsiasi permutazione può essere espressa come il prodotto di cicli disgiunti (più precisamente: cicli con orbite disgiunte); tali cicli commutano tra loro, e l'espressione della permutazione è unica a meno dell'ordine in cui sono messi i cicli. Il multiinsieme delle lunghezze dei cicli in questa espressione (il tipo di ciclo) è univocamente determinato dalla permutazione, e lo sono anche il segno e la classe di coniugio nel gruppo simmetrico.

Tra gli elementi del gruppo simmetrico S_n notevole importanza hanno gli l-cicli (con ${\textstyle 1\leq l\leq n}$), ossia gli elementi di S_n che hanno ordine l e che hanno esattamente n-l punti fissi.

• Il tipo o struttura ciclica nel caso di un singolo l-ciclo è semplicemente $\left[1^{(n-l)}\ {l}^{1}\right]=(1,\ldots ,1,l)$, mentre il loro numero si dimostra essere:

  $|Co(\sigma )|={\binom {n}{l}}(l-1)!\ ={\frac {n(n-1)\cdots (n-l+1)}{l}}\ ={\frac {n!}{(n-l)!\ l}}$

  che corrisponde al numero di elementi coniugati, cioè della classe di coniugio $Co(\sigma )$ con rappresentante $\sigma$ visto in precedenza.
  Una definizione analoga generalizzata si ha per il tipo $\left[{l_{1}}^{k_{1}}\ {l_{2}}^{k_{2}}\ \cdots {l_{r}}^{k_{r}}\right]=(l_{1},\ldots ,l_{1},\ l_{2},\ldots ,l_{2},\ \ldots ,l_{r},\ldots ,l_{r})$ :supponendo di ordinare i cicli con $l_{1}\leqslant l_{2}\cdots \leqslant l_{r}$.
• Il segno o anche detto parità di un l-ciclo

  $\operatorname {sgn} (\sigma )\ =\epsilon (\sigma )\ ={(-1)}^{(l-1)}={\begin{cases}+1\quad \sigma {\text{ pari}}\\-1\quad \sigma {\text{ dispari}}\\\end{cases}}$

  quindi se $l$ è dispari allora $\sigma$ è pari cioè si può ottenere come la composizione di un numero pari di 2-cicli e viceversa per $l$ pari.
  Nel caso generalizzato

  $\operatorname {sgn} (\sigma )\ ={[\operatorname {sgn} (\sigma _{1})]}^{k_{1}}\ {[\operatorname {sgn} (\sigma _{2})]}^{k_{2}}\cdots {[\operatorname {sgn} (\sigma _{r})]}^{k_{r}}$

• L'ordine di una permutazione che denotiamo $o(\sigma )$ si definisce come quel numero intero a cui elevare $\sigma$ per ottenere la permutazione identica, cioè:

  ${\sigma }^{\ o(\sigma )}\ ={\sigma }_{I}\ =(1)(2)\ldots (n)$

  e per un singolo ciclo $o(\sigma )=\operatorname {mcm} \ (1,\ l)=l$
  Nel caso generalizzato $o(\sigma )=\operatorname {mcm} \ (l_{1},l_{2}\ldots l_{r})$
• L'elemento inverso del ciclo $\sigma =(s_{0}~s_{1}~\dots ~s_{l-1})$ si dimostra essere sempre un l-ciclo con gli elementi messi in ordine inverso:

  $\sigma ^{-1}=(s_{l-1}~\dots ~s_{1}~s_{0})$.

  In particolare, essendo per una generica trasposizione

  $(s_{0}~s_{1})=(s_{1}~s_{0})\quad \forall s_{0},s_{1}\in X$, ogni 2-ciclo ha come inverso lo stesso ciclo.

  Nel caso generalizzato con r cicli distinti , poiché i cicli disgiunti commutano, l'inverso di un prodotto di cicli disgiunti è il risultato dell'inversione di ciascuno dei cicli separatamente, cioè:

  $\sigma ^{-1}=\left(\sigma _{1}\sigma _{2}\cdots \sigma _{r}\right)^{-1}={\sigma _{1}}^{-1}{\sigma _{2}}^{-1}\cdots {\sigma _{r}}^{-1}$

  e tenendo conto delle molteplicità, cioè $k_{1}$ cicli di tipo $l_{1}$-ciclo ... si ha

  $\sigma ^{-1}=\left(\sigma _{l_{1}1}\cdots \sigma _{l_{1}k_{1}}\right)^{-1}\left(\sigma _{l_{2}1}\cdots \sigma _{l_{2}k_{2}}\right)^{-1}\cdots \left(\sigma _{l_{r}1}\cdots \sigma _{l_{r}k_{r}}\right)^{-1}={\sigma _{l_{1}1}}^{-1}\cdots {\sigma _{l_{1}k_{1}}}^{-1}{\sigma _{l_{2}1}}^{-1}\cdots {\sigma _{l_{2}k_{2}}}^{-1}\cdots {\sigma _{l_{r}1}}^{-1}\cdots {\sigma _{l_{r}k_{r}}}^{-1}$

Trasposizioni (2-ciclo)

Un ciclo con soli due elementi viene detto una trasposizione.

Per esempio, la permutazione del gruppo simmetrico S₄

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

scambia 2 e 4. Essendo un 2-ciclo, viene scritta nella notazione abbreviata $\pi =(2,4)$.

Notazione postfissa di $P_{\pi }$
P_π * (1,2,3,4)^T = (1,4,3,2)^T

La matrice di permutazione $P_{\pi }$ corrispondente alla permutazione $\pi$, è

$P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\mathbf {e} _{\pi (3)}\\\mathbf {e} _{\pi (4)}\end{bmatrix}}={\begin{bmatrix}\mathbf {e} _{1}\\\mathbf {e} _{4}\\\mathbf {e} _{3}\\\mathbf {e} _{2}\end{bmatrix}}={\begin{bmatrix}1&0&0&0\\0&0&0&1\\0&0&1&0\\0&1&0&0\end{bmatrix}}=P_{\pi ^{-1}}$

viene pure detta matrice di trasposizione.

La stessa può essere rappresentata come trasformazione geometrica attiva nella forma di un quadrato, come a destra. Tale quadrato ha:

• gli 1 della matrice P_π rappresentati dalle caselle in rosso.
• i valori iniziali 1,2,3,4 da permutare sono i puntini neri nella diagonale principale
• le frecce curve indicano lo scambio tra 2 e 4 nella notazione postfissa o azione destra.

Da notare che $P_{\pi }=P_{\pi ^{-1}}$ cioè le due matrici coincidono e la notazione prefissa ha stessa rappresentazione come la postfissa e si differenzia solo per il verso delle frecce.

Proprietà

Qualsiasi permutazione può essere espressa come la composizione (prodotto) di trasposizioni: formalmente, sono generatori per il gruppo. In effetti, quando l'insieme che viene permutato è ${\textstyle X=\{1,\ 2,\ \ldots n\}{\text{ con }}|X|=n,\ n\in \mathbb {Z} }$, allora ogni permutazione può essere espressa come prodotti

$\sigma \ =(1~2)(2~3)(3~4)\cdots$.

Ciò segue perché una trasposizione arbitraria può essere espressa come il prodotto di trasposizioni adiacenti. Concretamente si può esprimere la trasposizione $(x~~y)\quad x<y$ muovendo $x$ a $y$ un passo alla volta, quindi spostando $y$ al punto in cui si trovava $x$, che scambia questi due e non apporta altre modifiche:

$(x~~y)=(x~~x+1)\cdot (x+1~~x+2)\cdots (y-1~~y)\cdot (y-2~~y-1)\cdots (x~~x+1)$

ad esempio

$(1~3)=(1~2)(2~3)(1~2)=(1~2~3)(1~2)$

$(1~4)=(1~2)(2~3)(3~4)(2~3)(1~2)=(1~2~3)(3~4)(2~3)(1~2)=(1~2~3~4)(2~3)(1~2)=(1~2~4)(1~2).$

La scomposizione di una permutazione in un prodotto di trasposizioni si ottiene seguendo i due passi:

• scrivendo la permutazione come prodotto di cicli disgiunti
  
  Metodo di calcolo decomposizione a cicli disgiunti :$\sigma \in S_{n}\quad \sigma \neq \sigma _{I}=(1)(2)\ldots (n)$

  Consideriamo i due insiemi

  ${\begin{aligned}\operatorname {X} &=\{1,2,\ldots ,n\}&&|\operatorname {X} |=n&&\\\operatorname {Fix} (\sigma )&=\{x\ |\sigma (x)=x\}=\bigcup _{j=r+1}^{s}X_{j}=\bigcup _{j=r+1}^{s}\{x_{j}\}\subseteq X&&|\operatorname {Fix} (\sigma )|=s-r&&r,s\in \mathbb {Z} \quad 1\leqslant r\leqslant s<n\\\end{aligned}}$

  Fatte queste premesse si opera nel seguente modo

  ${\begin{aligned}s_{11}&=\operatorname {min} \{X\setminus \operatorname {Fix} (\sigma )\}&&\exists l_{1}\in \mathbb {Z} ,\ l_{1}>1:{\sigma ^{l_{1}}(s_{11})}=s_{11}\in X_{1}=\{s_{11},\sigma (s_{11}),\ldots ,\sigma ^{l_{1}-1}(s_{11})\ \}&&\sigma _{1}=\left(s_{11}\ s_{12}\ \ldots \ s_{1l_{1}}\right)\\s_{21}&=\operatorname {min} \{X\setminus \left(X_{1}\operatorname {{\cup }\!\!\!{\cdot }\,} \operatorname {Fix} (\sigma )\right)\}&&\exists l_{2}\in \mathbb {Z} ,\ l_{2}>1:{\sigma ^{l_{2}}(s_{21})}=s_{21}\in X_{2}=\{s_{21},\sigma (s_{21}),\ldots ,\sigma ^{l_{2}-1}(s_{21})\ \}&&\sigma _{2}=\left(s_{21}\ s_{22}\ \ldots \ s_{2l_{2}}\right)\\\ldots &\ldots &&\ldots \ldots &&\ldots \ldots \\s_{r1}&=\operatorname {min} {\biggl \{}X\setminus \left({\overset {r-1}{\underset {i=1}{\operatorname {{\bigcup }\!\!\!\!{\cdot }\,} }}}\ X_{i}\ \operatorname {{\cup }\!\!\!{\cdot }\,} \operatorname {Fix} (\sigma )\right){\biggr \}}&&\exists l_{r}\in \mathbb {Z} ,\ l_{r}>1:{\sigma ^{l_{r}}(s_{r1})}=s_{r1}\in X_{r}=\{s_{r1},\sigma (s_{r1}),\ldots ,\sigma ^{l_{r}-1}(s_{r1})\ \}&&\sigma _{r}=\left(s_{r1}\ s_{r2}\ \ldots \ s_{rl_{r}}\right)\\\end{aligned}}$

  Ottenendo la decomposizione a cicli disgiunti

  $\sigma \ =\underbrace {\sigma _{1}\ \sigma _{2}\cdots \sigma _{r}\ } _{l_{i}{\mbox{-cicli}}}\underbrace {\sigma _{r+1}\sigma _{r+2}\cdots \sigma _{s}\ } _{1{\mbox{-ciclo}}}=\prod _{i=1}^{s}\sigma _{i}\qquad (s\ -\ r)+\sum _{i=1}^{r}l_{i}\ =\ n$

  Ad esempio la permutazione di $S_{8}$

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

  ammette una decomposizione a cicli disgiunti del tipo

  $\sigma \ =\ (1~2~3~4)(5~6~7~8)\ =\ (5~6~7~8)(1~2~3~4)$

  con l'insieme $\operatorname {Fix} (\sigma )=\{\emptyset \}$ cioè non ha punti fissi. Inoltre

  $X_{1}=\{1,2,3,4\},\ X_{2}=\{5,6,7,8\},\quad X_{1}\cap X_{2}=\{\emptyset \},\quad s=r=2$

• dividendo iterativamente ciascuno dei cicli di lunghezza 3 e più in un prodotto di una trasposizione e un ciclo di lunghezza uno in meno. Noi elenchiamo due modi per farlo, ma essi non sono unici. Segue il primo modo:

  ${\begin{aligned}(x_{1}~x_{2}~x_{3}~x_{4}~\ldots ~x_{l-1}~x_{l})&=(x_{1}~x_{2})\cdot (x_{2}~x_{3}~x_{4}~\ldots ~x_{l-1}~x_{l})\\&=(x_{1}~x_{2})\cdot (x_{2}~x_{3})\cdot (x_{3}~x_{4}~\ldots ~x_{l-1}~x_{l})\\&=\cdots \\&=(x_{1}~x_{2})\cdot (x_{2}~x_{3})\cdots (x_{l-1}~x_{l})\\\end{aligned}}$

  ciò significa che la richiesta iniziale è quella di spostare $x_{1}$ verso $x_{2},$ $x_{2}$ verso $x_{3},$ $x_{l-1}$ verso $x_{l},$ e infine $x_{l}$ verso $x_{1}.$
  
  Tale scrittura non è unica. Ad esempio si possono ruotare gli elementi mantenendo $x_{1}$ fisso eseguendo prima il fattore giusto (nella notazione operatore e seguendo le convenzioni sulle permutazioni): cioè muoviamo $x_{l}$ alla posizione iniziale di $x_{2},$ ottenendo il primo 2-ciclo, poi l'elemento $x_{l-1}$ ottenendo $(x_{1}\ x_{l})(x_{1}\ x_{l-1})=(x_{1}\ x_{l-1}\ x_{l})$ e proseguiamo con gli altri fino alla trasposizione $(x_{1}~x_{2}),$ eseguita per ultima, quindi indirizziamo $x_{l}$ dall'indice di $x_{2}$ per scambiare ciò che inizialmente erano $x_{1}$ e $x_{l}.$. Quello descritto è il secondo modo:

  ${\begin{aligned}(x_{1}~x_{2}~x_{3}~x_{4}~\ldots ~x_{l-1}~x_{l})&=(x_{1}~x_{l})\cdot (x_{1}~x_{2}~x_{3}~\ldots ~x_{l-1})\\&=(x_{1}~x_{l})\cdot (x_{1}~x_{l-1})\cdot (x_{1}~x_{2}~\ldots ~x_{l-2})\\&=\cdots \\&=(x_{1}~x_{l})\cdot (x_{1}~x_{l-1})\cdots (x_{1}~x_{2})\\\end{aligned}}$

  Continuando l'esempio iniziale otteniamo una decomposizione con 2-ciclo del tipo (per le due scritture analizzate tra le tante)

  $\sigma \ =\ \sigma _{1}\sigma _{2}=\ (1~2~3~4)(5~6~7~8)\ =\ (1~2)(2~3)(3~4)\ (5~6)(6~7)(7~8)=\ (1~4)(1~3)(1~2)\ (5~8)(5~7)(5~6)\ =\ \cdots$

  ogni 4-ciclo ha segno dispari infatti è formato da 3 trasposizioni, mentre il segno $\operatorname {sgn} (\sigma )=\epsilon (\sigma )=\operatorname {sgn} (\sigma _{1})\operatorname {sgn} (\sigma _{2})=(-1)(-1)=+1$ infatti si decompone in un numero pari di trasposizioni. Da notare che tale decomposizione non commuta perchè non abbiamo cicli disgiunti e può essere formata da scritture diverse (vedi puntini finali nella decomposizione di esempio).

Infatti, il gruppo simmetrico è un gruppo di Coxeter, nel senso che è generato da elementi di ordine 2 (le trasposizioni adiacenti), e tutte le relazioni hanno una certa forma.

Uno dei principali risultati sui gruppi simmetrici afferma che tutte le scomposizioni di una data permutazione in trasposizioni hanno o un numero pari oppure un numero dispari di trasposizioni. Ciò consente alla parità di una permutazione di essere un concetto ben definito.

Note

Libri con riferimenti

• (EN) John Fraleigh, A first course in abstract algebra, 5ª ed., Addison Wesley, 1993, ISBN 978-0-201-53467-2.}
• (EN) Joseph J. Rotman, A First Course in Abstract Algebra with Applications, 3ª ed., Prentice-Hall, 2006, ISBN 978-0-13-186267-8.
• (EN) Bruce E. Sagan, The Symmetric Group / Representations, Combinatorial Algorithms & Symmetric Functions, Wadsworth & Brooks/Cole, 1991, ISBN 978-0-534-15540-7.
• (EN) Thomas W. Hungerford, Algebra, 1ª ed., NY, Springer, 1984, DOI:/10.1007/978-1-4612-6101-8, ISBN 978-0-387-90518-1.

Libri

Postille

Bibliografia

• (EN) Anderson Marlow; Feil Todd, A First Course in Abstract Algebra, 2ª ed., Chapman & Hall/CRC, 2005, ISBN 1-58488-515-7.

Voci correlate

• Ordinamento ciclico

  un algoritmo di ordinamento basato sull'idea che la permutazione da ordinare può essere suddivisa in cicli, che possono essere ruotati individualmente per fornire un risultato ordinato

• Cicli e punti fissi
• Permutazione ciclica d'interi
• Notazione ciclica
• Permutazione circolare nelle proteine
• Algoritmo di Fisher–Yates
• Matrice trasposta