Verificando se todos os produtos de um conjunto de matrizes acabam sendo iguais a zero

Estou interessado no seguinte problema: dadas as matrizes inteiras decidem se todo produto infinito dessas matrizes eventualmente é igual à matriz zero.$A_1,A_2, \ldots, A_k$

Isso significa exatamente o que você pensa: diremos que o conjunto de matrizes tem a propriedade de que todos os seus produtos acabam sendo iguais a zero se não existir uma sequência infinita , todos em , de modo que para todos os .i 1 , i 2 , i 3 … { 1 , … , k } A i 1 A i 2 ⋯ A i l ≠ 0 $\{A_1, \ldots, A_k\}$$i_1, i_2, i_3\ldots$$\{1, \ldots, k\}$

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

O problema de decidir se todo produto eventualmente é igual a zero foi estudado antes? É decidível?

Parece que isso pode estar relacionado à mortalidade da matriz, que é indecidível, mas não vejo uma conexão clara.

Sua pergunta é equivalente a gerar uma álgebra nilpotente , que por sua vez é equivalente a cada um dos nilpotentes . Portanto, não é apenas decidível, mas em tempo em que é o expoente da multiplicação de matrizes.A i ˜ O ( n 2 ω ) $A_1, \dotsc, A_k$$A_i$$\tilde O(n^{2 \omega})$$\omega$

Seja a álgebra associativa gerada pelo : ou seja, tome todas as combinações lineares do e todos os seus produtos finitos. é chamado nilpotent se houver algum tal que todo produto de elementos de seja zero.Um i A i A N N $\mathcal{A}$$A_i$$A_i$$\mathcal{A}$$N$$N$$\mathcal{A}$

Primeiro, vamos ver por que sua condição implica que é nilpotente. Isto decorre de Konig Lema (compacidade): cada cadeia de comprimento n sobre o alfabeto { 1 , ... , k } corresponde a um produto de A 1 , ... , A k de comprimento n de uma forma óbvia. Considere a infinita árvore k- arraigada, cujos nós estão naturalmente em correspondência bijetiva com cadeias acima de { 1 , … , k } . Considere a subárvore T$\mathcal{A}$$n$$\{1, \dotsc, k\}$$A_1, \dotsc, A_k$$n$$k$$\{1, \dotsc, k\}$$T$que consiste naqueles nós em que o produto correspondente da é diferente de zero. O Lema de Konig diz que se T é infinito, então ele tem um caminho infinito (violando exatamente sua propriedade), portanto, T é finito. Podemos, então, tomar N ser o comprimento máximo de qualquer cadeia em T . Portanto, sua propriedade implica que A é nilpotente.$A_i$$T$$T$$N$$T$$\mathcal{A}$

O inverso também é verdadeiro, pois cada elemento de é uma combinação linear de produtos de A i .$\mathcal{A}$$A_i$

Em seguida, observe que é uma subalgebra de n × n matrizes e, portanto, é de dimensão finita.$\mathcal{A}$$n \times n$

Finalmente: uma álgebra associativa de dimensão finita na característica zero tem uma base de elementos nilpotentes (pendulares ou não - esta é a parte que contradiz a resposta de Yuval) se for nilpotente (veja, por exemplo, aqui ).

Assim, para resolver o problema, encontrar uma base para a álgebra associativa gerado pelo (pela versão linear-álgebra de procura em largura) e verificar que cada matriz na base é nilpotent. O limite superior ˜ O ( n 2 ω ) vem da solução de um sistema de equações lineares em n 2 variáveis ​​na busca pela primeira vez. Como dim A ≤ n 2, o BFS não pode durar muito, e como essas são n × n matrizes para verificar se uma matriz A é nilpotente, é necessário apenas verificar se A n$A_i$$\tilde O(n^{2\omega})$$n^2$$\dim \mathcal{A} \leq n^2$$n \times n$$A$ .$A^n = 0$

Eu obtive um algoritmo poli-tempo para esse problema (problema bastante trivial), ou seja, para verificar se o raio espectral da junta (JSR) é zero ou não, em 1995: http://en.wikipedia.org/wiki/Joint_spectral_radius

A história por trás do algoritmo é mais ou menos a seguinte: Blondel e Tsitsiklis afirmaram erroneamente que para matrizes booleanas verificando se JSR <1 é NP-HARD. Para qualquer conjunto de matrizes inteiras, o JSR é igual a zero ou maior ou igual a 1. Portanto, o exemplo de contador para a declaração deles foi o meu algoritmo (veja as erratas no artigo). A principal moral: consulte a Wikipedia primeiro!

A pergunta que você está fazendo é exatamente equivalente a decidir se o raio espectral da junta (JSR) do conjunto de matrizes é estritamente menor que um. A decidibilidade dessa questão permanece em aberto há algum tempo. (Na teoria do controle, isso é equivalente à decidibilidade da estabilidade de sistemas lineares comutados sob comutação arbitrária.)

Sabe-se que a seguinte variante de sua pergunta é indecidível: Dado um conjunto finito de matrizes quadradas, decida se todos os produtos permanecem delimitados; veja aqui .

A indecisão do acima exposto permanece válida mesmo se você tiver apenas 2 matrizes de tamanho 47x47: veja aqui .

Na linguagem JSR, a questão do teste "é JSR ?" é indecidível (consulte as referências acima), mas a decidibilidade do teste "é JSR < 1 ?" está aberto. A última pergunta está relacionada à chamada "conjectura racional da finitude": se a conjectura racional da finitude é verdadeira, então a pergunta que você está fazendo é decidível.$\le 1$$< 1$

Finalmente, a menos que P = NP, o JSR não seja aproximado em tempo polinomial (no sentido preciso definido neste artigo ).

Como resultado, uma das respostas acima, que afirma que um algoritmo eficiente deve ser falso.

No lado positivo, existem vários algoritmos (por exemplo, baseados em programação semidefinida) para aproximar o JSR. Os diferentes algoritmos vêm com diferentes garantias de desempenho. Veja, por exemplo, o seguinte (sem vergonha, por mim e pelos meus colegas - mas veja também as referências aqui ).

Em vários casos especiais, a pergunta que você está fazendo é um tempo polinomial decidível. Por exemplo, quando as matrizes são simétricas, ou classificam uma, ou se comutam.

Finalmente, um ótimo livro sobre o assunto é o seguinte .

Editar: infelizmente esta resposta está incorreta. O erro é destacado abaixo. O argumento funciona se nos for permitido transpor as matrizes.

Começamos provando um lema.

Lema. Deixe ser um n × n matriz e deixar que N seja o n x n matriz com aqueles na diagonal secundário. Se A n t e N t A são nilpotentes para todos os t ≥ 0, então A = 0 . Conclusão correta: A é triangular superior com zeros na diagonal. (A conclusão original é recuperada se também nos é permitido multiplicar por potências de transposição de N. )$A$$n\times n$$N$$n\times n$$AN^t$$N^tA$$t \geq 0$$A = 0$$A$$N$

Prova. Suponha, por exemplo, que e escreva A = ( a b c d e f g h i )$n = 3$ Começamos calculando A N 2 : A N 2 = ( 0 0 a 0 0 d 0 0 g ) . Essa matriz está na forma triangular e, portanto, se A N 2 é nilpotente, então g = 0 . Continue com A N 1 : A N 1 = (

$$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}.$$ $AN^2$ $$AN^2 = \begin{pmatrix} 0 & 0 & a \\ 0 & 0 & d \\ 0 & 0 & g \end{pmatrix}.$$ $AN^2$$g = 0$$AN^1$ Novamente, a matriz é na forma triangular, e por isso, seumaN1é então nilpotentesd=h=0. Continuando, AN0=( a b c 0 e f 0 0 i ). Como antes, concluímos quea= $$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}.$$ $AN^1$$d = h = 0$ $$AN^0 = \begin{pmatrix} a & b & c \\ 0 & e & f \\ 0 & 0 & i \end{pmatrix}.$$ e, portanto, A é triangular superior com zeros na diagonal.$a = e = i = 0$$A$

Se considerarmos agora , concluímos que A é triangular inferior com zeros na diagonal. Na verdade, nós não temos nada de novo a partir considerando N t A . Portanto A = 0 . $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$

Resumindo, a propriedade P mantém-se se todas as matrizes forem nilpotentes e todas elas comutarem.