Comprobando si todos los productos de un conjunto de matrices eventualmente son iguales a cero

19

Estoy interesado en el siguiente problema: dadas matrices enteras decide si cada producto infinito de estas matrices finalmente es igual a la matriz cero.A1,A2,,Ak

Esto significa exactamente lo que crees que hace: diremos que el conjunto de matrices tiene la propiedad de que todos sus productos eventualmente son iguales a cero si no existe una secuencia infinita i 1 , i 2 , i 3 ... , todo en { 1 , ... , k } , de modo que A i 1 A i 2A i l0 para todo l .{A1,,Ak}i1,i2,i3{1,,k}

Ai1Ai2Ail0
l

¿Se ha estudiado antes el problema de decidir si cada producto es igual a cero? ¿Es decidible?

Parece que podría estar relacionado con la mortalidad matricial, que es indecidible, pero no veo una conexión clara.

Robinson
fuente
Necesita algún tipo de propiedad de convergencia en el conjunto de matrices para garantizar que se define el producto infinito.
András Salamon
¿Estás operando en un campo finito o enteros con un crecimiento ilimitado? El caso = 1 es interesante por derecho propio. Usando enteros de -100 a 100 en una matriz de 5x5, ¿cuál es la potencia más alta que puede obtener antes de que se ponga a cero? k
Chad Brewbaker
2
@YuvalFilmus: creo que es diferente de la mortalidad. Deje que las dimensiones de las matrices sean , de modo que solo tengamos números, y suponga que A 0 = 0 , A 1 = 1 . ¿Mortal? Sí porque A 0 = 0 . ¿Cada producto es igual a cero? No: no es el producto 1 1 1 . Por otro lado, si A 0 = 0 , A 1 = 0, entonces tienes una secuencia que es mortal y cada producto es cero. 1A0=0,A1=1A0=0111A0=0,A1=0
Robinson
1
@ChadBrewbaker: estaba pensando que las entradas de las matrices son solo enteros. Supongo que es interesante desde el punto de vista de: ¿cuántas operaciones necesitas para comprobar que la matriz es nilpotente? Tenga en cuenta que si A es nilpotente, entonces es fácil ver que A n = 0 donde n es la dimensión de A, por lo que presumiblemente podría resolverlo cuadrando el registro de la matriz n veces. No tengo idea si esto es lo mejor que puedes hacer. k=1AAn=0nAlogn
Robinson
1
Curiosamente, esto solo en: arxiv.org/abs/1306.0729 . En lugar de preguntar si todos los productos son eventualmente cero, preguntan si algún producto es finalmente positivo. Muestran que el problema es NP-hard (o al menos eso es lo que deduzco del resumen).
Joshua Grochow

Respuestas:

17

Su pregunta es equivalente a si generan un álgebra nilpotente , que a su vez es equivalente a que cada uno de los A i sea ​​nilpotente . Por lo tanto, no solo es decidible, sino que en ˜ O ( n 2 ω ) tiempo donde ω es el exponente de la multiplicación de matrices.A1,,AkAiO~(n2ω)ω

Sea el álgebra asociativa generada por A i : es decir, tome todas las combinaciones lineales de A i y todos sus productos finitos. A se llama nilpotente si hay algo de N tal que cada producto de N elementos de A sea ​​cero.AAiAiANNA

Primero, veamos por qué su condición implica que es nilpotente. Esto se desprende del Lema de Konig (compacidad): cada cadena de longitud n sobre el alfabeto { 1 , ... , k } corresponde a un producto de A 1 , ... , A k de longitud n de una manera obvia. Considere el árbol con raíces k -ary infinito , cuyos nodos están naturalmente en correspondencia biyectiva con cadenas sobre { 1 , ... , k } . Considere el subárbol TAn{1,,k}A1,,Aknk{1,,k}Tconsistente en aquellos nodos donde el producto correspondiente de no es cero. El lema de Konig dice que si T es infinito, entonces tiene un camino infinito (violando exactamente su propiedad), por lo tanto, T es finito. Entonces podemos tomar N a ser la longitud máxima de cualquier cadena en T . Entonces su propiedad implica que A es nilpotente.AiTTNTA

Lo contrario también es cierto, ya que cada elemento de es una combinación lineal de productos de A i .AAi

A continuación, tenga en cuenta que es un subálgebra de n × n matrices y, por lo tanto, es de dimensión finita.An×n

Finalmente: un álgebra asociativa de dimensión finita en la característica cero tiene una base de elementos nilpotentes (conmutación o no, esta es la parte que contradice la respuesta de Yuval) si es nilpotente (ver, por ejemplo, aquí ).

Por lo tanto, para resolver su problema, encuentre una base para el álgebra asociativa generada por el (por la versión de álgebra lineal de la búsqueda de amplitud primero) y verifique que cada matriz en la base sea nilpotente. El límite superior ˜ O ( n 2 ω ) proviene de la resolución de un sistema de ecuaciones lineales en n 2 variables en la búsqueda de amplitud. Como tenue An 2, el BFS no puede durar mucho tiempo, y debido a que estas son n × n matrices para verificar si una matriz A es nula, uno solo necesita verificar que A n =AiO~(n2ω)n2dimAn2n×nA .An=0

Joshua Grochow
fuente
2
¿Crees que hay una manera de mostrar esto sin usar ningún principio de elección (incluso uno tan débil como el Lemma de König, que es equivalente a )? ACω
András Salamon
2
@Andras: Diría que es una pregunta para Chris Conidis. Ha estudiado preguntas como esa en matemática inversa (computable). Le preguntaré y lo señalaré aquí.
Joshua Grochow
1
@robinson: 1) Sí, el problema es decidible, de hecho en el tiempo donde ω es el exponente de la multiplicación de matrices. Esto viene de resolver sistemas de ecuaciones lineales sobre Q cuando se realiza la búsqueda de amplitud de álgebra lineal. 2) Sí, noción de base habitual cuando se ven las matrices como vectores en Q n 2 (o sobre R o C ). O(n2ω)ωQQn2RC
Joshua Grochow
1
Se empieza con una base de A . Ahora se intenta encontrar las matrices A A y B B tal que A B o B A no está en el lapso de B . Si tiene éxito, agregue el producto a B y continúe. De lo contrario, la multiplicación de cualquier matriz en el lapso de B por cualquier producto finito de matrices en A siempre termina en el lapso de B . Como la dimensión del álgebra está limitada, el proceso termina (en un máximo de n 2 pasos). BAAABBABBABBBABn2
Yuval Filmus
1
@robinson: No. Si el álgebra es nilpotente, entonces cada elemento del álgebra es nilpotente. Entonces, si encuentra algún elemento no nilpotente, entonces el álgebra no es nilpotente (y luego hay infinitos productos de sus matrices que nunca son cero).
Joshua Grochow
6

Obtuve un algoritmo de poli-tiempo para este problema (un problema bastante trivial), es decir, para verificar si el radio espectral conjunto (JSR) es cero o no, en 1995: http://en.wikipedia.org/wiki/Joint_spectral_radius

La historia detrás del algoritmo es más o menos la siguiente: Blondel y Tsitsiklis declararon erróneamente que para las matrices booleanas verificar si JSR <1 es NP-HARD. Para cualquier conjunto de matrices enteras, JSR es éter cero o mayor o igual 1. Por lo tanto, el contraejemplo de su declaración fue mi algoritmo (vea la errata de su artículo). La moraleja principal: ¡consulta la Wikipedia primero!

gurvits leonidos
fuente
5

La pregunta que hace es exactamente equivalente a decidir si el radio espectral conjunto (JSR) del conjunto de matrices es estrictamente menor que uno. La capacidad de decisión de esta pregunta ha permanecido abierta desde hace bastante tiempo. (En teoría de control, esto es equivalente a la capacidad de decisión de la estabilidad de los sistemas lineales conmutados bajo conmutación arbitraria).

Se sabe que la siguiente variante de su pregunta es indecidible: dado un conjunto finito de matrices cuadradas, decida si todos los productos permanecen limitados; ver aquí .

La indecidibilidad de lo anterior sigue siendo válida incluso si tiene solo 2 matrices de tamaño 47x47: consulte aquí .

En el lenguaje JSR, la cuestión de probar "¿es JSR ?" es indecidible (ver referencias arriba), pero la capacidad de decisión de la prueba "es JSR < 1 ?" Esta abierto. La última pregunta está relacionada con la llamada "conjetura de la finitud racional": si la conjetura de la finitud racional es verdadera, entonces la pregunta que usted hace es decidible.1<1

Finalmente, a menos que P = NP, el JSR no es aproximable en tiempo polinómico (en el sentido preciso definido en este documento ).

Como resultado, una de las respuestas anteriores que afirma un algoritmo eficiente debe ser falsa.

En el lado positivo, hay varios algoritmos (por ejemplo, basados ​​en programación semidefinida) para aproximar el JSR. Los diferentes algoritmos vienen con diferentes garantías de rendimiento. Vea, por ejemplo, lo siguiente (descaradamente por mí y mis colegas, pero vea también las referencias allí ).

En varios casos especiales, la pregunta que hace es el tiempo polinómico decidible. Por ejemplo, cuando las matrices son simétricas, o de rango uno, o si se conmutan.

Finalmente, un gran libro sobre el tema es el siguiente .

Amir Ali Ahmadi
fuente
Por favor, lea la declaración formal de la pregunta que hice - es no equivale a decidir si el JSR es estrictamente menor que uno. Quizás te engañe el título de la pregunta. En resumen, estoy preguntando acerca de cada producto igual a cero en tiempo finito , en lugar de en un sentido asintótico.
Robinson
2
Entonces la pregunta que haces es mucho más simple. Los siguientes son equivalentes: (i) La condición que define (ii) Todos los productos finitos son nilpotentes (iii) El JSR = 0 (iv) Todos los productos de longitud n son cero (n es la dimensión, esto es independiente del número de matrices k). La última condición obviamente implica capacidad de decisión y, de hecho, puede verificar la condición en tiempo polinómico. Consulte la Sección 2.3.1 del libro de Jungers vinculado al final de mi publicación. Mis disculpas por pensar que te referías a la versión asintótica. (Me engañó la frase "todos los productos finalmente son iguales a cero".)
Amir Ali Ahmadi
En cuyo caso, @AmirAliAhmadi no cubre la respuesta de Joshua Grochow?
Suresh Venkat
2
Me parece que sí, con un algoritmo diferente al que tengo en mente. (Nuevamente, mis disculpas por pensar que la pregunta era "¿todos los productos convergen a cero" (es decir, JSR <1?) Cuya capacidad de decisión es abierta). Sin embargo, existen algunas diferencias con la respuesta de Joshua. (1) En la equivalencia de (i) - (iv) en mi comentario anterior, no creo que deba usarse el Lema de Konig. (2) No entiendo por qué está tomando combinaciones lineales de las matrices. (3) Copio a continuación un algoritmo alternativo simple de la Sección 2.3.1 del libro de Jungers, atribuido allí a Leonid Gurvits.
Amir Ali Ahmadi
44
nknX0=I, Xj=i=1kAiTXj1AiXn=A product of length nATAknn
0

Editar: esta respuesta es desafortunadamente incorrecta. El error se resalta a continuación. El argumento funciona si se nos permite transponer las matrices.

Comenzamos demostrando un lema.

An×nNn×nANtNtAt0A=0AN

n=3

A=(abcdefghi),N=(010001000).
AN2
AN2=(00a00d00g).
AN2g=0AN1
AN1=(0ab0de0gh)=(0ab0de00h).
AN1d=h=0
AN0=(abc0ef00i).
a=e=i=0A

N2A,N1A,N0AANtAA=0

A1,,Aki1,[k]Ai1Aim=0mAiA1A2A2A1A1V1VtViA1A2A2A1dimVi>10ViA1=NA20t0A2A1tA1tA2

Resumiendo, la propiedad P se mantiene si todas las matrices son nulas y todas ellas viajan.

Yuval Filmus
fuente
44
N2Ag=0N1Ad=h=0N0Aa=e=i=0AA
De hecho, esta respuesta no es correcta. Si nadie más lo hace, publicaré un contraejemplo tanto para el lema como para la afirmación final cuando llegue a casa más tarde hoy.
Robinson
55
Como de costumbre, es cuando se reclama algo pero no se prueba que la prueba falla. Oh, bueno ...
Yuval Filmus
1
A0=(010001000),A1=(011000000)