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$ .
1 votos
Sólo una idea, pero $(AX)^2=A A^T$ . Si puedes calcular las raíces cuadradas de $A A^T$ se puede reducir la ecuación a $AX=\sqrt{A A^T}$ . Una forma de obtener la raíz cuadrada de $A A^T$ es ponerlo en la forma normal de Jordan como $(M D^{1/2} M^{-1})^2=M D M^{-1}$ .
1 votos
@abnry Me gusta esto. Da todas las soluciones posibles (como máximo $2^n$ para los casos no degenerados) de forma limpia y comprensible y además admite una complejidad temporal subfactorial en el peor de los casos. Si quieres escribir esto como respuesta, lo aceptaré.