2.3 Permutaciones

\( \newcommand{\Implies}{\Rightarrow} \newcommand{\Iff}{\Leftrightarrow} \renewcommand{\emptyset}{\varnothing} \newcommand{\powersetsym}{\mathcal{P}} \newcommand{\fto}{\rightarrow} \newcommand{\mto}{\mapsto} \newcommand{\Cx}{\mathbb{C}} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\Ns}{\mathbb{N}^*} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\K}{\mathbb{K}} \newcommand{\vv}[1]{\boldsymbol{#1}} \newcommand{\Abs}[1]{\left\lvert#1\right\rvert} \newcommand{\norm}[1]{ \left\|#1\right\| } \newcommand{\pnorm}[1]{\left\|#1\right\|_p} \newcommand{\supnorm}[1]{\left\|#1\right\|_\infty} \newcommand{\innerprod}[1]{\left\langle #1\right\rangle} \newcommand{\Ceil}[1]{\left\lceil #1\right\rceil} \newcommand{\Floor}[1]{\left\lfloor #1\right\rfloor} \newcommand{\Conj}[1]{\overline{#1}} \newcommand{\arccot}{\mathop{\text{arc\,cot}}\nolimits} \newcommand{\arcsec}{\mathop{\text{arc\,sec}}\nolimits} \newcommand{\arccsc}{\mathop{\text{arc\,csc}}\nolimits} \renewcommand{\arg}{\mathop{\text{arg}}\nolimits} \newcommand{\mcd}[1]{\mathop{\text{mcd}}\left(#1\right)} \newcommand{\mcm}[1]{\mathop{\text{mcm}}\left(#1\right)} \renewcommand{\ker}{\mathop{\text{ker}}\nolimits} \newcommand{\grad}{\mathop{\text{grad}}\nolimits} \newcommand{\dom}{\mathop{\text{dom}}\nolimits} \newcommand{\rng}{\mathop{\text{ran}}\nolimits} \newcommand{\diam}{\mathop{\text{diam}}\nolimits} \newcommand{\Obj}{\mathop{\text{obj}}\nolimits} \newcommand{\Hom}{\mathop{\text{hom}}\nolimits} \newcommand{\End}{\mathop{\text{end}}\nolimits} \newcommand{\Aut}[1]{\mathop{\mathrm{aut}}\nolimits(#1)} \newcommand{\Inn}[1]{\mathop{\mathrm{int}}\nolimits(#1)} \newcommand{\Deg}{\mathop{\mathrm{grad}}\nolimits} \newcommand{\Img}{\mathop{\text{im}}\nolimits} \newcommand{\Id}{\mathop{\mathrm{id}}\nolimits} \newcommand{\sgn}{\mathop{\mathrm{sgn}}\nolimits} \renewcommand{\Re}{\mathop{\mathrm{Re}}\nolimits} \renewcommand{\Im}{\mathop{\mathrm{Im}}\nolimits} \newcommand{\Char}{\mathop{\mathrm{car}}\nolimits} \renewcommand{\mod}[1]{\mathop{(\mathop{\text{mód}}\nolimits #1)}} \newcommand{\res}{\mathop{\text{mód}}} \newcommand{\categof}[1]{\mathsf{#1}} \newcommand{\CC}{\categof{C}} \newcommand{\CONJ}{\categof{Conj}} \newcommand{\SET}{\categof{Set}} \newcommand{\GRP}{\categof{Grp}} \newcommand{\AGRP}{\categof{Ab}} \newcommand{\morph}[1]{\mathrel{\mathop{\longrightarrow}\limits^{#1}}} \newcommand{\subgr}{\leq} \newcommand{\nsubgr}{\mathrel{\unlhd}} \newcommand{\iso}{\cong} \newcommand{\genby}[1]{\left\langle #1\right\rangle} \newcommand{\symgr}[1][n]{S_{#1}} \newcommand{\GenOf}[1]{\mathop{\text{gen}}\left(#1\right)} \newcommand{\normalizer}[2][G]{{\mathbf N}_{#1}(#2)} \newcommand{\centralizer}[2][G]{{\mathbf C}_{#1}(#2)} \newcommand{\orbit}[2][G]{\mathcal{O}_{#1}(#2)} \newcommand{\stab}[2][G]{#1(#2)} \newcommand{\GL}[2][n]{\mathrm{GL}(#1,#2)} \newcommand{\SL}[2][n]{\mathrm{SL}(#1,#2)} \newcommand{\Ort}[2][n]{\mathrm{O}(#1,#2)} \newcommand{\SO}[2][n]{\mathrm{SO}(#1,#2)} \newcommand{\KleinV}{\mathbf{V}}\)

2.3 Permutaciones

Antes de continuar, es conveniente contar con un concepto que nos permitirá dar ejemplos concretos de muchos de los conceptos que vienen a continuación.

En matemáticas elementales, una permutación de una lista de \(n\) objetos se entiende como un reordenamiento de los elementos de la lista. Por ejemplo, para la lista \((1,2,3,4)\) tenemos los \(4! = 24\) ordenamientos siguientes: \[ \begin {array}{cccccc} (1,2,3,4) & (1,2,4,3) & (1,3,2,4) & (1,3,4,2) & (1,4,2,3) & (1,4,3,2) \\ (2,1,3,4) & (2,1,4,3) & (2,3,1,4) & (2,3,4,1) & (2,4,1,3) & (2,4,3,1) \\ (3,1,2,4) & (3,1,4,2) & (3,2,1,4) & (3,2,4,1) & (3,4,1,2) & (3,4,2,1) \\ (4,1,2,3) & (4,1,3,2) & (4,2,1,3) & (4,2,3,1) & (4,3,1,2) & (4,3,2,1) \\ \end {array} \] Observemos que cualquiera de estos reordenamientos de \((1,2,3,4)\) puede entenderse como una biyección del conjunto \(X=\{1,2,3,4\}\) en sí mismo. Por ejemplo, el reordenamiento \((4,3,1,2)\) de \((1,2,3,4)\) es la aplicación \(\sigma :X\fto X\) que envía el 1 al 3, el 2 al 4, el 3 al 2 y el 4 al 1. En general, y puesto que ningún reordenamiento introduce repeticiones ni omisiones de los elementos de \(X\), deducimos que, en efecto, todo reordenamiento queda caracterizado por una biyección de \(X\) en sí mismo.

Notemos que la definición anterior es en esencia la misma si en lugar del conjunto \(X = \{1,\ldots ,n\}\) consideremos cualquier otro conjunto \(Y\) de \(n\) elementos. Teniendo \(Y\) el mismo cardinal que \(X\), podemos pensar que \(Y\) no es más que \(X\) con sus elementos “renombrados”. Para expresar esta situación con más detalle, supongamos que \(\symgr [Y]\) es el conjunto de las permutaciones de elementos de \(Y\), es decir, el conjunto de biyecciones \(\sigma :Y\fto Y\). Al ser \(|X| = |Y|\), existe una biyección \(f: X\fto Y\) que “traduce” los elementos de \(X\) a elementos de \(Y\), y con ella podemos traducir toda permutación \(\sigma \in \symgr [Y]\) en \[ f^{-1}\circ \sigma \circ f, \] una permutación de elementos de \(X\) (la composición de biyecciones es una biyección). Está claro que \(\sigma \) queda unívocamente determinada por \(\sigma \) y \(f\), o sea, que la aplicación dada por \(\sigma \mapsto f^{-1}\circ \sigma \circ f\) es una biyección entre las permutaciones de \(Y\) y las permutaciones de \(X\), luego los conjuntos \(\symgr \) y \(\symgr [Y]\) son en efecto intercambiables. Por lo tanto, cuando en algún punto hablemos del conjunto \(\symgr [Y]\) de las permutaciones en un conjunto \(Y\) de \(n\) elementos, el lector tendrá claro que no se trata de ningún concepto nuevo y que todo lo dicho para \(\symgr \) vale igual para este conjunto.

Como posiblemente el lector ya los sepa, existen \(n!\) formas distintas de ordenar un conjunto de \(n\) elementos, o sea que

Demostración: PENDIENTE.

Puesto que hemos definido a las permutaciones compo biyecciones de un conjunto en si mismo, ahora podemos entender el proceso de reordenar dos veces un conjunto de objetos simplemente como la composición de dos permutaciones: si \(\tau ,\sigma \in \symgr \), \(\tau \circ \sigma \) es la permutación que resulta de aplicar \(\sigma \) seguida de \(\tau \), pues ya sabemos (proposición xxx) que la composición de biyecciones es de nuevo una biyección, o sea, que dicha composición es una operación binaria en \(\symgr \), a la cual nos referiremos como producto de permutaciones. Se deja al lector verificar que esta operación verifica las propiedades de la definición de grupo (teorema 2.18).

Por lo regular representaremos el producto de dos permutaciones \(\tau \) y \(\sigma \) (en ese orden) con la notación \(\tau \sigma \) en lugar de \(\tau \circ \sigma \).

A continuación estudiaremos algunas propiedades básicas de las permutaciones que nos permitirán trabajar con ellas de manera más eficiente.

Una notación común para especificar una permutación \(\sigma \in \symgr \) consiste en un arreglo de dos filas como \[ \begin {pmatrix} 1 & 2 & 3 & \ldots & n \\ \sigma (1) & \sigma (2) & \sigma (3) & \ldots & \sigma (n) \end {pmatrix}, \] formada por \(n\) columnas en las que se coloca cada \(i\in \{1,\ldots ,n\}\) encima del valor al que éste es enviado por \(\sigma \). Por ejemplo, si \(\sigma \) es la permutación de \(\symgr [5]\) dada por \[ \sigma (1) = 4,\quad \sigma (2) = 3,\quad \sigma (3) = 5,\quad \sigma (4) = 1, \quad \sigma (5) = 2, \] entonces \[ \sigma = \begin {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 5 & 1 & 2 \end {pmatrix}. \] Aunque esta notación es un tanto tediosa, tiene la ventaja de facilitar el cálculo de productos de permutaciones. Por ejemplo, si \(\sigma \) es como arriba y \[ \tau = \begin {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 2 & 1 & 3 & 4 \end {pmatrix}, \] tenemos que \[ \tau \sigma = \begin {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 2 & 1 & 3 & 4 \end {pmatrix} \begin {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 5 & 1 & 2 \end {pmatrix} = \begin {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 4 & 5 & 2 \end {pmatrix}, \] donde el cálculo se realiza siguiendo los números de derecha izquierda (en la notación \(\tau \sigma \), \(\tau \) actúa después de \(\sigma \)), como se ilustra en la imagen siguiente:

La verdad es que esta forma de representar permutaciones no nos interesa mucho, pues vamos a introducir otra notación que no sólo es más concisa, sino que además hace manifiestas algunas propiedades importantes de una permutación dada y también permite hacer cálculos más rápidos con permutaciones. Esta notación se apoya en algunos conceptos adicionales que introducimos a continuación.

Aunque la composición de aplicaciones no es conmutativo, sí lo es entre permutaciones disjuntas.

Demostración: Sean \(\sigma ,\tau \in \symgr \) permutaciones disjuntas. Se debe probar que \(\tau \sigma (i) = \sigma \tau (i)\) para todo \(i\in \{1,\ldots ,n\}\). Para esto, observamos que si \(\tau \) mueve a \(i\), con \(\tau (i) = j \neq i\), entonces \(\tau \) también ha de mover a \(j\) por la inyectividad de \(\tau \), luego \(\sigma \) fija tanto a \(i\) como a \(j\), lo que implica que \(\tau \sigma (i) = \tau (i) = j = \sigma (j) = \sigma \tau (i)\). De forma similar se verifica que si \(\tau \) fija a \(i\), entonces \(\tau \sigma (i) = \sigma \tau (i)\). Esto demuestra que \(\tau \sigma = \sigma \tau \).

Consideremos ahora la permutación \[ \sigma = \begin {pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 7 & 1 & 2 & 6 & 5 \end {pmatrix} \in \symgr [7] \] y el efecto que tiene aplicar repetidamente \(\sigma \) a los elementos de \(\{1,\ldots ,7\}\). Cuando aplicamos \(\sigma \) por primera vez, ésta envía el 1 al 4. Como \(\sigma \) vuelva a actuar, ésta envía el 4 de regreso al 1, dando como resultado el “ciclo” de la imagen siguiente:

Ahora vemos qué pasa con los demás elementos. El menor de los enteros de \(\{1,\ldots ,7\}\) que no figura en el ciclo de arriba es el 2. Cuando \(\sigma \) actúa sobre el 2, éste es enviado al \(3\). Si \(\sigma \) actúa de nuevo, el 3 es enviado al 7, y si actúa otra vez, el 7 es enviado al 5. Al actuar \(\sigma \) sobre el 5, éste es enviado al 2, completándose así el ciclo

El menor (y el único) de los enteros del conjunto \(\{1,\ldots ,7\}\) que no está en el ciclo anterior es el 6, que queda fijado por \(\sigma \) y por tanto su ciclo es

La situación descrita por estos tres diagramas puede expresarse con la notación \[ (1\ 4)(2\ 3\ 7\ 5)(6), \] que especifica el efecto que \(\sigma \) tiene sobre cada elemento de \(\{1,\ldots ,7\}\). Decimos entonces que hemos descompuesto \(\sigma \) en “producto de ciclos disjuntos”. Si a los ciclos los definimos como ciertas permutaciones especiales, podemos dar completo sentido literal esas palabras.

Definición 2.41. Decimos que una permutación \(\sigma \in \symgr \) es un ciclo de longitud \(k\), o que es un \(k\)-ciclo, si, para para ciertos \(i_1,\ldots ,i_k\in \{1,\ldots ,n\}\), ésta verifica \[ \sigma (i_1) = i_2, \quad \sigma (i_2) = i_3, \ldots \quad ,\sigma (i_{k-1}) = i_k, \quad \sigma (i_k) = i_1 \] y \[\sigma (i) = i\] cuando \(i\notin \{i_1,\ldots ,i_k\}\). Usaremos la notación \[ (i_1\ i_2\ i_3\ldots i_k) \] para representar al \(k\)-ciclo que cumple dichas condiciones. A los 2-ciclos los llamamos transposiciones. Se trata de permutaciones que intercambian dos números \(i_1,i_2\in \{1,\ldots ,n\}\) y dejan fijos a todos los demás. Los ciclos de longitud 1 no mueven ningún elemento, así que todos ellos son la permutación identidad.

Observemos que la notación para un \(k\)-ciclo no es única, pues “rotar” las posiciones de sus números da lugar a la misma permutación. Por ejemplo \[ (i_1\ i_2\ i_3\ldots \ i_{k-1}\ i_k) = (i_k\ i_1\ i_2\ldots \ i_{k-2}\ i_{k-1}) = (i_2\ i_3\ i_4\ldots \ i_{k-1}\ i_k\ i_1), \] o sea que hay \(k\) formas distintas de escribir el mismo \(k\)-ciclo. Puesto que existen \[ n(n - 1)(n - 2)\cdots (n - k + 1) \] \(k\)-tuplas ordenadas de elementos tomados de \(\{1,\ldots ,n\}\), el total de \(k\)-ciclos distintos en \(\symgr \) es \begin {equation} \label {eq:num k-ciclos} \frac {1}{k} n(n - 1)(n - 2)\cdots (n - k + 1). \end {equation}

Por otra parte, cualquier ciclo de longitud uno es simplemente la identidad en \(\symgr \), que comúnmente representaremos por \((1)\).

Demostración: Lo probaremos por inducción sobre el número \(m\) de elementos movidos por una permutación \(\sigma \in \symgr \). Si \(m=0\), el teorema es cierto, pues en ese caso \(\sigma = (1)\). Supongamos el teorema cierto para todo entero menor que \(m > 0\). Entonces \(\sigma \) mueve al menos un elemento, digamos \(i\). Puesto que \(\sigma ^s(i)\in \{1,\ldots ,n\}\), las potencias \(\sigma ^s(i)\) no pueden ser todas distintas, así que existen enteros \(s,t\), con \(s > t\), tales que \(\sigma ^s(i) = \sigma ^t(i)\), o sea, que \(\sigma ^{s-t}(i) = i\), luego existe el menor entero \(r > 0\) tal que \(\sigma ^r(i) = i\), o sea que existen a lo sumo \(r \leq n\) potencias distintas de \(\sigma (i)\). Más aún, las potencias \[ \sigma (i),\quad \sigma ^2(i),\ldots \quad , \sigma ^r(i) \] son todas distintas, pues si dos de ellas fuesen iguales, digamos \(\sigma ^s(i) = \sigma ^t(i)\) con \(1\leq t < s \leq r\) entonces \(\sigma ^{s-t}(i) = i\) con \(s-t < r\), en contradicción con la minimalidad de \(r\). Sea \(\alpha \) el ciclo \[ \alpha = ( \sigma (i)\quad \sigma ^2(i)\quad \sigma ^3(i)\quad \ldots \quad \sigma ^r(i) ). \] Si \(r = m\), entonces \(\sigma = \alpha \) y el teorema se cumple. Si \(r < m\), entonces sea \(S\) el conjunto de puntos fijados por \(\alpha \), y definamos \(\beta \in \symgr \) por \[ \beta (j) = \begin {cases} \sigma (j), & j\in S, \\ j, & j\notin S. \end {cases} \] Entonces \(\sigma = \alpha \beta \), donde \(\beta \) mueve a lo sumo \(m - r\) elementos, así que, por hipótesis de inducción, \(\beta \) es un producto de ciclos, luego \(\sigma =\alpha \beta \) es también un producto de ciclos.

El procedimiento con el que más arriba factorizamos \[ \begin {pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 7 & 1 & 2 & 6 & 5 \end {pmatrix} = (1\ 4)(2\ 3\ 7\ 5)(6) \] es de carácter general y puede usarse para factorizar cualquier permutación \(\sigma \in \symgr \). El resultado es siempre un producto de ciclos disjuntos, como lo establece el teorema siguiente.

Demostración: Sean \(\alpha _1\cdots \alpha _k\) y \(\beta _1\cdots \beta _l\) dos descomposiciones de \(\sigma \in \symgr \) en ciclos disjuntos. Sin pérdida de generalidad, supondremos que \(l\geq k\) y probaremos la proposición por inducción sobre \(l\). El caso \(l=1\) es obvio. Supongamos la conclusión cierta para un entero \(l-1\) y sean \(\alpha _1\cdots \alpha _k\) y \(\beta _1\cdots \beta _l\) dos descomposiciones de \(\sigma \). Si \(\sigma \) mueve \(i\in \{1,\ldots ,n\}\), entonces un \(\alpha _s\) y un \(\beta _t\) mueven a \(i\). Puesto que los ciclos disjuntos conmutan, podemos asumir que se trata de \(\beta _l\) y de \(\alpha _k\). Observemos que entonces \(\beta _l^j(i) = \sigma ^j(i) = \alpha ^j(i)\) para todo \(j\geq 1\), por lo que \(\beta _l = \alpha _k\), o sea que \(\alpha _1\cdots \alpha _{k-1} = \beta _1\cdots \beta _{l-1}\). Por hipótesis de inducción, ambos miembros consisten de los mismos ciclos, de donde se sigue el resultado deseado.

Es inmediato que el inverso del ciclo \((i_1\ i_2\ i_3\ \ldots \ i_k)\) es el ciclo \[ (i_k\ i_{k-1}\ i_{k-2}\ \ldots \ i_1). \] Si la descomposición en ciclos disjuntos de \(\sigma \) es \(\sigma = \alpha _1\cdots \alpha _s\), entonces \[ \sigma ^{-1} = \alpha ^{-1}_s\cdots \alpha _1^{-1} = \alpha _1^{-1}\cdots \alpha _s^{-1}, \] pues ciclos disjuntos conmutan. Así, calcular la inversa de \(\sigma \) consiste simplemente en invertir el orden de los elementos de cada ciclo en la descomposición de \(\sigma \).

Nos referiremos como la estructura de ciclos de una permutación \(\sigma \) al número de \(k\)-ciclos que aparecen en la descomposición de \(\sigma \) en ciclos disjuntos para cada \(0 \leq k\leq n\).

Ejemplo 2.45. ¿Cuántas permutaciones hay con estructura de ciclos \((\bullet \ \bullet \ \bullet )(\bullet \ \bullet )\) en \(\symgr [5]\)? Aplicando la fórmula (2.2), determinamos que hay \(\frac {1}{3}(5\cdot 4\cdot 3) = 20\) ciclos de longitud 3. Obtenido este ciclo, no nos quedan más que 2 elementos para formar el 2-ciclo siguiente, luego éste sólo puede completarse de una manera y por tanto existen 20 permutaciones que son producto de un 3-ciclo y un 2-ciclo.

En la factorización de una permutación \(\sigma \) en ciclos disjuntos, por lo regular omitimos los ciclos de longitud 1 que resultan de considerar los elementos fijados por \(\sigma \), ya que dichos ciclos son todos la permutación identidad y resulta redundante escribirlos. Sin embargo, en ocasiones sí resulta útil incluirlos. Cuando incluimos un 1-ciclo para cada número fijado por \(\sigma \), hablamos de una factorización completa de \(\sigma \) en producto de ciclos disjuntos.

Ejemplo 2.46. Sean \(\sigma = (4\ 7\ 3\ 6)(5\ 2)(1)\) y \(\tau = (1\ 5\ 6)(3\ 2\ 7)(4)\). Para calcular el producto \(\sigma \tau \), podemos empezar por rastrear a dónde va a parar el primer número que veamos en la descomposición de \(\tau \), que es la primera en actuar por tratarse de una composición de aplicaciones. Haciéndolo así, vemos que \(\tau \) envía el 1 al 5 y que luego \(\sigma \) envía el 5 al 2, por lo que nuestro producto comienza por “\((1\ 2\ldots \)”. Aplicando este mismo proceso ahora al 2, obtenemos “\((1\ 2\ 3\ldots \)”, y continuando de esta manera con cada número que vayamos obteniendo, llegamos al resultado \(\sigma \tau = (1\ 2\ 3\ 5\ 4\ 7\ 6)\).

Consideremos las permutaciones \(\sigma = (4\ 7\ 3\ 6)(5\ 2)(1)\) y \(\tau = (1\ 5\ 6)(3\ 2\ 7)(4)\). Al calcular \begin {align*} \sigma ^\tau & = \Big ((1\ 5\ 6)(3\ 2\ 7)(4)\Big ) \Big ((4\ 7\ 3\ 6)(5\ 2)(1)\Big ) \Big ((6\ 5\ 1)(7\ 2\ 3)(4)\Big )^{-1} \\ & = (4\ 3\ 2\ 1)(6\ 7)(5), \end {align*} observamos que \(\sigma \) y \(\sigma ^\tau \) tienen la misma estructura de ciclos, y que, además, \[ \sigma ^{\tau } = \Big (\tau (4)\quad \tau (7)\quad \tau (3)\quad \tau (6)\Big ) \Big (\tau (5)\quad \tau (2)\Big ) \Big (\tau (1)\Big ). \] Se trata de una regla general:

Proposición 2.48. Sean \(\sigma ,\tau \in \symgr \). Si \(\sigma \) se expresa como un producto de ciclos disjuntos, entonces \(\sigma \) y \(\sigma ^\tau \) tiene la misma estructura de ciclos. Con más detalle, la descomposición en ciclos disjuntos de \(\sigma ^\tau \) se obtiene sustituyendo cada índice \(i\) por \(\tau (i)\) en cada uno de los ciclos de la descomposición de \(\sigma \).

Demostración: Es fácil ver que la conjugada de un producto de permutaciones es el producto de las conjugadas de éstas, luego basta con demostrar el teorema para el caso particular de un solo ciclo \(\alpha = (i_1\ i_2\ i_3\ \ldots \ i_k)\). Sea \[ \beta = (\tau (i_1)\ \tau (i_2)\ \tau (i_3)\ \ldots \ \tau (i_k)). \] Hay que demostrar que \(\tau \alpha \tau ^{-1} = \beta \). Para esto, observemos que si \(i\notin \{i_1,\ldots ,i_k\}\), entonces \(\tau \alpha \tau ^{-1}(\tau (i)) = \tau (i)\), pues \(\alpha (i) = i\), así que \(\tau \alpha \tau ^{-1}\) y \(\beta \) dejan fijos a los mismos elementos. Por otra parte, si \(i_j\in \{i_1,\ldots ,i_n\}\), entonces \[ \tau \sigma \tau ^{-1}(\tau (i_j)) = \tau \sigma (i_j) = \begin {cases} \tau (i_{j+1}) & \text {si } j < k, \\ \tau (i_1) & \text {si } j = k, \end {cases} \] o sea que \(\tau \alpha \tau ^{-1}(\tau (i_j)) = \beta (\tau (i_j))\), así que \(\tau \alpha \tau ^{-1}\) y \(\beta \) coinciden en todo punto y por lo tanto son iguales.

Propongámonos ahora determinar si existe alguna relación entre dos permutaciones que tengan la misma estructura de ciclos. Consideremos, por ejemplo, las permutaciones \(\sigma = (4\ 7\ 3)(5\ 2)(1\ 6)\) y \(\alpha = (4\ 3\ 1)(6\ 7)(2\ 5)\) de \(\symgr [7]\), y definamos \(\tau :\{1,\ldots ,7\}\fto \{1,\ldots ,7\}\) por

Puesto que estamos considerando factorizaciones completas de \(\sigma \) y \(\alpha \) en ciclos disjuntos, \(\tau \) está bien definida y es biyectiva, luego \(\tau = (4)(7\ 3\ 1\ 2)(6\ 5)\in \symgr [7]\). Tenemos entonces que \begin {align*} \alpha & = (4\ 3\ 1)(6\ 7)(2\ 5) \\ & = \Big (\tau (4)\quad \tau (7)\quad \tau (3)\Big ) \Big (\tau (5)\quad \tau (2)\Big ) \Big (\tau (1)\quad \tau (6)\Big ) \\ & = \sigma ^{\tau }, \end {align*} donde la última igualdad se da por la teorema 2.48. Ahora demostraremos esta relación en el caso general.

Demostración: (\(\Rightarrow \)) Sean \(\sigma ,\alpha \in \symgr \) de la misma estructura de ciclos. Entonces, a cada ciclo \((i_1\ i_2\ i_3\ \ldots \ i_k)\) en la descomposición de \(\sigma \) corresponde un ciclo \((j_1\ j_2\ j_3\ \ldots \ j_k)\) en la descomposición de \(\alpha \), y podemos definir la aplicación \(\tau \) por \(\tau (i_s) = j_s\) para cada ciclo de estas descomposiciones. Es evidente que se trata de una permutación de \(\symgr \), y la teorema 2.48 nos dice que \(\alpha = \sigma ^\tau \).

La afirmación recíproca es la teorema 2.48.

Demostración: Sean \(\tau , \sigma \in \symgr \). Entonces \begin {align*} \sgn (\tau \sigma ) & = \prod _{i < j}\frac {\tau \sigma (i) - \tau \sigma (j)}{i - j} \\ & = \prod _{i < j}\frac {\tau \sigma (i) - \tau \sigma (j)}{\sigma (i) - \sigma (j)} \prod _{i < j}\frac {\sigma (i) - \sigma (j)}{i - j} \\ & = \prod _{i < j}\frac {\tau (i) - \tau (j)}{i - j} \prod _{i < j}\frac {\sigma (i) - \sigma (j)}{i - j} \\ & = \sgn (\tau )\sgn (\sigma ). \end {align*}

Es posible descomponer una permutación en un producto de transposiciones, si bien no de forma única. Sin embargo, el teorema siguiente nos dice que el número de factores en una descomposición así es único módulo dos.

Demostración: Para la primera afirmación del teorema, basta probar que es cierta para un ciclo. En efecto, pues \[ (i_1\ i_2\ i_3\ \ldots \ i_k) = (i_1\ i_k)(i_1\ i_{k-1})(i_1\ i_{k-2})\cdots (i_1\ i_2). \] Para la segunda afirmación, observamos que si \(\alpha _1\cdots \alpha _r\) y \(\beta _1\cdots \beta _s\) son dos factorizaciones de una permutación \(\sigma \), entonces las proposiciones 2.52 y 2.51 nos dicen que \[ \sgn (\sigma ) = (-1)^{r} = (-1)^s, \] por lo que \(r\) y \(s\) son ambos pares o ambos impares.