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. $A_1,A_2, \ldots, A_k$

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 , todo en , de modo que para todo . $\{A_1, \ldots, A_k\}$ $i_1, i_2, i_3\ldots$ $\{1, \ldots, k\}$

A_{i_{1}} A_{i_{2}} \dots A_{i_{l}} \neq 0

$A_{i_1} A_{i_2} \cdots A_{i_l} \neq 0$

l

$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.

linear-algebra decidability 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

$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

. ¿Mortal? Sí porque

. ¿Cada producto es igual a cero? No: no es el producto

. Por otro lado, si

entonces tienes una secuencia que es mortal y cada producto es cero.

1

$1$

A_{0} = 0, A_{1} = 1

$A_0 = 0, A_1=1$

A_{0} = 0

$A_0 = 0$

1 \cdot 1 \cdot 1 \dots

$1 \cdot 1 \cdot 1 \cdots$

A_{0} = 0, A_{1} = 0

$A_0=0,A_1=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

es nilpotente, entonces es fácil ver que

donde

es la dimensión de

por lo que presumiblemente podría resolverlo cuadrando el

la matriz

veces. No tengo idea si esto es lo mejor que puedes hacer.

k = 1

$k=1$

A

$A$

A^{n} = 0

$A^n = 0$

n

$n$

A

$A$

\log n

$\log n$

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

17

Su pregunta es equivalente a si generan un álgebra nilpotente ~~, que a su vez es equivalente a que cada uno de los~~ ~~sea nilpotente~~ . Por lo tanto, no solo es decidible, sino que en tiempo donde es el exponente de la multiplicación de matrices. $A_1, \dotsc, A_k$ ~~$A_i$~~ $\tilde O(n^{2 \omega})$ $\omega$

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

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

Lo contrario también es cierto, ya que cada elemento de es una combinación lineal de productos de . $\mathcal{A}$ $A_i$

A continuación, tenga en cuenta que es un subálgebra de matrices y, por lo tanto, es de dimensión finita. $\mathcal{A}$ $n \times 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 proviene de la resolución de un sistema de ecuaciones lineales en variables en la búsqueda de amplitud. Como el BFS no puede durar mucho tiempo, y debido a que estas son matrices para verificar si una matriz es nula, uno solo necesita verificar que $A_i$ $\tilde O(n^{2\omega})$ $n^2$ $\dim \mathcal{A} \leq n^2$ $n \times n$ $A$ . $A^n = 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}_{ω}

$\text{AC}_\omega$

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

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

(o sobre

o

).

O (n^{2 ω})

$O(n^{2\omega})$

ω

$\omega$

Q

$\mathbb{Q}$

Q^{n^{2}}

$\mathbb{Q}^{n^2}$

R

$\mathbb{R}$

C

$\mathbb{C}$

Joshua Grochow

1

Se empieza con una base

de

. Ahora se intenta encontrar las matrices

y

tal que

o

no está en el lapso de

. Si tiene éxito, agregue el producto a

y continúe. De lo contrario, la multiplicación de cualquier matriz en el lapso de

por cualquier producto finito de matrices en

siempre termina en el lapso de

. Como la dimensión del álgebra está limitada, el proceso termina (en un máximo de

pasos).

B

$\mathcal{B}$

A

$\mathcal{A}$

A \in A

$A \in \mathcal{A}$

B \in B

$B \in \mathcal{B}$

A B

$AB$

B A

$BA$

B

$\mathcal{B}$

B

$\mathcal{B}$

B

$\mathcal{B}$

A

$\mathcal{A}$

B

$\mathcal{B}$

n^{2}

$n^2$

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 ?" 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. $\le 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

n

$n$

k^{n}

$k^n$

X_{0} = I, X_{j} = \sum_{i = 1}^{k} A_{i}^{T} X_{j - 1} A_{i}

$X_0=I,\ X_j=\sum_{i=1}^k A_i^TX_{j-1}A_i$

X_{n} = \sum_{A product of length n} A^{T} A

$X_n=\sum_{A\mbox{ product of length n}}A^TA$

k n

$kn$

n

$n$

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.

$A$ $n\times n$ $N$ $n\times n$ $AN^t$ $N^tA$ $t \geq 0$ $A = 0$ $A$ $N$

$n = 3$

A = (\begin{matrix} a & b & c \\ d & e & f \\ g & h & i \end{matrix}), N = (\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix}) .

$A = \begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix}, \quad N = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix}.$

A N^{2}

$AN^2$

A N^{2} = (\begin{matrix} 0 & 0 & a \\ 0 & 0 & d \\ 0 & 0 & g \end{matrix}) .

$AN^2 = \begin{pmatrix} 0 & 0 & a \\ 0 & 0 & d \\ 0 & 0 & g \end{pmatrix}.$

A N^{2}

$AN^2$

g = 0

$g = 0$

A N^{1}

$AN^1$

A N^{1} = (\begin{matrix} 0 & a & b \\ 0 & d & e \\ 0 & g & h \end{matrix}) = (\begin{matrix} 0 & a & b \\ 0 & d & e \\ 0 & 0 & h \end{matrix}) .

$AN^1 = \begin{pmatrix} 0 & a & b \\ 0 & d & e \\ 0 & g & h \end{pmatrix} = \begin{pmatrix} 0 & a & b \\ 0 & d & e \\ 0 & 0 & h \end{pmatrix}.$

A N^{1}

$AN^1$

d = h = 0

$d = h = 0$

A N^{0} = (\begin{matrix} a & b & c \\ 0 & e & f \\ 0 & 0 & i \end{matrix}) .

$AN^0 = \begin{pmatrix} a & b & c \\ 0 & e & f \\ 0 & 0 & i \end{pmatrix}.$

a = e = i = 0

$a = e = i = 0$

A

$A$

$N^2A,N^1A,N^0A$ $A$ $N^tA$ $A = 0$ $\square$

$A_1,\ldots,A_k$ $i_1,\ldots \in [k]$ $A_{i_1} \cdots A_{i_m} = 0$ $m$ $A_i$ $A_1 A_2 \neq A_2 A_1$ $A_1$ $V_1 \oplus \cdots \oplus V_t$ $V_i$ $A_1 A_2 \neq A_2 A_1$ $\dim V_i > 1$ $0$ $V_i$ $A_1 = N$ $A_2 \neq 0$ $t \geq 0$ $A_2 A_1^t$ $A_1^t A_2$

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

Yuval Filmus
fuente

44

N^{2} A

$N^2 A$

g = 0

$g = 0$

N^{1} A

$N^1 A$

d = h = 0

$d = h = 0$

N^{0} A

$N^0 A$

a = e = i = 0

$a=e=i=0$

A

$A$

A

$A$

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

A_{0} = (\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix}), A_{1} = (\begin{matrix} 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix})

$A_0 = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix}, A_1 = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}$

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

Respuestas: