PERMUTAZIONI


February 10, 2008
Dato un insieme X, le applicazioni bijettive dell’insieme in se stesso sono dette Permutazioni di un insieme:
{ } Γ (X ) = X →σ X |σ bijettiva

Se l’insieme è finito, un’applicazione dell’insieme in se stessa se è iniettiva è automaticamente surjettiva, e se è surjettiva è automaticamente iniettiva. Ma se l’insieme è infinito ciò non vale e quindi, in generale, bisogna prendere le applicazioni bijettive.

La composizione di due applicazioni iniettive (o surjettive o bijettive) è automaticamente un’applicazione iniettiva (o surjettiva o bijettiva, rispettivamente), perciò su Γ(x) è definita in modo naturale un’operazione di Composizione (binaria), cioè:

se σ,τ ∈ Γ (X ) ⇒ σ∘ τ ∈ Γ (X )

dove (σ∘τ ) (x) = σ(τ (x)). Allora si vede che l’operazione di Composizione (o Prodotto) in generale non è commutativa.

Es: sia X = {1,2,3}

( ) ( ) 1 2 3 1 2 3 2 3 1 ∘ 2 1 3

partiamo da destra:

( ) ( ) ( ) 1 2 3 1 2 3 1 2 3 2 3 1 ∘ 2 1 3 = 3 2 1

mentre

( ) ( ) ( ) 1 2 3 ∘ 1 2 3 = 1 2 3 2 1 3 2 3 1 1 3 2

Si ottengono due applicazioni diverse. Nei casi particolari in cui ad esempio la funzione è fatta da meno di tre elemtni, oppure se le due funzioni spostano elementi diversi, la composizione è commutativa.

Es:

( 1 2 ) ( 1 2 ) ( 1 2 ) 2 1 ∘ 1 2 = 2 1

( ) ( ) ( ) 1 2 1 2 1 2 1 2 ∘ 2 1 = 2 1

Es:

( ) ( ) ( ) 1 2 3 4 ∘ 1 2 3 4 = 1 2 3 4 2 1 3 4 1 2 4 3 2 1 4 3

( ) ( ) ( ) 1 2 3 4 1 2 3 4 1 2 3 4 1 2 4 3 ∘ 2 1 3 4 = 2 1 4 3

La permutazione di un dato insieme può sempre essere vista, se fa comodo, come la permutazione di un insieme più grosso. Basta pensare che gli elementi che non sono esplicitamente mossi stiano fermi.

Es:

( ) ( ) 1 2 3 ⇐ ⇒ 1 2 3 4 2 3 1 2 3 1 4

Poichè in generale la composizione di applicazioni è associativa, ciò vale anche per le permutazioni, cioè:

σ,τ,ρ ∈ Γ (X ) ⇒ (σ ∘τ)∘ ρ = σ ∘(τ ∘ ρ)

Es:

[( ) ( )] ( ) ( ) ( ) ( ) 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 2 3 1 ∘ 3 2 1 ∘ 1 3 2 = 1 3 2 ∘ 1 3 2 = 1 2 3

( ) [( ) ( ) ] ( ) ( ) ( ) 1 2 3 ∘ 1 2 3 ∘ 1 2 3 = 1 2 3 ∘ 1 2 3 = 1 2 3 2 3 1 3 2 1 1 3 2 2 3 1 3 1 2 1 2 3

Esistenza dell’Uno (elemento neutro rispetto alla composizione)

∀τ ∈ Γ (X ) ∃σ ∈ Γ (X )|σ∘ τ = τ

L’uno assoluto in teoria non esiste perchè a seconda dell’insieme su cui si effettua la permutazione, l’uno dovrà essere una permutazione di quell’insieme. Però, in base alla considerazione fatta secondo la quale gli elementi che non si scrivono sono considerati fermi, allora se prendessimo come uno quell’applicazione in cui non si scrive nulla, perchè tutto è lasciato fermo, allora va bene e si ha:

σ∘ 1 = 1∘ σ = σ

É l’applicazione identica dell’isieme X in se stesso, naturalmente dipendente dalla X.

Es:

( 1 2 3 ) ( 1 2 3 ) ( 1 2 3 ) ( 1 2 3 ) ( 1 2 3 ) 3 2 1 ∘ 1 2 3 = 3 2 1 = 1 2 3 ∘ 3 2 1

Per ogni permutazione, l’uno è unico.

Esistenza dell’Inversa

-1 -1 -1 σ : σ ∘ σ = 1 = σ ∘σ

Ciò è vero perchè un’applicazione bijettiva ammette un’inversa che è ancora bijettiva e la composizione con questa inversa, fatta a destra o a sinistra, è sempre l’applicazione identica che abbiamo chiamato 1.

Se si ha una permutazione, è semplice trovare l’applicazione inversa. Si capovolge la matrice, che può essere riordinata:

( 1 2 ... n )- 1 ( i1 i2 ... in ) i1 i2 ... in = 1 2 ... n

Es:

( ) ( ) ( ) 1 2 3 - 1 2 3 1 1 2 3 2 3 1 = 1 2 3 = 3 1 2

Es:

( ) ( ) f = 1 2 3 4 , g = 1 2 3 4 2 4 3 1 1 3 4 2

( 1 2 3 4 ) g ∘f = 3 2 4 1

( ) ( ) -1 1 2 3 4 - 1 1 2 3 4 f = 4 1 3 2 , g = 1 4 2 3

si verifica che:

( ) f- 1 ∘g-1 = 1 2 3 4 4 2 1 3

è l’inversa di g ∘ f.

Legge di Cancellazione

σ∘ τ = σ ∘ρ ⇒ τ = ρ

Nel caso dei reali positivi, la legge di cancellazione si dimostra moltiplicando ambedue i membri per l’inverso di σ, ma l’inverso di σ esiste anche nella composizione, per cui anche qui si può moltiplicare per σ-1. Da notare che il prodotto non è commutativo, quindi bisogna fare la legge di cancellazione da entrambe la parti. Poichè l’inverso si può comporre da entrambe le parti, anche qui la proprietà vale sia a destra sia a sinistra. Bisogna però fare attenzione ad una cosa: per cancellare bisogna avere σ dalla stessa parte. Quindi se σ ∘τ = σ ∘ρ ⇒ τ = ρ, se si ha τ ∘ σ = ρ ∘ σ ⇒ τ = ρ ma se si ha τ ∘ σ = σ ∘ ρ sarà ancora vero? Moltiplicando per σ-1 si ha che τ = σ ∘ ρ ∘ σ-1 e questo non vuol dire che τ = ρ.

Es:

( ) ( ) ( ) ( ) σ ∘ρ∘ σ-1 = 1 2 3 ∘ 1 2 3 ∘ 1 2 3 = 1 2 3 2 3 1 2 1 3 3 1 2 1 3 2

e ρ≠τ.

Gruppi di permutazioni

É possibile fare una permutazione anche su insiemi infiniti. Se si fissa una numerazione degli elementi x1, x2, x3, ..., xn allora le immagini saranno γx1, γx2,γx3, ..., γxn e la permutazione γ sarà:

( ) γ = x1 x2 ... xn γx1 γx2 ... γxn

Passando ad una indicizzazione, ogni permutazione su un insieme con n elementi può essere visto come la permutazione degli indici di questi elementi, quindi come la permutazione dei numeri da 1 a n e si ha:

( ) x1 x2 ... xn γ = γ1 γ2 ... γn

Infatti si parla spesso di permutazioni dei numeri da 1 a n perchè l’importante è rappresentare ciascun elemento dell’insieme con il numero, quindi se X = {1, 2, ..., n} allora Γ(X ) si scrive Γn.

Conclusioni

Poichè Γ(X) gode della proprietà associativa, possiede l’1, la funzione inversa ma non gode della commutatività, è un gruppo. Quindi il gruppo delle permutazioni è l’insieme delle permutazioni dotate dell’operazione binaria di composizione, dotata delle proprietà viste sopra.