

\appendix
\setcounter{chapter}{2}
\hypertarget{temacuatro}{ }
\chapter{Grupos de Permutaciones}
\label{temacuatro}

\hrule \vskip0.5cm
%-----------------------------------------------------------------
\noindent{\sffamily\bfseries Objetivos del cap\'{\i}tulo} $\,$
\begin{itemize}\footnotesize
 \item Se introduce y estudian los grupos de permutaciones $S_X$. Se demuestra que $S_X\cong S_Y$ si y s\'{o}lo si $\#X=\#Y$. Como
 consecuencia se introduce la notaci\'{o}n $S_n$ para el grupo de permutaciones de un conjunto con $n$ elementos.
 \item Se introduce la notaci\'{o}n matricial tanto para permutaciones como para ciclos. Se da la tabla de multiplicar de $S_3$ y
 se estudian los subgrupos $D_n$, o grupos de movimientos de un pol\'{\i}gono regular de $n$ lados.
 \item Se demuestra que toda permutaci\'{o}n se descompone como producto de ciclos disjuntos y que esta descomposici\'{o}n es \'{u}nica salvo orden.

 \item Se demuestra que toda permutaci\'{o}n se factoriza como producto de transposiciones (no de forma \'{u}nica).
  Se demuestra que el numer\'{o} de trasposiciones en tales descomposiciones puede variar, aunque conserva la paridad. Se define la paridad de una permutaci\'{o}n y se estudia el grupo alternado $A_n$.
\end{itemize}
\vskip0.25cm
%-----------------------------------------------------------------
\hrule \vskip0.3cm
\[\,\]





\hypertarget{GruSn}{ }
\section{Grupo $S_n$ y primeras propiedades}\label{GruSn}

\hypertarget{Dper}{ }
\begin{defi}\rm \label{Dper}
Sea $X$ un conjunto finito. Se define una permutaci\'{o}n en $X$ como una aplicaci\'{o}n biyectiva $f:X\to X$. Se denota por $S_X$ el
conjunto de todas las permutaciones de $X$.\index{Permutaci\'{o}n}
\end{defi}

\begin{prop}\rm
Sea $X$ un conjunto finito. Entonces $(S_X,\circ)$, en donde $\circ$ es la composici\'{o}n de aplicaciones, es un grupo. Es m\'{a}s, si
$X$ e $Y$ son dos conjuntos con el mismo n\'{u}mero de elementos (existe $g:X\to Y$ biyectiva) entonces $S_X\cong S_Y$.
\end{prop}
\Proof  Ya ha sido demostrado que $(S_X,\circ)$ es un grupo. Sea $g:X\to Y$ una biyecci\'{o}n. Veamos que la
aplicaci\'{o}n $$\Psi:S_X\to S_Y\quad\hbox{ definida por } \Psi(\sigma)=g\circ \sigma \circ g^{-1} $$ es un isomorfismo de grupos:
 es claro que $\Psi(\sigma):Y\to Y$ es biyectiva (al ser composici\'{o}n de aplicaciones biyectivas), por lo que $\Psi$ est\'{a} bien definida. Es mas, es un homomorfismo de grupos:

 $$\Psi(\sigma\circ \sigma')=g\circ \sigma\circ \sigma' \circ g^{-1}=g\circ \sigma\circ g^{-1}\circ g\circ \sigma' \circ g^{-1}=
 \Psi(\sigma)\circ\Psi(\sigma').$$
 Y si definimos $\Phi:S_Y\to S_X$
  como $\Phi(\tau)=g^{-1}\circ \tau\circ g$ tenemos que \begin{eqnarray*}
\Psi\Phi(\tau)=&\psi(g^{-1}\circ \tau\circ g)=g\circ g^{-1}\circ \tau\circ g\circ g^{-1}=\tau\\
  \Phi\Psi(\sigma)=&\Phi(g\circ \sigma\circ g^{-1})=g^{-1}\circ g\circ \sigma\circ g^{-1}\circ g=\sigma
  \end{eqnarray*}
  por lo que $\Psi$ es biyectiva y por tanto un isomorfismo de grupo. \EndProof

\textbf{Nota:} Dado un natural $n$, denotaremos por $S_n$ al \textbf{grupo de permutaciones} de un conjunto con $n$ elementos.
Normalmente  $X=\{1,2,\dots, n\}$\index{Grupo!de Permutaciones, $S_n$}. Los elementos de $S_n$ se denotan por letras griegas y se
re\-pre\-sentan en forma matricial: por ejemplo,  $$\sigma:\{1,2,3\}\to \{1,2,3\},\quad\hbox{definida por}\quad \sigma(1)=2,\sigma(2)=3\ \hbox{y}\ \sigma(3)=1$$ se denotar\'{a} por
$$\sigma=\left(\begin{array}{ccc} 1&2&3\\ 2&3&1
\end{array}\right)$$ con esta notaci\'{o}n, si queremos componer dos permutaciones:

$$\left(\begin{array}{cccc} 1&2&3&4\\ 2&3&1&4
\end{array}\right)\circ\left(\begin{array}{cccc} 1&2&3&4\\ 3&1&4&2
\end{array}\right)=\left(\begin{array}{cccc} 1&2&3&4\\ 1&2&4&3
\end{array}\right).$$
Es decir, se siguen componiendo de derecha a izquierda al ser aplicaciones.


\begin{ejem}
Veamos la tabla de multiplicar de $S_3$, el grupo de permutaciones con tres elementos: Sean
 $$\begin{array}{ccc}
\rho_0=\left(\begin{array}{ccc} 1&2&3\\ 1&2&3 \end{array}\right)&
 \rho_1=\left(\begin{array}{ccc} 1&2&3\\ 2&3&1 \end{array}\right)&
 \rho_2=\left(\begin{array}{ccc} 1&2&3\\ 3&2&1 \end{array}\right)\\
 \tau_1=\left(\begin{array}{ccc} 1&2&3\\ 1&3&2 \end{array}\right)&
 \tau_2=\left(\begin{array}{ccc} 1&2&3\\ 3&2&1 \end{array}\right)&
\tau_3=\left(\begin{array}{ccc} 1&2&3\\ 2&1&3 \end{array}\right)
\end{array}$$
tenemos entonces que la tabla de multiplicar es:\vskip.3truecm

 \noindent
\begin{tabularx}{15cm}{ll}
\includegraphics[scale=0.55]{Dibujos/Stres.eps}& \begin{minipage}[t][-1.2cm][b] {9.5cm} \textbf{Nota:} Como se puede ver, $(S_3,\circ)$ no es un
grupo abeliano: $$\rho_1 \circ \tau_1=\tau_3\quad \hbox{mientras que}\quad \tau_1\circ \rho_1=\tau_2.$$ Es m\'{a}s, los \'{o}rdenes de
los elementos son $$ \circ \rho_0=1,\quad \circ \rho_1=3\quad \circ \rho_2=3$$  $$ \circ \tau_1=2,\quad \circ \tau_2=2,\quad
\circ \tau_3=2$$ por lo que (como ya sab\'{\i}amos) no es un grupo c\'{\i}clico. \vfill\end{minipage}
\end{tabularx}
\vskip .3truecm
\end{ejem}


\hypertarget{Pper}{ }
\begin{prop}\rm \label{Pper}
Sea $n\in \NN$. Entonces:
 \item{(i)} $\# S_n=n!$
 \item{(ii)} La identidad de $S_n$ es $\Id=\left(\begin{array}{cccc} 1&2&\cdots&n\\ 1&2&\cdots&n
\end{array}\right)$
\item{(iii)} La inversa de una permutaci\'{o}n $\sigma\in S_n$ consiste en permutar la fila superior por la inferior re-ordenando
adecuadamente las columnas: $$\sigma=\left(\begin{array}{ccccc} 1&2&3&4&5\\ 2&5&1&4&3
\end{array}\right)\Rightarrow \left(\begin{array}{ccccc} 2&5&1&4&3\\ 1&2&3&4&5
\end{array}\right)\Rightarrow \sigma^{-1}=\left(\begin{array}{ccccc} 1&2&3&4&5\\ 3&1&5&4&2
\end{array}\right)$$
 \item{(iv)} Si $n,m\in \NN$ se tiene que $n\le m$ si y s\'{o}lo si  $S_n\lesssim S_m$.
 \item{(v)} $(S_n,\circ)$ es conmutativo si y s\'{o}lo si $n\le 2$.
\end{prop}
\textbf{Nota:} Dados $n,m\in \NN$ con $n\le m$,  $S_n$ no es subgrupo de $S_m$ ya que $S_n$ no es subconjunto de $S_m$. No obstante si que existen $H\le S_m$ con $H\cong S_n$. Esto se denotar\'{a} por $S_n\lesssim S_m$, o abusando de la notaci\'{o}n por $S_n\le S_m$.

\Proof (i). Sean $X,Y$ dos conjuntos con $n$ elementos. Veamos que el n\'{u}mero de biyecciones de $X$ en $Y$ es
$n!$\,: si $n=1$ existe una \'{u}nica biyecci\'{o}n. Luego el n\'{u}mero de biyecciones de $X$ en $Y$ es $1=1!$. Supongamos que el resultado
es cierto para $n-1$ y sean $X$, $Y$ dos conjuntos con $n$ elementos. Dado $x_1\in X$ puedo mandar $x_1$ a cualquier elemento de
$Y$, denotemos este elemento por $y_i$. Luego hay $n$ posibilidades, los restantes $X-\{x_1\}$ elementos los tendr\'{e} que mandar de
forma biyectiva a los elementos $Y-\{y_i\}$ luego, por la hip\'{o}tesis de inducci\'{o}n hay $(n-1)!$ posibilidades. As\'{\i}, podemos
construir $n(n-1)!=n!$ biyecciones de $X$ en $Y$. Tomando ahora $X=Y$ tenemos que $\#S_n=n!$.

(ii). Trivial.

(iii). Sea  $\sigma=\left(\begin{array}{ccccc} 1&2&3&\cdots&n\\ \sigma(1)&\sigma(2)&\sigma(3)&\cdots&\sigma(n)
\end{array}\right)$. Por el proceso anterior, si $\sigma$ manda $k$ a $\sigma(k)$, tenemos que la permutaci\'{o}n que construimos
manda $\sigma(k)$ a $k$, que es justamente la definici\'{o}n de la inversa.

(iv) Supongamos que $n\le m$ y sea la aplicaci\'{o}n $\Psi:S_n\to S_m$ definida por $$\Psi(\sigma)(k)=\left\{\begin{array}{cc}
\sigma(k)\quad&\hbox{si }\ k\le n\\ k\quad&\hbox{si }\ k> n
\end{array}\right.$$

Es claro que $\Psi$ es un monomorfismo de grupos: observar que si $k\le n$, para todo $\sigma\in S_n$,
$\Psi(\sigma)(k)=\sigma(k)\le n$. Por tanto
$$\begin{array}{ll}
\Psi(\sigma)\circ\Psi(\tau)(k)=\Psi(\sigma)(\tau(k))=\sigma(\tau(k))\quad&\hbox{si }\ k\le n\\
\Psi(\sigma)\circ\Psi(\tau)(k)=\Psi(\sigma)(k)=k\quad&\hbox{si }\ k> n\qquad \hbox{y}\\ \ \\
\Psi(\sigma \circ \tau)(k)= \sigma \circ \tau(k)=\sigma(\tau(k))\quad&\hbox{si }\ k\le n\\
\Psi(\sigma \circ \tau)(k)=k\quad&\hbox{si }\ k> n
\end{array}$$
 Luego $\Psi(\sigma)\circ\Psi(\tau)=\Psi(\sigma \circ \tau)$, lo que demuestra que $\Psi$ es un homomorfismo de grupos. Por otro
 lado, por definici\'{o}n, si $\Psi(\sigma)=\Id$, entonces $\sigma=\Id$ lo que demuestra que $\Psi$ es inyectiva (hemos demostrado que $\Ker(\Psi)=\{\Id\}$).  Por tanto
 $S_n\cong \im \Psi\le S_m$. Observar que $$\im(\Phi)=\{\sigma\in S_m\ \vert\ \sigma(k)=k\ \hbox{ si }\ k>n\}.$$
 Es m\'{a}s, por comodidad y claridad en la demostraci\'{o}n, hemos dejado fijos los $m-n$ \'{u}ltimos elementos pero pod\'{\i}amos haber dejado fijos
 cualquier conjunto de
 $m-n$ y el resultado ser\'{\i}a cierto.

 (v) Es claro que $S_2$ tiene dos elementos y por tanto $S_2\cong \ZZ_2$ es abeliano. Es m\'{a}s, si consideramos
 $$\rho_1=\left(\begin{array}{ccc} 1&2&3\\ 2&3&1\end{array}\right) \quad\hbox{y}\quad \tau_1=\left(\begin{array}{ccc} 1&2&3
 \\1&3&2
\end{array}\right)$$
Tenemos que $\rho_1\circ\tau_1=\tau_2=\left(\begin{array}{ccccc} 1&2&3\\ 3&2&1\end{array}\right)$ y $\tau_1\circ \rho_1=\tau_3=\left(\begin{array}{ccccc} 1&2&3\\
2&1&3\end{array}\right)$. Luego $S_3$ no es abeliano. ahora, por el apartado anterior, como $S_3\le S_n$ si $3\le n$, entonces $S_n$ no es
abeliano. \EndProof

Se deja como ejercicio el siguiente resultado:
\begin{prop}
El centro de $S_n$,  para $n\ge 3$ es $\{\Id\}$.
\end{prop}


\hypertarget{Ssn}{ }
\section{Subgrupos de $S_n$} \label{Ssn}

Vamos a comenzar esta secci\'{o}n demostrando que todo grupo finito es subgrupo de un cierto grupo de permutaciones:

\hypertarget{Tcay}{ }
\begin{center}
\shadowbox{\parbox{\columnwidth+0\fboxsep-10\fboxrule-\shadowsize}{
\centering
\begin{theo}[Teorema de Cayley]\index{Teorema de Cayley}\rm \label{Tcay}
Sea $G$ un grupo finito con $n$ elementos. Entonces $G$ es isomorfo a un subgrupo de $S_n$.
\end{theo}
}}
\end{center}





\Proof  Dado $a\in G$, la aplicaci\'{o}n $\Phi^l_a:G\to G$ es biyectiva y por tanto una permutaci\'{o}n en $G$. Veamos
que la aplicaci\'{o}n $$\Phi^l:G\to S_G\quad \hbox{definida por}\quad \Phi^l(a)=\Phi^l_a$$ es un monomorfismo de grupos:

$$\Phi^l(a*b)(x)=a*b*x=\Phi^l_a(b*x)=\Phi^l_a(\Phi^l_b(x))=\Phi^l_a\circ \Phi^l_b(x)$$
 por lo que $\Phi^l(a*b)=\Phi^l_a\circ \Phi^l_b$ y por tanto $\Phi$ es un homomorfismo de anillos. Es m\'{a}s, si $\Phi^l(a)=\Phi^l(b)$, entonces $a=a*e=\Phi^l(a)(e)=\Phi^l(b)(e)=b*e=b$,
 por lo que $\Phi$ es inyectiva. Por tanto $G\cong \im(\Phi^l)\le S_G$. \EndProof

En principio este teorema puede parecer muy pr\'{a}ctico, aunque en rea\-lidad es muy complicado calcular todos los subgrupos de
$S_n$. Es m\'{a}s, en la actualidad no est\'{a}n clasificados los grupos finitos (s\'{\i} que lo est\'{a}n los grupos abelianos finitos). Veamos
algunos subgrupos interesantes de $S_n$.

\begin{ejem}
Los subgrupos c\'{\i}clicos de $S_3$ son:
$$\begin{array}{ll}
\langle \rho_0\rangle=\{\rho_0\}& \langle \rho_1\rangle=\langle \rho_2\rangle=\{\rho_1,\rho_2,\rho_0\}\cong \ZZ_3\\
\langle \tau_1\rangle=\{\tau_1,\rho_0\}\cong \ZZ_2\hskip 1truecm\ &\langle \tau_2\rangle=\{\tau_2,\rho_0\}\cong \ZZ_2\\
\langle \tau_3\rangle=\{\tau_3,\rho_0\}\cong \ZZ_2&\
\end{array}$$
\end{ejem}

Veremos, una vez demostrado el Teorema de Lagrange, que \'{e}stos son todos los subgrupos propios de $S_3$.

\hypertarget{Gmov}{ }
\begin{defi}\rm \label{Gmov}
Se define una \textbf{figura}  $P$, como una colecci\'{o}n de puntos, llamados \textbf{v\'{e}rtices}, unidos dos a dos por aristas
r\'{\i}gidas. Un \textbf{movimiento} de $P$ ser\'{a} un cambio de posici\'{o}n de $P$ en donde los vertices permuten.

Observar que cada movimiento de $P$ queda determinado por la permutaci\'{o}n que sufren sus vertices y que
la composici\'{o}n de movimientos es el movimiento que corresponde con la composici\'{o}n de permutaciones. Por tanto el conjunto de todos los movimientos de una figura $P$ con $n$ aristas es un subgrupo de $S_n$. \index{Figura}\index{V\'{e}rtice}\index{Movimiento}
\end{defi}

\begin{defi}
Sea $n\in \NN$. Se define $D_n$, el \textbf{grupo Diedral} de $n$ lados,  como el conjunto de todos los movimientos de un pol\'{\i}gono regular de $n$ lados.\index{Grupo!Diedral}
\end{defi}

\begin{ejem}\rm
$\star$ Veamos que $D_3$, el conjunto de los movimientos de un tri\'{a}ngulo equil\'{a}tero es isomorfo a $S_3$.
\vskip .2truecm
 \noindent
\begin{tabularx}{15cm}{ll}
\includegraphics[scale=0.35]{Dibujos/MOvTrian.eps}& \begin{minipage}[t][-0.95cm][b] {9.4cm} Si giramos el triangulo 180 grados seg\'{u}n el eje que
pasa por $3$ y el centro del segmento formado por los v\'{e}rtices $1$ y $2$  obte\-nemos $\tau_3=(1,2)$ (ver figura). De forma
similar podemos obtener $\tau_1$ y $\tau_2$. \vskip 1.1truecm Si giramos en el sentido de la agujas del reloj el tri\'{a}ngulo
completo (seg\'{u}n figura) obte\-ne\-mos $\rho_1$. Si lo giramos en el sentido contrario de las agujas del reloj, obtenemos
$\rho_2$. Por \'{u}ltimo, si no lo movemos, obtenemos $\rho_0$. $\blacklozenge$ Por tanto $S_3\cong D_3$.\vfill\end{minipage}
\end{tabularx}
\vskip .3truecm



$\star$ Estudiemos en general, el subgrupo $D_n$:

 \vskip .4truecm
 \noindent
\begin{tabularx}{15cm}{ll}
\begin{minipage}[t][0cm][b] {10.6cm} Sea $P$ un pol\'{\i}gono regular de $n$ lados. Numeremos los vertices de $P$ de $1$ a $n$ siguiendo el movimiento de las agujas del reloj. Si movemos $P$ sobre $P$, y nos fijamos en el v\'{e}rtice $1$, tenemos que este puede ir a parar a cualquier v\'{e}rtice de $P$, digamos $k$. Es m\'{a}s, en este caso al v\'{e}rtice $2$ s\'{o}lo le quedan dos posibilidades: que \,caiga \,en \,el \,v\'{e}rtice posterior o en el\end{minipage} &\fbox{\includegraphics[scale=0.32]{Dibujos/Octog.eps}}
\end{tabularx}
\vskip .0001truecm \hskip -.4truecm anterior al v\'{e}rtice $1$. Por tanto $D_n$ tiene $2n$ elementos. Veamos cuales son:
\end{ejem}

Sea $\rho$ el movimiento que consiste en girar $360/n$ grados el pol\'{\i}gono $P$ en el sentido de las agujas del reloj y sea $\tau$ el movimiento que consiste en dejar fijo el v\'{e}rtice $1$ y mandar el v\'{e}rtice $2$ al v\'{e}rtice $n$ (y por tanto el v\'{e}rtice $n$ va a parar al v\'{e}rtice $2$). Tenemos entonces que los elementos de $D_n$ son
$$\{\rho,\rho^2,\dots,\rho^{n-1},\rho^n=\Id,\tau\circ\rho,\tau\circ\rho^2\dots,\tau\circ\rho^{n-1},\tau\}$$
En donde $\rho^k$ consiste en girar $k\, 360/n$ grados en el sentido de la agujas del reloj. Y en donde $\tau\circ \rho^k$  consiste en girar $k\, 360/n$ grados en dicho sentido y luego voltear el pol\'{\i}gono $180^o$ seg\'{u}n el eje que forma el v\'{e}rtice $1$ con el lado opuesto (ver figura).

\centerline{\includegraphics[scale=0.35]{Dibujos/Dene.eps}}

\begin{coro}
El elemento $\rho\in D_n$ tiene orden $n$, por lo que $S_n$ contiene un subgrupo isomorfo a $\ZZ_n$.
$$\ZZ_n\cong\langle \rho\rangle\le D_n\le S_n.$$
\end{coro}

\hypertarget{Fsn}{ }
\section{Factorizaci\'{o}n en $S_n$}\rm \label{Fsn}


 En lo que sigue denotaremos por $X$ al conjunto $\{1,2,\dots, n\}$.

\hypertarget{Cprev}{ }
\begin{defi}\rm \label{Cprev}
Sea $\sigma\in S_n$ el grupo de permutaciones con $n$ elementos.

$\bullet$ Se dice que $i\in X$ es fijado por $\sigma$, o queda \index{Elemento!Movido}\index{Elemento!Fijo}
\textbf{fijo} por $\sigma$,  si $\sigma(i)=i$. Denotamos por $\Delta_\sigma:=\{i\in X\ \vert\  \sigma(i)=i\}$.

$\bullet$  Se dice que $i$ es \textbf{movido} por $\sigma$ si $\sigma(i)\ne i$. Denotamos por $\Delta'_\sigma$ el conjunto de los elementos que mueve $\sigma$, $\Delta'_\sigma:=\{i\in X\ \vert\  \sigma(i)\ne i\}$.
\end{defi}

\begin{lema}\label{factimp}
Sea $\sigma\in S_n$ el grupo de permutaciones con $n$ elementos. Entonces:
 \item{(i)} $X=\Delta_\sigma\dot\cup \Delta'_\sigma$ (uni\'{o}n disjunta).
 \item{(ii)} Para todo $Y\subset X$ tal que $\sigma(Y)\subset Y$ se tiene: $\sigma(Y)=Y$, $\sigma(Y^c)=Y^c$. Es mas, $$\sigma\vert_Y:Y\to
 Y\quad \hbox{y}\quad \sigma\vert_{Y^c}:Y^c\to Y^c$$ son biyecciones. Por tanto, $\sigma^{-1}(Y)\subset Y$.
 \item{(iii)} $\sigma(\Delta'_\sigma)\subset  \Delta'_\sigma$ y $\Delta'_{\sigma^{-1}}=\Delta'_\sigma$.
 \item{(iv)} $\sigma\vert_{\Delta_\sigma}:\Delta_\sigma\to \Delta_\sigma$ y $\sigma\vert_{\Delta'_\sigma}:\Delta'_\sigma\to \Delta'_\sigma$ son biyectivas.
\end{lema}

\Proof (i) es trivial.

(ii) La restricci\'{o}n de $\sigma$ al conjunto $Y$, $\sigma\vert_Y:Y\to Y$ es una aplicaci\'{o}n inyectiva y como $Y$ es un conjunto
finito,  es sobreyectiva. Por lo que es una biyecci\'{o}n (y por tanto $\sigma^{-1}(Y)=Y$). Por tanto todo elemento de $Y$ es imagen
de un elemento de $Y$. Dado ahora $z\in Y^c$, si $\sigma(z)\in Y$, $\sigma(z)$ ser\'{\i}a imagen de un elemento de $Y$ y de un
elemento de $Y^c$, lo que contradice que $\sigma$ sea inyectiva. Por tanto $\sigma(Y^c)\subset Y^c$. Por ultimo, repitiendo el
argumento para $Y^c$ tenemos que $\sigma\vert_{Y^c}:Y^c\to Y^c$ es biyectiva.

 (iii)  Como $\sigma(\Delta_\sigma)\subset \Delta_\sigma$, se tiene, por (ii), que $\sigma(\Delta'_\sigma)\subset \Delta'_\sigma$.
 Es m\'{a}s, $\Delta_\sigma=\Delta_{\sigma^{-1}}$, ($\sigma(x)=x$ si y s\'{o}lo si $\sigma^{-1}(x)=x$). Por lo que
 $$\Delta'_{\sigma^{-1}}=X-\Delta_{\sigma^{-1}}=X-\Delta_\sigma=\Delta'_\sigma$$

 (iv) Se sigue de (ii) y (iii). \EndProof


\begin{defi}
 Dos permutaciones $\sigma,\tau\in S_n$ se dicen que son \textbf{disjuntas} si no hay ning\'{u}n elemento de $X$ que sea movido por ambas
permutaciones. Es decir, si $\Delta'_\sigma\cap \Delta'_\tau=\emptyset$ \index{Permutaci\'{o}n!Disjunta}
\end{defi}

\begin{prop}
Si $\sigma,\tau\in S_n$ son dos permutaciones disjuntas, $\sigma\tau=\tau\sigma$.
\end{prop}
\Proof
Denotemos por $\Delta_\sigma$ y $\Delta_\tau$ los elementos que quedan fijos respectivamente por $\sigma$ y $\tau$  y por
$\Delta_\sigma'$ y$\Delta'_\tau$  los elementos que  son movidos respectivamente por $\sigma$ y  $\tau$. Por hip\'{o}tesis,
$\Delta'_\sigma\cap \Delta'_\tau=\emptyset$, luego $X=\Delta'_\sigma\dot \cup  \Delta'_\tau\dot \cup Y$ con $Y\subset
\Delta_\sigma\cap\Delta_\tau$. As\'{\i},  $\Delta'_\sigma\subset \Delta_\tau$ y $\Delta'_\tau\subset \Delta_\sigma$ y por tanto:

$$\begin{array}{ll} \hbox{si }\   x\in \Delta'_\tau, (\implies \tau(x)\in \Delta_\tau'\subset \Delta_\sigma) & \hbox{ entonces, }
\sigma\circ \tau
(x)=\sigma(\tau(x))=\tau(x)\\
\hbox{si }\   x\in \Delta'_\sigma, (\implies x\in \Delta_\tau) & \hbox{ entonces, }   \sigma\circ \tau
(x)=\sigma(\tau(x))=\sigma(x)\\
\hbox{si }\   x\in Y,  & \hbox{ entonces, }   \sigma\circ \tau (x)=x
\end{array}$$ de forma similar,
$$\begin{array}{ll}
\hbox{si }\   x\in \Delta'_\tau, (\implies x\in \Delta_\sigma) & \hbox{ entonces, }   \tau\circ \sigma
(x)=\tau(\sigma(x))=\tau(x)\\
\hbox{si }\   x\in \Delta'_\sigma, (\implies \sigma(x)\in \Delta_\sigma'\subset \Delta_\tau) &
\hbox{ entonces, } \tau\circ \sigma
(x)=\tau(\sigma(x))=\sigma(x)\\
\hbox{si }\   x\in Y,  & \hbox{ entonces, }   \tau\circ \sigma (x)=x
\end{array}$$ Por lo que $\sigma\circ \tau=\tau\circ \sigma$.\EndProof



\begin{defi}\rm
Se dice que una permutaci\'{o}n $\sigma\in S_n$ es un \textbf{ciclo} de longitud $k$ si existen $a_1,a_2,\dots, a_k\in X$ tales que
$\sigma(a_i)=a_{i+1}$ para $i=1,2,\dots, k-1$, $\sigma(a_k)=a_1$ y ning\'{u}n otro elemento de $X$ es movido por $\sigma$.
\end{defi}\index{Permutaci\'{o}n!Ciclica o Ciclo}



\noindent \textbf{Notaci\'{o}n:} $\blacklozenge$ Normalmente un ciclo $\sigma\in S_n$ se denota por $\sigma=(a_1, a_2,\dots, a_k)$, lo que
significa que $\sigma$ mueve los elementos $a_i$ seg\'{u}n la definici\'{o}n de ciclo y deja fijo cualquier otro elemento.

$\blacklozenge$ Observar que al dar una permutaci\'{o}n en su forma matricial, sabemos a que $S_n$ pertenece. Mientras que  al dar un ciclo no sabemos en que grupo de permutaciones nos encontramos.

$\blacklozenge$ Observar que la representaci\'{o}n de una permutaci\'{o}n en ciclos no es \'{u}nica: $(1,2,3)=(2,3,1)=(3,1,2)$.

\begin{lema}[Ejercicio]
Sea $\sigma=(a_1,a_2,\dots,a_k)$ un ciclo de longitud $k$ en $S_n$. Entonces:
\item{(i)} $\sigma$ tiene orden $k$.
\item{(ii)} $\sigma^{-1}=(a_k,\dots, a_2,a_1)$
\end{lema}

\begin{ejem}\rm
Por ejemplo: $\rho_1$ y $\rho_2$ son ciclos de longitud tres,

$$\rho_1=\left(\begin{array}{ccc} 1&2&3\\ 2&3&1 \end{array}\right)=(1,2,3),\quad
 \rho_2=\left(\begin{array}{ccc} 1&2&3\\ 3&2&1 \end{array}\right)=(3,2,1)$$

 $\tau_1,\tau_2$ y $\tau_3$ son ciclos de longitud dos,

 \begin{eqnarray*}
\tau_1=\left(\begin{array}{ccc} 1&2&3\\ 1&3&2 \end{array}\right)=(2,3),&
 \tau_2=\left(\begin{array}{ccc} 1&2&3\\ 3&2&1 \end{array}\right)=(1,3),\\
\tau_3=\left(\begin{array}{ccc} 1&2&3\\ 2&1&3 \end{array}\right)=(1,2)&,
 \end{eqnarray*}
 y
$\rho_0=\left(\begin{array}{ccc} 1&2&3\\ 1&2&3 \end{array}\right)=(1)$ es un ciclo de longitud uno.
\end{ejem}


\hypertarget{Fciclo}{ }
\begin{center}
\shadowbox{\parbox{\columnwidth+0\fboxsep-10\fboxrule-\shadowsize}{
\centering
\begin{theo}\rm \label{Fciclo}
Toda permutaci\'{o}n $\sigma\in S_n$ distinta de la identidad se descompone como producto de ciclos disjuntos de
longitud mayor o igual que dos. Es m\'{a}s, esta descomposici\'{o}n es \'{u}nica salvo orden.
\end{theo}
}}
\end{center}


\Proof Sea $\gamma$ una permutaci\'{o}n arbitraria de $S_n$, $X=\{1,2,\dots, n\}$ y $\Delta'_\gamma$
 el conjunto de elementos de $X$ que son movidos por $\gamma$. Vamos a demostrar, por inducci\'{o}n al n\'{u}mero de elementos de
  $\Delta'_\gamma$, que $\gamma$ se factoriza como producto de ciclos disjuntos de elementos de $\Delta'_\gamma$:

Si $\#\Delta'_\gamma=2$ (nunca puede ser uno) tenemos que $\Delta'_\gamma=\{k_1,k_2\}$ y necesa\-ria\-mente $\gamma$ es igual al
ciclo $(k_1,k_2)$. Supongamos que toda permutaci\'{o}n $\gamma$, con $\#\Delta'_\gamma<m$, se factoriza como producto de ciclos
disjuntos de elementos de $\Delta'_\gamma$ y sea $\gamma$ con $\#\Delta'_\gamma=m$. Consideremos $k_1\in \Delta'_\gamma$ y el
subconjunto
$$Y=\{k_1,\sigma(k_1),\sigma^2(k_1),\dots,\sigma^m(k_1),\dots\}\subset \Delta'_\gamma.$$ Como
$\Delta'_\gamma\subset X$ es finito, existen $r,s\in \NN$, con $r<s$,  tales que $\sigma^r(k_1)=\sigma^s(k_1)$. Si $r\ne 0$, operando
 por la izquierda por $\sigma^{-r}$ tenemos que
$$k_1=\sigma^{-r}\sigma^r(k_1)=\sigma^{-r}\sigma^s(k_1)=\sigma^{s-r}(k_1)$$
y por tanto podemos considerar  $m_1$ el menor natural tal que $k_1=\sigma^{m_1}(k_1)$. Tenemos que
$Y=\{k_1,\sigma(k_1),\dots,\sigma^{m_1}(k_1\}$. Sea $c_1=(k_1,\sigma(k_1),\dots,\sigma^{m_1}(k_1))$, ciclo de longitud $m_{1+1}$.
Observar que si $x\in Y$, $$c_1(x)=\sigma(x)\eqno(1)$$ Como $\sigma(Y)\subset Y$, tenemos, por \ref{factimp}(ii) que
$$\sigma\vert_{\Delta'_\gamma-Y}: \Delta'_\gamma-Y\to \Delta'_\gamma-Y$$ es biyectivo por lo que podemos considerar la
permutaci\'{o}n:
$$\overline \sigma:X\to X \quad \hbox{definida por}\quad \overline\sigma(s):=\left\{\begin{array}{l}
\sigma(s)\quad \hbox{si}\quad s\in \Delta'_\gamma-Y\\
s\hskip .98truecm \hbox{si}\quad s\notin \Delta'_\gamma-Y
\end{array}\right.$$
Observar que $\overline \sigma$ toma los mismos valores que $\sigma$ en $\Delta'_\gamma-Y$, que adem\'{a}s tiene menos elementos que
$\Delta'\sigma$. por lo que por el proceso de inducci\'{o}n $\overline \sigma=c_2\circ\cdots\circ c_r$, producto de ciclos disjuntos
de elementos de $\Delta'\sigma$. Por tanto, $c_1$ es disjunto a todos los anteriores (los elementos de $c_1$ son los de $Y$).
Veamos que $\sigma=c_1\circ c_2\circ\cdots\circ c_r$:

Dado $x\in X$:

$\bigstar$ si $x\in \Delta'_\sigma-Y$, $c_2\circ\cdots\circ c_r(x)=\overline \sigma(x)=\sigma(x)\in \Delta'_\sigma-Y$ por lo que
$$c_1\circ c_2\circ\cdots\circ c_r(x)=c_1(c_2\circ\cdots\circ c_r(x))=c_2\circ\cdots\circ c_r(x)=\sigma(c)$$

$\bigstar$ si $x\in Y$, $c_2\circ\cdots\circ c_r(x)=x$ por lo que
$$c_1\circ
c_2\circ\cdots\circ c_r(x)=c_1(c_2\circ\cdots\circ c_r(x))=c_1(x)=\sigma(x)$$

$\bigstar$ si $x\in \Delta_\sigma$, $$c_1\circ c_2\circ\cdots\circ c_r(x)=x=\sigma(x)$$

Por lo que hemos ``factorizado"\  la permutaci\'{o}n $\sigma$.  Supongamos ahora que tenemos dos factorizaciones en ciclos disjuntos.
$$\sigma=c_1\circ c_2\circ\cdots\circ c_r=c'_1\circ c'_2\circ\cdots\circ c'_{r'}$$

Sea $c_1=(k_1,k_2,\dots, k_s)$. Si aplicamos la primera factorizaci\'{o}n  a $k_1$ (como la factorizaci\'{o}n es de ciclos disjuntos) nos
aparece $k_2$. Por lo que $k_1$ pertenece a alg\'{u}n ciclo de la segunda factorizaci\'{o}n. Es mas, aplicando reiteradamente la primera
factorizaci\'{o}n a $k_1$ obtenemos (por este orden) $k_2,k_3,\dots, k_s,k_1$. Por lo que el ciclo de la segunda factorizaci\'{o}n en
donde est\'{a} $k_1$ es exactamente $(k_1,k_2,\dots, k_s)$, es decir, $c_1$. Si simplificamos ahora $c_1$ de ambas factorizaciones y
reiteramos el proceso obtenemos que los ciclos son los mismos, lo que demuestra el teorema. \EndProof

\hypertarget{Paridad}{ }
\section{Paridad y Grupo alternado}\label{Paridad}


\hypertarget{Dtrans}{ }
\begin{defi}\rm \label{Dtrans}
Se define una \textbf{transposici\'{o}n} como un ciclo de longitud 2. \index{Permutaci\'{o}n!Transposici\'{o}n}
\end{defi}

\noindent\textbf{Nota:} Si $\sigma$ es una transposici\'{o}n, $\sigma^{-1}=\sigma$.
\begin{lema}
Cualquier ciclo de longitud $n$ se descompone como producto de $n-1$ transposiciones.
\end{lema}

\Proof
Sea $\sigma=(a_1,a_2,\dots,a_n)$ un ciclo de longitud $n$. Entonces
$$\sigma=(a_1,a_2)\circ (a_2,a_3)\circ \cdots \circ(a_{n-1},a_n)\eqno{(*)}$$
Demostremos la igualdad ($*$) por inducci\'{o}n a $n$. Si $n=2$ no tenemos nada que demostrar. Supongamos que la identidad es cierta para $n-1$. Entonces
$$(a_1,a_2)\circ (a_2,a_3)\circ \cdots \circ(a_{n-2},a_{n-1})\circ (a_{n-1},a_n)=(a_1,a_2,\dots,a_{n-1})(a_{n-1},a_n)$$
pero $$\begin{array}{l}
(a_1,a_2,\dots,a_{n-1})(a_{n-1},a_n)a_n=(a_1,a_2,\dots,a_{n-1})a_{n-1}=a_1\\
(a_1,a_2,\dots,a_{n-1})(a_{n-1},a_n)a_{n-1}=(a_1,a_2,\dots,a_{n-1})a_{n}=a_n\\
(a_1,a_2,\dots,a_{n-1})(a_{n-1},a_n)a_k=(a_1,a_2,\dots,a_{n-1})a_{nk}=a_{k+1}\quad k\le n-1
\end{array}$$
Por lo que $(a_1,a_2,\dots,a_{n-1})(a_{n-1},a_n)=(a_1,a_2,\dots,a_n)$.\EndProof


\textbf{Nota:} La siguiente es otra descomposici\'{o}n de un ciclo como producto de transposiciones: $(a_1,a_2,\dots,a_n)=(a_1,a_n)\circ(a_1,a_{n-1})\circ\cdots\circ (a_1,a_2)$.


\begin{coro}\rm
Toda permutaci\'{o}n $\sigma\in S_n$ se descompone como producto de transposiciones (no necesariamente disjuntas y no de forma \'{u}nica).
\end{coro}

\begin{lema}[Ejercicio]\rm \label{invtrans}
Sea $\sigma\in S_n$ una permutaci\'{o}n. Si $\sigma$ est\'{a} descompuesta como producto de transposiciones: $\sigma=\tau_1\circ\tau_2\circ\cdots\circ \tau_n$. Entonces $\sigma^{-1}=\tau_n\circ\cdots\circ \tau_2\circ \tau_1$.
\end{lema}

\hypertarget{Upar}{ }
\begin{center}
\shadowbox{\parbox{\columnwidth+0\fboxsep-10\fboxrule-\shadowsize}{
\centering
\begin{theo}\rm \label{Upar}
Sea $\sigma\in S_n$. Entonces, si  $\sigma$ se puede descomponer con un n\'{u}mero par (impar) de transposiciones, cualquier otra descomposici\'{o}n de $\sigma$ tendr\'{a} un n\'{u}mero par (impar) de transposiciones.
\end{theo}
}}
\end{center}

\Proof Demostremos en primer lugar esta propiedad para la permutaci\'{o}n identidad. Como $\Id=(1,2)\circ(1,2)$ (producto de dos transposiciones), tenemos que demostrar que cualquier descomposici\'{o}n de la identidad se escribe con un n\'{u}mero par de transposiciones: supongamos que $$\Id=(a_1,b_1)\circ\cdots\circ(a_n,b_n)$$
Sea $k$ un elemento de $X$ que aparezca  en alguna de las transposiciones. Supongamos que  $(a_i,b_i)$ es la primera transposici\'{o}n en la que aparece $k$, es decir, $a_i$ o $b_i$ es igual a $k$ (supongamos $a_i=k$) y $k$ no aparece en ninguna transposici\'{o}n $(a_r,b_r)$ con $r>i$.

  $\bullet$ Veamos que $i\ne 1$: en caso contrario  $$k=\Id\, k=(a_1,b_1)\circ\cdots\circ(a_n,b_n)k=(a_1,b_1)k=(k,b_1)k=b_1$$ una contradicci\'{o}n.

  $\bullet$ Por tanto la transposici\'{o}n $(k,b_i)$ no es la primera, con lo que nos podr\'{\i}amos encontrar con los siguientes casos para $(a_{i-1},b_{i-1})\circ (k,b_i)$: dados $x,y,z\in X$ distintos,
$$\begin{array}{l}
(x,y)\circ(z,b_1)=(z,b_1)\circ(x,y) \\
(x,z)\circ(z,b_1)=(z,b_1,x)=(x,z,b_1)=(x,b_1)\circ(x,z)\\
(x,b_1)\circ(z,b_1)=(b_1,z,x)=(z,x,b_1)=(z,b_1)\circ(z,x)\\
(z,b_1)\circ(x,b_1)=\Id
\end{array}$$
Luego, o me desaparecen dos transposiciones (caso cuarto), o puedo acercar  la transposici\'{o}n $(k,b_i)$ al primer lugar sin que haya mas apariciones de $k$ en lugares anteriores. Por tanto, como no puedo llegar al primer lugar, en alg\'{u}n momento desaparecer\'{a}.

Repitiendo este proceso para cualquier elemento que aparezca en las transposiciones se hace desaparecer (de dos en dos), con lo que, quitando un n\'{u}mero par de transposiciones se quitan todas, es decir, $n$ es par.

Hagamos ahora el caso general. Sea $\sigma\in S_n$ y supongamos que $$\sigma=(a_1,b_1)\circ\cdots\circ(a_n,b_n)=(a'_1,b'_1)\circ\cdots\circ(a'_m,b'_m)$$
Tenemos entonces que $\sigma^{-1}=(a_n,b_n)\circ\cdots\circ(a_1,b_1)$ y por tanto
$$\Id=(a_n,b_n)\circ\cdots\circ(a_1,b_1)\circ (a'_1,b'_1)\circ\cdots\circ(a'_m,b'_m)$$
Por el resultado anterior, $n+m$ es un n\'{u}mero par lo que obliga a que  $n$ y $m$ sean pares o $n$ y $m$ sean impares.
\EndProof


\hypertarget{Galt}{ }
\begin{defi}\rm \label{Galt}
Se dice que una \textbf{permutaci\'{o}n} $\sigma\in S_n$ es \textbf{par} si se puede escribir con un n\'{u}mero par de transposiciones. En caso contrario se dir\'{a} que $\sigma$ es \textbf{impar}. \index{Permutaci\'{o}n!Par}\index{Permutaci\'{o}n!Impar}
\end{defi}

\begin{prop}
Sea $n\in \NN$. Entonces $A_n:=\{\sigma\in S_n\ \vert\ \sigma\hbox{ es par}\}$ es un subgrupo de $S_n$, llamado el subgrupo alternado. Es m\'{a}s, $\#A_n=n!/2$.
\end{prop}

\Proof Es claro que el producto de dos permutaciones pares es una permutaci\'{o}n par. Por tanto la operaci\'{o}n es cerrada en $A_n$ (por uno de los ejercicios de clase $A_n$ es subgrupo de $S_n$, al ser $A_n$ finito). Ya se ha demostrado que $\Id\in A_n$ y por (\ref{invtrans}), si $\sigma\in A_n$, $\sigma^{-1}\in A_n$. Por \'{u}ltimo, la aplicaci\'{o}n
$$\Psi:A_n\to S_n-A_n\quad\hbox{definida por}\quad \Psi(\sigma)=\sigma\circ (1,2)$$

$\star$ Est\'{a} bien definida, ya que si $\sigma$ es par, $\sigma\circ (1,2)$ es impar.

$\star$ Tiene por aplicaci\'{o}n inversa la funci\'{o}n $\Phi: S_n-A_n\to A_n$ definida por $\Psi(\sigma)=\sigma\circ (1,2)$

$$\begin{array}{l}
\Psi\circ \Phi(\sigma)=\Psi(\sigma\circ (1,2))= \sigma\circ (1,2)\circ (1,2)=\sigma\\
\Phi\circ \Psi(\sigma)=\Phi(\sigma\circ (1,2))= \sigma\circ (1,2)\circ (1,2)=\sigma
\end{array}$$
Por lo que $\#A_n=\#(S_n-A_n)$ y por tanto $\#A_n=n!/2$.\EndProof

\hypertarget{Ejjcuatro}{}
\section{Ejercicios del Tema}\label{Ejjcuatro}
\setcounter{ejj}{0}

\begin{ejj}\rm
Sea $\sigma=(a_1,a_2,\dots,a_k)$ un ciclo de longitud $k$ en $S_n$. Entonces:
\item{(i)} $\sigma$ tiene orden $k$.
\item{(ii)} $\sigma^{-1}=(a_k,\dots, a_2,a_1)$
\end{ejj}

\begin{ejj}\rm
Sea $\sigma\in S_n$ una permutaci\'{o}n. Supongamos que $\sigma$ est\'{a} descompuesta como producto de
transposiciones: $\sigma=\tau_1\circ\tau_2\circ\cdots\circ \tau_n$. Entonces
$\sigma^{-1}=\tau_n\circ\cdots\circ \tau_2\circ \tau_1$.
\end{ejj}

\begin{ejj}\rm
Encuentra  una permutaci\'{o}n $\sigma\in S_{10}$ de orden m\'{a}ximo (demuestralo).\hfill\fbox{$*$}
\end{ejj}

\begin{ejj}\rm
Sean $\sigma,\tau$ dos ciclos disjuntos de longitud $n$ y $m$. Calcula el orden de
$\sigma\tau$.\hfill\fbox{$*$}
\end{ejj}

\begin{ejj}
Demuestra que el centro de $S_n$, para $n\ge 3$, es $\{\Id\}$.\hfill\fbox{$*$}
\end{ejj}

\begin{ejj}\rm
Descomp\'{o}n en ciclos disjuntos y en transposiciones las siguientes permutaciones:
$$\sigma=\left(\begin{array}{ccccccc} 1&2&3&4&5&6&7\\ 2&5&7&6&1&4&3 \end{array}\right),\quad
\tau=\left(\begin{array}{ccccccc} 1&2&3&4&5&6&7\\ 7&5&3&1&2&4&6 \end{array}\right)$$
\end{ejj}

\begin{ejj}\rm
Encuentra una figura $P$ tal que el conjunto de sus movimientos sea $S_4$.\hfill\fbox{$**$}
\end{ejj}


\begin{ejj}\rm
Calcula el subgrupo de movimientos de un rect\'{a}ngulo \'{a}ureo.
\end{ejj}

\begin{ejj}\rm
Demuestra que la transposici\'{o}n $(1,2)$ no se puede escribir como producto de ciclos de longitud $3$.
\end{ejj}

\begin{ejj}\rm
Demuestra que $D:=\{\sigma\in S_7\ \vert\ \sigma(1)=1 ,\sigma(4)=4\}\le S_7$.  ?`A quien es isomorfo?
\end{ejj}


\begin{ejj}\rm
Demuestra que $\sigma\tau$ y $\tau\sigma$, permutaciones de $S_n$, tienen la misma paridad.
\end{ejj}


\begin{ejj}\rm
Sea $B_n$ el conjunto de permutaciones impares de $S_n$. Definimos en $B_n$ el producto $$\sigma\star
\tau=\sigma\circ (1,2)\circ \tau$$ Demuestra que $(B_n,\star)$ tiene estructura de grupo. ?`Es isomorfo a
$A_n$?\hfill\fbox{$*$}
\end{ejj}


