En matemáticas , particularmente en la 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 pre-multiplicar, para formar PA ) o columnas (al post-multiplicar, para formar AP ), de la matriz A .
Definición
Dada una permutación π de m elementos,
representado en forma de dos líneas por
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 , permutar las columnas o permutar las filas, de acuerdo con π . 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 en la otra representación. Este artículo se ocupará principalmente de una de estas representaciones y la otra solo se mencionará cuando exista una diferencia a tener en cuenta.
La matriz de permutación m × m P π = ( p ij ) obtenida permutando las columnas de la matriz identidad I m , es decir, para cada i , p ij = 1 si j = π ( i ) y p ij = 0 en caso contrario, se denominará representación de columna en este artículo. [1] Dado que las entradas en la fila i son todas 0 excepto que aparece un 1 en la columna π ( i ), podemos escribir
dónde , un vector de base estándar , denota un vector de fila de longitud m con 1 en la posición j- ésima y 0 en todas las demás posiciones. [2]
Por ejemplo, la matriz de permutación P π correspondiente a la permutación es
Observe que la j- ésima columna de la matriz identidad I 5 aparece ahora 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 en caso contrario, se denominará representación de fila .
Propiedades
La representación en columna de una matriz de permutación se utiliza en esta sección, excepto cuando se indique lo contrario.
Multiplicar veces un vector de columna g permutará las filas del vector:
El uso repetido de este resultado muestra que si M es una matriz de tamaño apropiado, el producto,es sólo una permutación de las filas de M . Sin embargo, al observar que
para cada k muestra que la permutación de las filas está dada por π −1 . (es la transpuesta de la matriz M. )
Como las matrices de permutación son matrices ortogonales (es decir,), la matriz inversa existe y se puede escribir como
Multiplicar un vector fila h veces permutará las columnas del vector:
Una vez más, la aplicación repetida de este resultado muestra que después de la multiplicación de una matriz M de la matriz de permutación P π , es decir, MP π , los resultados en la permutación de las columnas de M . Note también que
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
Las mismas matrices que actúan sobre los vectores de fila (es decir, después de la multiplicación) se componen de acuerdo con la misma regla
Para ser claros, las fórmulas anteriores usan la notación de prefijo para la composición de permutación, es decir,
Dejar ser la matriz de permutación correspondiente a π en su representación de fila. Las propiedades de esta representación se pueden determinar a partir de las de la representación de columna, ya que En particular,
De esto se sigue que
Similar,
Grupo de matriz
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 }. Ya que hay n ! permutaciones, hay n ! matrices de permutación. Según las fórmulas anteriores, las matrices de permutación n × n forman un grupo bajo la multiplicación de matrices con la matriz de identidad como elemento de identidad .
El mapa S n → A ⊂ GL ( n , Z 2 ) es una representación fiel . Por lo tanto, | A | = n ! .
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 que 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 el casco convexo del conjunto de matrices de permutación. [3]
Propiedades algebraicas lineales
El rastro de una matriz de permutación es el número de puntos fijos de la permutación. Si la permutación tiene puntos fijos, entonces 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 de permutación.
Calcular los valores propios de una matriz de permutación, escribir como producto de ciclos , digamos,. Sean las longitudes correspondientes de estos ciclos, y deja ser el conjunto de soluciones complejas de . La unión de todoss es el conjunto de valores propios de la correspondiente matriz de permutación. La multiplicidad geométrica de cada valor propio es igual al número des que lo contienen. [4]
De la teoría de grupos sabemos que cualquier permutación puede escribirse como producto de transposiciones . Por lo tanto, cualquier matriz de permutación P se factoriza como un producto de matrices elementales de intercambio de filas , cada una de las cuales tiene un determinante -1. Por tanto, el determinante de una matriz de permutación P es solo la firma de la permutación correspondiente.
Ejemplos de
Permutación de filas y columnas
Cuando una matriz de permutación P se multiplica desde la izquierda con una matriz M para hacer PM , permutará las filas de M (aquí los elementos de un vector de columna),
cuando P se multiplica desde la derecha con M para hacer MP permuta la columnas de M (aquí los elementos de un vector de fila):
Las permutaciones de filas y columnas son, por ejemplo, reflexiones (ver más abajo) y permutaciones cíclicas (ver matriz de permutación cíclica ).
reflexiones | ||
---|---|---|
Estos arreglos de matrices son reflejos de los que están directamente arriba. |
Permutación de filas
La matriz de permutación P π correspondiente a la permutación es
Dado un vector g ,
Explicación
Una matriz de permutación siempre tendrá la forma
donde e a i representa el i- ésimo vector base (como una fila) para R j , y donde
es la permutación forma de la matriz de permutación.
Ahora, al realizar la multiplicación de matrices , esencialmente se forma 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 0 , ..., g 5 ) T ,
- e a yo · v = g a yo
Entonces, el producto de la matriz de permutación con el vector v anterior, será un vector en la forma ( g a 1 , g a 2 , ..., g a j ), y que esto es una permutación de v ya que han dicho que la forma de permutación es
Entonces, las matrices de permutación sí permutan el orden de los elementos en los vectores multiplicados por ellos.
Formas restringidas
- Matriz 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 como máximo una entrada en cada diagonal y antidiagonal
Ver también
Referencias
- Brualdi, Richard A. (2006). Clases de matrices combinatorias . Enciclopedia de las matemáticas y sus aplicaciones. 108 . Cambridge: Cambridge University Press . ISBN 0-521-86565-4. Zbl 1106.05001 .
- Joseph, Najnudel; Ashkan, Nikeghbali (2010), The Distribution of Eigenvalues of Randomized Permutation Matrices , arXiv : 1005.0402 , Bibcode : 2010arXiv1005.0402N