Archivo de la etiqueta: permutaciones

Álgebra Moderna I: Teorema de Cayley

Por Cecilia del Carmen Villatoro Ramos

Deja un comentario

Introducción

¡Hoy es el día en el que comenzamos la Unidad 4!

A partir de esta unidad veremos cada uno de los elementos de los grupos (para cualquier grupo) se puede ver como una permutación. Para fines introductorios, ilustremos qué pasa en el caso de un grupo finito. Sea $G = \{e,g_2,\dots, g_n\}$, podemos escribir su tabla de producto ($*$):

$*$$e$$g_2$$g_3$$\cdots$$g_n$
$e$
$g_2$
$g_3$
$\vdots$
$a = g_i$$ae$$ag_2$$ag_3$$\cdots$$ag_n$
$\vdots$
$g_n$

¿Qué pasa si elegimos un elemento fijo? Fijemos $g_i$, para distinguirlo, denotémoslo como $a = g_i.$ Así, en la tabla del producto ese renglón quedaría $ae \;\; ag_2 \;\; ag_3 \;\; \cdots \;\; ag_n$. Como $a = g_i \in G$ y todos los demás elementos también, ese renglón está conformado por elementos de $G$.

Podría darse el caso en que $ag_k = ag_t$ para algún $k,t\in \{1,\dots,n\}$, pero como $G$ es un grupo, podemos cancelar la $a$. Entonces $ag_k = ag_t \Leftrightarrow g_k = g_t$. Así, si suponemos que $g_k \neq g_t$ para todas $g \neq t$ con $g,t\in \{1,\dots,n\}$, en el renglón de $a$ aparecen $n$ elementos distintos. Es decir, aparecen todos los $n$ elementos de $G$ pero quizás en otro orden.

De esta manera, el efecto que tiene $a$ sobre los elementos de $G$ es de moverlos. Esto sucederá en cualquier renglón de la tabla, es decir, cualquier elemento de $G$ funciona como una permutación. Esto es importante porque nos permitirá visualizar a cualquier grupo como un grupo de permutaciones.

Esta es la razón por la cual las permutaciones son tan importantes y por eso tenemos que estudiarlas bien.

La función tao $\tau$

Bajo la idea propuesta en la demostración, todo grupo se puede pensar como un subgrupo de un grupo de permutaciones. Para formalizar esta idea comenzaremos con un lema.

Lema.
Sea $G$ un grupo, $a\in G$. La función $\tau_a:G \to G$ dada por $\tau_a(g) = ag$ para todo $g\in G$, es una biyección.

Demostración.

Sea $G$ un grupo, $a\in G$. Consideremos la función $\tau_a:G\to G$ con $\tau_a(g) = ag$ para todo $g\in G$.

P.D. $\tau_a$ es biyectiva.
Consideremos la función $\tau_{a^{-1}}:G\to G$ con $\tau_{a^{-1}} = a^{-1} g$, para toda $g\in G.$ Dado $g\in G$.
\begin{align*}
\tau_{a^{-1}}\circ\tau_a(g) & = \tau_{a^{-1}}(\tau_a(g)) = \tau_{a^{-1}}(ag) = a^{-1}(ag) = g\\
\tau_a\circ\tau_{a^{-1}}(g) &= \tau_a(\tau_{a^{-1}}(g)) = \tau_a(a^{-1}g) = a(a^{-1}g) = g.
\end{align*}

Donde todas las igualdades son por definición de $\tau$ y $\tau^{-1}$ ó por propiedades de grupo.

Así, $\tau_{a^{-1}}$ es la inversa de $\tau_a$ y entonces $\tau_a$ es biyectiva.

$\blacksquare$

Observación. Si $a\neq e$, $\tau_a$ no es un homomorfismo.
La demostración queda como ejercicio. Sucederá que si $a\neq e$, entonces $\tau_a$ seguirá siendo función biyectiva, pero no un homomorfismo.

El título de la entrada

El Teorema de Cayley es quien nos dirá exactamente lo que queremos formalizar esta entrada.

Teorema. Teorema de Cayley.
Todo grupo de $G$ es isomorfo a un subgrupo de $S_G$. En particular, todo grupo finito de orden $n$ es isomorfo a un subgrupo de $S_n$.

Demostración.
Sea $G$ un grupo. Definimos,
\begin{align*}
\phi: G \to S_G \text{ con } \phi(a) = \tau(a) \; \forall a\in G.
\end{align*}

Veamos que $\phi$ es un homomorfismo.
Tomemos $a,b\in G$.
P.D. $\phi(ab) = \phi(a)\circ\phi(b) = \phi(a)\phi(b)$.

Dado $g\in G$, aplicamos la función $\phi(ab)$ a $g$.
\begin{align*}
\phi(ab)(g) &= \tau_{ab}(g)\\
&= (ab)g \\
&= a(bg) \\
&= \tau_a(\tau_b(g)) \\
& = \tau_a\circ\tau_b(g) = \phi(a)\circ\phi(b)(g).
\end{align*}

Por lo tanto $\phi$ es un homomorfismo.

Veamos que $\phi$ es un monomorfismo. Sea $a\in \text{Núc }\varphi$,
\begin{align*}
\Rightarrow\; & \phi(a) = \text{id}_G & \text{Definición de Núc}\\
\Rightarrow\; & \phi(a) (g) = \text{id}_G(g) &\forall g\in G \\
\Rightarrow\; & \tau_a(g) = a & \forall g\in G\\
\Rightarrow\; &ag = g & \forall g\in G \\
\Rightarrow\; &a = e.
\end{align*}

En particular, podría ser $g = e$. Entonces podríamos probar que $a = e$ de distintas maneras y obtener lo mismo. De esta manera $\phi$ es un monomorfismo.

Así, al restringir el codominio de $\phi $ a la imagen $\text{Im }\phi$ obtenemos un isomorfismo.
Por lo tanto $G\cong \text{Im }\phi \leq S_G$. Con esto tenemos la primero parte del teorema demostrada.

En particular, si $|G| = n $ tenemos que $S_G \cong S_n$ y como $G\cong \text{Im }\phi \leq S_n$, entonces $G$ es isomorfo a un subgrupo de $S_n$.

$\blacksquare$

Ejemplo:

Tomemos $V = \{(0,0), (1,0), (0,1), (1,1)\}$ el grupo de Klein, con la suma entrada a entrada módulo 2.
Sean $a_1 = (0,0), a_2 = (1,0), a_3 = (0,1), a_4 = (1,1)$. Tenemos la tabla de suma de la siguiente manera:

$+$$a_1$$a_2$$a_3$$a_4$
$a_1$$a_1$$a_2$$a_3$$a_4$
$a_2$$a_2$$a_1$$a_4$$a_3$
$a_3$$a_3$$a_4$$a_1$$a_2$
$a_4$$a_4$$a_3$$a_2$$a_1$

Entonces $\tau_{a_2}$ intercambia $a_1$ y $a_2$ e intercambia $a_3$ y $a_4$ de lugar. Viendo a $a_2$ como una permutación, correspodería a $\sigma \in S_4$ con $\sigma = (1\;2)(3\;4).$

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Demostrar la observación:
    Observación. Si $a\neq e$, $\tau_a$ no es un homomorfismo.
  2. Para los siguientes grupos $G$ y $a\in G$ determina cómo es la función $\tau_g:$
    • $G$ es cíclico de orden 6, $g$ un generador de $G$.
    • $G = D_{2(4)}$, $g = b$ la reflexión sobre el eje $x$.
    • $G = Q$, $g = -j$.
  3. En los diferentes inicios del ejercicio anterior, describe cómo se puede visualizar al elemento $g\in G$ como una permutación en $S_n$ con $n = |G|.$

Más adelante…

Esta entrada es la primera de la unidad 4 porque a partir de aquí, sólo nos podemos ir más abstracto. Aquí vimos que un grupo se puede ver como permutaciones porque podemos multiplicar $g\in G$ con todos los elementos de $G$. Pero a lo largo de este curso vimos varias operaciones que están definidas a partir del producto de $G$, por ejemplo, si tenemos $aN \in G/N$ con $N$ normal en $G$, es perfectamente válido operar $gaN$. Siguiendo la lógica del Teorema de Cayley, ¿qué significa esto? ¿Será posible una relación similar entre cualesquiera dos grupos? Estas y más preguntas serán respondidas en las siguientes entradas.

Entradas relacionadas

Cálculo Diferencial e Integral III: Determinantes

Por Alejandro Antonio Estrada Franco

Deja un comentario

Introducción

El determinante de una matriz cuadrada es un número asociado a esta. Como veremos, los determinantes nos proporcionarán información de interés para varios problemas que se pueden poner en términos de matrices.

Recuerda que los temas de esta unidad son tratados a manera de repaso, por lo cual no nos detenemos en detallar las demostraciones, ni a extender las exposiciones de las definiciones. Para mayor detalle, te remitimos al curso de Álgebra Lineal I, específicamente comenzando con la entrada Transformaciones multilineales. Aún así, es recomendable que revises estas notas en el curso de Cálculo Diferencial e Integral III, pues sintentizamos los temas de tal manera que recuperamos los conceptos relevantes para el cálculo de varias variables. Así mismo, en ocasiones, abordamos las definiciones y resultados de manera un poco distinta, y es muy instructivo seguir los mismos conceptos abordados con un sabor ligeramente distinto.

Permutaciones

Recordemos que en la entrada anterior definimos para cada $n\in \mathbb{N}$ el conjunto $[n]=\{1, 2,\ldots, n\}$.

Definición. Una permutación del conjunto $[n]$ es una función biyectiva $\sigma :[n]\rightarrow [n]$. Una forma de escribir a $\sigma$ de manera más explícita es la siguiente:
\[ \sigma = \begin{pmatrix} 1 & 2 & \dots & n \\
\sigma(1) & \sigma(2) & \dots & \sigma(n) \end{pmatrix} \]

Podemos pensar también a una permutación como un reacomodo de los números $1, 2, …, n$. Pensado de esta manera, escribimos $\sigma =\sigma(1) \sigma(2)\dots \sigma(n)$.

El conjunto de todas las permutaciones del conjunto $[n]$ se denota como $S_n$. Una observación interesante es que $S_{n}$ tiene $n!$ elementos.

Definición. Para $\sigma \in S_{n}$, una inversión en $\sigma$ consiste en un par $(i,k)\in [n]\times [n]$ tal que $i>k$ pero $i$ precede a $k$ en $\sigma$ cuando se considera $\sigma$ como lista. Diremos que $\sigma$ es permutación par o impar según tenga un número par o impar de inversiones.

Ejemplo. Consideremos $\sigma=12354$ permutación en $[5]$. Tenemos que $(5,4)$ es una inversión en $\sigma$ pues $5>4$ pero en la permutación $5$ precede a $4$. Al tener $\sigma$ una sola inversión, es una permutación impar.

$\triangle$

Definición. El signo de $\sigma$, denotado $\text{sign}(\sigma)$ se define como:
\[
\text{sign}(\sigma )= \begin{cases} 1 & \text{si $\sigma$ es par} \\
-1 & \text{si $\sigma$ es impar.}\end{cases}
\]

Sea $A\in M_{n}(\mathbb{R})$. Pensemos en un producto de $n$ entradas de $A$ tomadas de tal manera que se eligió una y sólo una de cada fila y columna. Podemos reordenar los números para poner en orden la fila de la que tomamos cada uno, y escribir el producto como
\begin{equation}
a_{1j_{1}} a_{2j_{2}}\dots a_{nj_{n}}.
\label{eq:producto}
\end{equation}

Así, $a_{kj_{k}}$ nos dice que en la fila $k$ tomamos la entrada de la columna $j$. Como se eligió una y sólo una entrada por columna, tenemos que $j_1,\ldots,j_n$ es una permutación de $[n]$. Y viceversa, cada permutación $\sigma =j_{1}\dots j_{n} \in S_{n}$ determina un producto como en \eqref{eq:producto}. Por ello la matriz $A$ nos entrega $n!$ productos con esta característica.

Determinantes en términos de permutaciones

A partir de las permutaciones podemos definir a los determinantes.

Definición. El determinante de la matriz $A$, denotado por $\det(A)$, se define como:
\[
\det(A)=\sum_{\sigma \in S_{n}} \left(\text{sign}(\sigma)\prod_{i=1}^{n} a_{i\sigma (i)}\right)
\]
donde
\[
\sigma = \begin{pmatrix} 1 & 2 & \dots & n \\
\sigma (1) & \sigma (2) & \dots & \sigma (n)
\end{pmatrix}
\]

Ejemplo. Para la matriz \[ A= \begin{pmatrix} 0 & 2 & 1 \\ 1 & 2 & 0 \\ 3 & 0 & 1 \end{pmatrix} \] tomemos en cuenta las permutaciones del conjunto $[3]$ las cuales son: \[ \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix} \]

De acuerdo a la definición de determinante, tenemos:

\begin{align*}
\det(A)=&(1)a_{11}a_{22}a_{33}+(-1)a_{11}a_{23}a_{32}+(-1)a_{12}a_{21}a_{33}+\\
&(1)a_{12}a_{23}a_{31}+(1)a_{13}a_{22}a_{31}+(-1)a_{13}a_{21}a_{32}\\
=&0\cdot 2\cdot 1+(-1)0\cdot 0\cdot 0+(-1)2\cdot 1\cdot 1+\\
&(1)2\cdot 0\cdot 3+(1)1\cdot 2\cdot 3+(-1)1\cdot 1\cdot 0\\
=&4.
\end{align*}

$\triangle$

Propiedades de los determinantes

Veamos algunas de las propiedades que tienen los determinantes. Aprovecharemos para introducir algunas matrices especiales.

Definición. La matriz identidad $I\in M_{n}(\mathbb{R})$ es aquella que cumple que en las entradas de la forma $(i,i)$ son iguales a 1 y el resto las entradas son iguales a 0.

Definición. Diremos que una matriz $A\in M_n(\mathbb{R})$ es una matriz triangular superior si cumple $a_{ij}=0$ para $i>j$. La llamaremos triangular inferior si cumple $a_{ij}=0$ para $i<j$. Finalmente, diremos que es diagonal si cumple $a_{ij}=0$ para $i\neq j$ (en otras palabras, si simultáneamente es triangular superior e inferior).

Definición. Sea $A\in M_{m,n}(\mathbb{R})$. La transpuesta de la matriz $A$, denotada por $A^t$, es la matriz en $M_{n,m}(\mathbb{R})$ cuyas entradas están definidas como $(a^{t})_{ij} =a_{ji}$.

El siguiente resultado enuncia algunas propiedades que cumplen los determinantes de la matriz identidad, de matrices transpuestas, y de matrices triangulares superiores, triangulares inferiores y diagonales.

Proposición. Sea $A\in M_{n}(\mathbb{R})$. Se cumple todo lo siguiente.

  1. $\det(A)=\det(A^{t})$.
  2. Si $A$ tiene dos filas iguales $\det(A)=0$.
  3. Si $A$ tiene dos columnas iguales $\det(A)=0$.
  4. Si $A$ es triangular superior, triangular inferior, o diagonal, $\det(A)=\prod_{i=1}^{n} a_{ii}$.
  5. $\det(I_n)=1$.

Demostración.

  1. Notemos que (tarea moral) $\text{sign}( \sigma )= \text{sign}( \sigma ^{-1})$, así tenemos que
    \begin{align*}
    \det(A^{t})&=\sum_{\sigma \in S_{n}} \text{sign}(\sigma)a_{\sigma (1) 1}\dots a_{\sigma (n) n}\\
    &=\sum_{\sigma \in S_{n}} \text{sign}(\sigma ^{-1})a_{1\sigma (1)}\dots a_{n\sigma (n)}\\
    &= \sum_{\sigma \in S_{n}} \text{sign}(\sigma)a_{1\sigma (1)}\dots a_{n\sigma (n)}\\&= \det(A).
    \end{align*}
  2. Si tenemos dos filas iguales, en cada producto $a_{1\sigma (1)}\cdots a_{n\sigma (n)}$ tenemos dos factores de la misma fila, por tanto para cada producto tenemos otro igual en la suma solo que con signo contrario (signo de la permutación correspondiente); al hacer la suma estos sumandos se anularán por pares resultando en cero.
  3. Mismo argumento que en el inciso anterior.
  4. Si tenemos una matriz triangular, ya sea superior, o inferior $\prod_{i=1}^{n} a_{i\sigma (i)}\neq 0$ sólo cuando $\sigma(i)=i$ ya que en otro caso este producto siempre tendrá algún factor cero.
  5. Es un corolario de la propiedad anterior, pues la matriz identidad es una matriz diagonal con puros unos en la diagonal.

$\square$

Otra propiedad muy importante del determinante es que es multiplicativo. A continuación enunciamos el resultado, y referimos al lector a la entrada Propiedades de determinantes para una demostración.

Teorema. Sean $A$ y $B$ matrices en $M_n(\mathbb{R})$. Se tiene que $$\det(AB)=\det(A)\det(B).$$

Mas adelante…

En la siguiente entrada revisaremos la teoría de sistemas de ecuaciones lineales. Comenzaremos definiéndolos, y entendiéndolos a partir de las operaciones elementales que definimos en la entrada anterior. Hablaremos un poco de cómo saber cuántas soluciones tiene un sistema de ecuaciones. Así mismo veremos que en ciertos sistemas de ecuaciones lineales, podemos asociar una matriz cuyo determinante proporciona información relevante para su solución.

Un poco más adelante también hablaremos de diagonalizar matrices. A grandes rasgos, esto consiste en encontrar representaciones más sencillas para una matriz, pero que sigan compartiendo muchas propiedades con la matriz original. El determinante jugará de nuevo un papel muy importante en esta tarea.

Tarea moral

  1. Sea $\sigma \in S_{n}$. Muestra que su inversa, $\sigma ^{ -1}$ también es una permutación. Después, muestra que
    \[\text{sign}(\sigma)= \text{sign}(\sigma ^{-1}).\]
    Sugerencia: no es difícil hacerlo por inducción sobre el número de inversiones.
  2. Encuentra explícitamente cuántas inversiones tiene la permutación $\sigma$ en $S_n$ dada por $S(j)=n-j+1$.
  3. Escribe con más detalle la demostración de que una matriz y su transpuesta tienen el mismo determinante. Puedes pensarlo como sigue. Toma \[ \det(A)=\sum_{\sigma \in S_{n}} \text{sign}(\sigma)a_{1\sigma(1)}\cdot \dots \cdot a_{n\sigma (n)}.\] Supón que las filas $s$ y $t$ son iguales; para cada factor argumenta por qué \[ a_{1\sigma (1)}\cdots a_{s\sigma (s)} \cdots a_{t\sigma (t)}\cdots a_{n\sigma (n)} \] el factor \[ a_{1\sigma (1)}\cdots a_{t\sigma (t)}\cdots a_{s\sigma (s)} \cdots a_{n\sigma (n)} \] donde permutamos el $t$-ésimo factor con el $s$-ésimo también está en la suma, y por qué ambos son de signos contrarios.
  4. Demuestra que el producto de una matriz triangular superior con otra matriz triangular superior también es una matriz triangular superior. Enuncia y demuestra lo análogo para matrices triangulares inferiores, y para matrices diagonales.
  5. Argumenta con más detalle por qué el determinante de una matriz triangular superior es el produto de las entradas en su diagonal. Específicamente, detalla el argumento de las notas que dice que «en otro caso, este producto siempre tendrá algún factor cero».

Entradas relacionadas

Probabilidad I: Principios de Conteo 2 – Permutaciones

Por Octavio Daniel Ríos García

Deja un comentario

Introducción

En la entrada pasada vimos dos principios básicos de conteo: el de la suma y el del producto. En particular, el principio del producto tiene aplicaciones más especializadas. Tal es el caso de las permutaciones y las combinaciones. Dada una colección de objetos, es posible extraer una cantidad fija $k$ de ellos y formar arreglos de tamaño $k$. De estos arreglos puede o no importarnos el orden de los objetos que los forman. Esto da lugar al concepto que veremos en esta entrada: las permutaciones.

Motivación

Comenzaremos con el concepto de permutación. Dada una colección de $n$ objetos, es posible extraer $k$ (con $k \leq n$) de ellos para formar un arreglo lineal. Es decir, se acomodan los elementos en una línea. Lo que nos interesa es ver la cantidad de arreglos lineales de tamaño $k$ que pueden obtenerse de una colección de $n$ objetos. Sin embargo, en un arreglo nos importa el orden en el que se acomodan los objetos. Así, dos arreglos lineales con los mismos elementos pero ordenados de diferente manera se consideran como distintos. Por ello, si queremos la cantidad de arreglos lineales ordenados posibles, estas diferencias se toman en cuenta. Comencemos con un ejemplo.

Ejemplo. En un grupo de $10$ estudiantes, se escoge a $5$ de ellos y se sientan en una fila para una fotografía. ¿Cuántos arreglos lineales pueden formarse?

Como mencionamos anteriormente, la palabra arreglo designa una importancia al orden de los elementos. Si $\mathrm{A}$, $\mathrm{B}$, $\mathrm{C}$, …, $\mathrm{I}$, $\mathrm{J}$ denotan a los $10$ estudiantes, entonces $\mathrm{BCEFI}$, $\mathrm{CEFIB}$ y $\mathrm{ABCFG}$ son tres arreglos lineales distintos. Además, observa que los dos primeros arreglos constan de los mismos $5$ estudiantes, lo que los hace distintos es el orden en el que están acomodados sus elementos.

Ahora, para responder a la pregunta que hicimos, vamos a valernos del principio del producto. Tenemos que considerar las $5$ posiciones (porque estamos tomando $5$ de los $10$ estudiantes que tiene el grupo) y debemos de considerar además cuántos estudiantes hay disponibles para ocupar cada posición.

\[ \underset{\substack{ \phantom{x} \\ \text{1a} \\ \text{Posicion}}}{10} \cdot \underset{\substack{ \phantom{x} \\ \text{2a} \\ \text{Posicion}}}{9} \cdot \underset{\substack{ \phantom{x} \\ \text{3a} \\ \text{Posicion}}}{8} \cdot \underset{\substack{ \phantom{x} \\ \text{4a} \\ \text{Posicion}}}{7} \cdot \underset{\substack{ \phantom{x} \\ \text{5a} \\ \text{Posicion}}}{6} \]

En la 1ᵃ posición puede ir cualquiera de los $10$ estudiantes. No es posible duplicar a los estudiantes, por lo que las repeticiones no son posibles aquí. Por ello, podemos seleccionar únicamente a alguno de los $9$ estudiantes restantes para ocupar la 2ᵃ posición. Similarmente, ahora nos quedan $8$ estudiantes para ocupar la 3ᵃ posición. Continuamos así hasta llegar a que sólo $6$ estudiantes pueden ocupar la 5ᵃ posición. Así, tenemos un total de $30{,}240$ arreglos posibles de $5$ estudiantes tomados del grupo de $10$.

Permutaciones de objetos distintos

Seguramente ya notaste que en este tipo de problemas surgen productos de enteros consecutivos (observa el ejemplo que acabamos de ver, y el ejemplo de las placas de la entrada anterior). En Álgebra Superior I puede que hayas visto el concepto de factorial. Este concepto permite una escritura más sencilla de las operaciones que aparecen en los problemas de conteo. Por ello, lo incluimos como recordatorio:

Recordatorio. Sea $n \in \mathbb{N}$. Se define el número $n$ factorial (denotado por $n!$) como sigue:

\begin{align*} 0! &= 1, \\ n! &= (n)(n − 1)(n − 2) \cdots (3)(2)(1), & \text{para $n \geq 1$}. \end{align*}

Así, se puede observar que

\begin{align*} 1! &= 1, \\ 2! &= 2 \cdot 1 = 2, \\ 3! &= 3 \cdot 2 \cdot 1 = 6, \\ 4! &= 4 \cdot 3 \cdot 2 \cdot 1 = 24, \\ 5! &= 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120. \\ \end{align*}

Además, para cualquier $n \in \mathbb{N}$ se cumple que $(n + 1)! = (n+1)(n!)$.

Utilizando la notación del factorial podemos simplificar el resultado obtenido en el último ejemplo.

\begin{align*} 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 = 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot \frac{5 \cdot 4 \cdot 3 \cdot 2\cdot 1}{5 \cdot 4 \cdot 3 \cdot 2\cdot 1} = \frac{10!}{5!}. \end{align*}

Esto es, al dividir $10!$ entre $5!$ se cancelan los últimos términos de $10!$. Efectivamente, la expresión resultante coincide con lo que obtuvimos en el ejemplo.

Definición 1.18. Dada una colección de $n$ objetos distintos, cualquer arreglo lineal formado con estos objetos es llamado una permutación de la colección.

Por ejemplo, si tenemos las letras $\mathrm{a}$, $\mathrm{b}$ y $\mathrm{c}$, hay $6$ maneras de acomodar (o permutar) estas letras: $\mathrm{abc}$, $\mathrm{acb}$, $\mathrm{bac}$, $\mathrm{bca}$, $\mathrm{cab}$ y $\mathrm{cba}$. Por otro lado, si nos interesa tomar arreglos de $2$ letras, entonces hay $6$ permutaciones de tamaño $2$ de la colección: $\mathrm{ab}$, $\mathrm{ac}$, $\mathrm{ba}$, $\mathrm{bc}$, $\mathrm{ca}$ y $\mathrm{cb}$.

Principio de las permutaciones. Sean $n, r \in \mathbb{N}$ tales que $1 \leq r \leq n$. Si tenemos $n$ objetos distintos, entonces por la regla del producto, el número de permutaciones de tamaño $r$ de los $n$ objetos es

\begin{align*} P(n,r) &= \underset{\substack{ \phantom{x} \\ \text{1a} \\ \text{Posicion}}}{(n)} \cdot \underset{\substack{ \phantom{x} \\ \text{2a} \\ \text{Posicion}}}{(n − 1)} \cdot \underset{\substack{ \phantom{x} \\ \text{3a} \\ \text{Posicion}}}{(n − 2)} \cdots \underset{\substack{ \phantom{x} \\ \text{$r$-esima} \\ \text{Posicion}}}{(n − r + 1)} \\ &= (n)(n−1)(n−2) \cdots (n−r+1) \cdot \frac{(n−r)(n−r−1) \cdots (3)(2)(1)}{(n−r)(n−r−1) \cdots (3)(2)(1)} \\ &= \frac{n!}{(n−r)!}. \end{align*}

Como mencionamos previamente, aplicamos el principio del producto para determinar el número de permutaciones que pueden hacerse a partir de una colección dada.

Algunas propiedades importantes que observar.

  1. Cuando $r = 0$, $P(n, 0) = 1 = \frac{n!}{(n−0)!}$, por lo que $P(n, r)$ está bien definido incluso para $r = 0$.
  2. Al permutar todos los $n$ objetos de la colección, se tiene $r = n$. Por ello, $P(n,n) = \frac{n!}{0!} = n!$ es el número de permutaciones posibles de todos los objetos de la colección.
  3. Es importante notar que el número de permutaciones de tamaño $r$ de una colección de $n$ objetos es un resultado del principio del producto cuando no permitimos repetición. En consecuencia, $P(n,r)$ es el número de arreglos lineales de tamaño $r$ en los que no se permiten repeticiones. Sin embargo, cuando sí permitimos las repeticiones, por el principio del producto hay $n^{r}$ arreglos lineales posibles.

Ejemplo. El número de permutaciones de las letras en la palabra $\mathrm{CARMESI}$ es $7!$, pues todas las letras son distintas entre sí. Si queremos formar permutaciones de tamaño $4$, entonces el número de permutaciones de tamaño $4$ es $P(7,4) = \frac{7!}{(7 − 4)!} = \frac{7!}{3!} = 840$. Por otro lado, si permitimos repeticiones de letras, entonces el número de cadenas de $11$ letras que podemos formar es $7^{11} = 1{,}977{,}326{,}743$.

Permutaciones con objetos repetidos

Ejemplo. ¿Qué pasa cuando nuestra colección tiene objetos repetidos o indistinguibles? Por ejemplo, ¿cuál es el número de permutaciones de las $4$ letras en la palabra $\mathrm{PALA}$? En este caso, la letra $\mathrm{A}$ se repite. Veamos cómo se ven todas las permutaciones de estas letras.

Tabla de Arreglos
$\mathrm{A \, A \, L \, P}$$\mathrm{A_{1} \, A_{2} \, L \, P}$$\mathrm{A_{2} \, A_{1} \, L \, P}$
$\mathrm{A \, A \, P \, L}$$\mathrm{A_{1} \, A_{2} \, P \, L}$$\mathrm{A_{2} \, A_{1} \, P \, L}$
$\mathrm{A \, L \, A \, P}$$\mathrm{A_{1} \, L \, A_{2} \, P}$$\mathrm{A_{2} \, L \, A_{1} \, P}$
$\mathrm{A L \, P \, A}$$\mathrm{A_{1} \, L \, P \, A_{2}}$$\mathrm{A_{2} \, L \, P \, A_{1}}$
$\mathrm{A \, P \, A \, L}$$\mathrm{A_{1} \, P \, A_{2} \, L}$$\mathrm{A_{2} \, P \, A_{1} \, L}$
$\mathrm{A \, P \, L \, A}$$\mathrm{A_{1} \, P \, L \, A_{2}}$$\mathrm{A_{2} \, P \, L \, A_{1}}$
$\mathrm{L \, A \, A \, P}$$\mathrm{L \, A_{1} \, A_{2} \, P}$$\mathrm{L \, A_{2} \, A_{1} \, P}$
$\mathrm{L \, A \, P \, A}$$\mathrm{L \, A_{1} \, P \, A_{2}}$$\mathrm{L \, A_{2} \, P \, A_{1}}$
$\mathrm{L \, P \, A \, A}$$\mathrm{L \, P \, A_{1} \, A_{2}}$$\mathrm{L \, P \, A_{2} \, A_{1}}$
$\mathrm{P \, A \, A \, L}$$\mathrm{P \, A_{1} \, A _{2}\, L}$$\mathrm{P \, A_{2} \, A _{1}\, L}$
$\mathrm{P \, A \, L \, A}$$\mathrm{P \, A_{1} \, L \, A_{2}}$$\mathrm{P \, A_{2} \, L \, A_{1}}$
$\mathrm{P \, L \, A \, A}$$\mathrm{P \, L \, A_{1} \, A_{2}}$$\mathrm{P \, L \, A_{2} \, A_{1}}$
(a)(b)

En la tabla de la izquierda (a) pusimos todos los arreglos distintos que se pueden formar con las letras que tenemos. Por otro lado, si distinguimos a las dos letras $\mathrm{A}$ como $\mathrm{A_{1}}$ y $\mathrm{A_{2}}$, nuestra colección se vuelve una colección de objetos distintos. Así, en la tabla de la derecha (b) pusimos todos los arreglos con las letras de la palabra $\mathrm{PA_{1}LA_{2}}$. En este caso sí sabemos calcular el número de permutaciones posibles, es $P(4,4) = 4! = 24$. La tabla revela que para cada arreglo en el que las $\mathrm{A}$’s son indistinguibles le corresponden dos permutaciones con $\mathrm{A}$’s distintas. En consecuencia,

\begin{align*} 2 \cdot (\text{Arreglos distintos con las letras $\mathrm{P}$, $\mathrm{A}$, $\mathrm{L}$, $\mathrm{A}$}) = (\text{Permutaciones de los simbolos $\mathrm{P}$, $\mathrm{A_{1}}$, $\mathrm{L}$, $\mathrm{A_{2}}$}), \end{align*}

por lo que la respuesta a nuestra pregunta original de encontrar todas las permutaciones de las $4$ letras en la palabra $\mathrm{PALA}$ es $\frac{4!}{2} = 12$.

Ejemplo. Usando la misma idea que desarrollamos en el ejemplo anterior, considera ahora las permutaciones de las $9$ letras de la palabra $\mathrm{COCODRILO}$.

Primero, observa que hay $3! = 6$ maneras de acomodar a las $\mathrm{O}$’s distinguidas por cada arreglo en el que las $\mathrm{O}$’s no están distinguidas. Por ejemplo, observa la siguiente tabla:

Tabla de arreglos
$\mathrm{C \, O \, C \, O \, D \, R \, I \, L \, O}$$\mathrm{C \, O_{1} \, C \, O_{2} \, D \, R \, I \, L \, O_{3}}$
$\mathrm{C \, O_{1} \, C \, O_{3} \, D \, R \, I \, L \, O_{2}}$
$\mathrm{C \, O_{2} \, C \, O_{1} \, D \, R \, I \, L \, O_{3}}$
$\mathrm{C \, O_{2} \, C \, O_{3} \, D \, R \, I \, L \, O_{1}}$
$\mathrm{C \, O_{3} \, C \, O_{1} \, D \, R \, I \, L \, O_{2}}$
$\mathrm{C \, O_{3} \, C \, O_{2} \, D \, R \, I \, L \, O_{1}}$
(a) Arreglo sin distinguir las $\mathrm{O}$’s.(b) Arreglos distinguendo a las tres letras $\mathrm{O}$.

Por cada permutación de las letras en la palabra $\mathrm{COCODRILO}$ sin distinguir a las $\mathrm{O}$’s, hay $3$ espacios ocupados por letras $\mathrm{O}$. Por ello, al distinguir a cada una, estamos permutando esas $3$ $\mathrm{O}$’s, que pueden acomodarse de $P(3,3) = 3! = 6$ maneras. Por otro lado, lo mismo pasa con las $\mathrm{C}$’s. En este caso, hay $2!$ maneras de acomodar las $\mathrm{C}$’s distinguidas por cada arreglo sin distinguir las $\mathrm{C}$’s. Por lo tanto, se tiene que

\begin{align*} (3!)(2!)(\text{Arreglos distintos con las letras en $\mathrm{COCODRILO}$}) = (\text{Permutaciones de los simbolos $\mathrm{C}_{2}$, $\mathrm{O_{1}}$, $\mathrm{C}_{2}$, $\mathrm{O_{2}}$, $\mathrm{D}$, $\mathrm{R}$, $\mathrm{I}$, $\mathrm{L}$, $\mathrm{O_{3}}$}), \end{align*}

así que el número de arreglos distintos de las $9$ letras en $\mathrm{COCODRILO}$ es $\frac{9!}{(3!)(2!)} = 30{,}240$.

Podemos enunciar un principio general para arreglos con objetos que se repiten siguiendo la idea desarrollada en los últimos ejemplos.

Permutaciones con objetos repetidos. Si tenemos una colección de $n$ objetos y dentro de esta colección tenemos $n_{1}$ objetos indistinguibles de un $1$er tipo, $n_{2}$ objetos indistinguibles de un $2$do tipo, …, y $n_{r}$ objetos indistinguibles de un $r$-ésimo tipo, de tal manera que

\[ n_{1} + n_{2} + \cdots + n_{r} = n, \]

entonces la cantidad de permutaciones de los $n$ objetos dados es

\[\frac{n!}{(n_{1}!)(n_{2}!) \cdots (n_{r}!)}. \]

Este valor es conocido como el coeficiente multinomial de $n_{1}$, $n_{2}$, …, $n_{r}$.

Ejemplo. La ciudad de $\mathrm{CONSTANTINOPLA}$ fue la ciudad capital del imperio bizantino entre los años 395 y 1204. Podemos aplicar el último principio de conteo que desarrollamos para encontrar la cantidad de permutaciones de las letras en la palabra $\mathrm{CONSTANTINOPLA}$.

Para ello, primero hay que encontrar cuántas letras distintas tiene. Observa que en total tiene $9$ letras distintas. En consecuencia, podemos pensar de cada letra distinta como un tipo de objeto. Así, tenemos $9$ tipos de objetos en la colección, y hay que contar cuántos objetos de cada tipo hay. Esto lo podemos ver en la siguiente tabla.

TipoLetraNúmero de letras de ese tipo
$1$$\mathrm{A}$$n_{1} = 2$
$2$$\mathrm{C}$$n_{2} = 1$
$3$$\mathrm{I}$$n_{3} = 1$
$4$$\mathrm{L}$$n_{4} = 1$
$5$$\mathrm{N}$$n_{5} = 3$
$6$$\mathrm{O}$$n_{6} = 2$
$7$$\mathrm{P}$$n_{7} = 1$
$8$$\mathrm{S}$$n_{8} = 1$
$9$$\mathrm{T}$$n_{9} = 2$

Además, el número de letras en $\mathrm{CONSTANTINOPLA}$ es $14$, precisamente el resultado de sumar todos los $n_{i}$. Así, obtenemos que la cantidad de premutaciones posibles de las letras en $\mathrm{CONSTANTINOPLA}$ es

\[ \frac{14!}{(2!)(1!)(1!)(1!)(3!)(2!)(1!)(1!)(2!)} = \frac{14!}{(2!)(3!)(2!)(2!)} = 1{,}816{,}214{,}400. \]

Otra pregunta que podemos resolver es, ¿cuántas permutaciones tienen a las $3$ $\mathrm{N}$’s juntas? Para verlo, podemos pensar en que la cadena de letras $\mathrm{NNN}$ es un solo símbolo, y partir de la colección de símbolos $\mathrm{A}$, $\mathrm{A}$, $\mathrm{C}$, $\mathrm{I}$, $\mathrm{L}$, $\mathrm{NNN}$ (como un solo símbolo), $\mathrm{O}$, $\mathrm{O}$, $\mathrm{P}$, $\mathrm{S}$, $\mathrm{T}$, $\mathrm{T}$, y hacer lo mismo. Así, el número de permutaciones que tiene a las $3$ $\mathrm{N}$’s juntas es

\[ \frac{12!}{(2!)(1!)(1!)(1!)(1!)(2!)(1!)(1!)(2!)} = \frac{12!}{(2!)(2!)(2!)} = 59{,}875{,}200. \]

Tarea moral

Los siguientes ejercicios son opcionales. Es decir, no formarán parte de tu calificación. Sin embargo, te recomiendo resolverlos para que desarrolles tu dominio de los conceptos abordados en esta entrada.

  1. ¿Cuántas permutaciones de los dígitos $0$, $1$, $2$, …, $9$ hay cuyo primer dígito es $3$ o cuyo último dígito es $7$?
  2. Encuentra el número de permutaciones de la palabra $\mathrm{MISSISSIPPI}$.
  3. ¿Cuántas cadenas de $13$ símbolos pueden hacerse con $6$ estrellas $*$ y $7$ barras $|$? Por ejemplo:\[ |*|*|***|*|||, \qquad ******|||||||, \qquad |*|*|*|*|*|*|. \]

Más adelante…

En la siguiente entrada continuaremos con nuestro estudio de los principios de conteo. El siguiente concepto será el de combinación, que se deriva del concepto de permutación, siendo la combinación un concepto un poco más especializado.

Por otro lado, el concepto de permutación con objetos repetidos te será de utilidad en el curso de Probabilidad II para algo que se conoce como la distribución multinomial. Cuando veamos lo que son las variables aleatorias y las funciones de distribución te quedará claro a qué nos referimos por «distribución multinomial».

Entradas relacionadas

Álgebra Moderna I: Permutaciones y Grupo Simétrico

Por Cecilia del Carmen Villatoro Ramos

Deja un comentario

Introducción

La Unidad 2 empieza con algunas definiciones nuevas. Veremos un ejemplo específico de grupo, primero definiremos qué es una permutación y luego, el conjunto de todas las permutaciones, al que llamaremos grupo simétrico junto con la composición. Este grupo es importante porque más adelante descubriremos que los grupos se pueden visualizar como subgrupos de grupos de permutaciones.

Primeras definiciones

Definición. Una permutación de un conjunto $X$ es una función biyectiva de $X$ en $X$.

Notación. Denotaremos por $S_X$ al conjunto

\begin{align*}
S_X = \{\sigma: X \to X | \sigma \text{ es biyectiva}\}.
\end{align*}

Si $X = \{1,…,n\}$, $S_X$ se denota por $S_n$. Si tomamos $\alpha, \beta \in S_X$ la composición de $\alpha$ seguida de $\beta$ se denota por $\beta\alpha$.

Observación 1. $S_X$ con la composición es un grupo, se llama el Grupo Simétrico.

Observación 2. $|S_n| = n!$

Definición. Sea $\alpha \in S_n$, $i \in \{1,2,…,n\}$.

Decimos que $\alpha$ mueve a $i$ si $\alpha(i) \neq i$, y que $\alpha$ fija a $i$ si $\alpha(i) = i$. El soporte de $\alpha$ es

\begin{align*}
\text{sop }\alpha = \{i \in \{1,\dots, n\}: \alpha(i) \neq i\}.
\end{align*}

Ejemplo

Sea $\alpha \in S_{10}$, definida como

\begin{align*}
\alpha = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\
8 & 3 & 1 & 7 & 2 & 6 & 4 & 5 & 9 & 10 \end{pmatrix}.
\end{align*}

La matriz es una manera de representar una permutación, la fila de arriba son todos los elementos de $X= \{1,2,3,4,5,6,7,8,9,10\}$ y la fila de abajo está formada por las imágenes bajo $\alpha$ de cada elemento de la fila de arriba. Es decir, la matriz de $\alpha$ se puede leer como: «$\alpha$ manda al $1$ al $8$», «el $ 2 $ lo manda al $3$», etc. Entonces tenemos que, $\alpha$ mueve a $1,2,3,4,5,7,8$ y fija al $6,9,10$. Así

\begin{align*}
\text{sop } \alpha = \{1,2, 3, 4, 5, 7, 8\}.
\end{align*}

Definición de ciclo

Definición. Sea $\alpha \in S_n$, $r\in\z$, $r>1$. Decimos que $\alpha$ es un ciclo de longitud $r$ o un $r$-ciclo si existen $i_1, \dots, i_r \in \{1, \dots, n\}$ distintos tales que $\text{sop }\alpha = \{i_1, \dots, i_r\}$ y

\begin{align*}
\alpha(i_t) = \begin{cases}
i_{t+1} & \text{si } t \in \{1, \dots, r-1\} \\
i_1 & \text{si } t = r
\end{cases}
\end{align*}

Figura para ilustrar la definición de un ciclo.

Diremos que la permutación $\text{id}\in S_n$ es un ciclo de longitud $1$ o un $1$-ciclo. Los ciclos de longitud dos se llaman transposiciones.

Las transposiciones son muy importantes porque, como veremos más adelante, nos permitirán describir a las demás permutaciones.

Notación.

  • Un $r$-ciclo $\alpha$, tal que cada $i_j$ va a $i_{j+1}$ para cada $j \in \{1,…,r-1\}$ y $i_r$ regresa a $i_1$ se denota como $\alpha = (i_1\; i_2 \; \dots \; i_r)$.
  • Además, denotamos como $r = \text{long } \alpha$ a la longitud de $\alpha$.

Ejemplos

  1. $\alpha \in S_8$ con $\alpha = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 4 & 3 & 5 & 8 & 2 & 7 & 6 \end{pmatrix}$.

\begin{align*}
\alpha &= (2 \; 4 \; 5 \; 8 \; 6) = (4 \; 5 \; 8 \; 6 \; 2) \\
& = (5 \; 8 \; 6 \; 2 \; 4) = (8 \; 6 \; 2 \; 4 \; 5) \\
& = (6 \; 2 \; 4 \; 5 \; 8).
\end{align*}

Representación de $\alpha$.

En este caso, $\alpha$ es un $5-$ciclo y $\text{long }\alpha = 5$.
Observemos que el ciclo se puede comenzar a escribir con cualquier elemento de su soporte, siempre y cuando se cumpla la regla de correspondencia establecida.

2. Ahora, consideremos $\beta \in S_8$ como

Representación de $\beta$.

\begin{align*}
\beta =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 2 & 5 & 4 & 3 & 6 & 7 & 8\end{pmatrix},
\end{align*}
entonces podemos decir que $\beta = (3 \; 5)$, porque a los otros elementos los deja fijos.

Si componemos $\beta$ con el $\alpha$ del ejemplo anterior obtenemos:

\begin{align*}
\alpha\beta &= (2 \; 4 \; 5 \; 8 \; 6) (3 \; 5) = (2 \; 4 \; 5 \; 3 \; 8 \; 6).
\end{align*}

Para verificar qué ésta es efectivamente la composición de $\beta$ seguida de $\alpha$, tenemos que observar a dónde manda a cada elemento:

  • Comenzamos con el $2$ (esto es arbitrario, se puede comenzar con el número que sea), observamos que $\beta$ lo deja fijo, entonces nos fijamos a dónde lo manda $\alpha$, en este caso, el $2$ es mandado al $4$. Así, $\alpha\beta$ manda al $2$ en el $4$.
  • Repetimos el proceso con el $4$, $\beta$ lo deja fijo y $\alpha$ lo manda al $5$. Así, $\alpha\beta$ manda al $4$ en el $5$.
  • Ahora con el $5$, $\beta$ manda al $5$ en $3$, entonces ahora vemos a dónde manda $\alpha$ al $3$, en este caso lo deja fijo. Así, $\alpha\beta$ manda al $5$ en el $3$.
  • Entonces ahora tenemos que observar a dónde es mandado el $3$ después de la composición. Primero, $\beta$ manda el $3$ al $5$ y $\alpha$ manda el $5$ al $8$, por lo tanto $\alpha\beta$ manda el $3$ al $8$.
  • Así continuamos con todos los elementos que aparezcan en la composición hasta terminar.

    Ahora, veamos qué sucede con $\beta\alpha$. El proceso es análogo:
    \begin{align*}
    \beta\alpha &= (3 \; 5) (2 \; 4 \; 5 \; 8 \; 6) = (3 \; 5 \; 8 \; 6 \; 2 \; 4).
    \end{align*}
    Por lo tanto $\alpha\beta \neq \beta\alpha$.

3. En $S_5$. Podemos considerar la siguiente permutación: $(1 \; 2 \; 3 \; 4)(2 \; 4 \; 5)$. A esta permutación la podemos simplificar usando el mismo procedimiento que en el ejemplo 2.

Observamos a dónde lleva cada uno de sus elementos:

  • Comencemos con el 2, la primera parte de la permutación, lleva el 2 al 4 y, la segunda parte lleva el 4 al 1.
  • Ahora veamos a dónde va el 1. La primera parte lo deja fijo y la segunda lo lleva al 2. Entonces obtenemos una permutación $(1\;2)$. Pero todavía falta ver el resto de elementos.
  • Ahora, veamos qué sucede con el 3. La primera parte lo deja fijo y la segunda lo manda al 4.
  • La primera parte de nuestra permutación manda el 4 al 5 y, el 5 se queda fijo.
  • Por último, el 5 es mandado al 2 por la primera parte de la permutación y, la segunda parte manda al 2 en el 3. Por lo tanto, el 5 regresa al 3. Esto se puede escribir como:

\begin{align*}
(1 \; 2 \; 3 \; 4)(2 \; 4 \; 5) = (1 \; 2) (3 \; 4 \; 5).
\end{align*}

Es decir:

Representación de $(1 \; 2 \; 3 \; 4)(2 \; 4 \; 5) = (1 \; 2) (3 \; 4 \; 5)$.

Este ejemplo nos permite intuir que en ocasiones las permutaciones se pueden simplificar.

Observación. Si $n \geq 3$, entonces $S_n$ no es abeliano.

Tarea moral

  1. Demostrar la observación 1: $S_X$ con la composición es un grupo, se llama el Grupo Simétrico.
  2. Sea $X$ un conjunto infinito, $H$ la colección de permutaciones de $S_X$ que mueven sólo un número finito de elementos y $K$ la colección de permutaciones que mueven a lo más $50$ elementos. ¿Son $H$ y $K$ subgrupos de $S_X$?
  3. Considera los siguientes elementos de $S_{10}$
    \begin{align*} \alpha &= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
    10 & 4 & 3 & 2 & 9 & 7 & 5 & 1 & 6 & 8 \end{pmatrix} \\\\
    \beta &= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
    10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \end{pmatrix}. \end{align*}
    Encuentra $\alpha \beta, \beta \alpha, \alpha^{-1}$ y $\beta^{-1}$.
  4. Sea $a \in S_n, $ con $n > 2$. Si $\alpha$ conmuta con toda permutación de $S_n$ ¿puedes decir quién debe ser $\alpha$?

Más adelante…

Por el momento continuaremos hablando de las permutaciones. El último ejemplo visto nos da la noción de permutaciones disjuntas, este tema es el que profundizaremos en la siguiente entrada, pero por el momento ¿puedes imaginarte de qué se trata?

Entradas relacionadas

Álgebra Lineal I: Transformaciones multilineales

Por Leonardo Ignacio Martínez Sandoval

8 respuestas

Introducción

Con esta entrada empieza el cuarto y último bloque del curso de Lineal I. En este último bloque hablaremos de determinantes de matrices, de eigenvectores, eigenvalores y de polinomios característicos. Además, probaremos el teorema espectral para matrices simétricas reales. Nuestro cimiento teórico para definir a los determinantes y probar sus propiedades fácilmente serán las transformaciones multilineales, que generalizan a las formas bilineales de las que ya hemos hablado.

Antes de empezar, vale la pena recapitular lo que hemos aprendido en los bloques anteriores:

  • Bloque 1: Primero, hablamos de vectores y matrices con entradas reales, y sus operaciones básicas. Luego, vimos que nos ayudan a plantear y resolver sistemas de ecuaciones lineales. Aquí hablamos de varias equivalencias de matrices invertibles. Al final de este bloque, definimos espacios vectoriales en general. En ellos hablamos de conjuntos generadores, independientes y bases. Mediante el lema de Steinitz definimos y probamos propiedades de espacios de dimensión finita.
  • Bloque 2: Vimos la teoría básica de transformaciones lineales. Hablamos de imágenes y kernels de transformaciones. Vimos cómo se comportan con independientes y bases. Luego hablamos de cómo representar transformaciones lineales entre espacios de dimensión finita usando matrices, y en particular cómo hacer cambios de base.
  • Bloque 3: Este bloque fue más «geométrico». Primero, vimos formas lineales y la teoría de dualidad y la aplicamos para ver que todo subespacio es intersección de hiperplanos. Luego, definimos formas bilineales y cuadráticas. De ahí salió la noción de producto interior, que nos permite «hacer geometría» en espacios vectoriales. Hablamos de desigualdades vectoriales, de bases ortogonales, para qué sirven y cómo encontrarlas.

La intuición que obtuvimos de formas bilineales nos ayudará a entender formas multilineales. Pero antes de entrar en este tema, que es un poco técnico, veamos un ejemplo que nos ayudará a entender lo que nos espera en este bloque.

Elevando una matriz a la 100

Considera la matriz $$A=\begin{pmatrix}-4&-10\\3&7\end{pmatrix}.$$ Imagina que para alguna aplicación queremos elevarla a la $100$. Esto probablemente lo puedas hacer a mano, y mejor aún, a computadora. Pero en aplicaciones en la vida real, puede que hacer los cálculos matriciales sea mucho incluso para una computadora. ¿Habrá una forma de que sea más fácil hacer $A^{100}$?

Resulta que para este caso en particular, sí. Considera las matrices $$B=\begin{pmatrix}3 & 5\\ 1& 2\end{pmatrix}$$ y $$D=\begin{pmatrix}1&0\\0&2\end{pmatrix}.$$ La matriz $B$ es invertible, con inversa $$B^{-1}=\begin{pmatrix}2&-5 \\-1&3\end{pmatrix},$$ como puedes verificar. Además, la matriz $A$ se puede «factorizar» así: $$A=B^{-1}DB.$$

Esto es muy útil para nuestros fines. Nota que
\begin{align*}
A^2&=(B^{-1}DB)(B^{-1}DB)\\
&=B^{-1}D^2B,
\end{align*}

y que de hecho inductivamente $A^n=B^{-1}D^n B$ para cualquier entero positivo $n$.

Por otro lado, como la matriz $D$ es diagonal, sus potencias son muy sencillas, de hecho, se puede probar inductivamente que $D^n=\begin{pmatrix}1&0\\0&2^{n}\end{pmatrix}$ para cualquier entero positivo $n$. De esta forma, podemos hacer $A^n$ con tan solo dos multiplicaciones de matrices:
\begin{align*}
A^n&=B^{-1}D^nB\\
&=\begin{pmatrix}2&-5 \\ -1&3\end{pmatrix}\begin{pmatrix}1&0\\ 0&2^{n}\end{pmatrix}\begin{pmatrix}3 & 5\\ 1& 2\end{pmatrix}\\
&=\begin{pmatrix}2&-5 \\ -1&3\end{pmatrix}\begin{pmatrix}3&5 \\ 2^n&2^{n+1}\end{pmatrix}\\
&=\begin{pmatrix}6-5\cdot 2^n& 10-5\cdot 2^{n+1}\\ -3+3\cdot 2^n & -5+3\cdot 2^{n+1}\end{pmatrix}
\end{align*}

Así, el problema que queremos resolver es sencillo ahora. Basta tomar $n=100$ para obtener $$A^{100}=\begin{pmatrix}6-5\cdot 2^{100} & 10-5\cdot 2^{101}\\ -3+3\cdot 2^{100} & -5+3\cdot 2^{101}\end{pmatrix}.$$

Si podemos escribir una matriz $A$ como $B^{-1}DB$ con $B$ invertible y $D$ diagonal, decimos que es diagonalizable. La conclusión anterior es que una matriz diagonalizable se puede elevar fácilmente a potencias.

Todo esto está muy bien pero, ¿de dónde salen las matrices $B$ y $D$? ¿toda matriz es diagonalizable? ¿qué otras ventajas tiene diagonalizar una matriz? Este tipo de preguntas son las que estudiaremos en este bloque.

Diagonalizar matrices de 2×2

El determinante de una matriz $A=\begin{pmatrix}a&b\\c&d\end{pmatrix}$ en $M_2(\mathbb{R})$, como quizás hayas visto antes, está dado por $ad-bc$. Resulta que una forma sistemática para encontrar matrices $B$ y $D$ como las del ejemplo de arriba es la siguiente:

  • Tomar una matriz $A$.
  • Considerar el polinomio $P(\lambda)=\det(\lambda I – A)$. A este polinomio se le conoce como el polinomio característico de $A$.
  • Encontrar las raíces $\lambda_1$ y $\lambda_2$ de $P(\lambda)$. A estos valores se les llama los eigenvalores de $A$.
  • Encontrar vectores $v_1$ y $v_2$ no cero tales que $(A-\lambda_1I) v_1 =0$ y $(A-\lambda_2 I)v_2 = 0$. Estos simplemente son sistemas lineales homogéneos, que ya sabemos resolver con reducción gaussiana. A estos vectores se les llama eigenvectores de $A$.
  • Usar a $\lambda_1$ y $\lambda_2$ como las entradas de la matriz diagonal $D$.
  • Usar a $v_1$ y $v_2$ como columnas de la matriz $B^{-1}$. Encontrar la inversa de $B^{-1}$ para encontrar a $B$.

¿Cómo se hace en dimensiones más altas? ¿Siempre podemos seguir este proceso esto? ¿Hay algunos tipos de matrices para los que siempre funcione? Estas son otras preguntas que responderemos en el transcurso de estas semanas.

Mientras tanto, veamos qué sucede si aplicamos este método para la matriz $A=\begin{pmatrix}-4&-10\\3&7\end{pmatrix}$ del ejemplo. Tenemos que el determinante de $\lambda I-A = \begin{pmatrix}\lambda+4&-10\\-3&\lambda – 7\end{pmatrix}$ es el polinomio \begin{align*}P(\lambda)&= (\lambda+4)(\lambda-7)+30\\ &=\lambda^2-3\lambda-28+30\\ &=\lambda^2-3\lambda+2,\end{align*} cuyas raíces son $1$ y $2$. De aquí construimos $$D=\begin{pmatrix}1&0\\0&2\end{pmatrix}.$$

Busquemos los eigenvectores. Por un lado, si queremos que suceda que $Av=v$ para un vector $v=(x,y)$, necesitamos que $$(-4x-10y, 3x+7y)=(x,y),$$ y una de las soluciones es $(x,y)=(2,-1)$. Por otro lado, si queremos que suceda que $Av=2v$ para un vector $v=(x,y)$, necesitamos que $$(-4x-10y,3x+7y)=(2x,2y),$$ y una de las soluciones es $(x,y)=(-5,3)$. De aquí construimos $$B^{-1}=\begin{pmatrix}2&-5 \\-1&3\end{pmatrix},$$ y podemos hacer reducción gaussiana para encontrar $B$. Observa que obtenemos exactamente las mismas matrices que propusimos en el ejemplo.

Nos gustaría poder hacer esto mismo en dimensiones más altas y entender cuándo y por qué funciona. Para ello, lo primero que necesitamos hacer es entender muy bien el concepto de determinante y aprender a manejar hábilmente sus propiedades principales.

Hay varias formas de definir determinante y quizás ya hayas visto algunas en cursos anteriores. En este curso definiremos determinante mediante transformaciones multilineales. Es un poco más abstracto, pero ayuda a que sea más fácil probar técnicas para trabajar con determinantes y entender por qué funcionan.

Transformaciones multilineales

En el bloque anterior ya hablamos de formas bilineales. Como recordatorio, tomábamos un espacio vectorial real $V$ y una forma bilineal era una función $b:V\times V\to \mathbb{R}$ tal que cada que fijábamos una entrada, la función era lineal en la otra. La palabra «forma» la usábamos porque la imagen caía en el campo.

Generalizaremos esta idea para más entradas, y para cuando la imagen cae en cualquier espacio vectorial. Trabajaremos en espacios vectoriales sobre un campo $F$, que puedes pensar que es $\mathbb{R}$ o $\mathbb{C}$.

Definición. Sean $V_1,\ldots, V_d$ y $W$ espacios vectoriales sobre $F$. Una función $f:V_1\times \ldots \times V_d\to W$ es multilineal si cada que fijamos una $i$ y para cada $j\neq i$ fijamos vectores $v_j$ en $V_j$, la transformación $$V_i\to W$$ dada por $$v_i\mapsto f(v_1,v_2,\ldots,v_d)$$ es lineal.

Aclaración. De nuevo, es muy importante no confundir una transformación multilineal con una transformación lineal del espacio vectorial $V_1\times \ldots \times V_d$ a $W$.

Ejemplo. Consideremos $\mathbb{R}^3=\mathbb{R}\times \mathbb{R} \times \mathbb{R}$ y consideramos la transformación $T:\mathbb{R}^3\to \mathbb{R}$ dada por $T(x,y,z)=xyz.$ Afirmamos que esta es una transformación multilineal.

Si fijamos $y$ y $z$, tenemos que mostrar que la transformación $x\mapsto xyz$ es lineal, lo cual es cierto pues para $x_1,x_2$ reales y $r$ real se cumple que
\begin{align*}
T(x_1+rx_2,y,z)&=(x_1+rx_2)yz\\
&=x_1yz + rx_2yz\\
&=T(x_1,y,z)+rT(x_2,y,z).
\end{align*}

De manera similar se prueba para las otras entradas.

Sin embargo, $T$ no es una transformación lineal. Por ejemplo, no saca escalares ya que $T(1,1,1)=1\cdot 1\cdot 1=1$ y $$T(2,2,2)=8\neq 2 = 2T(1,1,1).$$

$\square$

Las transformaciones multilineales son muy generales, y ayudan a crear algo que se llama el producto tensorial. Sin embargo, para los fines que necesitamos ahora, no hace falta tanta generalidad. Sólo nos enfocaremos en las transformaciones multilineales cuando $V_1=V_2=\ldots=V_d$, es decir, en transformaciones $f:V^d\to W$.

Definición. Para $d$ un entero positivo y $V$, $W$ espacios vectoriales, una transformación $d$-lineal es una transformación multilineal de $V^d$ a $W$.

Ejemplo. Si $V$ es un espacio vectorial real y $W=\mathbb{R}$, entonces toda forma bilineal $b:V\times V\to \mathbb{R}$ es una transformación $2$-lineal.

Ejemplo. Tomemos $V=\mathbb{R}^3$ y $d=4$. Tomemos las siguientes formas lineales en $V$:
\begin{align*}
l_1(x,y,z)&=x+y+z\\
l_2(x,y,z)&=3x-2y+z\\
l_3(x,y,z)&=y\\
l_4(x,y,z)&=x+z.
\end{align*}

Consideremos la transformación $T:V^4\to \mathbb{R}$ dada por $$T(v_1,v_2,v_3,v_4)=l_1(v_1)l_2(v_2)l_3(v_3)l_4(v_4),$$ por ejemplo, si $v_1=(1,0,0)$, $v_2=(0,1,0)$, $v_3=(0,1,1)$ y $v_4=(1,1,1)$, tenemos que

\begin{align*}
l_1(v_1)&=l_1(1,0,0)=1+0+0=1\\
l_2(v_2)&=l_2(0,1,0)=0-2+0=-2\\
l_3(v_3)&=l_3(0,1,1)=1\\
l_4(v_4)&=l_4(1,1,1)=1+1=2,
\end{align*}

y por lo tanto $$T(v_1,v_2,v_3,v_4)=(1)(-2)(1)(2)=-4.$$

Tenemos que $T$ es $4$-lineal pues para cada $i$, al fijar las tres entradas $v_j$ con $j\neq i$ tenemos que $T(v_1,v_2,v_3,v_4)$ es de la forma $cl_i(v_i)$ con $c$ un escalar. Como $l_i$ es una forma lineal, $cl_i$ también.

$\square$

Nos interesan un tipo todavía más restringido de transformaciones multilineales. Para definirlas, tenemos que hacer una pequeña desviación hacia el tema de permutaciones.

Permutaciones y signos

Tomemos un entero positivo y usemos $[n]$ para hablar del conjunto de los enteros de $1$ a $n$, es decir, $[n]:=\{1,2,\ldots,n\}$.

Definicion. Una permutación de $[n]$ es una función biyectiva $\sigma: [n]\to [n]$.

En otras palabras, una permutación básicamente «revuelve los elementos» de $[n]$. Usualmente expresamos a la permutación con la notación $$\begin{pmatrix} 1 & 2 & \ldots & n\\ \sigma(1) & \sigma(2) & \ldots & \sigma(n)\end{pmatrix}$$

Ejemplo. La función $\sigma:[3]\to [3]$ tal que $\sigma(1)=2$, $\sigma(2)=3$ y $\sigma(3)=1$ es una permutación que manda al conjunto ordenado $(1,2,3)$ al conjunto ordenado $(2,3,1)$. La expresamos como $$\begin{pmatrix} 1& 2 & 3\\ 2 & 3 & 1\end{pmatrix}.$$

$\square$

Como las permutaciones son funciones, entonces podemos componerlas. Para evitar complicar la notación, no pondremos el signo de composición $\circ$, sino simplemente permutaciones adyacentes. La composición usualmente no es conmutativa.

Ejemplo. Tomemos la permutación $\sigma_1:[4]\to [4]$ representada por $$\begin{pmatrix}1& 2 & 3 & 4 \\ 3 & 2 & 1 & 4\end{pmatrix}$$ y la permutación $\sigma_2:[4]\to [4]$ representada por $$\begin{pmatrix}1& 2 & 3 & 4 \\ 4 & 2 & 3 & 1\end{pmatrix}.$$

¿Qué hace la función $\sigma_1 \sigma_2$? Es una función de $[4]$ a $[4]$ y cumple lo siguiente:
\begin{align*}
\sigma_1(\sigma_2(1))&=\sigma_1(4)=4,\\
\sigma_1(\sigma_2(2))&=\sigma_1(2)=2,\\
\sigma_1(\sigma_2(3))&=\sigma_1(3)=1,\\
\sigma_1(\sigma_2(4))&=\sigma_1(1)=3,
\end{align*}

es decir, la composición es la permutación representada por $$\begin{pmatrix}1& 2 & 3 & 4 \\ 4 & 2 & 1 & 3\end{pmatrix}.$$

Por otro lado, la función $\sigma_2\sigma_1$ hace algo un poco diferente. También es una función de $[4]$ a $[4]$ y cumple lo siguiente:
\begin{align*}
\sigma_2(\sigma_1(1))&=\sigma_2(3)=3,\\
\sigma_2(\sigma_1(2))&=\sigma_2(2)=2,\\
\sigma_2(\sigma_1(3))&=\sigma_2(1)=4,\\
\sigma_2(\sigma_1(4))&=\sigma_2(4)=1,
\end{align*}

así que es la permutación representada por $$\begin{pmatrix}1& 2 & 3 & 4 \\ 3 & 2 & 4 & 1\end{pmatrix}.$$

$\square$

Al conjunto de permutaciones de $[n]$ le llamamos $S_n$. Tomemos una permutación $\sigma$ en $S_n$. Para dos elementos $i<j$ en $[n]$, decimos que $\sigma$ los invierte si $\sigma(i)>\sigma(j)$.

Definición. Sea $\sigma$ un elemento de $S_n$. Decimos que el signo de $\sigma$ es $1$ si invierte una cantidad par de parejas, y es $-1$ si invierte una cantidad impar de parejas. Al signo de $\sigma$ lo denotamos $\text{sign}(\sigma)$.

Ejemplo. La permutación $$\begin{pmatrix}1& 2 & 3 & 4 & 5\\ 5 & 2 & 1 & 4 & 3\end{pmatrix}$$ invierte a la pareja $(1,2)$ pues $\sigma(1)=5>2=\sigma(2)$. Todas las parejas que invierte son $(1,2)$, $(1,3)$, $(1,4)$, $(1,5)$, $(2,3)$, $(4,5)$. Estas son $6$ parejas, que son una cantidad par, así que la permutación tiene signo $1$.

La permutación identidad en $S_n$ no invierte ninguna pareja, así que tiene signo $1$.

$\square$

En la siguiente entrada combinaremos estas nociones de permutaciones y de transformaciones multilineales para hablar de antisimetría y alternancia. Por el momento, reflexiona en lo siguiente: si $\sigma$ es una permutación en $S_n$ y $f:V^n\to W$ es una transformación $n$-lineal, entonces la transformación $\sigma f:V^n \to W$ definida por $$(\sigma f)(x_1,x_2,\ldots,x_n) = f(x_{\sigma(1)},x_{\sigma(2)},\ldots,x_{\sigma(n)})$$ también es una transformación $n$-lineal.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  • Toma $T:V^d\to W$ una transformación $d$-lineal. Muestra que si de entre $x_1,\ldots,x_d$ elementos de $V$ alguno de ellos es el vector $0$, entonces $T(x_1,\ldots,x_d)=0$.
  • Muestra que la transformación del ejemplo de transformaciones multilineales también es lineal en la segunda y tercera entradas.
  • Supón que $l_1,\ldots,l_d$ son formas lineales de $V$ al campo $F$. Muestra que $f:V^d\to F$ dada por $$f(x_1,\ldots,x_d)=l_1(x_1)\ldots l_d(x_d)$$ es una transformación $d$-lineal.
  • Encuentra una transformación lineal $T:\mathbb{R}^3\to \mathbb{R}$ que no sea una transformación multilineal.
  • Muestra que la composición de dos permutaciones siempre es una permutación.
  • Muestra que para dos permutaciones $\sigma_1$ y $\sigma_2$ se tiene que $$\text{sign}(\sigma_1\sigma_2)=\text{sign}(\sigma_1)\text{sign}(\sigma_2).$$

Más adelante…

En esta primera entrada de la cuarta unidad hemos visto cómo la intuición que obtuvimos cuando estudiamos formas bilineales, nos ha ayudado a entender el concepto de formas multilíneales. En las siguientes entradas del blog, abordaremos el concepto de determinante y aprenderemos cómo se usa.

Para la definición de determinante y para demostrar algunas de sus propiedades , usaremos lo que aprendimos en esta entrada sobre las transformaciones multilineales. Veremos que es una herramienta del álgebra lineal bastante útil y entender detalladamente cómo funciona será fundamental para abordar uno de los teoremas más importantes del curso: el teorema espectral.

Entradas relacionadas