Permutazioni continuo a non capire
Buonasera,
Non riesco a capire come viene calcolato il prodotto dei cicli disgiunti e non.
Scusate ho trovato un altro thread, ma non riesco a capire i passaggi.
Esempio1:
In S7 il prodotto di cicli (non disgiunti)
p = ( 2 5 3 7)(1 4 3 6 7)(4 2 7 1)(3 5 4 6)
1 → 1 → 4 → 3 → 7 si parte dal primo elemento e lo si segue
7 → 7 → 1 → 4 → 4 si riparte dall'elemento a cui si era arrivati
4 → 6 → 6 → 7 → 2 si continua allo stesso modo
2 → 2 → 7 → 1 → 1 il ciclo si è chiuso perché si è ottenuto l'elemento di partenza.
3 → 5 → 5 → 5 → 3 l’elemento sta fermo
5 → 4 → 2 → 2 → 5 l’elemento sta fermo
6 → 3 → 3 → 6 → 6 l’elemento sta fermo
p = (1 7 4 2)(3)(5)(6) = (1 7 4 2)
Quale primo elemento e lo si segue cosa?
Cosa vuol dire che si parte da destra a sinistra?
Esempio2:
σ^2= σ ◦ σ = (1, 2, 3, 4, 5, 6, 7, 8)(1, 2, 3, 4, 5, 6, 7, 8) = (1, 3, 5, 7)(2, 4, 6, 8),
σ^3= σ ◦ σ^2 = (1, 2, 3, 4, 5, 6, 7, 8)(1, 3, 5, 7)(2, 4, 6, 8) = (1, 4, 7, 2, 5, 8, 3, 6),
Da dove deriva (1, 4, 7, 2, 5, 8, 3, 6) ?
Esempio3:
Sia S5 il gruppo delle permutazioni di 5 elementi e sia f = (1 3 2 4) ∈ S5
Si scriva f come prodotto di cicli di lunghezza 2?
Si calcolino f^2 = f ◦ f, f^3 = f^2 ◦ f, f^4 = f^3 ◦ f?
Non avendo capito come si effettua il prodotto non so come risolverlo.
Sulla wiki: http://it.wikipedia.org/wiki/Permutazione alla voce notazione abbiamo: "Alternativamente, si può codificare la stessa permutazione sfruttando il teorema enunciato sopra, scrivendola come prodotto di cicli. Nel nostro caso, otteniamo (1 2 5)(3 4)."
Con la notazione ciclica, due permutazioni possono essere composte in modo agevole: ad esempio (1 2 5)(3 4) e (1 2 3) danno (1 2 5)(3 4)(1 2 3) = (1 3 4)(2 5).
Si noti che composizione è fatta da sinistra verso destra, come si legge nelle lingue occidentali. Per esempio, per vedere in cosa viene mandato 1 dalla composizione (1 2 5)(3 4)(1 2 3) si vede che (1 2 5) lo manda in 2, (3 4) non muove 2, e infine (1 2 3) manda 2 in 3.
Continuo a non capire...qualche anima pia potrebbe spiegarmi meglio?
In generale, consiglierei questo link:
http://www.dti.unimi.it/citrini/FMD/dispense/Totale.pdf
Grazie!
Non riesco a capire come viene calcolato il prodotto dei cicli disgiunti e non.
Scusate ho trovato un altro thread, ma non riesco a capire i passaggi.
Esempio1:
In S7 il prodotto di cicli (non disgiunti)
p = ( 2 5 3 7)(1 4 3 6 7)(4 2 7 1)(3 5 4 6)
1 → 1 → 4 → 3 → 7 si parte dal primo elemento e lo si segue
7 → 7 → 1 → 4 → 4 si riparte dall'elemento a cui si era arrivati
4 → 6 → 6 → 7 → 2 si continua allo stesso modo
2 → 2 → 7 → 1 → 1 il ciclo si è chiuso perché si è ottenuto l'elemento di partenza.
3 → 5 → 5 → 5 → 3 l’elemento sta fermo
5 → 4 → 2 → 2 → 5 l’elemento sta fermo
6 → 3 → 3 → 6 → 6 l’elemento sta fermo
p = (1 7 4 2)(3)(5)(6) = (1 7 4 2)
Quale primo elemento e lo si segue cosa?
Cosa vuol dire che si parte da destra a sinistra?
Esempio2:
σ^2= σ ◦ σ = (1, 2, 3, 4, 5, 6, 7, 8)(1, 2, 3, 4, 5, 6, 7, 8) = (1, 3, 5, 7)(2, 4, 6, 8),
σ^3= σ ◦ σ^2 = (1, 2, 3, 4, 5, 6, 7, 8)(1, 3, 5, 7)(2, 4, 6, 8) = (1, 4, 7, 2, 5, 8, 3, 6),
Da dove deriva (1, 4, 7, 2, 5, 8, 3, 6) ?
Esempio3:
Sia S5 il gruppo delle permutazioni di 5 elementi e sia f = (1 3 2 4) ∈ S5
Si scriva f come prodotto di cicli di lunghezza 2?
Si calcolino f^2 = f ◦ f, f^3 = f^2 ◦ f, f^4 = f^3 ◦ f?
Non avendo capito come si effettua il prodotto non so come risolverlo.
Sulla wiki: http://it.wikipedia.org/wiki/Permutazione alla voce notazione abbiamo: "Alternativamente, si può codificare la stessa permutazione sfruttando il teorema enunciato sopra, scrivendola come prodotto di cicli. Nel nostro caso, otteniamo (1 2 5)(3 4)."
Con la notazione ciclica, due permutazioni possono essere composte in modo agevole: ad esempio (1 2 5)(3 4) e (1 2 3) danno (1 2 5)(3 4)(1 2 3) = (1 3 4)(2 5).
Si noti che composizione è fatta da sinistra verso destra, come si legge nelle lingue occidentali. Per esempio, per vedere in cosa viene mandato 1 dalla composizione (1 2 5)(3 4)(1 2 3) si vede che (1 2 5) lo manda in 2, (3 4) non muove 2, e infine (1 2 3) manda 2 in 3.
Continuo a non capire...qualche anima pia potrebbe spiegarmi meglio?
In generale, consiglierei questo link:
http://www.dti.unimi.it/citrini/FMD/dispense/Totale.pdf
Grazie!
Risposte
folgo , le permutazioni sono alla fine bigezioni su insiemi finiti.
quando tu scrivi
$p = ( 2 5 3 7)(1 4 3 6 7)(4 2 7 1)(3 5 4 6)$ stai componendo permutazioni che sono date dai cicli.
E la composizione, per convenzione,si effettua da destra verso sinistra.
Scriviti un po le singole permutazioni in forma matriciale e cerca un po di capire , componendo, il senso.
Per l'esercizio due, hai che $f = (1 3 2 4) in S_5$.
Scriverlo in cicli di lunghezza due significa scriverlo sottoforma di trasposizioni.
hai dunque che $f = (1,3)(1,2)(1,4)$.
Poi hai da calcolare $f^2 = f ◦ f, f^3 = f^2 ◦ f, f^4 = f^3 ◦ f$
Tieni in mente che $o(f) = 4$
Quindi è semplice dire che $f^4 = id$ . Mentre $f^3 = f^2 ◦ f = f^-1 = (1,4,2,3)$ (perché posso dire con sicurezza questo?)
Mentre $f^2 = f ◦ f = (1,2)(3,4)$. (qui ho composto due volte il ciclo)
Più chiaro adesso?
quando tu scrivi
$p = ( 2 5 3 7)(1 4 3 6 7)(4 2 7 1)(3 5 4 6)$ stai componendo permutazioni che sono date dai cicli.
E la composizione, per convenzione,si effettua da destra verso sinistra.
Scriviti un po le singole permutazioni in forma matriciale e cerca un po di capire , componendo, il senso.
Per l'esercizio due, hai che $f = (1 3 2 4) in S_5$.
Scriverlo in cicli di lunghezza due significa scriverlo sottoforma di trasposizioni.
hai dunque che $f = (1,3)(1,2)(1,4)$.
Poi hai da calcolare $f^2 = f ◦ f, f^3 = f^2 ◦ f, f^4 = f^3 ◦ f$
Tieni in mente che $o(f) = 4$
Quindi è semplice dire che $f^4 = id$ . Mentre $f^3 = f^2 ◦ f = f^-1 = (1,4,2,3)$ (perché posso dire con sicurezza questo?)
Mentre $f^2 = f ◦ f = (1,2)(3,4)$. (qui ho composto due volte il ciclo)
Più chiaro adesso?
Grazie per la risposta.
Sono un passo indietro.
Esempio 1:
1 2 3 4
2 3 1 4
E' un ciclo di lunghezza 3 (123), il 4 non cambia e non lo scrivo. Fin qui ci sono.
Allora:
La rappresentazione ciclica di una permutazione si ottiene partendo da
un elemento (generalmente 1) e scrivendo, alla sua destra, la sua immagine
(dunque (1 f(1)::)). Si prosegue ancora scrivendo a destra l'immagine di f(1)
e si ripete il procedimento fi no a quando si trova un elemento la cui immagine
è 1 e che chiude il ciclo (perche siamo sicuri che un tale elemento esiste ?).
Se tutti gli elementi sono presenti nel ciclo, abbiamo nito, altrimenti si apre
un nuovo ciclo con il primo elemento non presente in quello appena concluso.
Potresti spiegarmi i passaggi coi quali si trovano
1 2 3 4 5
3 4 2 5 1
E' un ciclo di lunghezza 5 (12345)
Il libro indica la seguente rappresentazione:
(1 3 2 4 5)
Partendo da 1 e scrivendo alla sua destra l'immagine
f(1)=3, f(2)=4, f(3)=2 e così via?
(3,4,*) ma è sbagliato..come fare nel trovare (1 3 2 4 5)?
Esempio 2:
Di seguito una rappresentazione ciclica:
1 2 3 4 5
3 5 1 2 4
(1 3)(2 5 4)
Ciclo di lunghezza 2, ma come faccio a trovare (1 3)(2 5 4)?
Grazie
Sono un passo indietro.
Esempio 1:
1 2 3 4
2 3 1 4
E' un ciclo di lunghezza 3 (123), il 4 non cambia e non lo scrivo. Fin qui ci sono.
Allora:
La rappresentazione ciclica di una permutazione si ottiene partendo da
un elemento (generalmente 1) e scrivendo, alla sua destra, la sua immagine
(dunque (1 f(1)::)). Si prosegue ancora scrivendo a destra l'immagine di f(1)
e si ripete il procedimento fi no a quando si trova un elemento la cui immagine
è 1 e che chiude il ciclo (perche siamo sicuri che un tale elemento esiste ?).
Se tutti gli elementi sono presenti nel ciclo, abbiamo nito, altrimenti si apre
un nuovo ciclo con il primo elemento non presente in quello appena concluso.
Potresti spiegarmi i passaggi coi quali si trovano
1 2 3 4 5
3 4 2 5 1
E' un ciclo di lunghezza 5 (12345)
Il libro indica la seguente rappresentazione:
(1 3 2 4 5)
Partendo da 1 e scrivendo alla sua destra l'immagine
f(1)=3, f(2)=4, f(3)=2 e così via?
(3,4,*) ma è sbagliato..come fare nel trovare (1 3 2 4 5)?
Esempio 2:
Di seguito una rappresentazione ciclica:
1 2 3 4 5
3 5 1 2 4
(1 3)(2 5 4)
Ciclo di lunghezza 2, ma come faccio a trovare (1 3)(2 5 4)?
Grazie
Definizione di ciclo
Sia $sigma in S_n$ una permutazione e sia $k in ZZ$ tale che $1<=k<=n$. $sigma$ è detto ciclo o k-ciclo o ciclo di lunghezza k se $EEc_1,c_2,...,c_k in X={1,2,3,4,...,n}$, a due a due disgiunti, tali che:
$sigma(c_1)=c_2, sigma(c_2)=c_3, sigma(c_3)=c_4,...,sigma(c_k)=c_1$ e $sigma(x)=x, AAx in X$ con $x!=c_1,c_2,c_3,...,c_k$
Sia $sigma in S_n$ una permutazione e sia $k in ZZ$ tale che $1<=k<=n$. $sigma$ è detto ciclo o k-ciclo o ciclo di lunghezza k se $EEc_1,c_2,...,c_k in X={1,2,3,4,...,n}$, a due a due disgiunti, tali che:
$sigma(c_1)=c_2, sigma(c_2)=c_3, sigma(c_3)=c_4,...,sigma(c_k)=c_1$ e $sigma(x)=x, AAx in X$ con $x!=c_1,c_2,c_3,...,c_k$
Preso da un altro sito. Mi e' stato utile per capire (finalmente!)
In un gruppo di permutazioni il prodotto è dato dalla composizione delle permutazioni medesime, quindi la permutazione A*B è la permutazione che si ottiene applicando prima B e poi A all'insieme {1, 2, 3, 4, 5}. La scrittura che hai per esempio per B, ovvero
1 2 3 4 5
2 1 5 3 4
ti dice che B manda 1 in 2 e 2 in 1, 3 in 5, 4 in 3 ed infine 5 in 4.
Per A invece, che è data come
1 2 3 4 5
5 1 4 3 2
si ottiene che manda 1 in 5, 2 in 1 e così via. Applicandole successivamente vedi che B manda 1 in 2, poi A manda 2 in 1, quindi A*B manda 1 in 1. Poi, B manda 2 in 1 e A manda 1 in 5, quindi A*B manda 2 in 5. Il 3 viene mandato da B in 5, che A manda in 2, perciò A*B manda 3 in 2. Il 4 va in 3 che viene mandato in 4, quindi A*B manda 4 in 4, ed infine il 5 viene mandato da B in 4, che A manda in 3, da cui si ottiene che A*B(5) = 3.
Dal ragionamento sopra vedi allora che puoi scrivere A*B come
1 2 3 4 5
1 5 2 4 3.
Un ciclo invece, come per esempio (1, 5, 6), è la scrittura compatta per scrivere la permutazione che manda 1 in 5, 5 in 6, 6 in 1 e lascia fisso tutto il resto. In S7 la puoi scrivere anche come
1 2 3 4 5 6 7
5 2 3 4 6 1 7.
Se hai un prodotto di cicli per calcolare il risultato in generale devi calcolare in ordine i prodotti come sopra. Se però i cicli sono disgiunti (ovvero i numeri che compaiono in un ciclo non compaiono in nessun altro, non come nell'esempio che hai messo tu, dove il 6 è sia nel primo che nel secondo ciclo) come per esempio in questo caso:
(1, 2, 3)(4, 5)(6, 7)
puoi scrivere direttamente la permutazione che è loro composizione e che è quella che manda 1 in 2, 2 in 3, 3 in 1, 4 in 5, 5 in 4, 6 in 7 e 7 in 6 e che puoi scrivere come
1 2 3 4 5 6 7
2 3 1 5 4 7 6
questo perchè cicli disgiunti commutano.
Per il procedimento inverso (ovvero per scrivere una permutazione come prodotto di cicli disgiunti) parti da un elemento e metti tutte le sue immagini successive finchè non torni dove sei partito, poi prendi un elemento che non compaia in questo ciclo e ripeti l'operazione finchè non hai esaurito i numeri. Per fare un esempio prendiamo la B della prima parte. B manda 1 in 2 e 2 in 1, siamo tornati al punto di partenza, quindi (1, 2) è il primo ciclo. Il 2 è già coperto dal ciclo appena trovato, quindi passiamo al 3: esso va in 5, che va in 4, che torna in 3. Di nuovo sei dove sei partito, perciò (3, 5, 4) è un altro ciclo. Non essendoci altri elementi, il procedimento finisce e B = (1, 2)(3, 5, 4).
Adesso vediamo il periodo: come in ogni gruppo il periodo n di una permutazione p è il più piccolo intero positivo n tale che p^n = id.
Se ci pensi un attimo vedi che il periodo di un ciclo, ovvero il numero di volte che lo devi applicare per tornare al punto di partenza, coincide col numero di elementi che compaiono nella sua scrittura: (1, 2) avrà periodo 2 e (3, 5, 4) 3 per esempio.
Data una qualsiasi permutazione p, il suo periodo sarà il minimo comune multiplo dei periodi dei cicli disgiunti in cui essa si decompone. Per fare un esempio sempre con B, B è prodotto di un 2-ciclo (periodo 2) e di un 3-ciclo (periodo 3), perciò avrà periodo mcm(2, 3) = 6.
In un gruppo di permutazioni il prodotto è dato dalla composizione delle permutazioni medesime, quindi la permutazione A*B è la permutazione che si ottiene applicando prima B e poi A all'insieme {1, 2, 3, 4, 5}. La scrittura che hai per esempio per B, ovvero
1 2 3 4 5
2 1 5 3 4
ti dice che B manda 1 in 2 e 2 in 1, 3 in 5, 4 in 3 ed infine 5 in 4.
Per A invece, che è data come
1 2 3 4 5
5 1 4 3 2
si ottiene che manda 1 in 5, 2 in 1 e così via. Applicandole successivamente vedi che B manda 1 in 2, poi A manda 2 in 1, quindi A*B manda 1 in 1. Poi, B manda 2 in 1 e A manda 1 in 5, quindi A*B manda 2 in 5. Il 3 viene mandato da B in 5, che A manda in 2, perciò A*B manda 3 in 2. Il 4 va in 3 che viene mandato in 4, quindi A*B manda 4 in 4, ed infine il 5 viene mandato da B in 4, che A manda in 3, da cui si ottiene che A*B(5) = 3.
Dal ragionamento sopra vedi allora che puoi scrivere A*B come
1 2 3 4 5
1 5 2 4 3.
Un ciclo invece, come per esempio (1, 5, 6), è la scrittura compatta per scrivere la permutazione che manda 1 in 5, 5 in 6, 6 in 1 e lascia fisso tutto il resto. In S7 la puoi scrivere anche come
1 2 3 4 5 6 7
5 2 3 4 6 1 7.
Se hai un prodotto di cicli per calcolare il risultato in generale devi calcolare in ordine i prodotti come sopra. Se però i cicli sono disgiunti (ovvero i numeri che compaiono in un ciclo non compaiono in nessun altro, non come nell'esempio che hai messo tu, dove il 6 è sia nel primo che nel secondo ciclo) come per esempio in questo caso:
(1, 2, 3)(4, 5)(6, 7)
puoi scrivere direttamente la permutazione che è loro composizione e che è quella che manda 1 in 2, 2 in 3, 3 in 1, 4 in 5, 5 in 4, 6 in 7 e 7 in 6 e che puoi scrivere come
1 2 3 4 5 6 7
2 3 1 5 4 7 6
questo perchè cicli disgiunti commutano.
Per il procedimento inverso (ovvero per scrivere una permutazione come prodotto di cicli disgiunti) parti da un elemento e metti tutte le sue immagini successive finchè non torni dove sei partito, poi prendi un elemento che non compaia in questo ciclo e ripeti l'operazione finchè non hai esaurito i numeri. Per fare un esempio prendiamo la B della prima parte. B manda 1 in 2 e 2 in 1, siamo tornati al punto di partenza, quindi (1, 2) è il primo ciclo. Il 2 è già coperto dal ciclo appena trovato, quindi passiamo al 3: esso va in 5, che va in 4, che torna in 3. Di nuovo sei dove sei partito, perciò (3, 5, 4) è un altro ciclo. Non essendoci altri elementi, il procedimento finisce e B = (1, 2)(3, 5, 4).
Adesso vediamo il periodo: come in ogni gruppo il periodo n di una permutazione p è il più piccolo intero positivo n tale che p^n = id.
Se ci pensi un attimo vedi che il periodo di un ciclo, ovvero il numero di volte che lo devi applicare per tornare al punto di partenza, coincide col numero di elementi che compaiono nella sua scrittura: (1, 2) avrà periodo 2 e (3, 5, 4) 3 per esempio.
Data una qualsiasi permutazione p, il suo periodo sarà il minimo comune multiplo dei periodi dei cicli disgiunti in cui essa si decompone. Per fare un esempio sempre con B, B è prodotto di un 2-ciclo (periodo 2) e di un 3-ciclo (periodo 3), perciò avrà periodo mcm(2, 3) = 6.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo