L'ordine di una permutazione

L'ordine di una permutazione è il numero minimo di volte che la permutazione deve essere applicata a se stessa per ritornare alla configurazione originale.

Per calcolare l'ordine di una permutazione devo seguire tre passi

• Scrivo la permutazione come prodotto di cicli disgiunti
• Conto la lunghezza di ogni ciclo
• Calcolo il minimo comune multiplo delle lunghezze dei cicli

Il minimo comune multiplo delle lunghezze dei cicli corrisponde all'ordine della permutazione.

Nota. A volte l'ordine di una permutazione è anche chiamato "periodo" di una permutazione. In questo caso viene preso in prestito un termine che si usa nelle funzione periodiche. Il significato è sempre lo stesso. Quindi, parlare di "ordine" o di "periodo" della permutazione è la stessa cosa.

Un esempio pratico

Prendo in considerazione una semplice permutazione in forma tabellare

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

In questa permutazione c'è un solo ciclo (1 2 3). In altre parole 1 va al posto di 2, 2 va al posto di 3 e 3 va al posto di 1.

Applicando questa permutazione tre volte, ovvero \(2, 3, 1 \rightarrow 3, 1, 2 \rightarrow 1, 2, 3\), si ritorna alla configurazione iniziale.

• Prima permutazione $$ \sigma_1 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} $$
• Seconda permutazione $$ \sigma_2 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} $$
• Terza permutazione $$ \sigma_3 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} = id $$

Dunque, l'ordine di questa permutazione è 3.

Esempio 2

Considero la permutazione seguente in forma tabellare

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

In questa permutazione ci sono due cicli.

Quindi, riscrivo la permutazione come prodotto di cicli disgiunti.

$$ (1 \ 3 \ 5 ) ( 2 \ 4 \ 6 ) $$

Per determinare l'ordine di una permutazione composta da cicli disgiunti, posso procedere così:

Trovo la lunghezza di ogni ciclo.

• Il primo ciclo \((1, 3, 5)\) ha lunghezza 3 perché 1→3, 3→5, 5→1.
• Il secondo ciclo \((2, 4, 6)\) ha anch'esso lunghezza 3 perché 2→4, 4→6→2.

Quindi, entrambi i cicli hanno ordine 3.

A questo punto calcolo il minimo comune multiplo delle lunghezze dei due cicli. Dal momento che entrambi i cicli hanno ordine 3, il minimo comune multiplo di 3 e 3 è sempre 3.

$$ mcm(3,3)=3 $$

Quindi, l'ordine della permutazione è 3. Questo significa che applicando la permutazione tre volte, ottengo nuovamente la sequenza originale.

Verifica. Faccio una rapida verifica calcolando tutte le permutazioni. $$ \sigma_1 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 4 & 5 & 6 &  1 & 2  \end{pmatrix} $$ $$ \sigma_2 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 5 & 6 & 1 & 2 & 3 & 4  \end{pmatrix} $$ $$ \sigma_3 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 2 & 3 & 4 & 5 & 6  \end{pmatrix} = 3 $$ Dopo tre applicazioni di questa permutazione, ogni elemento torna alla sua posizione iniziale. L'ordine della permutazione è effettivamente uguale a a 3.

Esempio 3

Considero una permutazione sui numeri [1 2 3 4 5 6] che per semplicità scrivo direttamente nella forma di cicli disgiunti

$$ (1 \ 2 \ 4)(3 \ 6) $$

La permutazione è composta da due cicli (1 2 4) e (3 6).

Nota. Nei cicli non è presente il numero 5. Questo vuole dire che si tratta di un punto fisso 5→5. In altre parole, questo elemento non cambia la propria posizione in ogni permutazione.

Calcolo le lunghezze dei due cicli disgiunti.

• Il ciclo (1 2 4) ha una lunghezza pari a 3 perché 1→2, 2→4, 4→1
• Il ciclo (3 6) ha una lunghezza uguale a 2 perché 3→6, 6→3.

Quindi, il primo ciclo ha lunghezza 3 mentre il secondo ha lunghezza 2.

Per trovare l'ordine della permutazione calcolo il minimo comune multiplo delle lunghezze dei due cicli.

$$ mcm(3, 2) = 6 $$

Pertanto, l'ordine della permutazione è 6.

Questo vuol dire che devo applicare sei volte la permutazione su se stessa per far tornare ogni elemento alla sua posizione iniziale.

Verifica. Faccio una rapida verifica calcolando tutte le permutazioni di $ (1 \ 2 \ 4)(3 \ 6) $ usando la notazione tabellare che ritengo poco sintetica ma più facile da comprendere. $$ \sigma_1 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 4 & 6 & 1 &  5 & 3  \end{pmatrix} $$ $$ \sigma_2 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 2 &  5 & 6  \end{pmatrix} $$ $$ \sigma_3 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 2 & 6 & 4 &  5 & 3  \end{pmatrix} $$ $$ \sigma_4 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 4 & 3 & 1 &  5 & 6  \end{pmatrix} $$ $$ \sigma_5 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 6 & 2 &  5 & 3  \end{pmatrix} $$ $$ \sigma_6 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 2 & 3 & 4 &  5 & 6  \end{pmatrix} = id $$ Dopo sei applicazioni della permutazione, si ritorna alla configurazione iniziale (identità) e ogni elemento torna alla sua posizione iniziale. Quindi, l'ordine della permutazione è uguale a a 6.

Esempio 4

In questo esempio provo a calcolare una permutazione più complessa dei numeri da 1 a 8.

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

Questa permutazione è composta da tre cicli disgiunti

Determino la lunghezza di ogni ciclo:

1. Il primo ciclo \((1 \  2 \ 3)\) ha lunghezza 3.
2. Il secondo ciclo \((4 \ 5)\) ha lunghezza 2.
3. Il terzo ciclo \((6 \ 7 \ 8)\) ha lunghezza 3.

L'ordine complessivo della permutazione è il minimo comune multiplo delle lunghezze dei cicli.

$$ mcm(3, 2, 3) = 6 $$

In conclusione, l'ordine della permutazione \((1 \ 2 \ 3)(4 \ 5)(6 \ 7 \ 8)\) è 6.

Questo significa che applicando la permutazione sei volte, ogni elemento tornerà alla sua posizione iniziale.

E così via.