Archivo de la etiqueta: Orden de un grupo

Álgebra Moderna I: Paridad de una permutación

Por Cecilia del Carmen Villatoro Ramos

Introducción

En la entrada anterior descubrimos que toda permutación se puede factorizar en producto de transposiciones. Mas aún, el polinomio de Vandermonde nos permite saber que, aunque hayan varias factorizaciones, en realidad, todas siempre tienen una cantidad par (o un cantidad impar) de transposiciones. Con esto, podemos definir el signo de una permutación.

Ya teniendo una noción de la paridad de una permutación podemos jugar con las consecuencias: podemos deducir qué pasa si multiplicamos dos permutación con la misma paridad, qué sucede cuando tienen distinta paridad y además, como es raro en los cursos de matemáticas… ¡podemos agrupar por paridad! En esta entrada, descubrimos que el conjunto de transposiciones con signo par, es en realidad un grupo con $\frac{n!}{2}$ elementos. Este conjunto es llamado el grupo alternante.

¿Pares o impares?

Definición. Sea $\alpha \in S_n$, $\alpha$ es par si $\alpha = \text{id}$ o si $\alpha$ es un producto de un número par de transposiciones. Por otro lado, $\alpha$ es impar si es un producto de un número impar de transposiciones.

La función signo es $sgn: S_n \to \{+1, -1\}$ definida como
\begin{align*}
sgn \; \alpha = \begin{cases} +1 & \text{si } \alpha \text{ es par} \\
-1 & \text{si } \alpha \text{ es impar}
\end{cases}
\end{align*}

Observación. Sean $\alpha = \tau_{1} \cdots \tau_r \in S_n$, con $\tau_{1}, \cdots, \tau_r$ transposiciones. Entonces $sgn\;\alpha = (-1)^r$.

Demostración.
La definición nos asegura que $sgn\;\alpha = +1$ si y sólo si $r$ es par.

$\square$

Proposición. Sean $\alpha, \beta \in S_n$. Entonces $$sgn \;(\alpha \, \beta) = sgn\, \alpha \; sgn \, \beta.$$

Esto nos dice que la función signo ($sgn$) es multiplicativa. Esto lo hace más sencilla de trabajar.

Demostración.

Esto es bastante fácil de demostrar, para usar lo que vimos tenemos que expresar a estas permutaciones como producto de transposiciones.

Sean $\alpha, \beta \in S_n$, con $\alpha = \tau_{1} \cdots \tau_r$, $\beta = \rho_1 \cdots \rho_t$. Donde, $\tau_1, \cdots, \tau_r, \rho_{1}, \cdots, \rho_t$ son transposiciones.

Si calculamos el signo del producto $\alpha\,\beta$ y usando la observación anterior, obtenemos lo siguiente:
\begin{align*}
sgn(\alpha \, \beta) &= sgn(\tau_1 \cdots \tau_r \, \rho_1 \cdots \rho_t) \\
& = (-1)^{r+t} & \text{Observación anterior}\\
& = (-1)^r \, (-1)^t & \text{Propiedades de las potencias}\\
& = sgn\, \alpha \; sgn\, \beta &\text{Observación anterior}
\end{align*}

Esto es precisamente lo que queríamos probar.

$\square$

Podemos concluir que para calcular el signo de un producto, basta entender el signo de cada uno de los factores.

Calculando el signo de una transposición

Seguiremos puliendo la idea que nos dio la proposición anterior hasta llegar a una fórmula para sacar el signo de una permutación. Pero por ahora, veamos qué sucede con los $r$-ciclos

Lema. Sea $\sigma = (i_1 \cdots i_r) \in S_n$ un $r$-ciclo. Entonces $sgn\, \sigma = (-1)^{r-1}$.

Demostración.
Recordemos que en la entrada anterior vimos que podemos ver a $\sigma$ como producto de transposiciones:
\begin{align*}
\sigma &= (i_1 \cdots i_r) = (i_1\,i_r) \cdots (i_1 \, i_2).
\end{align*}
Ituitivamente, estamos intercambiando a $i_1$ con los elementos que le siguen, esto nos da $r-1$ transposiciones. Por lo tanto, $\sigma$ es un producto de $r-1$ transposiciones. De acuerdo con la observación, podemos concluir que $sgn \, \sigma = (-1)^{r-1}$.

$\square$

Teorema. Sea $\alpha \in S_n$, $\alpha = \beta_1 \cdots \beta_t$ una factorización completa de $\alpha$. Entonces $sgn\,\alpha = (-1)^{n-t}$, donde $n$ es la cantidad de elementos que estoy permutando y $t$ es la cantidad de factores que tiene la factorización completa de $\alpha$.

Demostración.
Como el signo es multiplicativo,
\begin{align*}
sgn\,\alpha = \prod_{i=1}^t sgn\,\beta_i.
\end{align*}
Estamos tomando una factorización completa de $\alpha$, entonces todos los $\beta_i$ son ciclos disjuntos. Así que su signo está dado por la longitud del ciclo (de acuerdo al lema dado):
\begin{align*}
sgn\,\beta_i = (-1)^{\text{long}\,\beta_i-1} \qquad \forall i\in\{1,\dots,t\}.
\end{align*}
Juntando ambas ecuaciones y sumando los $t$ exponentes obtenemos las siguientes igualdades
\begin{align*}
sgn\,\alpha &= \prod_{i = 1}^{t} sgn \,\beta_i & \text{Proposición}
\\&= \prod_{i = 1}^t (-1)^{\text{long}\,\beta_i – 1} &\text{Lema}\\
& = (-1)^{\left(\sum_{i = 1}^t \text{long}\,\beta_i \right) – t} = (-1)^{n-t}. &\text{Leyes de exponentes}
\end{align*}

Como la factorización es completa, la siguiente igualdad se cumple: $$\sum_{i = 1}^t \text{long}\,\beta_i = n.$$

Por lo tanto $sgn\,\alpha = (-1)^{n-t}$.

$\square$

Esta forma resulta útil porque ya no necesito descomponer una permutación en producto de transposiciones, nos basta con encontrar una factorización completa. Veamos esto con un ejemplo.

Ejemplo.
Consideremos $\alpha \in S_{10}$ como
\begin{align*}
\alpha = \begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\
2 & 4 & 7 & 5 & 1 & 8 & 3 & 9 & 6 & 10
\end{pmatrix}.
\end{align*}

También podemos escribirla como $\alpha = (1\;2\;4\;5)(3\;7)(6\;8\;9)(10)$. Esto nos muestra que $\alpha$ es una factorización completa con 4 factores.

Entonces, de acuerdo con el teorema que acabamos de probar, $sgn\,\alpha = (-1)^{10-4} = (-1)^6 = +1$.

Por otro lado podemos sacar una factorización de $\alpha$ en transposiciones: $\alpha = (1 \; 5)(1 \; 4)(1 \; 2)(3 \; 7)(6 \; 9)(6 \; 8)$ que tiene 6 transposiciones. Entonces, efectivamente $\alpha$ es un producto de un número par de transposiciones.

Hora de Agrupar

Hemos visto que la función $sgn$ es una función mutliplicativa. Esto nos da como consecuencia que al multiplicar dos permutaciones con la misma paridad, te da como resultado una permutación par. En caso contrario, el resultado es impar. Ahora nos fijaremos solamente en las permutaciones pares.

Definición. El grupo alternante para $n$ elementos está definido como

$$A_n = \{\alpha \in S_n | sgn \, \alpha = +1\}.$$

Observación. $A_n$ efectivamente es un subgrupo de $S_n$.

Demostración.
Si $\alpha = \text{id}$, por definición del signo, $sgn\,\text{id} = +1$. Así, $\text{id}\in A_n$.

Sean $\alpha, \beta \in A_n$.
Como la función signo es multiplicativa:
\begin{align*}
sgn\,\alpha\beta = sgn \, \alpha \; sgn \, \beta = (+1)(+1) = +1.
\end{align*}
Así, $\alpha\beta \in A_n$. Es decir, $A_n$ es cerrada bajo el producto.

Por último, sea $\alpha \in A_n$.

Por un lado, usando la propiedad multiplicativa del signo obtenemos:
\begin{align*}
sgn\,(\alpha\alpha^{-1}) = sgn \, \alpha \; sgn \, \alpha^{-1} = (+1)\, sgn\, \alpha^{-1}.
\end{align*}

Por otro lado, como $\alpha \,\alpha^{-1} = \text{id}$, tenemos:
\begin{align*}
sgn\,(\alpha\,\alpha^{-1}) = sgn\, \text{id} = +1.
\end{align*}

Por lo tanto $sgn\,(\alpha\, \alpha^{-1}) = +1$, así $\alpha^{-1} \in A_n$. Es decir, $A_n$ es cerrada bajo inversos.

Por lo tanto $A_n$ es un subgrupo de $S_n$.

$\square$

El siguiente resultado nos muestra que el grupo alternante $A_n$ «parte en dos» a las permutaciones, es decir, la mitad de permutaciones son pares.

Proposición. Sea $n>1$, entonces $|A_n| = \frac{n!}{2}$.

Demostración. Podemos ver a $S_n$ como la unión de las permutaciones pares e impares, esto se expresa así $$S_n = A_n \cup (S_n\setminus A_n).$$
Pero, podemos dar una biyección definida como $\phi: A_n \to S_n\setminus A_n$, definida como $\phi \, \alpha = (1\;2)\alpha$.

Entonces, $|A_n| = \# S_n \setminus A_n$.

Así, como dijimos que

$n! = |S_n| = |A_n| + \# S_n\setminus A_n = 2 |A_n|$.

Por lo tanto $|A_n| = \frac{n!}{2}$.

Notación. Para denotar la cardinalidad u orden de un conjunto $A$, usamos dos notaciones:
\begin{align*}
|A| \to & \;\text{Si $A$ es un grupo.}\\
\# A \to & \;\text{Si $A$ no es un grupo (o si no sabemos si $A$ es un grupo o no).}
\end{align*}

Tarea moral

  1. Considera el elemento $\alpha \in S_{12}$ como
    \begin{align*}
    \alpha = \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 &10&11&12\\
    2 & 11&4& 1 & 8 &12& 3 & 6 & 9 & 5 & 7 & 10
    \end{pmatrix}
    \end{align*}
    1. Encuentra $\alpha^{-1}$, el signo de $\alpha$ y el de $\alpha^{-1}$.
    2. En general, ¿qué pasará con el signo de una permutación y de su inversa?
  2. Sea $\alpha$ un $r$ ciclo en $S_n$. ¿Podemos determinar el signo de $\alpha$ a partir de la paridad de $r$?
  3. Dada $\alpha \in S_n$ decimos que los números $i,j \in \{1,2,\dots,n\}$ forman una inversión si $i<j$ pero $\alpha(i) > \alpha(j)$. ¿Qué relación existe entre la paridad y el número de inversiones de $\alpha$?
  4. Encuentra todos los elementos de $A_4$.

Más adelante…

Esta entrada nos sirvió para construir los cimientos, es importante que lo tengamos claro antes de avanzar. En la siguiente entrada definiremos el producto de $S$ con $T$, veremos en qué situaciones el producto de los subconjuntos conmuta, cuándo se cumple que $ST$ es un subgrupo de $G$. Esto nos ayudará para definir las clases laterales. Más adelante, estas clases nos ayudarán a definir una nueva relación de equivalencia.

Entradas relacionadas

Álgebra Moderna I: Orden de un grupo

Por Cecilia del Carmen Villatoro Ramos

Introducción

Ya vimos qué es el orden de un elemento y el grupo cíclico generado por ese elemento. En esta entrada veremos a qué se le denomina el orden de un grupo, que en realidad es un concepto que ya conoces.

Primero repasemos cómo es el conjunto generado por $a$, éste se puede describir así:

$\{\dots, a^{-2}, a^{-1}, e, a^{1}, a^2, \dots\}$.

En esa sucesión de potencias de $a$, si el elemento $a$ tiene orden finito, eventualmente encontraremos $a^{o(a)}$. Por la entrada anterior sabemos que $o(a)$ es el mínimo entero positivo tal que $a^{o(a)} = e$. Entonces, $a^{o(a) + 1} = e a = a$. Esto nos puede indicar que en algún momento la sucesión se volverá a repetir. Entonces el rango que no tiene repeticiones sería el siguiente:

$e, a, a^2, \dots a^{o(a) -1}$.

A continuación formalizaremos esta idea, definiremos el orden de un grupo y relacionaremos el orden de un elemento con el orden del grupo generado por éste.

Definición de orden de un grupo

Definición: Sea $G$ un grupo. El orden de $G$ es la cardinalidad del conjunto $G$ y se denota por $|G|$.

Teorema: Sean $G$ un grupo y $a\in G$ un elemento de orden finito. Entonces

$|\left< a\right>| = o(a)$.

Demostración.
Sea $G$ un grupo y $a \in G$ de orden finito.

Considera que $e$ es el neutro en $G$. Primero veamos que

$\begin{align*} \left< a\right> = \{e, a, a^2, \dots, a^{o(a)-1}\} \end{align*}$.

$\subseteq]$
Sea $x \in \left< a\right>$, entonces existe algún $k \in \z $ tal que $x =a^k$.
Por el algoritmo de la división existen $q, r \in \z$ tales que

$k = o(a)q + r\;$ con $\;0 \leq r < o(a)$.

Entonces, sustituyendo el valor de $k$,

$x = a^k = a^{o(a)q + r}$.

Si seguimos realizando operaciones con los exponentes, obtenemos:

$\begin{align*}
a^{o(a)q + r} &= (a^{o(a)})^q a^r \\
&= e^q a^r &\text{ por la definición de orden}\\
&= e a^r &\text{ya que $e$ es el neutro}\\
&= a^r &\text{ya que $e$ es el neutro}
\end{align*}$

es decir, $x = a^r$ para algún $ r \in \z$, con $0\leq r < o(a)$. Entonces

$x \in \{e, a, a^2, \dots, a^{o(a)-1}\}$.

Hemos demostrado así la primera contención.

$\supseteq]$

Esta contención es más sencilla porque claramente

$\{e, a, a^2, \dots, a^{o(a)-1}\} \subseteq \{\dots, a^{-2}, a^{-1}, e, a, a^2, \dots\}$.

Y como $\left< a\right> = \{ a^{k}\mid k\in\mathbb{Z}\}=\{\dots, a^{-2}, a^{-1}, e, a, a^2, \dots\}$, se cumple la segunda contención y con ella la igualdad de conjuntos.

Todavía nos falta un detalle. Hasta ahora sabemos que

$\begin{align*} \left< a\right> = \{e, a, a^2, \dots, a^{o(a)-1}\} \end{align*}$

pero nada nos asegura que $|\{e, a, a^2, \dots, a^{o(a)-1}\}| = o(a)$, es decir que tenga tantos elementos como el orden de $a$. Esto lo probaremos viendo que no existen elementos repetidos.

Supongamos que $a^{i} = a^j$ para $i, j \in \{0,1,\dots, o(a)-1\}$, supongamos sin pérdida de generalidad que $i \leq j$.

Multiplicando ambos lados por $(a^i)^{-1}$ obtenemos,

$\begin{align*} a^{i}(a^{i})^{-1} &= a^j(a^{i})^{-1}\\
e &= a^{j-i}.\end{align*}$

Entonces, $e = a^{j-i}$, pero, por la elección de $i$ y de $j$ sabemos que $0 \leq j – i < o(a)$. Entonces, debido a la definición de $o(a)$ esto sólo es posible si $j-i=0$, es decir $j = i$.

Así $\left< a\right> = \{e, a, a^2, \dots, a^{o(a)-1}\}$ tiene $o(a)$ elementos. Por lo tanto

$|\left< a\right>| = o(a)$.

$\square$

Un pequeño ejemplo

Ejemplo.
Recordemos que de acuerdo a lo que se definió en un ejemplo de la entrada anterior tenemos que $U(\z_{7})$ consiste de todas las clases módulo 7 que tienen inverso multiplicativo, es decir $U(\z_{7}) = \{ \bar{n}\in\z_7\mid (n,7)=1\}$. Tenemos que $U(\z_{7}) = \{\bar{1}, \bar{2}, \bar{3}, \bar{4}, \bar{5}, \bar{6}\}$. Sabemos que este conjunto es un grupo con la multiplicación. Observemos que en los enteros módulo 7 no todas las clases tienen inverso multiplicativo, sólo aquellas representadas por primos relativos con 7, por eso $\bar{0}$ no está en nuestro conjunto $U(\z_{7})$.

Podemos hacer algunas operaciones:

  • $(\bar{4})^2 = \overline{4^2} = \overline{16} = \bar{2}$, en este caso $(\bar{4})^2$ no es el neutro, entonces intentemos lo siguiente:
  • $(\bar{4})^3 = (\bar{4})^2\,\bar{4} = \bar{2}\, \bar{4} = \bar{8} = \bar{1}$, así $o(\bar{4}) = 3$.

Por lo tanto, $\left< \bar{4} \right> = \{\bar{1}, \bar{4}, (\bar{4})^2\} = \{\bar{1}, \bar{4}, \bar{2}\}$ , así $\left|\left< \bar{4}\right>\right| = 3$.

Consecuencias

Hasta ahora hemos visto que la cantidad de elementos que hay en el generado por $a$, es decir $\left< a\right>$, está definido por el orden de $a$, denotado por $(o(a))$. En consecuencia tenemos el siguiente corolario.

Corolario. Sea $G$ un grupo y $a\in G$. Tenemos que $a$ es de orden finito si y sólo si $\left< a\right>$ es un conjunto finito.

Demostración.
Sea $G$ un grupo y $a\in G$.

$|\Rightarrow)$ Si $a$ es de orden finito, por el primer teorema que probamos en esta entrada,

$|\left< a \right>| = o(a) \in \z^+$

$\therefore$ $|\left< a \right>|$ es finito.

$|\Leftarrow)$ Si $\left< a \right>$ es un conjunto finito, entonces
$\{\dots, a^{-1}, e, a^1, a^2, \dots\}$ tiene repeticiones.

Sean $i,j \in \z$ con $i \neq j$ tales que $a^{i} = a^j$.
Sin pérdida de generalidad supongamos que $i < j$. Multiplicando por $(a^{i})^{-1}$ en ambos lados,

$\begin{align*}a^{i} (a^{i})^{-1} &= a^{j} (a^{i})^{-1}\\
e &= a^{j-i}\end{align*}$

con $j-i \in \z^+$. Por lo tanto $a$ es de orden finito.

$\square$

Corolario. Todo elemento de un grupo finito es de orden finito.

Demostración.
Sea $G$ un grupo finito y $a\in G$.

Como $\left< a \right> \subseteq G$ y $G$ es finito, entonces $\left< a \right>$ también es finito por el corolario anterior $a$ es de orden finito.

$\square$

Tarea moral

  1. Considera $G = \left< a \right>$ un grupo cíclico infinito:
    1. Encuentra el subgrupo de $G$ con la menor cantidad de elementos posible, que tenga como elemento a $a^4$.
    2. Encuentra el subgrupo de $G$ con la menor cantidad de elementos posible, que tenga como elementos a $a^4$ y a $a^6$.
    3. Encuentra el subgrupo de $G$ con la menor cantidad de elementos posible, que tenga como elementos a $a^4$ y a $a^9$.
    4. ¿Son cíclicos? Si lo son, encuentra un generador.
  2. Sea $G$ un grupo finito. Sea $S$ el subgrupo de elementos $g$ tales que $g^5 = e$, donde $e$ es el elemento neutro de $G$. Prueba que el orden de $S$ es impar.
    Hint: si $G$ es un grupo, $a \in G$ y existe $p \in \z$ primo tal que $a^p = e$, entonces $o(a) = p$.
  3. ¿Es posible que exista un grupo infinito tal que cada elemento sea de orden finito? De ser cierto, da un ejemplo. En caso contrario prueba que. no existe tal grupo.

Más adelante…

En las siguientes entradas estudiaremos más resultados y consecuencias que se derivan de todas las definiciones que hemos dado.

Entradas relacionadas