Álgebra de permutaciones

Permutaciones

Consideremos el conjunto de índices $\{1,2,\ldots,n\}$. Entendemos por permutación una aplicación inyectiva del conunto $\{1,2,\ldots,n\}$ sobre sí mismo, de manera que $1\mapsto i_1$, $2\mapsto i_2$, $\ldots$, $n\mapsto i_n$, y notamos dicha permutación de la forma $i=[i_1,i_2,\ldots,i_n]$. Así, por ejemplo, la permutación $i=[2,4,3,1]$ significa que a $1$ le corresponde el $2$; al $2$ el $4$; al $3$ el $3$ y al $4$ el $1$, esto es, $i_1=2$, $i_2=4$,$i_3=3$ y $i_4=4$.

A partir de $n$ índices podemos obtener $n!$ permutaciones distintas.

Podemos componer dos permutaciones $i=[i_1,i_2,\ldots,i_n]$ y $j=[j_1,j_2,\ldots,j_n]$, obteniendo otra permutación de las $n!$ posibles. Esta nueva permutación, $k$, que resulta la notamos de la forma $(j\circ i)_k$, leyéndose $i$ compuesta con $j$, queriendo significar con ello que actúa primero la permutación $i$ y en segundo lugar la permutación $j$ sobre el resultado de la primera; así $(j \circ i)_k=j_{i_k}$

Ejemplo de permutación con $n=4$
Consideremos $i=[2,4,3,1]$ y $j=[4,2,1,3]$. Entonces $j\circ i$ es otra permutación, $k=(j\circ i)_k=j_{i_k}$ y es tal que:
  $k_1=j_{i_1}=j_2=2$
  $k_2=j_{i_2}=j_4=3$
  $k_3=j_{i_3}=j_3=1$
  $k_4=j_{i_4}=j_1=4$
Es decir, $$j \circ i=[2,3,1,4]$$

El grupo de permutaciones $(\mathcal{P}_n,\circ)$

El conjunto de las permutaciones, $\mathcal{P}$, de $n$ índices con la operación composición (o producto) de permutaciones, $(\mathcal{P}_n,\circ)$, tiene estructura de grupo. En efecto, la operación es interna; se cumple la propiedad asociativa $i\circ (j\circ k) = (i \circ j) \circ k$, para cualesquiera permutaciones $i,j$ y $k$; y, existe elemento neutro, que no es otro que $e=[1,2,\ldots,n]$, habida cuenta de que $e\circ i=i\circ e$ para toda permutación $i\in \mathcal{P}_n$, y dada cualquier permutación, $i$, existe para ésta un elemento simétrico, que designaremos por $i'$ y es tal que $i_m=n$ si y sólo si $i'_n=m$, para cualesquiera valores de índices $n,m\in \{1,2,\ldots,n\}$, por lo que $i \circ i' = i' \circ i = e$. Cabe decir, además, que, para cualesquiera permutaciones $i$ y $j$, no se cumple la propiedad conmutativa: $i\circ j \neq j \circ i$ luego dicho grupo no es conmutativo.

Ejemplo de cálculo de la permutación inversa de una permutación dada
Consideremos la permutación $\mathcal{P}_4 \ni i=[4,1,2,3]$. Entonces, como $1$ está en el segundo lugar en la permutación $i$, esto es, $i'_1=2$, ya que $i_2=1$; razonando de la misma manera, deducimos que $i'_2=3$, puesto que $i_3=2$; $i'_3=4$ (ya que $i_4=4$), y $i'_4=1$, pues $i_1=4$. Por consiguiente la permutación inversa de $i=[4,3,2,1]$ es $i'=[2,3,4,1]$.
Comprobemos que $e=[1,2,3,4]=i'\circ i=i'_{i_k}$ donde $k=1,2,3,4$:
  $i'_{i_1}=i'_4=1=e_1$
  $i'_{i_2}=i'_1=2=e_2$
  $i'_{i_3}=i'_2=3=e_3$
  $i'_{i_4}=i'_3=4=e_4$
y también que, $e=[1,2,3,4]=i\circ i'=i_{i'_k}$ donde $k=1,2,3,4$:
  $i_{i'_1}=i_2=1=e_1$
  $i_{i'_2}=i_3=2$
  $i_{i'_3}=i_4=3$
  $i_{i_4}=i_1=4$

Trasposiciones

Llamamos trasposición al intercambio de dos índices ($r$ por $s$, y $s$ por $r$) sin alterar el lugar del resto de los índices, y lo escribimos de la forma $(r,s)$. Ejemplo: $(2,4)=[1,4,3,2]$. Resulta evidente que la inversa de una trasposición es ella misma ya que $(r,s)=(s,r)$.

Teorema. Toda permutación se puede escribir como un producto (composición) de un número finito de trasposiciones.
Ejemplo
Se considera la permutación $[3,4,2,1]$. Veamos cómo escribirla como un producto de trasposiciones.
$[3,4,2,1]=(1,3)\circ [1,4,2,3]=$
  $=(1,3)\circ (2,4) \circ [1,2,4,3]$
    $=(1,3)\circ (2,4) \circ (3,4)\circ [1,2,3,4]$, que podemos escribir también como
      $[3,4,2,1]=(1,3)\circ (2,4) \circ (3,4)$, puesto que la última permutación que resulta (a la derecha) en el paso anterior $[1,2,3,4]$ es el elemento neutro del producto.

(...) $\diamond$