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 n × n puede representar una permutación de n elementos. Premultiplicar una matriz de n filas M por una matriz de permutación P , formando PM , da como resultado permutar las filas de M , mientras que postmultiplicar una matriz de n columnas M , 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 las matrices ortogonales cuyas entradas son todas no negativas . ^[2] ${\displaystyle P^{-1}=P^{\mathsf {T}}}$

Las dos correspondencias permutación/matricial

Existen dos correspondencias biunívocas naturales entre las permutaciones y las matrices de permutación, una de las cuales funciona a lo largo de las filas de la matriz y la otra a lo largo de sus columnas. A continuación se muestra 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 de la parte superior derecha. La primera fila de tiene su 1 en la tercera columna porque . En términos más generales, tenemos dónde, cuándo y en caso contrario. ${\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. Como las dos recetas difieren solo al intercambiar i con j , la matriz es la transpuesta de ; y, como es una matriz de permutación, tenemos . Trazando 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

Al multiplicar una matriz M por o por la izquierda o la derecha, se permutarán 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 adoptar el punto de vista de la coartada , mientras que permutar los índices por adoptarí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 una 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 en 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 al posmultiplicar una matriz de n columnas M por 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 premultiplicar por o postmultiplicar por , y permutan las filas o columnas respectivamente por π ⁻¹ , en lugar de por π . ${\displaystyle R_{\pi }}$ ${\displaystyle C_{\pi }}$

La transpuesta es también 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 resolvemos aquí.) 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 en esta suma es el producto de dos entradas diferentes en la columna de P ; por lo tanto, todos los términos son 0 y la suma es 0. Cuando , estamos sumando los cuadrados de las entradas en la fila de P , por lo que la suma es 1. El producto es, por lo tanto, la matriz identidad. Un argumento simétrico muestra lo mismo para , lo que implica 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}}}$

Multiplicación de matrices de permutación

Dadas dos permutaciones de n elementos 𝜎 y 𝜏, el producto de las matrices de permutación basadas en columnas correspondientes C _σ y C _τ se da, ^{[1] : 25} como podría esperarse, por donde la permutación compuesta aplica primero 𝜏 y luego 𝜎, trabajando de derecha a izquierda: Esto se deduce porque premultiplicar alguna matriz por C _τ y luego premultiplicar el producto resultante por C _σ da el mismo resultado que premultiplicar solo una vez por la combinada . $${\displaystyle C_{\sigma }C_{\tau }=C_{\sigma \,\circ \,\tau },}$$ ${\displaystyle \sigma \circ \tau }$ $${\displaystyle (\sigma \circ \tau )(k)=\sigma \left(\tau (k)\right).}$$ ${\displaystyle C_{\sigma \,\circ \,\tau }}$

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

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

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

Algunas personas, al aplicar una función a un argumento, escriben la función después del argumento ( notación de posfijo ), en lugar de antes. Al hacer álgebra lineal, trabajan con espacios lineales de vectores fila y aplican una función lineal a un argumento utilizando la matriz de la función para posmultiplicar el vector fila del argumento. A menudo utilizan un operador de composición de izquierda a derecha, que aquí denotamos utilizando un punto y coma; por lo que la composición se define mediante ${\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 de matrices

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

Hay n ! matrices de permutación, ya que hay n ! permutaciones y la función es una correspondencia biunívoca entre permutaciones y matrices de permutación. (La función es otra correspondencia de este tipo). Por las fórmulas anteriores, esas n × n matrices de permutación forman un grupo de orden n ! bajo la multiplicación de matrices, con la matriz identidad como su elemento identidad , un 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 difieren 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}$

Sea , 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 sea , el grupo opuesto , que utiliza la composición de izquierda a derecha " ". La función que lleva π a su matriz basada en columnas es una representación fiel , y lo mismo ocurre con la función 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 envoltura convexa de las matrices de permutación. ^[5]

Propiedades algebraicas lineales

Así como cada permutación está asociada a dos matrices de permutación, cada matriz de permutación está asociada a 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í estamos denotando la inversa de C como y la inversa de R como . Podemos entonces calcular las propiedades algebraicas lineales de P a partir de algunas propiedades combinatorias que son compartidas por las dos permutaciones y . ${\displaystyle \kappa }$ ${\displaystyle \rho }$ ${\displaystyle \kappa _{P}}$ ${\displaystyle \rho _{P}=\kappa _{P}^{-1}}$

Un punto está fijo por justo cuando está fijo por , y la traza de P es el número de tales puntos fijos compartidos. ^{[1] : 322} Si el entero k es uno de ellos, entonces el vector 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 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 del multiconjunto de es entonces el multiconjunto de valores propios de P . Dado que escribir como un producto de ciclos daría el mismo número de ciclos de las mismas longitudes, el análisis 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 algebraica y geométrica 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}}$

De 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 un producto de matrices elementales de cambio de fila , cada una de las cuales tiene determinante −1. Por lo tanto, 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.

Véase también

• Matriz de signos alternados
• Matriz de intercambio
• Matriz de permutación generalizada
• Polinomio de la torre
• Permanente

Referencias

1. Artin, Michael (1991). Álgebra . Prentice Hall. págs. 24-26, 118, 259, 322. ISBN 0-13-004763-5.OCLC 24364036  .
2. Zavlanos, Michael M.; Pappas, George J. (noviembre de 2008). "Un enfoque de sistemas dinámicos para la correspondencia de grafos ponderados". Automatica . 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 . Sea el conjunto de matrices ortogonales y el conjunto de matrices no negativas elemento por elemento. Entonces, , donde es 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 y eligen cuál es la que más se ajusta a sus otras convenciones. Por ejemplo, Artin utiliza la correspondencia basada en columnas. Aquí hemos inventado dos nombres para poder analizar ambas opciones.
4. Conway, John H. ; Burgiel, Heidi; Goodman-Strauss, Chaim (2008). Las simetrías de las cosas . AK Peters/CRC Press. pág. 179. doi :10.1201/b21368. ISBN 978-0-429-06306-0. OCLC  946786108. Una permutación (por ejemplo, de los nombres de varias personas) puede considerarse como el traslado de los nombres o de las personas. El punto de vista del alias considera la permutación como la asignación de un nuevo nombre o alias a cada persona (del latín alias = de otra manera). Alternativamente, desde el punto de vista de la coartada, trasladamos a las personas a los lugares correspondientes a sus nuevos nombres (del latín alibi = en otro lugar).
5. Brualdi 2006, pág. 19
6. Najnudel y Nikeghbali 2013, pág. 4

• Brualdi, Richard A. (2006). Clases de matrices combinatorias . Enciclopedia de matemáticas y sus aplicaciones. Vol. 108. Cambridge: Cambridge University Press . ISBN 0-521-86565-4.Zbl 1106.05001  .
• Najnudel, Joseph; Nikeghbali, Ashkan (2013) [2010], "La distribución de valores propios de matrices de permutación aleatorias", Annales de l'Institut Fourier , 63 (3): 773–838, arXiv : 1005.0402 , Bibcode :2010arXiv1005.0402N