Matriz de permutación

Matriz con exactamente un 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 con todas las demás entradas 0. ^{[1] : 26} Una matriz de permutación de n × n puede representar una permutación de n elementos. La multiplicación previa de una matriz M de n filas por una matriz de permutación P , formando PM , da como resultado la permutación de las filas de M , mientras que la multiplicación posterior de una matriz M de n columnas , formando MP , permuta las columnas de M.

Toda matriz de permutación P es ortogonal , con su inversa igual a su transpuesta : . ^{[1] : 26} De hecho, las matrices de permutación se pueden caracterizar como matrices ortogonales cuyas entradas son todas no negativas . ^[2] ${\displaystyle P^{-1}=P^{\mathsf {T}}}$

Las dos correspondencias permutación/matriz

Existen dos correspondencias naturales uno a uno entre permutaciones y matrices de permutaciones, una de las cuales funciona a lo largo de las filas de la matriz y la otra a lo largo de sus columnas. Aquí hay un ejemplo, comenzando con una permutación π en forma de dos líneas en la parte superior izquierda:

${\displaystyle {\begin{matrix}\pi \colon {\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}&\longleftrightarrow &R_{\pi }\colon {\begin{pmatrix}0&0&1&0\\0&1&0&0\\0&0&0&1\\1&0&0&0\end{pmatrix}}\\[5pt]{\Big \updownarrow }&&{\Big \updownarrow }\\[5pt]C_{\pi }\colon {\begin{pmatrix}0&0&0&1\\0&1&0&0\\1&0&0&0\\0&0&1&0\end{pmatrix}}&\longleftrightarrow &\pi ^{-1}\colon {\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}}\end{matrix}}}$

La correspondencia basada en filas lleva la permutación π a la matriz en la esquina superior derecha. La primera fila de tiene su 1 en la tercera columna porque . De manera más general, tenemos dónde , cuándo y de otra manera. ${\displaystyle R_{\pi }}$ ${\displaystyle R_{\pi }}$ ${\displaystyle \pi (1)=3}$ ${\displaystyle R_{\pi }=(r_{ij})}$ ${\displaystyle r_{ij}=1}$ ${\displaystyle j=\pi (i)}$ ${\displaystyle r_{ij}=0}$

La correspondencia basada en columnas lleva π a la matriz en la parte inferior izquierda. La primera columna de tiene su 1 en la tercera fila porque . De manera más general, tenemos donde es 1 cuando y 0 en caso contrario. Dado que las dos recetas difieren sólo al intercambiar i con j , la matriz es la transpuesta de ; y, como es una matriz de permutación, tenemos . Siguiendo los otros dos lados del cuadrado grande, tenemos y . ^[3] ${\displaystyle C_{\pi }}$ ${\displaystyle C_{\pi }}$ ${\displaystyle \pi (1)=3}$ ${\displaystyle C_{\pi }=(c_{ij})}$ ${\displaystyle c_{ij}}$ ${\displaystyle i=\pi (j)}$ ${\displaystyle C_{\pi }}$ ${\displaystyle R_{\pi }}$ ${\displaystyle R_{\pi }}$ ${\displaystyle C_{\pi }=R_{\pi }^{\mathsf {T}}=R_{\pi }^{-1}}$ ${\displaystyle R_{\pi ^{-1}}=C_{\pi }=R_{\pi }^{-1}}$ ${\displaystyle C_{\pi ^{-1}}=R_{\pi }}$

Las matrices de permutación permutan filas o columnas

Multiplicar una matriz M por cualquiera de los lados izquierdo o derecho permutará las filas o columnas de M por π o π ⁻¹ . Los detalles son un poco complicados. ${\displaystyle R_{\pi }}$ ${\displaystyle C_{\pi }}$

Para empezar, cuando permutamos las entradas de un vector mediante alguna permutación π , movemos la entrada del vector de entrada a la ranura del vector de salida. ¿Qué entrada termina entonces, digamos, en la primera ranura de la salida? Respuesta: La entrada para la cual y por lo tanto . Argumentando de manera similar sobre cada una de las ranuras, encontramos que el vector de salida es ${\displaystyle (v_{1},\ldots ,v_{n})}$ ${\displaystyle i^{\text{th}}}$ ${\displaystyle v_{i}}$ ${\displaystyle \pi (i)^{\text{th}}}$ ${\displaystyle v_{j}}$ ${\displaystyle \pi (j)=1}$ ${\displaystyle j=\pi ^{-1}(1)}$

${\displaystyle {\big (}v_{\pi ^{-1}(1)},v_{\pi ^{-1}(2)},\ldots ,v_{\pi ^{-1}(n)}{\big )},}$

aunque estemos permutando por , no por . Por lo tanto, para permutar las entradas por , debemos permutar los índices por . ^{[1] : 25} (Permutar las entradas por a veces se denomina tomar el punto de vista de la coartada , mientras que permutar los índices por tomaría el punto de vista del alias . ^[4] ) ${\displaystyle \pi }$ ${\displaystyle \pi ^{-1}}$ ${\displaystyle \pi }$ ${\displaystyle \pi ^{-1}}$ ${\displaystyle \pi }$ ${\displaystyle \pi }$

Ahora, supongamos que multiplicamos previamente alguna matriz de n filas por la matriz de permutación . Según la regla de multiplicación de matrices , la entrada en el producto es ${\displaystyle M=(m_{i,j})}$ ${\displaystyle C_{\pi }}$ ${\displaystyle (i,j)^{\text{th}}}$ ${\displaystyle C_{\pi }M}$

$${\displaystyle \sum _{k=1}^{n}c_{i,k}m_{k,j},}$$

donde es 0 excepto cuando , cuando es 1. Por lo tanto, el único término de la suma que sobrevive es el término en el que , y la suma se reduce a . Como hemos permutado el índice de fila por , hemos permutado las filas de M por π . ^{[1] : 25} Un argumento similar muestra que la multiplicación posterior de una matriz M de n columnas permuta sus columnas por π . ${\displaystyle c_{i,k}}$ ${\displaystyle i=\pi (k)}$ ${\displaystyle k=\pi ^{-1}(i)}$ ${\displaystyle m_{\pi ^{-1}(i),j}}$ ${\displaystyle \pi ^{-1}}$ ${\displaystyle R_{\pi }}$

Las otras dos opciones son multiplicar previamente o posmultiplicar por , y permutan las filas o columnas respectivamente por π ⁻¹ , en lugar de por π . ${\displaystyle R_{\pi }}$ ${\displaystyle C_{\pi }}$

La transpuesta también es la inversa.

Un argumento relacionado demuestra que, como afirmamos anteriormente, la transpuesta de cualquier matriz de permutación P también actúa como su inversa, lo que implica que P es invertible. (Artin deja esa prueba como ejercicio, ^{[1] : 26} que aquí resolvemos.) Si , entonces la entrada de su transpuesta es . La entrada del producto es entonces ${\displaystyle P=(p_{i,j})}$ ${\displaystyle (i,j)^{\text{th}}}$ ${\displaystyle P^{\mathsf {T}}}$ ${\displaystyle p_{j,i}}$ ${\displaystyle (i,j)^{\text{th}}}$ ${\displaystyle PP^{\mathsf {T}}}$

$${\displaystyle \sum _{k=1}^{n}p_{i,k}p_{j,k}.}$$

Siempre que el término de esta suma sea el producto de dos entradas diferentes en la columna de P ; entonces todos los términos son 0 y la suma es 0. Cuando , estamos sumando los cuadrados de las entradas en la fila de P , entonces la suma es 1. Por lo tanto, el producto es la matriz identidad. Un argumento simétrico muestra lo mismo para , implicando que P es invertible con . ${\displaystyle i\neq j}$ ${\displaystyle k^{\text{th}}}$ ${\displaystyle k^{\text{th}}}$ ${\displaystyle i=j}$ ${\displaystyle i^{\text{th}}}$ ${\displaystyle PP^{\mathsf {T}}}$ ${\displaystyle P^{\mathsf {T}}P}$ ${\displaystyle P^{-1}=P^{\mathsf {T}}}$

Multiplicar matrices de permutación

Dadas dos permutaciones de n elementos 𝜎 y 𝜏, el producto de las correspondientes matrices de permutación basadas en columnas C _σ y C _τ está dado, ^{[1] : 25,} como era de esperar, por

$${\displaystyle C_{\sigma }C_{\tau }=C_{\sigma \,\circ \,\tau },}$$

${\displaystyle \sigma \circ \tau }$

$${\displaystyle (\sigma \circ \tau )(k)=\sigma \left(\tau (k)\right).}$$

C _τC _σ ${\displaystyle C_{\sigma \,\circ \,\tau }}$

Para las matrices basadas en filas, hay un giro: el producto de R _σ y R _τ viene dado por

${\displaystyle R_{\sigma }R_{\tau }=R_{\tau \,\circ \,\sigma },}$

con 𝜎 aplicado antes de 𝜏 en la permutación compuesta. Esto sucede porque debemos multiplicar posteriormente para evitar inversiones en la opción basada en filas, por lo que multiplicaríamos posteriormente primero por R _σ y luego por R _τ .

Algunas personas, cuando aplican una función a un argumento, escriben la función después del argumento ( notación postfija ), en lugar de antes. Al hacer álgebra lineal, trabajan con espacios lineales de vectores fila y aplican un mapa lineal a un argumento usando la matriz del mapa para multiplicar posteriormente el vector fila del argumento. A menudo utilizan un operador de composición de izquierda a derecha, que aquí denotamos mediante punto y coma; entonces la composición está definida por ${\displaystyle \sigma \,;\,\tau }$

${\displaystyle (\sigma \,;\,\tau )(k)=\tau \left(\sigma (k)\right),}$

o, más elegantemente, por

${\displaystyle (k)(\sigma \,;\,\tau )=\left((k)\sigma \right)\tau ,}$

con 𝜎 aplicado primero. Esa notación nos da una regla más simple para multiplicar matrices de permutación basadas en filas:

${\displaystyle R_{\sigma }R_{\tau }=R_{\sigma \,;\,\tau }.}$

grupo matriz

Cuando π es la permutación identidad, que tiene para todo i , tanto C _π como R _π son la matriz identidad . ${\displaystyle \pi (i)=i}$

No hay ! matrices de permutación, ya que hay n ! permutaciones y el mapa es una correspondencia uno a uno entre permutaciones y matrices de permutaciones. (El mapa es otra correspondencia de este tipo.) Según las fórmulas anteriores, esas matrices de permutación n × n forman un grupo de orden n . bajo multiplicación de matrices, con la matriz identidad como su elemento identidad , grupo que denotamos . El grupo es un subgrupo del grupo lineal general de matrices invertibles n × n de números reales. De hecho, para cualquier campo F , el grupo también es un subgrupo del grupo , donde las entradas de la matriz pertenecen a F . (Cada campo contiene 0 y 1 con y y eso es todo lo que necesitamos para multiplicar matrices de permutación. Diferentes campos no están de acuerdo sobre si , pero esa suma no surge). ${\displaystyle C\colon \pi \mapsto C_{\pi }}$ ${\displaystyle R}$ ${\displaystyle {\mathcal {P}}_{n}}$ ${\displaystyle {\mathcal {P}}_{n}}$ ${\displaystyle GL_{n}(\mathbb {R} )}$ ${\displaystyle {\mathcal {P}}_{n}}$ ${\displaystyle GL_{n}(F)}$ ${\displaystyle 0+0=0,}$ ${\displaystyle 0+1=1,}$ ${\displaystyle 0*0=0,}$ ${\displaystyle 0*1=0,}$ ${\displaystyle 1*1=1;}$ ${\displaystyle 1+1=0}$

Denotemos el grupo simétrico , o grupo de permutaciones , en {1,2,..., n } donde la operación de grupo es la composición estándar de derecha a izquierda " "; y denotemos el grupo opuesto , que usa la composición de izquierda a derecha " ". El mapa que lleva π a su matriz basada en columnas es una representación fiel , y lo mismo ocurre con el mapa que lleva π a . ${\displaystyle S_{n}^{\leftarrow }}$ ${\displaystyle \circ }$ ${\displaystyle S_{n}^{\rightarrow }}$ ${\displaystyle \,;\,}$ ${\displaystyle C\colon S_{n}^{\leftarrow }\to GL_{n}(\mathbb {R} )}$ ${\displaystyle C_{\pi }}$ ${\displaystyle R\colon S_{n}^{\rightarrow }\to GL_{n}(\mathbb {R} )}$ ${\displaystyle R_{\pi }}$

Matrices doblemente estocásticas

Toda matriz de permutación es doblemente estocástica . El conjunto de todas las matrices doblemente estocásticas se denomina politopo de Birkhoff , y las matrices de permutación desempeñan un papel especial en ese politopo. 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, siendo las matrices de permutación precisamente los puntos extremos (los vértices) del politopo de Birkhoff. El politopo de Birkhoff es, por tanto, la cáscara convexa de las matrices de permutación. ^[5]

Propiedades algebraicas lineales

Así como cada permutación está asociada con dos matrices de permutación, cada matriz de permutación está asociada con dos permutaciones, como podemos ver al reetiquetar el ejemplo en el gran cuadrado de arriba comenzando con la matriz P en la parte superior derecha:

${\displaystyle {\begin{matrix}\rho _{P}\colon {\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}&\longleftrightarrow &P\colon {\begin{pmatrix}0&0&1&0\\0&1&0&0\\0&0&0&1\\1&0&0&0\end{pmatrix}}\\[5pt]{\Big \updownarrow }&&{\Big \updownarrow }\\[5pt]P^{-1}\colon {\begin{pmatrix}0&0&0&1\\0&1&0&0\\1&0&0&0\\0&0&1&0\end{pmatrix}}&\longleftrightarrow &\kappa _{P}\colon {\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}}\end{matrix}}}$

Así que aquí denotamos la inversa de C como y la inversa de R como . Luego podemos calcular las propiedades algebraicas lineales de P a partir de algunas propiedades combinatorias que comparten las dos permutaciones y . ${\displaystyle \kappa }$ ${\displaystyle \rho }$ ${\displaystyle \kappa _{P}}$ ${\displaystyle \rho _{P}=\kappa _{P}^{-1}}$

Un punto se fija por just cuando se fija por , y la traza de P es el número de dichos puntos fijos compartidos. ^{[1] : 322} Si el número entero k es uno de ellos, entonces el vector de base estándar e _k es un vector propio de P . ^{[1] : 118} ${\displaystyle \kappa _{P}}$ ${\displaystyle \rho _{P}}$

Para calcular los valores propios complejos de P , escriba la permutación como una composición de ciclos disjuntos , digamos . (Las permutaciones de subconjuntos disjuntos se conmutan, por lo que aquí no importa si estamos componiendo de derecha a izquierda o de izquierda a derecha). Para , sea la longitud del ciclo y sea el conjunto de soluciones complejas de , siendo esas soluciones las raíces de la unidad . La unión multiconjunto de es entonces el conjunto múltiple de valores propios de P . Dado que escribir como producto de ciclos daría el mismo número de ciclos de la misma duración, analizar daría el mismo resultado. La multiplicidad de cualquier valor propio v es el número de i para el cual contiene v . ^[6] (Dado que cualquier matriz de permutación es normal y cualquier matriz normal es diagonalizable sobre los números complejos, ^{[1] : 259} las multiplicidades algebraicas y geométricas de un valor propio v son las mismas). ${\displaystyle \kappa _{P}}$ ${\displaystyle \kappa _{P}=c_{1}c_{2}\cdots c_{t}}$ ${\displaystyle 1\leq i\leq t}$ ${\displaystyle c_{i}}$ ${\displaystyle \ell _{i}}$ ${\displaystyle L_{i}}$ ${\displaystyle x^{\ell _{i}}=1}$ ${\displaystyle \ell _{i}^{\,{\text{th}}}}$ ${\displaystyle L_{i}}$ ${\displaystyle \rho _{P}}$ ${\displaystyle \rho _{p}}$ ${\displaystyle L_{i}}$

Por la teoría de grupos sabemos que cualquier permutación puede escribirse como una composición de transposiciones . Por lo tanto, cualquier matriz de permutación se factoriza como producto de matrices elementales de cambio de filas , cada una de las cuales tiene determinante −1. Así, el determinante de la matriz de permutación P es el signo de la permutación , que también es el signo de . ${\displaystyle \kappa _{P}}$ ${\displaystyle \rho _{P}}$

Formularios restringidos

• Matriz de costas , una matriz de permutación en la que los vectores de desplazamiento entre las entradas son todos distintos
• Rompecabezas de n-reinas , una matriz de permutación en la que hay como máximo una entrada en cada diagonal y antidiagonal

Ver también

• Matriz de signos alternos
• Matriz de intercambio
• Matriz de permutación generalizada
• polinomio de torre
• Permanente

Referencias

1. Artin, Michael (1991). Álgebra . Prentice Hall. págs. 24-26, 118, 259, 322.
2. Zavlanos, Michael M.; Pappas, George J. (noviembre de 2008). "Un enfoque de sistemas dinámicos para la coincidencia de gráficos ponderados". Automática . 44 (11): 2817–2824. CiteSeerX 10.1.1.128.6870 . doi :10.1016/j.automatica.2008.04.009. S2CID  834305 . Consultado el 21 de agosto de 2022 . Denotemos el conjunto de matrices ortogonales y denotemos el conjunto de matrices no negativas por elementos. Entonces, donde está el conjunto de matrices de permutación.  ${\displaystyle O_{n}}$ ${\displaystyle n\times n}$ ${\displaystyle N_{n}}$ ${\displaystyle n\times n}$ ${\displaystyle P_{n}=O_{n}\cap N_{n}}$ ${\displaystyle P_{n}}$ ${\displaystyle n\times n}$
3. Esta terminología no es estándar. La mayoría de los autores utilizan sólo una de las dos correspondencias, eligiendo cuál es coherente con sus otras convenciones. Por ejemplo, Artin utiliza la correspondencia basada en columnas. Hemos inventado aquí dos nombres para discutir ambas opciones.
4. Conway, John H.; Burgiel, Heidi; Goodman-Strauss, Chaim (2008). Las simetrías de las cosas . AK Peters. pag. 179. Se puede considerar que una permutación (digamos, de los nombres de varias personas) mueve los nombres o las personas. El punto de vista del alias considera que la permutación asigna un nuevo nombre o alias a cada persona (del latín alias = de lo contrario). Alternativamente, desde el punto de vista de la coartada trasladamos a las personas a los lugares correspondientes a sus nuevos nombres (del latín coartada = en otro lugar).
5. Brualdi (2006) p.19
6. J Najnudel, A Nikeghbali 2010 p.4

• Brualdi, Richard A. (2006). Clases de matrices combinatorias . Enciclopedia de Matemáticas y sus aplicaciones. vol. 108. Cambridge: Prensa de la Universidad de Cambridge . ISBN 0-521-86565-4. Zbl  1106.05001.
• José, Najnudel; Ashkan, Nikeghbali (2010), La distribución de valores propios de matrices de permutación aleatorias , arXiv : 1005.0402 , Bibcode : 2010arXiv1005.0402N