Elementos de $S_n$ que no puede ser producto de transposiciones de $\leq n-2$

Question

Es bien sabido que cada elemento de a $S_n$ se puede escribir como un producto de en la mayoría de las $n-1$ transposiciones. Este teorema queda demostrado en todos los libros que tratan sobre la permutación de grupos. Pero, me parece que la siguiente pregunta natural es generalmente ni discutido ni poner en la Sección de Ejercicios en el libro.

Pregunta: ¿existe siempre un elemento en $S_n$ que no puede ser producto de $\leq n-2$ transposiciones? Podemos enumerar las ciclo-tipo de este tipo de elementos?

El natural supongo que sería el $n$-ciclos en $S_n$ serían los elementos que responder a la pregunta. Pero no podía demostrarlo. Me pueden ayudar? Una sugerencia sería también suficiente.

Answer 1

Si $\sigma \in S_n$ es una permutación, vamos a $f(\sigma)$ el número de ciclos en el ciclo de descomposición de $\sigma$, incluyendo el 1-ciclos como puntos fijos. Entonces para cualquier transposición $\tau = (i j)$,$f(\sigma\tau)=f(\sigma)\pm 1$, donde el signo es $+$ si $i$ $j$ están en el mismo ciclo en $\sigma$, e $-$ si se encuentran en diferentes ciclos en $\sigma$.

A partir de esto, y el hecho de que $f(id) = n$, se deduce que, si $\sigma$ es el producto de $\le n-2$ transposiciones, a continuación,$f(\sigma) \ge 2$. Desde $f($n del ciclo de$) = 1$, se deduce que un $n$-ciclo no es el producto de $\le n-2$ transposiciones.

Answer 2

Se nos nota en primer lugar de dos hechos simples.

1) Si $\sigma=(a_1 \ \ldots\ a_n)$ $n$- ciclo, a continuación, $\sigma(a_i \ a_j)$ es un producto de dos ciclos disjuntos, la suma de cuyas longitudes se $n$.

2) Si $\sigma=(a_1\ \ldots\ a_k)$ $\theta=(b_1 \ \ldots\ b_l)$ dos $k$ $l$ ciclos respectivamente, a continuación, $\sigma\theta(a_i\ b_j)$ $k+l$ ciclo.

Ahora supongamos que tenemos una $n$ciclo $\sigma$ que puede ser escrito como el producto de $t$ transposiciones $\tau_1,\ldots, \tau_t$ donde $t\leq n-2$.

Tenga en cuenta que, el uso de $(1)$$(2)$, podemos ver que $\sigma \tau_t\cdots\tau_{1}$ es un producto de no más de $t+1\leq n-1$ ciclos disjuntos, entonces la suma de cuyas longitudes se $n$. Así, en un ciclo entre estos ciclos disjuntos debe tener la longitud de, al menos,$2$, y por lo tanto, esta permutación es no trivial.

Por otro lado, la permutación $\tau_1\cdots\tau_t\cdot\tau_t\cdots \tau_1$ es claramente trivial.

Answer 3

Se puede demostrar que: Un elemento en $S_n$ se puede escribir como un producto de $\leq n-2$ transposiciones si y sólo si el elemento no es un $n$-ciclo. Así que la respuesta a su pregunta: sí, siempre hay elementos en $S_n$ que no puede ser escrito como un producto de $\le n-2$ transposiciones, y estos elementos son precisamente los $n$-ciclos.

Para demostrar la afirmación anterior, se puede examinar cómo el número de ciclos en una permutación de los cambios cuando componemos la permutación con una transposición. Si $g=(123)(45)(6) \in S_6$, entonces el número de ciclos en $g$$c(g)=3$. Usted puede trabajar ejemplos para ver que componen $g$ con cualquier transposición $(i,j)$ reduce el $c$ por 1 o aumenta el $c$ 1, según como si $i$ $j$ son diferentes o de la misma ciclos de $g$. Por ejemplo, componer $g$ $(14)$ combinación de los dos ciclos en $g$ que contienen 1 y 4, reduciendo $c$ 1, mientras que la composición de $g$ $(12)$ se divide el ciclo de $(123)$$g$, aumentando $c$ por 1.

Ahora, $g \in S_n$ es un producto $g=t_1 \cdots t_k$ de transposiciones iff $g t_k \cdots t_1$ es la identidad (recordemos que una transposición es su propia inversa). Por el argumento en el párrafo anterior, la composición de $g$ $k$ transposiciones puede reducir o aumentar el $c$ a la mayoría de los $k$. La identidad de permutación ha $c=n$. Tenemos que redactar un $n$-ciclo con transposiciones hasta llegar a la identidad de permutación. Empezando con un $n$ ciclo, que ha $c=1$, el número de transposiciones necesarias para dividir el $n$ ciclo en $n$ 1-ciclos (y por lo tanto aumentar el $c$$n$) es, al menos, $n-1$ (por el argumento en el párrafo anterior). Por lo tanto, una $n$-ciclo no puede ser expresado como un producto de menos de $n-1$ transposiciones.