ORDEN DE UNA PERMUTACIÓN - SIGNATURA DE UNA PERMUTACIÓN
Corolario.- El orden de una permutación
es el mínimo común múltiplo (m.c.m.) de
los órdenes de sus ciclos disjuntos.
Demostración.- La permutación
vendrá dada en la forma: \( \sigma = \gamma_1 , ···
, \gamma_k \) de donde resulta:
\(\sigma^n = (\gamma_1, ··· , \gamma_k)^n = \gamma_1^n ···
\gamma_k^n = I \)
\( \Longrightarrow \forall i \quad \gamma_i^n = I\)
pero para que resulte esta equivalencia es necesario que n
sea múltiplo de los órdenes de todos los \(
\gamma_i \). Por lo tanto podemos tomar como orden de la permutación
el menor de dichos múltiplos que será el m.c.m.
Proposición.-
Toda permutación \( \sigma \) de n se puede poner como
producto de transposiciones.
Sabernos que toda permutación se puede poner en la
forma:
\( \sigma \in S_n \Rightarrow \sigma = \gamma_1 , ··· ,
\gamma_k\)
donde \( \gamma_i\) son ciclos longitud mayor o igual a 2.
Por otro lado, cada ciclo \( \gamma_i \) se puede expresar
según la, notación circular:
\( \gamma_i = (a_1, a_2, ··· , a_p) = (a_1, a_2)(a_2, a_3)
··· (a_{p-1}, a_p)\)
Ejemplos:
\( \begin{pmatrix} 1 & 2 & 3 & 4 & 5 &
6 \\ \\ 3 & 6 & 1 & 4 & 2 & 5
\end{pmatrix} = \begin{pmatrix} 1 & 3 \\ \\ 3 &
1 \end{pmatrix} \begin{pmatrix} 2 & 6 & 5 \\ \\
6 & 5 & 2 \end{pmatrix} \begin{pmatrix} 4 \\ \\
4 \end{pmatrix} = (1, 3)(2, 6, 5)(4) = (1, 3)(2, 6, 5) \)
\( \begin{pmatrix} 1 & 2 & 3 & 4 \\ \\ 2 &
3 & 4 & 1 \end{pmatrix} = \begin{pmatrix} 1 &
3 & 4 & 2 \\ \\ 2 & 3 & 4 & 1 \end{pmatrix}
\begin{pmatrix} 1 & 2 & 4 & 3 \\ \\ 1 &
3 & 4 & 2 \end{pmatrix} \begin{pmatrix} 1 &
2 & 3 & 4 \\ \\ 1 & 2 & 4 & 3 \end{pmatrix}
= (1, 2)(2, 3)(3, 4) \)
Como ejemplo general podemos poner:
\( \begin{pmatrix} 1 & 2 & 3 & 4 & 5 &
6 & 7 & 8 \\ \\ 5 & 3 & 8 & 6 &
7 & 4 & 1 & 2
\end{pmatrix} = \begin{pmatrix} 1 & 5 & 7 \\ \\
5 & 7 & 1 \end{pmatrix} \begin{pmatrix} 2 &
3 & 8 \\ \\ 3 & 8 & 2 \end{pmatrix} = \begin{pmatrix}
4 & 6 \\ \\ 6 & 4 \end{pmatrix} = \)
\( (1, 5, 7)(2, 3, 8)(4, 6) = (1, 5)(5, 7)(2, 3)(3, 8)(4,
6)\)
Sea \( \sigma \) una permutación de n; siendo \( \sigma
\) biyectiva, como hemos visto, se tiene para \( i, j \in
n \):
\( i < j \Rightarrow \left \{ \begin{array}{lll} \sigma
(i) < \sigma (j) \\ ó \\
\sigma (i) > \sigma (j) \end{array} \right. \)
Definición: inversión.-
Cuando para i < j es \( \sigma (i) > \sigma (j) \) se
dice que los dos elementos \( \sigma (i) \; y \; \sigma (j)
\) presentan una inversión.
Definición: signatura.- Se
llama signatura de una permutación al número
de inversiones que presente.
Definición: paridad .- Llamaremos
paridad de una permutación al número que se
obtiene mediante la operación:
\( \epsilon ( \sigma ) = (-1)^{sig(\sigma)} \)
Una permutación se dice que es par si tiene paridad
+1, e impar si tiene paridad -1. La, paridad de la permutación
identidad vale +1 puesto que al aplicar dicha permutación
no se produce ningún cambio y, por tanto, no se produce
ninguna inversión.
Toda trasposición tiene paridad (-1). Podemos escribir:
\( \begin{pmatrix} 1 & 2 & ··· & i-1 & i
& i+1 & ··· & j-1 & j & j+1 & ···
& n \\ \\ 1 & 2 & ··· & i-1 & j &
i+1 & ··· & j-1 & i & j+1 & ··· &
n \end{pmatrix} \)
Vemos que los elementos del conjunto {1, n - {i, j}} no presentan
ninguna, inversión dos a dos.
Por otro lado, los elementos\( \sigma (i) = j \quad , \quad
\sigma (j) = i \) no presentan ninguna inversión con
los elementos de los conjuntos {1, ..., (i-1)} y {(j+1), ...
, n}
Podemos también decir que los elementos \( \sigma (i)
\; y \; \sigma (j) \) presentan una inversión entre
ellos y además se tiene:
\( \sigma (i) \) presenta una inversión con cada elemento
de {(i+1), ..., (j-1)} (A1)
\( \sigma (j) \) presenta una inversión con cada elemento
de {(i+1), ..., (j-1)} (A2)
Por lo tanto, el número total de inversiones será
impar, puesto que las inversiones obtenidas en (A1 + A2) siempre
suman un número par. Nos queda entonces, tan solo,
la inversión entre \(\sigma (i) \; y \; \sigma (j)
\) con lo que, en resumen, podemos decir que toda trasposición
es impar.