Archivo de la etiqueta: permutaciones

Probabilidad I: Principios de Conteo 2 – Permutaciones

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: Factorización Completa

Introducción

Consideremos $\alpha \in S_7$ como $\alpha = (1\,3\,2)(6\,4)$, esta permutación fija a $5$ y a $7$. Entonces también podemos escribirla como $\alpha = (1\,3\,2)(6\,4)(5)(7)$. Notamos que una de las cosas en las que difieren es que en la segunda descomposición estamos agregando uno ciclos, pero también $\alpha = (1 \, 3 \, 2) (7) (6 \, 4)(5)$ es otra forma diferente de expresar a la permutación escribiendo a los uno ciclos. En esta entrada nos planteamos la posibilidad de escribir a $\alpha$ como un producto de ciclos distintos incluyendo a todos los uno ciclos y analizamos en qué difieren todas las distintas maneras de hacerlo.

Antes de empezar, podrías intentar escribir todas las maneras posibles de describir a $\alpha$ escribiendo a los uno ciclos. ¿Notas algo en común entre todas? Al final de esta entrada, tendremos la respuesta más clara.

Definición de una factorización completa

Para empezar, necesitamos definir un nuevo concepto.

Definición. Sea $\alpha \in S_n$. Una factorización completa de $\alpha$ es una descomposición de $\alpha$ en ciclos disjuntos con un $1-$ciclo por cada elemento fijado por $\alpha$.

Ejemplos.

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

    Entonces $\alpha = (1 \; 3)\,(4 \; 5 \; 7)$ es una factorización de $\alpha$ en ciclos distintos pero no es una factorización completa de $\alpha$. Por otro lado $\alpha = (1 \; 3)\,(4 \; 5 \; 7)\,(2) \,(6) \,(8)$ sí es una factorización completa de $\alpha$.
  2. Sea $\beta$ dada por \begin{align*}
    \beta = (2 \; 4 \; 6 \; 8) \, (1 \; 3 \; 5)\,(7).
    \end{align*}

    Esa es una factorización completa de $\beta \in S_8$, pero no en $S_{10}$, en $S_{10}$ una factorización completa de de $\beta$ sería
    \begin{align*}
    \beta = (2 \; 4 \; 6 \; 8) \, (1 \; 3 \; 5)\,(7)\, (9) \, (10).
    \end{align*}

Una herramienta misteriosa que nos ayudará más tarde

El siguiente resultado es un lema técnico que nos ayudará a resolver el problema planteado al inicio de esta entrada. De manera informal el lema nos dice que si tenemos una factorización de una permutación en factores distintos, el factor que mueve a un elemento de su soporte, moverá a ese elemento de la misma forma que la permutación misma. También nos dice que si dos ciclos y cada una de sus potencias mueven a un elemento de su soporte de la misma forma, entonces los ciclos son iguales.

Lema.

  1. Sea $\alpha \in S_n$, $\alpha = \beta_1 \cdots \beta_t$ una factorización en permutaciones disjuntas e $i \in \{1,\dots,n\}$. Si $\beta_1(i) \neq i$ entonces $\alpha^k(i) = \beta_1^k(i)$ para toda $k \in \z$.
  2. Sean $\beta,\gamma \in S_n$ ciclos. Si existe $i \in \{1, \dots, n\}$ tal que $\beta(i) \neq i \neq \gamma (i)$ y $\beta^k(i) = \gamma^k(i)$ para toda $k \geq 1$, entonces $\beta = \gamma$.

Demostración.

  1. Sea $\alpha = \beta_1 \cdots \beta_t \in S_n$ una factorización en permutaciones disjuntas. Sea $i \in \{1, \dots,n\}$ tal que $\beta_1(i) \neq i$.
    Entonces, $\alpha^k = (\beta_1(\beta_2 \cdots \beta_t))^k = \beta_1^k(\beta_2 \cdots\beta_t)^k$ para toda $k \in \z$ ya que como $\beta_1$ y $(\beta_2 \cdots\beta_t)$ son disjuntas, conmutan.
    Además, como $\beta_1(i)\neq i$, el hecho de que $\beta_1, \dots, \beta_t$ sean disjuntas implica que $\beta_2(i)=\dots \beta_t(i)=i$, entonces $\beta_2 \cdots \beta_t(i) = i$. Así $\alpha^k(i) = \beta_1^k (\beta_2\cdots \beta_t)^k(i) = \beta_1^k(i)$ para toda $k \in \z$.
  2. Sean $\beta, \gamma \in S_n$ ciclos, $i \in \{1, \dots, n\}$ tal que $\beta$ y $\gamma$ mueven a $i$ y $\beta^k(i) = \gamma^k(i)$ para todo $k \geq 1$.
    P.D. $\beta = \gamma$
    Como $\beta$ y $\gamma$ son ciclos que mueven a $i$, entonces los podemos escribir como $\beta = (i \; i_1 \; \cdots \; i_r)$ y $\gamma = (i \; j \; \cdots \; j_l)$.
    Si observamos cómo mueven a los elementos, tenemos que
    \begin{align*}
    \beta^k(i) = i_k, \; k\in \{1, \dots, r\}, \; \beta^{r+1}(i) = i \\
    \gamma^k(i) = j_k, \; k \in \{1, \dots, l\}, \; \beta^{l+1}(i) = i
    \end{align*}
    Supongamos que $r \neq l$, sin pérdida de generalidad, $r < l$.
    \begin{align*}
    i &= \beta^{r+1}(i) \\
    & = \gamma^{r+1}(i) & \text{porque }\beta^k(i) = \gamma^k(i) \;\; \forall k \geq 1 \\
    & = j_{r+1} \neq i & r+1 \leq l
    \end{align*}
    Esto es una contradicción.
    Así, $r = l$ y $i_k = \beta^k(i) = \gamma^k(i) = j_k$ para toda $k \in \{1,\dots,r\}$.
    Por lo tanto $\beta = \gamma$.

$\square$

No es UNA factorización completa, es LA factorización completa

Recortemos la pregunta de la introducción ¿qué tienen en común todas las formas de describir a $\alpha$ como un producto de ciclos distintos en el que se incluyen todos los uno ciclos? He aquí la respuesta.

Teorema. Una factorización completa es única salvo por el orden de los factores.

Demostración.

Dado que en una factorización completa los $1-$ciclos corresponden a los elementos que quedan fijos, basta probar que los ciclos de longitud mayor a $1$ que aparecen en toda factorización completa coinciden.

Haremos inducción sobre $k = \#$sop $\alpha$.

Caso base. Cuando $k = 0$, entonces $\alpha =$ id y por lo tanto no tiene ciclos de longitud mayor a 1.

Sea $k > 0$.
Hipótesis de Inducción. Supongamos que si $\beta \in S_n$ con $\#$sop $\beta < k$, cualesquiera dos factorizaciones completas de $\beta$ tienen exactamente los mismos ciclos de longitud mayor a 1.

Sean $\alpha = \beta_1 \cdots \beta_t = \gamma_1 \cdots \gamma_s$, con $t,s \in \n^+$ dos factorizaciones de $\alpha$ obtenidas de omitir los $1-$ciclos en dos factorizaciones completas de $\alpha$.

Como $k>0$, existe $i \in \{1,\dots,n\}$ tal que $\alpha(i) \neq i$ y entonces también deben existir algún $\beta_j$ y algún $\gamma_l$ que muevan a $i$. Sin pérdida de generalidad supongamos que $\beta_1(i) \neq i \neq \gamma_1(i)$.

Entonces, por el inciso 1 del lema anterior,
\begin{align*}
\beta_i^k(i) = \alpha^k(i) = \gamma_1(i)^k \qquad \forall k \in \z
\end{align*}

y, por el inciso 2 del mismo lema,
\begin{align*}
\beta_1 = \gamma_1 .
\end{align*}

Así, cancelando $\beta_1$ tenemos que

\begin{align*}
\beta_2 \cdots \beta_t = \gamma_2 \cdots \gamma_s.
\end{align*}

Pero $\beta_2 \cdots \beta_t = \gamma_{2} \cdots \gamma_s$ son dos factorizaciones de una permutación que mueve menos de $k$ elementos con ciclos disjuntos de longitud mayor a $1$.

Por la hipótesis de inducción, $t = s$ y $\beta_2, \dots, \beta_t$son los mismos que $\gamma_2, \dots, \gamma_t$ salvo por el orden.

Por lo tanto, $\beta_1,\dots,\beta_t$ son los mismos que $\gamma_1,\dots,\gamma_s$ salvo por el orden.

$\square$

Tarea moral

  1. Considera el siguiente elemento de $S_9$
    \begin{align*}
    \alpha = \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
    9 & 8 & 1 & 4 & 3 & 7 & 6 & 2 & 5
    \end{pmatrix}
    \end{align*}
    Encuentra la factorización completa de $\alpha$.
  2. Sea $\alpha \in S_n$ y $\alpha = \beta_1 \dots \beta_t$ una factorización completa de $\alpha$. Analiza qué ocurre con $\displaystyle \sum_{i= 1}^t \text{long } \beta_i$.
  3. Considera el ejercicio 3 de la entrada de permutaciones:
    Sean $\alpha, \beta \in 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 las factorizaciones completas de $\alpha, \beta, \alpha\beta, \beta\alpha$ y $\beta^{-1}$.

Más adelante…

Entonces ya sabemos que existe una factorización única para cada permutación. La usaremos para definir el concepto de estructura cíclica en la siguiente entrada.

Entradas relacionadas

Álgebra Moderna I: Permutaciones y Grupo Simétrico

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

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

  • 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

El principio de divide y conquista en conteo

CombinatoriaMuchas veces es mejor dividir un problema grande en problemas pequeños. A esto se le conoce como el principio de Divide y conquista. En esta serie de videos veremos en qué consiste aplicándolo al conteo. Después recapitularemos lo que vimos.

Ir a los videos…