¿Puedes permutar completamente los elementos de una matriz aplicando matrices de permutación?

Question

Supongamos que tengo un $n\times n$ matriz $A$ . ¿Puedo, utilizando sólo la pre y post multiplicación por matrices de permutación, permutar todos los elementos de $A$ ? Es decir, no debería haber condiciones vinculantes, como $a_{11}$ siempre estará a la izquierda de $a_{n1}$ etc.

Esto parece ser intuitivamente obvio. Lo que creo es que puedo escribir la matriz como un $n^2$ -Entonces puedo permutar todas las entradas multiplicándolas por una matriz de permutación adecuada, y luego volver a formar una matriz con el vector permutado.

Answer 1

Por lo general, no es posible hacerlo.

Para un ejemplo concreto, sabemos que no pueden existir matrices de permutación $P,Q$ tal que $$ P\pmatrix{1&2\\2&1}Q = \pmatrix{2&1\\2&1} $$ Si tal $P$ y $Q$ existía, entonces ambas matrices tendrían necesariamente el mismo rango.

Answer 2

Permítanme añadir un argumento más:

Para $n \ge 2$ :

Supongamos que las entradas del $n \times n$ matriz $A$ son todos distintos. Entonces hay $(n^2)!$ permutaciones distintas de $A$ .

Hay $n!$ Permutaciones de filas de $A$ (generado por la premultiplicación por varias matrices de permutación), y $n!$ col-permutaciones de $A$ (generado por la postmultiplicación por matrices de permutación). Si consideramos todo expresiones de la forma $$ RAC $$ donde $R$ y $C$ cada rango de forma independiente sobre todos los $n!$ matrices de permutación, obtenemos como máximo $(n!)^2$ posibles resultados. Pero para $n > 1$ tenemos \begin{align} (n!)^2 &= [ n \cdot (n-1) \cdots 2 \cdot 1 ] [ n \cdot (n-1) \cdots 2 \cdot 1 ] \\ &< [ 2n \cdot (2n-1) \cdots (n+2) \cdot (n+1) ] [ n \cdot (n-1) \cdots 2 \cdot 1 ] \\ &= (2n)! \\ &\le (n^2)! \end{align} porque $2n \le n^2$ para $n \ge 2$ y el factorial es una función creciente sobre los enteros positivos. Por lo tanto, el número de resultados posibles de aplicar permutaciones de filas y coles a $A$ es menor que el número de permutaciones posibles de los elementos de $A$ . Por lo tanto, hay alguna permutación de $A$ que no aparece en nuestra lista de todos los $RAC$ matrices.

Por cierto, para terminar: para $1 \times 1$ matrices, la respuesta es "sí, todas las permutaciones pueden, de hecho, realizarse mediante permutaciones de filas y columnas". Sospecho que lo sabías. :)

Answer 3

Dados dos elementos $a_1$ y $a_2$ las propiedades " $a_1$ y $a_2$ están en diferentes filas" y " $a_1$ y $a_2$ están en columnas diferentes" se conservan con cualquier permutación. Prueba:

Una permutación de columna no afectará a la fila en la que se encuentre algo. Una permutación de fila tiene que enviar una fila entera a la misma fila, así que si empiezan en la misma fila, terminan en la misma fila. Las permutaciones son invertibles, así que si no pueden llevar dos elementos de la misma fila a filas diferentes, tampoco pueden llevar elementos de filas diferentes a la misma fila.

Un argumento análogo es válido para estar en las mismas o diferentes columnas.

Así, una permutación de filas y columnas se caracteriza completamente por lo que hace a una diagonal; para saber a dónde envía un elemento arbitrario, basta con tomar la fila a la que se envió su fila y la columna a la que se envió su columna.

Answer 4

Algunos usuarios de MSE son muy sensibles a la palabra "obvio", pero creo que es descaradamente obvio que la respuesta a su pregunta es "no" en general. La razón es sencilla: al multiplicar por la izquierda (por la derecha) $A$ por una matriz de permutación, estás permutando cada fila (columna) de $A$ en su conjunto. Por lo tanto, las entradas en la misma fila (columna) de $A$ seguirán alineados en una fila (columna). No se puede romper la alineación de filas o columnas aplicando permutaciones a la izquierda y/o a la derecha a $A$ .

Desde otra perspectiva, si se vectoriza $PAQ$ se convierte en $\operatorname{vec}(PAQ)=(Q^T\otimes P)\operatorname{vec}(A)$ . Mientras que el producto Kronecker $Q^T\otimes P$ es un $n^2\times n^2$ matriz de permutación, está claro que no todos los $n^2\times n^2$ Las matrices de permutación son tensores descomponibles.