Come calcolare velocemente le classi di coniugio
Salve a tutti,
sia $H$ un sottogruppo di $S_n$ e supponiamo che $H \ne S_n$.
Supponiamo che $\sigma \in H$ e di voler calcolare la classe di coniugio di $\sigma$.
Domanda 1: esiste un metodo "veloce", cioè che non sia il calcolare tutti i prodotti del tipo $h \sigma h^-1$ per trovare la classe di coniugio di $\sigma$?
Quello che avevo pensato era di andare a vedere le permutazioni di $H$ con la stessa struttura ciclica di $\sigma$ e poi di verificare in qualche modo se fossero coniugate oppure no. Tuttavia mi sono sorti dei dubbi. Cerco di chiarire iil tutto con qualche esempio.
Esempio 1 (tratto dal Piacentini Cattaneo pag. 229)
Sia $a=(135)(27)$ e $a'=(317)(52)$ in $S_7$. Vogliamo trovare una $b\in S_7$ tale che $a'=bab^-1$.
Allora necessariamente $b$ deve "mandare $a$ in $a'$" nel senso che deve essere $b(1)=3,b(1)=3,b(5)=7,b(2)=5,b(7)=2$ e quindi $b$ deve essere del tipo
$ ( ( 1 , 2 , 3, 4 , 5 , 6 , 7 ),( 3 , 7 , 1 , , 7 , , 2 ) ) $
Di matrici di questo tipo in $S_7$ ce ne sono precisamente 2
$ ( ( 1 , 2 , 3, 4 , 5 , 6 , 7 ),( 3 , 7 , 1 , 4 , 7 ,6 , 2 ) ) $
$ ( ( 1 , 2 , 3, 4 , 5 , 6 , 7 ),( 3 , 7 , 1 , 6, 2 ,4 , 5 ) ) $
Domanda 2: con il sistema che ho illustrato sopra si trovano TUTTE le $b\in S_7$ tali che $a'=bab^-1$?
Secondo me no.
Consideriamo infatti $H \subset S_5$, $H=<(1234),(25)(34)>$. Si prova che $H$ è un sottogruppo di ordine $20$.
Vogliamo trovare la classe di coniugio di $(25)(34)$ che denotiamo con $C$.
Da calcoli vari viene fuori che tutti gli elementi "candidabili" a stare in $C$ sono:
$(2,5)(3,4), (1,2)(4,5), (1,3)(2,4), (1,4)(3,5), (1,5)(2,3)$
Naturalmente voglio evitare di fare tutti i prodotti. Cerco allora di capire se gli elementi di sopra possono effettivamente stare in $C$.
Prendiamo ad esempio l'elemento $(12)(45)$.
Se $(12)(45) \in C$ allora esiste $b \in H$ tale che $(12)(45)=b(2,5)(3,4)b^-1$.
Supponiamo, per assurdo, che il metodo che ho esposto sopra mi trovi tutti i $b$ siffatti.
Allora necessariamente
$ b= ( ( 1 , 2 , 3, 4 , 5 ),( 3 , 1 , 4 , 5 , 2 ) )=(13452) $
D'altra parte si può dimostrare (l'ho calcolato in Sage
) che $(13452)$ non sta in $H$.
Quindi dovrei dedurre che $(2,5)(3,4)$ non è coniugato di $(12)(45)$ che è assurdo!
Infatti da calcoli vari risulta
$C={ (1,2)(4,5), (1,5)(2,3), (1,3)(2,4), (2,5)(3,4), (1,4)(3,5)}$
sia $H$ un sottogruppo di $S_n$ e supponiamo che $H \ne S_n$.
Supponiamo che $\sigma \in H$ e di voler calcolare la classe di coniugio di $\sigma$.
Domanda 1: esiste un metodo "veloce", cioè che non sia il calcolare tutti i prodotti del tipo $h \sigma h^-1$ per trovare la classe di coniugio di $\sigma$?
Quello che avevo pensato era di andare a vedere le permutazioni di $H$ con la stessa struttura ciclica di $\sigma$ e poi di verificare in qualche modo se fossero coniugate oppure no. Tuttavia mi sono sorti dei dubbi. Cerco di chiarire iil tutto con qualche esempio.
Esempio 1 (tratto dal Piacentini Cattaneo pag. 229)
Sia $a=(135)(27)$ e $a'=(317)(52)$ in $S_7$. Vogliamo trovare una $b\in S_7$ tale che $a'=bab^-1$.
Allora necessariamente $b$ deve "mandare $a$ in $a'$" nel senso che deve essere $b(1)=3,b(1)=3,b(5)=7,b(2)=5,b(7)=2$ e quindi $b$ deve essere del tipo
$ ( ( 1 , 2 , 3, 4 , 5 , 6 , 7 ),( 3 , 7 , 1 , , 7 , , 2 ) ) $
Di matrici di questo tipo in $S_7$ ce ne sono precisamente 2
$ ( ( 1 , 2 , 3, 4 , 5 , 6 , 7 ),( 3 , 7 , 1 , 4 , 7 ,6 , 2 ) ) $
$ ( ( 1 , 2 , 3, 4 , 5 , 6 , 7 ),( 3 , 7 , 1 , 6, 2 ,4 , 5 ) ) $
Domanda 2: con il sistema che ho illustrato sopra si trovano TUTTE le $b\in S_7$ tali che $a'=bab^-1$?
Secondo me no.
Consideriamo infatti $H \subset S_5$, $H=<(1234),(25)(34)>$. Si prova che $H$ è un sottogruppo di ordine $20$.
Vogliamo trovare la classe di coniugio di $(25)(34)$ che denotiamo con $C$.
Da calcoli vari viene fuori che tutti gli elementi "candidabili" a stare in $C$ sono:
$(2,5)(3,4), (1,2)(4,5), (1,3)(2,4), (1,4)(3,5), (1,5)(2,3)$
Naturalmente voglio evitare di fare tutti i prodotti. Cerco allora di capire se gli elementi di sopra possono effettivamente stare in $C$.
Prendiamo ad esempio l'elemento $(12)(45)$.
Se $(12)(45) \in C$ allora esiste $b \in H$ tale che $(12)(45)=b(2,5)(3,4)b^-1$.
Supponiamo, per assurdo, che il metodo che ho esposto sopra mi trovi tutti i $b$ siffatti.
Allora necessariamente
$ b= ( ( 1 , 2 , 3, 4 , 5 ),( 3 , 1 , 4 , 5 , 2 ) )=(13452) $
D'altra parte si può dimostrare (l'ho calcolato in Sage
) che $(13452)$ non sta in $H$.Quindi dovrei dedurre che $(2,5)(3,4)$ non è coniugato di $(12)(45)$ che è assurdo!
Infatti da calcoli vari risulta
$C={ (1,2)(4,5), (1,5)(2,3), (1,3)(2,4), (2,5)(3,4), (1,4)(3,5)}$
Risposte
Ho pensato ulteriormente alla questione e ho elaborato una congettura. Ricapitolo brevemente la questione:
Problema: sia $H
Procedimento per ottenere le $c$ :
1. Si allineano $a,b$ rispettando la struttura ciclica in tutti i modi possibili, eventualmente scalando di un posto le permutazioni, per ottenere delle permutazioni incomplete.
Nell'esempio otterremo 6 permutazioni incomplete.
$ ( ( 1 , 2 , 3, 4 , 5 , ? ,? ),( 1 , 3 , 2 , 4 ,7 , ? , ? ) ) $
$ ( ( 1 , 2 , 3, 4 , 5 , ? ,? ),( 1 , 3 , 2 , 7 ,4 , ? , ? ) ) $
$ ( ( 1 , 2 , 3, 4 , 5 , ? ,? ),( 2 , 1 , 3 , 4 ,7 , ? , ? ) ) $
$ ( ( 1 , 2 , 3, 4 , 5 , ? ,? ),( 2 , 1 , 3 , 7 ,4 , ? , ? ) ) $
$ ( ( 1 , 2 , 3, 4 , 5 , ? ,? ),( 3 , 2 , 1 , 4 ,7 , ? , ? ) ) $
$ ( ( 1 , 2 , 3, 4 , 5 , ? ,? ),( 3 , 2 , 1 , 7 ,4 , ? , ? ) ) $
2. Si completano le permutazioni sostituendo i punti interrogativi, in tutti i modi possibili.
Nell'esempio otterremmo dalla prima permutazione
$ ( ( 1 , 2 , 3, 4 , 5 , 6 ,7 ),( 1 , 3 , 2 , 4 ,7 , 5 , 6 ) ) $
$ ( ( 1 , 2 , 3, 4 , 5 , 6 ,7 ),( 1 , 3 , 2 , 4 ,7 , 6 , 5 ) ) $
e quindi in totale avremmo, ragionando in modo analogo, 12 permutazioni complete.
L'insieme di tutte queste permutazioni sono le $c$ del ragionamento di sopra.
Ho verificato questa congettura in un paio di casi; in uno in particolare, avevo a che fare con un sottogruppo di $S_5$ di ordine $20$; applicando questo metodo sono riuscito a trovare le classi di coniugio in breve tempo. Sarebbe interessante capire se è stata una coincidenza oppure se la congettura è effettivamente vera in generale.
Problema: sia $H
Procedimento per ottenere le $c$ :
1. Si allineano $a,b$ rispettando la struttura ciclica in tutti i modi possibili, eventualmente scalando di un posto le permutazioni, per ottenere delle permutazioni incomplete.
Nell'esempio otterremo 6 permutazioni incomplete.
$ ( ( 1 , 2 , 3, 4 , 5 , ? ,? ),( 1 , 3 , 2 , 4 ,7 , ? , ? ) ) $
$ ( ( 1 , 2 , 3, 4 , 5 , ? ,? ),( 1 , 3 , 2 , 7 ,4 , ? , ? ) ) $
$ ( ( 1 , 2 , 3, 4 , 5 , ? ,? ),( 2 , 1 , 3 , 4 ,7 , ? , ? ) ) $
$ ( ( 1 , 2 , 3, 4 , 5 , ? ,? ),( 2 , 1 , 3 , 7 ,4 , ? , ? ) ) $
$ ( ( 1 , 2 , 3, 4 , 5 , ? ,? ),( 3 , 2 , 1 , 4 ,7 , ? , ? ) ) $
$ ( ( 1 , 2 , 3, 4 , 5 , ? ,? ),( 3 , 2 , 1 , 7 ,4 , ? , ? ) ) $
2. Si completano le permutazioni sostituendo i punti interrogativi, in tutti i modi possibili.
Nell'esempio otterremmo dalla prima permutazione
$ ( ( 1 , 2 , 3, 4 , 5 , 6 ,7 ),( 1 , 3 , 2 , 4 ,7 , 5 , 6 ) ) $
$ ( ( 1 , 2 , 3, 4 , 5 , 6 ,7 ),( 1 , 3 , 2 , 4 ,7 , 6 , 5 ) ) $
e quindi in totale avremmo, ragionando in modo analogo, 12 permutazioni complete.
L'insieme di tutte queste permutazioni sono le $c$ del ragionamento di sopra.
Ho verificato questa congettura in un paio di casi; in uno in particolare, avevo a che fare con un sottogruppo di $S_5$ di ordine $20$; applicando questo metodo sono riuscito a trovare le classi di coniugio in breve tempo. Sarebbe interessante capire se è stata una coincidenza oppure se la congettura è effettivamente vera in generale.
Se ho capito l'idea, sì funziona. L'idea è che vuoi esplicitare il fatto che mandare [tex]a[/tex] in [tex]b[/tex] significa mandare i cicli di [tex]a[/tex] nei cicli di [tex]b[/tex] della stessa lunghezza. Occhio però, che naturalmente se ti trovi cicli della stessa lunghezza in [tex]a[/tex] (e [tex]b[/tex]) allora quando li allinei devi scambiarli tra loro in tutti i modi possibili.
Insomma, quello che sostieni è, secondo me, che nei casi piccoli i conti si possono fare a mano. Il problema è che in casi grandi (cioè generali) non si possono fare i conti a mano. Per esempio, se ti chiedessi di caratterizzare il fatto che due permutazioni pari con la stessa struttura ciclica siano coniugate nel gruppo alterno, come faresti? Non potresti certo (così mi pare) applicare il tuo metodo. Per la cronaca, ecco la caratterizzazione:
Mi spiego meglio: la complessità di un algoritmo che decida se due elementi in un dato gruppo finito sono coniugati non migliora (sembra non migliorare) se ci restringiamo ai sottogruppi dei gruppi simmetrici, perché tutti i gruppi sono sottogruppi dei gruppi simmetrici.
Insomma, quello che sostieni è, secondo me, che nei casi piccoli i conti si possono fare a mano. Il problema è che in casi grandi (cioè generali) non si possono fare i conti a mano. Per esempio, se ti chiedessi di caratterizzare il fatto che due permutazioni pari con la stessa struttura ciclica siano coniugate nel gruppo alterno, come faresti? Non potresti certo (così mi pare) applicare il tuo metodo. Per la cronaca, ecco la caratterizzazione:
Aggiungo una cosa: non c'è molta speranza di trovare un procedimento algoritmico "veloce" perché per il teorema di Cayley ogni gruppo finito si immerge in un qualche gruppo simmetrico. Quindi che un gruppo sia sottogruppo di [tex]S_n[/tex] per qualche [tex]n[/tex] non è che sia una gran novità
Mi spiego meglio: la complessità di un algoritmo che decida se due elementi in un dato gruppo finito sono coniugati non migliora (sembra non migliorare) se ci restringiamo ai sottogruppi dei gruppi simmetrici, perché tutti i gruppi sono sottogruppi dei gruppi simmetrici.
"Martino":
Insomma, quello che sostieni è, secondo me, che nei casi piccoli i conti si possono fare a mano
Più che altro, il problema è che nel passare da gruppi di ordine 10 o 12 a gruppi di ordine 25-30 c'è una grande differenza, a livello di conti a mano. In particolare il mio prof. ogni tanto ci spara negli scritti qualche gruppo di ordine intorno ai 20 : in questi casi il metodo che ho illustrato consente di risparmiare parecchio tempo, rispetto al metodo "brutale" di calcolare tutti i prodotti. Certamente concordo con te sul fatto che in generale i conti non si possono fare "a mano"-
Tutte le altre osservazioni che ha i fatto sono molto interessanti. Grazie.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo