cómo encontrar la raíz de la permutación

Question

Observe que $$\bigl(\begin{smallmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 1 & 5 & 3 \end{smallmatrix}\bigr)* \bigl(\begin{smallmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 1 & 5 & 3 \end{smallmatrix}\bigr) = \bigl(\begin{smallmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 2 & 3 & 1 \end{smallmatrix}\bigr),$$

así que $\bigl(\begin{smallmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 2 & 3 & 1 \end{smallmatrix}\bigr)$ es el cuadrado de una permutación. En términos más generales, ¿cómo puedo comprobar si una permutación es cuadrada y cómo puedo encontrar su raíz?

Answer 1

Cualquier permutación puede escribirse como un producto de ciclos disjuntos $\sigma = c_1\cdot\ldots\cdot c_n$ . Porque los ciclos disjuntos conmutan, $\sigma^2 = c_1^2\cdot\ldots\cdot c_n^2$ .

Así que una permutación cuadrada es aquella que consiste en un producto de ciclos cuadrados disjuntos. Ahora bien, ¿cuándo un ciclo es cuadrado? Si $c=(i_1 i_2\ldots i_k)$ , entonces c^2 toma $i_1$ a $i_3$ , $i_2$ a $i_4$ y así sucesivamente. En otras palabras:

Si $k$ es impar, $c^2$ es otro $k$ -ciclo, lo que significa que cada $k$ -el ciclo es un cuadrado.

Si $k$ es par, entonces $c^2=(i_1i_3\ldots i_{k-1})(i_2i_4\ldots i_{k})$

Por lo tanto: una permutación es un cuadrado si y sólo si el número de ciclos de cualquier longitud par en su descomposición de ciclos disjuntos es par, y el algoritmo que se puede utilizar para encontrar su raíz es el siguiente:

1. Encuentra las raíces de todos los ciclos Impares, $\sqrt{c} = (i_1 i_{(k+1)/2} i_2 i_{(k+3)/2} \ldots i_k i_{(k-1)/2})$
2. Tomar parejas $c=(i_1\ldots i_k),d=(j_1\ldots j_k)$ de los ciclos pares de la misma longitud y construir $\sqrt{c,d} = (i_1j_1\ldots i_kj_k)$

Su permutación es un ejemplo de un ciclo impar con una raíz que coincide con lo que seguiría este método.

Answer 2

Una permutación $\sigma \in S_n$ tiene una representación única como producto de ciclos disjuntos. Demostramos que $\sigma$ tiene una raíz cuadrada en $S_n$ si y sólo si el número de ciclos de igual longitud par en la representación es par (o cero). Esta condición es necesaria porque el cuadrado de un ciclo de longitud par $2k$ se divide en dos ciclos disjuntos de longitud $k$ y los cuadrados de los ciclos de longitud impar tienen longitud impar.

Tu ejemplo de permutación es un ciclo impar, y por tanto no tiene ciclos de longitud par. Por lo tanto, satisface la condición. Otro ejemplo sería $(12)(34)(567)$ que tiene dos ciclos de longitud $2$ y no hay ciclos de longitudes pares de otras longitudes.

Para que un algoritmo encuentre la raíz cuando $\sigma \in S_n$ satisface la condición, dejemos que $\sigma = \alpha_1 \alpha_1^* \alpha_2 \alpha_2^* \ldots \alpha_t \alpha_t^* \beta_1 \beta_2 \ldots \beta_s$ sea un producto de ciclos disjuntos donde para todo $i$ El $\alpha_i, \alpha_i^*$ son ciclos de la misma longitud par y $\beta_i$ son ciclos de longitud impar.

Basta con encontrar para todos $i$ una raíz cuadrada $\sigma_i$ para $\alpha_i \alpha_i^*$ que mueve los mismos elementos $\alpha_i \alpha_i^*$ y de forma similar una raíz $\tau_i$ para $\beta_i$ tal que $\tau_i$ mueve los mismos elementos $\beta_i$ hace. Entonces $\sigma = \tau^2$ , donde $\tau = \sigma_1 \sigma_2 \ldots \sigma_t \tau_1 \tau_2 \ldots \tau_s$ .

Si $\alpha_i = (a_1 a_2 \ldots a_{2k})$ y $\alpha_i^* = (a_1^* a_2^* \ldots a_{2k}^*)$ , dejemos que $\sigma_i = (a_1 a_1^* a_2 a_2^* \ldots a_{2k} a_{2k}^*)$ .

Si $\beta_i = (a_1 a_2 \ldots a_{2k+1})$ , entonces dejemos que $\tau_i = (a_1 a_{k+1} a_2 a_{k+2} a_3 a_{k+3} \ldots a_{k + (k+1)} a_{k+1})$ .

Por ejemplo, si $\sigma = (12)(34)(567)$ entonces $(12)(34) = (1324)^2$ y $(567) = (576)^2$ Así que $\sigma$ tiene una raíz cuadrada $\tau = (1324)(576)$ .