Matriz de permutación

ImprimirCitar

Matriz con exactamente 1 por fila y columna

En matemáticas, particularmente en teoría de matrices, una matriz de permutación es una matriz binaria cuadrada que tiene exactamente una entrada de 1 en cada fila y cada columna y ceros en el resto. Cada una de estas matrices, digamos $P$ , representa una permutación de $m$ elementos y, cuando se usa para multiplicar otra matriz, digamos $A$ , da como resultado la permutación de las filas (al premultiplicar, para formar $PA$ ) o columnas (al posmultiplicar, para formar $AP$ ) de la matriz $A$ .

Definición

Dada una permutación $π$ de m elementos,

pi:lbrace 1,ldotsmrbrace to lbrace 1,ldotsmrbrace

representado en forma de dos líneas por

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

hay dos formas naturales de asociar la permutación con una matriz de permutación; es decir, comenzando con la matriz de identidad m × m, $I m$ , permute las columnas o permute las filas, según $π$ . Ambos métodos para definir matrices de permutación aparecen en la literatura y las propiedades expresadas en una representación se pueden convertir fácilmente a la otra representación. Este artículo se ocupará principalmente de una de estas representaciones y la otra solo se mencionará cuando haya una diferencia que deba tenerse en cuenta.

La matriz de permutación m × m P_$π$ = (p_ij) obtenido al permutar las columnas de la matriz identidad $I m$ , es decir, para cada i, $p ij = 1$ si j = $π$ (i) y $p ij = 0$ de lo contrario, se denominará representación de columna en este artículo. Dado que las entradas en la fila i son todas 0 excepto que aparece un 1 en la columna $π$ (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}$ , a vector de base estándar, denota un vector de fila de longitud m con 1 en el ja posición y 0 en cada otra posición.

Por ejemplo, la matriz de permutación P_$π$ correspondiente a la permutación ${displaystyle pi ={begin{pmatrix}1&2&3&4&5\1&4&2&5&3end{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&0end{bmatrix}}.

Observe que ahora aparece la columna jésima de la matriz de identidad $I 5$ como la $π$ (j)ésima columna de P_$π$.

La otra representación, obtenida permutando las filas de la matriz identidad $I m$ , es decir, para cada j, p_ij = 1 si i = $π$ (j) y $p ij = 0$ de lo contrario, se denominará representación de fila.

Propiedades

La representación de columna de una matriz de permutación se usa a lo largo de esta sección, excepto cuando se indique lo contrario.

Multiplicación $P_{{pi }}$ veces un vector de columna g permute las filas del vector:

{displaystyle 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 adecuado, el producto, ${displaystyle P_{pi }M}$ es sólo una permutación de las filas de $M$ . Sin embargo, observando que

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

k

π

⁻¹

{displaystyle M^{mathsf {T}}}

M

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

{displaystyle P_{pi }^{-1}=P_{pi ^{-1}}=P_{pi }^{mathsf {T}}.}

Multiplicar un vector de fila h veces $P_{{pi }}$ permute las columnas del vector:

{displaystyle mathbf {h} P_{pi }={begin{bmatrix}h_{1}&h_{2}&cdots &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)}&cdots &h_{pi ^{-1}(n)}end{bmatrix}}}

Nuevamente, la aplicación repetida de este resultado muestra que después de multiplicar una matriz $M$ por la matriz de permutación $P π$ , es decir, $M P π$ , da como resultado la permutación de las columnas de $M$ . Note también que

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

Dadas dos permutaciones $π$ y $σ$ de $m$ elementos, las matrices de permutación correspondientes $P π$ y $P σ$ que actúan sobre los vectores columna se componen con

{displaystyle P_{sigma }P_{pi },mathbf {g} =P_{pi ,circ ,sigma },mathbf {g}.}

{displaystyle mathbf {h} P_{sigma }P_{pi }=mathbf {h} P_{pi ,circ ,sigma }.}

{displaystyle (pi ,circ ,sigma)(k)=pi left(sigma (k)right).}

Vamos ${displaystyle Q_{pi }}$ ser la matriz de permutación correspondiente a $π$ en su representación fila. Las propiedades de esta representación se pueden determinar desde las de la representación de la columna desde ${displaystyle Q_{pi }=P_{pi }^{mathsf {T}}=P_{{pi }^{-1}}.}$ En particular,

{displaystyle 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}}.}

{displaystyle Q_{sigma }Q_{pi },mathbf {g} =Q_{sigma ,circ ,pi },mathbf {g}.}

{displaystyle mathbf {h} ,Q_{sigma }Q_{pi }=mathbf {h} ,Q_{sigma ,circ ,pi }.}

Las matrices de permutación se pueden caracterizar como matrices ortogonales cuyas entradas son todas no negativas.

Grupo de matrices

Si (1) denota la permutación de identidad, entonces $P (1)$ es la matriz de identidad.

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

El mapa $S n \to GL(n, Z 2)$ que envía una permutación a su representación de columna es una representación fiel.

Matrices doblemente estocásticas

Una matriz de permutación es en sí misma una matriz doblemente estocástica, pero también juega un papel especial en la teoría de estas matrices. El teorema de Birkhoff-von Neumann dice que toda matriz real doblemente estocástica es una combinación convexa de matrices de permutación del mismo orden y las matrices de permutación son precisamente los puntos extremos del conjunto de matrices doblemente estocásticas. Es decir, el politopo de Birkhoff, el conjunto de matrices doblemente estocásticas, es la envolvente convexa del conjunto de matrices de permutación.

Propiedades algebraicas lineales

La traza de una matriz de permutación es el número de puntos fijos de la permutación. Si la permutación tiene puntos fijos, puede escribirse 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 de permutación.

Para calcular los eigenvalues de una matriz de permutación ${displaystyle P_{sigma }}$ , escribir $sigma$ como producto de ciclos, digamos, ${displaystyle sigma =C_{1}C_{2}cdots C_{t}}$ . Que las longitudes correspondientes de estos ciclos sean ${displaystyle l_{1},l_{2}...l_{t}}$ , y dejar ${displaystyle R_{i}(1leq ileq t)}$ ser el conjunto de soluciones complejas ${displaystyle x^{l_{i}}=1}$ . La unión de todos $R_{i}$ s es el conjunto de eigenvalues de la matriz de permutación correspondiente. La multiplicidad geométrica de cada eigenvalue equivale al número de $R_{i}$ Eso lo contiene.

De la teoría de grupos sabemos que cualquier permutación puede escribirse como un producto de transposiciones. Por lo tanto, cualquier matriz de permutación $P$ factoriza como un producto de matrices elementales de intercambio de filas, cada una con determinante −1. Por lo tanto, el determinante de una matriz de permutación $P$ es la firma de la permutación correspondiente.

Ejemplos

Permutación de filas y columnas

Cuando una matriz M se multiplica por una matriz de permutación P a la izquierda para formar PM, el producto es el resultado de permutar la filas de M. Como caso especial, si M es un vector columna, PM es el resultado de permutar las entradas de M:

P · (1, 2, 3, 4)^T = (4, 1, 3, 2)^T

Cuando, en cambio, M se multiplica por una matriz de permutación a la derecha para hacer MP, el producto es el resultado de permutar las columnas de M. Como caso especial, si M es un vector fila, entonces MP es el resultado de permutar las entradas de M:

(1, 2, 3, 4) · P = (2, 4, 3, 1)

Permutación de filas

La matriz de permutación P_π correspondiente a la permutación ${displaystyle pi ={begin{pmatrix}1&2&3&4&5\1&4&2&5&3end{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&0end{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 de permutación siempre tendrá la forma

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

donde e_{a_i} representa la iésimo vector de base (como una fila) para R^j, y donde

{begin{bmatrix}1&2&ldots &j\a_{1}&a_{2}&ldots &a_{j}end{bmatrix}}

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

Ahora, al realizar la multiplicación de matrices, uno forma esencialmente el producto escalar de cada fila de la primera matriz con cada columna de la segunda. En este caso, formaremos 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}

Entonces, el producto de la matriz de permutación con el vector v anterior, será un vector en la forma (g_a₁, g_a₂,..., g_{a_j}), y que esto entonces es 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}}.

Entonces, las matrices de permutación realmente permutan el orden de los elementos en vectores multiplicados por ellos.

Formularios restringidos

Sierra de Costas, una matriz de permutación en la que los vectores de desplazamiento entre las entradas son todos distintos
n-queens puzzle, una matriz de permutación en la que hay en la mayoría de una entrada en cada diagonal y antidiagonal

Contenido relacionado

Más resultados...