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).

Para n = 3 se tiene:

Matrices de permutación par:

{\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\\\end{pmatrix}}{\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\\\end{pmatrix}}{\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\\\end{pmatrix}}

Matrices de permutación impar:

{\begin{pmatrix}0&0&1\\0&1&0\\1&0&0\\\end{pmatrix}}{\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\\\end{pmatrix}}{\begin{pmatrix}1&0&0\\0&0&1\\0&1&0\\\end{pmatrix}}

Puede notarse que las matrices de permutación conforman un grupo de orden n! respecto al producto.

Definición

Dada una permutación $\pi$ de m elementos,

$\pi :\lbrace 1,\ldots ,m\rbrace \to \lbrace 1,\ldots ,m\rbrace$

representada en forma de dos líneas por

${\begin{pmatrix}1&2&\cdots &m\\\pi (1)&\pi (2)&\cdots &\pi (m)\end{pmatrix}},$

hay dos maneras naturales de asociar la permutación con una matriz de permutación; a es decir, comenzando con la matriz identidad de m × m, $I_{m}$ , permuta las columnas o permuta las filas, según $\pi$ . 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.

La matriz permutación de m × m $P_{\pi }$ = (p_ij) que se obtiene al permutar las columnas de la matriz identidad $I_{m}$ es decir, por cada i, p_ij = 1 si j = $\pi$ (i) y 0 en caso contrario, se referirá a la representación de la columna en este artículo. Dado que las entradas en la fila i son todas 0 excepto que un 1 aparece en la columna $\pi$ (i), podemos escribir

$P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (m)}\end{bmatrix}},$

donde $\mathbf {e} _{j}$ , 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.

Por ejemplo, la matriz permutación $P_{\pi }$ correspondiente a la permutación: $\pi ={\begin{pmatrix}1&2&3&4&5\\1&4&2&5&3\end{pmatrix}},$ es

$P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\mathbf {e} _{\pi (3)}\\\mathbf {e} _{\pi (4)}\\\mathbf {e} _{\pi (5)}\end{bmatrix}}={\begin{bmatrix}\mathbf {e} _{1}\\\mathbf {e} _{4}\\\mathbf {e} _{2}\\\mathbf {e} _{5}\\\mathbf {e} _{3}\end{bmatrix}}={\begin{bmatrix}1&0&0&0&0\\0&0&0&1&0\\0&1&0&0&0\\0&0&0&0&1\\0&0&1&0&0\end{bmatrix}}.$

Observemos que la columna j de la matriz identidad $I_{5}$ ahora aparece como la columna $\pi (j)$ de $P_{\pi }$

La otra representación, obtenida por permutar las filas de la matriz identidad $I_{m}$ , es decir, por cada j, p_ij = 1 si i = $\pi (j)$ y 0 en caso contrario, se denominará representación de la fila.

Propiedades

La representación de las columnas de una matriz permutación se utiliza a lo largo de esta sección, salvo que se indique lo contrario.

Multiplicando $P_{\pi }$ veces un vector columna g permutará las filas del vector:

$P_{\pi }\mathbf {g} ={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (n)}\end{bmatrix}}{\begin{bmatrix}g_{1}\\g_{2}\\\vdots \\g_{n}\end{bmatrix}}={\begin{bmatrix}g_{\pi (1)}\\g_{\pi (2)}\\\vdots \\g_{\pi (n)}\end{bmatrix}}.$

El uso repetido de este resultado muestra que si $M$ es una matriz de tamaño apropiado, el producto, $P_{\pi }$ $M$ es sólo una permutación de las filas de $M$ . Sin embargo, observando que

$P_{\pi }\mathbf {e} _{k}^{\mathsf {T}}=\mathbf {e} _{\pi ^{-1}(k)}^{\mathsf {T}}$

para cada $k$ se muestra que la permutación de las filas viene dada por $\pi ^{-1}$ . ( $M^{T}$ es la transpuesta de $M$ ).

Como las matrices de permutación son matrices ortogonales (es decir, $P_{\pi }P_{\pi }^{\mathsf {T}}=I$ ), existe la matriz inversa y se puede escribir como

$P_{\pi }^{-1}=P_{\pi ^{-1}}=P_{\pi }^{\mathsf {T}}.$

Multiplicar un vector fila h veces $P_{\pi }$ permutará las columnas del vector:

$\mathbf {h} P_{\pi }={\begin{bmatrix}h_{1}\;h_{2}\;\dots \;h_{n}\end{bmatrix}}{\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (n)}\end{bmatrix}}={\begin{bmatrix}h_{\pi ^{-1}(1)}\;h_{\pi ^{-1}(2)}\;\dots \;h_{\pi ^{-1}(n)}\end{bmatrix}}$

Una vez más, la aplicación repetida de este resultado muestra que la post-multiplicación de una matriz $M$ por la matriz permutación $P_{\pi }$ o sea, $M$ $P_{\pi }$ resulta en la permutación de las columnas de $M$ . Nótese también que

$\mathbf {e} _{k}P_{\pi }=\mathbf {e} _{\pi (k)}.$

Dadas dos permutaciones $\pi$ y σ de m elementos, las correspondientes matrices de permutación $P_{\pi }$ y $P_{\sigma }$ actúan sobre vectores columna y están compuestos por

$P_{\sigma }P_{\pi }\,\mathbf {g} =P_{\pi \,\circ \,\sigma }\,\mathbf {g} .$

Las mismas matrices que actúan sobre los vectores fila (es decir, post-multiplicación) se componen según la misma regla

$\mathbf {h} P_{\sigma }P_{\pi }=\mathbf {h} P_{\pi \,\circ \,\sigma }.$

Para ser claros, las fórmulas anteriores utilizan la notación polaca para la composición de permutación, es decir,

$\pi \,\circ \,\sigma (k)=\pi \left(\sigma (k)\right).$

Dejemos que $Q_{\pi }$ sea la matriz permutación correspondiente a $\pi$ en su representación en filas. Las propiedades de esta representación se pueden determinar a partir de las de la representación de la columna, ya que $Q_{\pi }=P_{\pi }^{\mathsf {T}}=P_{{\pi }^{-1}}.$ En particular,

$Q_{\pi }\mathbf {e} _{k}^{\mathsf {T}}=P_{{\pi }^{-1}}\mathbf {e} _{k}^{\mathsf {T}}=\mathbf {e} _{(\pi ^{-1})^{-1}(k)}^{\mathsf {T}}=\mathbf {e} _{\pi (k)}^{\mathsf {T}}.$

De ello se deduce que

$Q_{\sigma }Q_{\pi }\,\mathbf {g} =Q_{\sigma \,\circ \,\pi }\,\mathbf {g} .$

Del mismo modo,

$\mathbf {h} \,Q_{\sigma }Q_{\pi }=\mathbf {h} \,Q_{\sigma \,\circ \,\pi }.$

Otras propiedades:

El elemento neutro del grupo es la matriz identidad.
El elemento inverso de cada elemento del grupo de matrices de permutación es la matriz traspuesta correspondiente.
Cada elemento del grupo de matrices de permutación es una matriz ortogonal.
El producto de matrices de permutación par siempre genera una matriz de permutación par.
El producto de matrices de permutación impar siempre genera una matriz de permutación par.
El producto de matrices de permutación de paridad distinta siempre genera una matriz de permutación impar.
Observe que las matrices de permutación par conforman un semigrupo y que además el grupo de matrices de permutación no es conmutativo.
Cada elemento del grupo de matrices de permutación fuera del semigrupo es una matriz simétrica.

Grupo matricial

Si (1) denota la permutación identidad, entonces $P_{1}$ es la matriz identidad.

Dejemos que $S_{n}$ denote denote el grupo simétrico, o grupo de permutaciones, en {1,2,..., $n$ }. Puesto que hay n permutaciones, hay n! matrices permutación. Por las fórmulas anteriores, las matrices permutación de $n \times n$ forman un grupo bajo la matriz multiplicación con la matriz identidad como elemento neutro.

El mapa $S n \to A \subset GL(n, Z 2)$ es una representación fiel. Por lo tanto, $| A | = n!$

Matrices dobles estocásticas

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. Es decir, el politopo de Birkhoff, el conjunto de matrices dobles estocásticas, es la envolvente convexa del conjunto de matrices permutación.

Propiedades algebraicas lineales

La traza de una matriz permutación es el número de puntos fijos de la permutación. Si la permutación tiene puntos fijos, se puede escribir en forma de ciclo como $π = (a 1)(a 2)...(a k)σ$ donde $σ$ no tiene puntos fijos, Entonces $e a 1, e a 2,..., e a k$ son vectores propios de la matriz permutación.

Para calcular los vectores propios de una matriz permutación $P_{\sigma }$ anotamos $\sigma$ como un producto de permutaciónes cíclicas, es decir, $\sigma =C_{1}C_{2}\cdots C_{t}$ . Dejemos que las longitudes correspondientes de estos ciclos sean $l_{1},l_{2}...l_{t}$ , y dejemos que $R_{i}(1\leq i\leq t)$ sea el conjunto de soluciones complejas de $x^{l_{i}}=1$ . La unión de todos los $R_{i}$ forman el conjunto de autovalores de la matriz permutación correspondiente. La multiplicidad geométrica de cada autovalor es igual al número de $R_{i}$ que lo contengan.

De la teoría de grupos sabemos que cualquier permutación puede ser expresada como producto de transposiciones. Por lo tanto, cualquier matriz permutación $P$ los factores como producto de un intercambio de matrices elementales, cada una de las cuales tiene como determinante -1. Por lo tanto, el determinante de una matriz permutación $P$ es sólo la paridad de la permutación correspondiente.

Ejemplos

Permutación de filas y columnas

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).

Permutación de filas

La matriz permutación P_π corresponde a la permutación: $\pi ={\begin{pmatrix}1&2&3&4&5\\1&4&2&5&3\end{pmatrix}},$ hay

$P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\mathbf {e} _{\pi (3)}\\\mathbf {e} _{\pi (4)}\\\mathbf {e} _{\pi (5)}\end{bmatrix}}={\begin{bmatrix}\mathbf {e} _{1}\\\mathbf {e} _{4}\\\mathbf {e} _{2}\\\mathbf {e} _{5}\\\mathbf {e} _{3}\end{bmatrix}}={\begin{bmatrix}1&0&0&0&0\\0&0&0&1&0\\0&1&0&0&0\\0&0&0&0&1\\0&0&1&0&0\end{bmatrix}}.$

Dado un vector g,

$P_{\pi }\mathbf {g} ={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\mathbf {e} _{\pi (3)}\\\mathbf {e} _{\pi (4)}\\\mathbf {e} _{\pi (5)}\end{bmatrix}}{\begin{bmatrix}g_{1}\\g_{2}\\g_{3}\\g_{4}\\g_{5}\end{bmatrix}}={\begin{bmatrix}g_{1}\\g_{4}\\g_{2}\\g_{5}\\g_{3}\end{bmatrix}}.$

Explicación

Una matriz permutación siempre será de la forma

${\begin{bmatrix}\mathbf {e} _{a_{1}}\\\mathbf {e} _{a_{2}}\\\vdots \\\mathbf {e} _{a_{j}}\\\end{bmatrix}}$

donde e_{a_i} representa el i vector base (como fila) para R^j, y donde
${\begin{bmatrix}1&2&\ldots &j\\a_{1}&a_{2}&\ldots &a_{j}\end{bmatrix}}$

es la forma permutación de la matriz permutación.

Ahora, al realizar la matriz multiplicación, uno forma esencialmente el producto escalar de cada fila de la primera matriz con cada columna de la segunda. En este caso, estaremos formando el producto escalar de cada fila de esta matriz con el vector de elementos que queremos permutar. Es decir, por ejemplo, v= (g₀,...,g₅)^T,

e_{a_i}·v=g_{a_i}

Así, el producto de la matriz permutación con el vector v anterior, será un vector en la forma (g_a_₁, g_a_₂, ..., g_{a_j}) , y ésta es pues una permutación de v ya que hemos dicho que la forma de permutación es

${\begin{pmatrix}1&2&\ldots &j\\a_{1}&a_{2}&\ldots &a_{j}\end{pmatrix}}.$