Matriz permutación
La matriz permutación es la matriz cuadrada con todos sus n×n elementos iguales a 0, excepto uno cualquiera por cada fila y columna, el cual debe ser igual a 1.
De acuerdo a esta definición existen n!
matrices de permutación distintas, de las cuales una mitad corresponde a matrices de permutación par (con el determinante igual a 1) y la otra mitad a matrices de permutación impar (con el determinante igual a -1).
Ambos métodos para definir las matrices de permutación aparecen en la literatura y las propiedades expresadas en una representación pueden ser fácilmente convertidas a la otra representación.
Este artículo tratará principalmente de una sola de estas representaciones y la otra sólo se mencionará cuando haya una diferencia que haya que tener en cuenta.
= (pij) que se obtiene al permutar las columnas de la matriz identidad
(i) y 0 en caso contrario, se referirá a la representación de la columna en este artículo.
, un vector de base estándar, denota un vector de longitud m con un 1 en la posición j y 0 en cualquier otra posición.
Observemos que la columna j de la matriz identidad
La otra representación, obtenida por permutar las filas de la matriz identidad
y 0 en caso contrario, se denominará representación de la fila.
El uso repetido de este resultado muestra que si
se muestra que la permutación de las filas viene dada por
), existe la matriz inversa y se puede escribir como
actúan sobre vectores columna y están compuestos por
Las mismas matrices que actúan sobre los vectores fila (es decir, post-multiplicación) se componen según la misma regla
Para ser claros, las fórmulas anteriores utilizan la notación polaca para la composición de permutación, es decir,
Otras propiedades: Si (1) denota la permutación identidad, entonces
Por las fórmulas anteriores, las matrices permutación de n × n forman un grupo bajo la matriz multiplicación con la matriz identidad como elemento neutro.
El mapa Sn → A ⊂ GL(n, Z2) es una representación fiel.
Una matriz permutación es en sí misma una matriz doble estocástica, pero también desempeña un papel especial en la teoría de dichas matrices.
El teorema de Birkhoff-von Neumann dice que cada matriz real doble estocástica es una combinación convexa de matrices permutación del mismo orden y que las matrices permutación son precisamente los puntos extremos del conjunto de matrices dobles estocásticas.
Si la permutación tiene puntos fijos, se puede escribir en forma de ciclo como π = (a1)(a2)...(ak)σ donde σ no tiene puntos fijos, Entonces ea1,ea2,...,eak son vectores propios de la matriz permutación.
Para calcular los vectores propios de una matriz permutación
Dejemos que las longitudes correspondientes de estos ciclos sean
Cuando una matriz permutación P es multiplicada por la izquierda por una matriz M para generar PM permutará las filas de M (aquí los elementos de un vector columna), cuando P es multiplicada por la derecha por M para generar MP permutará las columnas de M (aquí los elementos de un vector fila):
Las permutaciones de filas y columnas son por ejemplo reflexiones (ver más abajo) y permutaciones cícicas (ver matriz circulante).
Una matriz permutación siempre será de la forma
donde eai representa el i vector base (como fila) para Rj, y donde
Es decir, por ejemplo, v= (g0,...,g5)T, eai·v=gai Así, el producto de la matriz permutación con el vector v anterior, será un vector en la forma (ga1, ga2, ..., gaj) , y ésta es pues una permutación de v ya que hemos dicho que la forma de permutación es
