OliForum Matematico

Salve a tutti, spero di non aver sbagliato sezione dove porre questa domanda:
se ogni permutazione può essere scritta come composizione di trasposizioni (in numero pari se la permutazione è pari e il contrario se è dispari),qual è il numero minimo di trasposizioni che occorrono per esprimere in questo modo la permutazione generica $\sigma$ ?
Sono riuscito solo a fare alcune considerazioni del tipo :
se ho una permutazione

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

allora il numero di permutazioni $n$ sarà sicuramente minore o uguale al numero di elementi "fuori posto" ossia sicuramente in questo caso $n<4$ (dato che solo il 2 è al suo posto); Come procedere?

Se non erro, il numero di trasposizioni dovrebbe essere esattamente il numero di elementi fuori posto: prima di tutto divido la permutazione in cicli (piccola spiegazione di cos'è un ciclo: è un insieme di elementi $i_1...i_k$ scelti tra gli $n$ insiemi da permutare tali che $\sigma(i_1)=i_2, \sigma(i_2)=i_3... \sigma(i_k)=i_1$. Questo ciclo è di lunghezza $k$). Puoi scrivere la permutazione come unione di cicli disgiunti, e notare che per scrivere un ciclo di lunghezza $k$ servono $k$ trasposizioni; i cicli di lunghezza $1$ sono i punti fissi che non scrivi, quindi il numero di trasposizioni è proprio il numero di elementi fuori posto (spero si capisca la spiegazione ).

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

Questa permutazione ha 6 elementi fuori posto, ma è chiaramente una permutazione dispari in quanto vi sono 7 inversioni. Inoltre si scrivere come prodotto di 5 trasposizioni. Quindi non è così, o sbaglio?

Non dovrebbe essere il numero di elementi meno il numero di cicli? Forse mi ricordo male.

gilgamesh ha scritto:$\sigma= \begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 \\
2 & 3 & 7 & 1 & 5 & 4 & 6
\end{pmatrix}$

Questa permutazione ha 6 elementi fuori posto, ma è chiaramente una permutazione dispari in quanto vi sono 7 inversioni. Inoltre si scrivere come prodotto di 5 trasposizioni. Quindi non è così, o sbaglio?

Ok, si in effetti ora che ci penso una per una cosa del genere:
$\sigma= \begin{pmatrix}
1 & 2 & 3 \\
2 & 3 & 1
\end{pmatrix}$
Bastano due trasposizioni invece di tre (cioé la terza segue dalle prime due), quindi se togli la trasposizione di troppo dovrebbe essere "elementi totali-punti fissi-# di cicli".
Poi non capisco a cosa tu ti stia riferendo alla prima parte con le permutazioni dispari e pari...cioè so cosa sono, ma non vedo come c'entrino.

Appena ho qualche minuto verifico la formula.Comunque mi riferisco al fatto che essendoci 6 elementi fuori posto , se il numero di trasposizioni necessarie fosse pari a 6 (come affermavi precedentemente) ci sarebbe un assurdo in quanto , dato che il numero di inversioni è dispari, la permutazione è dispari e non può essere scritta come un prodotto di un numero pari di trasposizioni.

karlosson_sul_tetto ha scritto:

gilgamesh ha scritto:$\sigma= \begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 \\
2 & 3 & 7 & 1 & 5 & 4 & 6
\end{pmatrix}$

Questa permutazione ha 6 elementi fuori posto, ma è chiaramente una permutazione dispari in quanto vi sono 7 inversioni. Inoltre si scrivere come prodotto di 5 trasposizioni. Quindi non è così, o sbaglio?

Ok, si in effetti ora che ci penso una per una cosa del genere:
$\sigma= \begin{pmatrix}
1 & 2 & 3 \\
2 & 3 & 1
\end{pmatrix}$
Bastano due trasposizioni invece di tre (cioé la terza segue dalle prime due), quindi se togli la trasposizione di troppo dovrebbe essere "elementi totali-punti fissi-# di cicli".
Poi non capisco a cosa tu ti stia riferendo alla prima parte con le permutazioni dispari e pari...cioè so cosa sono, ma non vedo come c'entrino.

Nel mio esempio io ho contato 2 cicli : $(4,1,2,3,7,6)$ e $ (5)$
si cui uno quindi è banale in quanto coincide con la permutazione identica. Per cui con questa formula "elementi totali-punti fissi-# di cicli" si ottiene $7-1-1$ (ho considerato il numero di cicli non banali). Dovrebbe andar bene?

Si, come dice anche Troleito, puoi pure considerare i punti fissi come cicli di lunghezza 1 semplificandoti la vita.

Che poi potrebbe anche andar bene a questo punto:

$p=\sum^{n}_{i=1} l_i -n $

dove $l_i=$ lunghezza del ciclo i-esimo, $n=$ numero di cicli non banali (con banali intendo permutazione identica), $p=$ numero di permutazioni cercato

Piccola dimostrazione: scriviamo \(\sigma\) come prodotto di cicli, e sia \((a_1 \ \ \ldots \ \ a_k)\) un ciclo generico di \(\sigma\). Si riesce a realizzare \(n-\#cicli\) (come giustamente dicevate) con l'identità \( (a_1 \ldots a_k ) = (a_1\ \ a_2) (a_1\ \ a_3) \ldots (a_1\ \ a_k)\). D'altronde non si può far meglio, perchè:
1. gli elementi \(a,b\) di ogni trasposizione \((a b)\) devono appartenere allo stesso ciclo;
2. Ogni trasposizione assegna l'immagine \(b\) all'elemento \(a\) e viceversa; possiamo "non cambiare" l'immagine di \(b\), in ogni ciclo, una volta sola, altrimenti la permutazione non sarebbe bigettiva.
Non so se è chiara!