¿Es cualquier transposición producto de transposiciones simples?

Question

¿Es cualquier transposición producto de transposiciones simples? En caso afirmativo, ¿cómo puede usted probar esto?

Answer 1

Cada elemento de a $S_n$ se puede escribir como un producto de simples transposiciones. Este hecho puede ser probado por inducción en $n$.

Como un primer paso, demostrar que $(1,m)$ es siempre un producto de la simple transposición de la inducción de la $m$. El caso de $m = 2$ es trivial, por lo que asumimos que el $(1,m-1)$ es un producto de la simple transposición. Pero $(1,m) = (m-1,m)(1,m-1)(m-1,m)$, lo $(1,m)$ es un producto de la simple transposición.

Ahora nos muestran que todas las transposiciones en $S_n$ son producto de transposiciones de la forma $(1,m)$. El caso de $n = 2$ es trivial, por lo que asumimos que cualquier transposición de $S_{n-1}$ es un producto. Dada la transposición $t$, se deben tener algunas $m$, posiblemente $1$ que intercambia la posición con 1. Si llevamos a cabo la transposición $(1,m)$, sólo tenemos $n-1$ posiciones de izquierda a permutar, que se puede hacer con simples transposiciones por la hipótesis inductiva. Esto completa la prueba.

Answer 2

Existe un algoritmo que toma una permutación y escribe como producto de transposiciones simples. Se llama ordenamiento de burbuja.

Qué es: Si $f(i) > f(i+1)$, escriba $f$ = $f' \circ (i,i+1)$. Repita en $f'$ hasta la identidad y se quedan con un producto de la simple transposición.

Answer 3

Sí. Una manera de ver esto es darse cuenta de lo que sucede cuando usted conjuga transposiciones por transposiciones. Por ejemplo, que usted puede conseguir un paso más cerca a una transposición simple de $(5,6)(3,6)(5,6)=(3,5)$ $(3,6)$ $(3,5)$ muestra, por conjugar en $(5,6)$. Entonces $(4,5)(3,5)(4,5)=(3,4)$, por lo que hemos conseguido a una transposición simple después de $2$ conjugaciones. Para escribir $(3,6)$ como producto de transposiciones simples, simplemente puede relajarse esto: $(3,6)=(5,6)(4,5)(3,4)(4,5)(5,6)$.