¿Cómo encontrar todas las soluciones de la ecuación matricial $XAX=A^T$ ?

Question

Hace poco me pidieron que resolviera un problema en una entrevista de programación que implicaba cuadros de palabras y al reflexionar un poco más me di cuenta de que se podía reformular como una pregunta de álgebra lineal. Como mi solución tiene una complejidad de tiempo en el peor de los casos de $O(n!)$ si $n$ es la anchura de $A$ Por curiosidad personal, estoy tratando de encontrar una solución mejor, medida por la complejidad de tiempo en el peor de los casos.

Dado un $n$ por $n$ matriz cuadrada $A$ sobre los reales con $n\geq 2$ ¿hay un $n$ por $n$ matriz de permutación $X$ Satisfaciendo a $$XA=(XA)^T?$$

Desde $(XA)^T=A^TX^T$ y $X$ es una matriz de permutación, tenemos $X^T=X^{-1}$ Por lo tanto, esto equivale a preguntar si hay soluciones para $$XAX=A^T$$ que son matrices de permutación. Ingenuamente, esperaba que hubiera una solución única, pero las técnicas numéricas indican fuertemente una gran variedad de soluciones, incluso cuando existe una permutación satisfactoria.

Por desgracia, no parece que las soluciones formen un subespacio lineal. Por ejemplo, si $X$ es una solución, entonces $(aX)A(aX)=a^2A^T$ para cualquier $a$ , por lo que la mayoría de los múltiplos de $X$ no son soluciones para la mayoría de las matrices $A$ . Existen problemas similares para las sumas de las soluciones. Teniendo esto en cuenta, no sé muy bien qué método se puede utilizar para enumerar las soluciones. Si no forman un subespacio lineal, no podemos simplemente enumerar una base.

Cualquier solución parcial, teorema, indicación en la dirección correcta o problemas relacionados sería de gran ayuda. No estoy familiarizado con lo que parece ser un no lineal ecuación matricial (si esa es la terminología correcta).

Actualización Esto parece ser un caso especial de algo llamado ecuación algebraica de Riccati como se indica en otra pregunta . Las técnicas que he encontrado hasta ahora hacen hincapié en uno de los dos enfoques:

• Algoritmos para encontrar cualquier solución a partir de una conjetura inicial dada.
• Algoritmos para encontrar la única solución estabilizadora, si es que existe.

Dada la base teórica de control de estos enfoques, suelen suponer que $A^T$ es simétrica. En mi caso, si $A^T$ fueran simétricos podría simplemente tomar $X$ que sea la identidad y se haga, y esa suposición simplifica demasiado el problema. Además, esas soluciones no parecen tener una forma limpia de enumerar todas las soluciones, lo que impide comprobar si alguna resulta ser una matriz de permutación. ¿Alguien tiene más consejos desde el punto de vista de la ecuación de Riccati?

Me gustaría añadir que, estrictamente hablando, se puede responder a la pregunta en tiempo finito simplemente enumerando todas las matrices de permutación del tamaño adecuado y comprobando si satisfacen $XA=(XA)^T$ . Por alguna razón que me cuesta describir, creo que esto no capta el espíritu de la pregunta.

Actualización @GCab señala que $A$ necesitaría una estructura muy peculiar para $X$ para ser una matriz de permutación. Así es, y $A$ tendría que ser simétrica en alguna permutación de filas o columnas. Esto nos da algunas ideas. Si $X$ es cualquier matriz de permutación, entonces $$(XAX)_{ij}=A_{ji}=(A^T)_{ij}$$ para cualquier $i$ , $j$ para que $X_{ij}=1$ y esto no se cumple cuando $X_{ij}=0$ . En otras palabras, los elementos de $A$ vienen en pares, excepto posiblemente la diagonal principal de $XA$ . De este modo, se pueden descartar muchas permutaciones posibles, ya que cualquier elemento que aparezca una sola vez en $A^T$ debe dar la ubicación de un $1$ en $X$ .

Hay muchos otros trucos combinatorios de este tipo que pueden mejorar mucho el tiempo medio de ejecución. Del mismo modo, se puede observar que para una permutación $X$ para que exista como solución, debe existir una biyección $f$ entre las filas y columnas de $A$ para que si $r$ es una fila de $A$ entonces el recuento de cada elemento de $r$ es el mismo que su cuenta en $f(r)$ . Esta heurística tiene el potencial de clasificar fácilmente una elección de $A$ como no tener una solución satisfactoria, pero todavía podría tomar una enorme cantidad de tiempo para confirmar que un determinado $A$ tiene una satisfactoria $X$ .

Answer 1

Si su ecuación es resoluble, entonces necesariamente hay una solución para $(AX)^2=A A^T$ . (Obsérvese que sólo existe una equivalencia directa si $A$ es invertible).

Así, si podemos calcular todas las matrices $B_i$ tal que $B_i^2 = AA^T$ entonces debemos buscar soluciones para $AX = B_i$ . Si $A A^T = N D N^{-1}$ es una descomposición normal de Jordan, entonces $B_i = N D_i^{1/2} N^{-1}$ es una raíz cuadrada donde $D_i^{1/2}$ es una raíz cuadrada de $D$ . En el caso de $D$ diagonal, hay $2^n$ posibles raíces cuadradas. No estoy seguro de la teoría que hay detrás de la búsqueda de raíces cuadradas de matrices. Puede que estas sean todas las raíces cuadradas pero no lo sé.

Sin embargo, en nuestro caso podemos utilizar el hecho de que $A A^T$ es semidefinido positivo, lo que simplifica mucho. En este caso, $A A^T = N D N^{-1}$ donde $D$ es diagonal. Se sabe que en este caso hay una única raíz cuadrada semidefinida positiva. No sé si todas las raíces cuadradas se generan a partir de ésta.

Si la restricción de $X$ es que es una matriz de permutación, entonces debería ser fácil determinar si $AX=B_i$ tiene una solución. Una vez que encontramos una solución, debemos comprobar que satisface nuestra ecuación original $XAX=A^T$ si $A$ no es invertible.

Answer 2

Si $\bf X$ es una matriz de permutación, entonces su acción sobre una matriz $\bf A$ es permutar (intercambiar) las filas del mismo si se multiplica por la izquierda ( $\bf X \bf A$ ), o sus columnas cuando se multiplican por la derecha ( $\bf A \bf X$ ).

Así que no se puede obtener de intercambiar las filas con las columnas ( ${\bf A}^T$ ), a menos que la matriz tenga una estructura peculiar.

Empecemos con $n=2$ . Además de la identidad, el otro PM es la matriz de intercambio $${\bf J} = \left( {\matrix{ 0 & 1 \cr 1 & 0 \cr } } \right)$$

Y $$\eqalign{ & {\bf J}\,{\bf A} = \left( {\matrix{ 0 & 1 \cr 1 & 0 \cr } } \right)\left( {\matrix{ {a_{\,1,\,1} } & {a_{\,1,\,2} } \cr {a_{\,2,\,1} } & {a_{\,2,\,2} } \cr } } \right) = \left( {\matrix{ {a_{\,2,\,1} } & {a_{\,2,\,2} } \cr {a_{\,1,\,1} } & {a_{\,1,\,2} } \cr } } \right) \cr & {\bf J}\,{\bf A}\,{\bf J}\, = \left( {\matrix{ {a_{\,2,\,1} } & {a_{\,2,\,2} } \cr {a_{\,1,\,1} } & {a_{\,1,\,2} } \cr } } \right)\left( {\matrix{ 0 & 1 \cr 1 & 0 \cr } } \right) = \left( {\matrix{ {a_{\,2,\,2} } & {a_{\,2,\,1} } \cr {a_{\,1,\,2} } & {a_{\,1,\,1} } \cr } } \right)\quad \leftrightarrow \quad {\bf A}^{\,T} = \left( {\matrix{ {a_{\,1,\,1} } & {a_{\,2,\,1} } \cr {a_{\,1,\,2} } & {a_{\,2,\,2} } \cr } } \right) \cr}$$

lo que significa que $\bf A$ tendrá una diagonal constante.

Toda permutación puede expresarse mediante el producto de Transposiciones y en particular por el producto de Transposiciones adyacentes .
Una matriz de transposición adyacente consiste en una matriz de identidad en la que a $2 \times 2$ bloque diagonal se sustituye por $\bf J$ .

Entonces supongo que puedes continuar desde aquí.

Answer 3

Dejemos que $A\in M_n(\mathbb{R})$ . ¿Existe una matriz de permutación $X$ s.t. $XA$ ¿es simétrico?

$XA$ resulta en una permutación de las filas de $A$ entonces necesariamente, $A=[a_{i,j}]$ tiene como máximo $n(n+1)/2$ entradas distintas $a_{i,j}$ . En consecuencia, si $A$ se elige al azar, entonces no hay soluciones. Más concretamente

Existe una solución de permutación si $A=PS$ donde $P$ es una permutación y $S$ es simétrica.

Método 1. (El peor). Consideramos el sistema algebraico

$(*)$ $XA$ es simétrica, $X^TX=I_n$ . En general, este sistema tiene $2^n$ soluciones. Queda por ver si, entre las soluciones, hay permutaciones; por desgracia, es difícil encontrar todas las soluciones (incluso aproximaciones) y es prácticamente imposible cuando $n\geq 10$ .

Método 2. Podemos probar sucesivamente todas las permutaciones. Cada prueba es muy rápida, por lo que es factible cuando (por ejemplo) $n=10$ y quizás hasta $n=20$ ( $20!\approx 2.10^{18}$ ). Pero más allá, eso es imposible;

Método 3. Hay un caso fácil. Suponemos que $A$ tiene exactamente $n$ entradas que aparecen exactamente una vez.

Por supuesto, estas entradas son los elementos de la diagonal de $S$ (si hay soluciones). En la fila del índice $i$ debe existir exactamente una entrada de este tipo: $a_{i,k_i}$ . Además, la secuencia $k_1,\cdots,k_n$ debe ser una permutación $\sigma$ de $1,\cdots,n$ . Finalmente, si existe una solución, entonces es única y es igual a $X=U^T$ , donde $U$ es la matriz de permutación asociada a $\sigma$ .

Por supuesto, este método tiene una complejidad muy pequeña; sólo necesita comparaciones e intercambios.