Vérifier si tous les produits d'un ensemble de matrices sont finalement égaux à zéro

Je m'intéresse au problème suivant: étant donné les matrices entières décident si chaque produit infini de ces matrices est finalement égal à la matrice zéro.$A_1,A_2, \ldots, A_k$

Cela signifie exactement ce que vous pensez qu'il fait: nous dirons que l'ensemble des matrices a la propriété que tous ses produits finissent par être égaux à zéro s'il n'existe pas de séquence infinie , tous dans , de telle sorte que pour tout .$\{A_1, \ldots, A_k\}${ 1 , … , k } A i 1 A i 2 ⋯ A i l ≠ 0 $i_1, i_2, i_3\ldots$$\{1, \ldots, k\}$

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

Le problème de décider si chaque produit est finalement égal à zéro a-t-il été étudié auparavant? Est-ce décidable?

On dirait que cela pourrait être lié à la mortalité matricielle, qui est indécidable, mais je ne vois pas de lien clair.

Votre question équivaut à savoir si génèrent une algèbre nilpotente , qui à son tour est équivalente à chacun des A i étant nilpotent . Il est donc non seulement décidable, mais en ˜ O ( n 2 ω ) temps où ω est l'exposant de la multiplication matricielle.$A_1, \dotsc, A_k$$A_i$$\tilde O(n^{2 \omega})$$\omega$

Soit l'algèbre associative générée par l' A i : c'est-à-dire prendre toutes les combinaisons linéaires de l' A i et tous ses produits finis. A est appelé nilpotent s'il existe des N tels que chaque produit de N éléments de A est nul.$\mathcal{A}$$A_i$$A_i$$\mathcal{A}$$N$$N$$\mathcal{A}$

Voyons d'abord pourquoi votre condition implique que est nul. Cela découle du lemme de Konig (compacité): chaque chaîne de longueur n sur l'alphabet { 1 , … , k } correspond à un produit de A 1 , … , A k de longueur n de manière évidente. Considérons l' arbre enraciné k -ary infini , dont les nœuds sont naturellement en correspondance bijective avec des chaînes sur { 1 , … , k } . Considérons le sous-arbre $\mathcal{A}$$n$$\{1, \dotsc, k\}$$A_1, \dotsc, A_k$$n$$k$$\{1, \dotsc, k\}$$T$composé des nœuds où le produit correspondant de est différent de zéro. Le lemme de Konig dit que si T est infini, alors il a un chemin infini (violant exactement votre propriété), donc T est fini. On peut alors prendre N être la longueur maximale d'une chaîne en T . Votre propriété implique donc que A est nul.$A_i$$T$$T$$N$$T$$\mathcal{A}$

L'inverse est également vrai, car chaque élément de est une combinaison linéaire de produits de A i .$\mathcal{A}$$A_i$

Ensuite, notez que est une sous-algèbre de n × n matrices, et est donc de dimension finie.$\mathcal{A}$$n \times n$

Enfin: une algèbre associative de dimension finie dans le zéro caractéristique a une base d'éléments nilpotents (navettes ou non - c'est la partie qui contredit la réponse de Yuval) si elle est nilpotente (voir, par exemple, ici ).

Ainsi, pour résoudre votre problème, trouvez une base pour l'algèbre associative générée par la (par la version d'algèbre linéaire de la recherche en largeur d'abord) et vérifiez que chaque matrice de la base est nilpotente. La borne supérieure ˜ O ( n 2 ω ) provient de la résolution d'un système d'équations linéaires en n 2 variables dans la recherche en largeur d'abord. Comme dim A ≤ n 2, le BFS ne peut pas durer très longtemps, et parce que ce sont n × n matrices pour vérifier si une matrice A est nilpotente, il suffit de vérifier que A n$A_i$$\tilde O(n^{2\omega})$$n^2$$\dim \mathcal{A} \leq n^2$$n \times n$$A$ .$A^n = 0$

J'ai obtenu un algorithme poly-temps pour ce problème (problème assez trivial), c'est-à-dire pour vérifier si le rayon spectral conjoint (JSR) est nul ou non, en 1995: http://en.wikipedia.org/wiki/Joint_spectral_radius

L'histoire derrière l'algorithme est à peu près la suivante: Blondel et Tsitsiklis ont déclaré à tort que pour les matrices booléennes, vérifier si JSR <1 est NP-HARD. Pour tout ensemble de matrices entières, JSR est un éther nul ou supérieur ou égal à 1. Ainsi, le contre-exemple de leur énoncé était mon algorithme (voir les errata de leur article). La morale principale: consultez d'abord Wikipédia!

La question que vous posez équivaut exactement à décider si le rayon spectral conjoint (JSR) de l'ensemble de matrices est strictement inférieur à un. La décidabilité de cette question est restée ouverte depuis un certain temps maintenant. (Dans la théorie du contrôle, cela équivaut à la décidabilité de la stabilité des systèmes linéaires commutés sous commutation arbitraire.)

La variante suivante de votre question est connue pour être indécidable: étant donné un ensemble fini de matrices carrées, décidez si tous les produits restent bornés; voir ici .

L'indécidabilité de ce qui précède reste valable même si vous n'avez que 2 matrices de taille 47x47: voir ici .

Dans le langage JSR, la question du test "est JSR ?" est indécidable (voir références ci-dessus), mais la décidabilité des tests "est JSR < 1 ?" est ouvert. Cette dernière question est liée à la soi-disant "conjecture de finitude rationnelle": Si la conjecture de finitude rationnelle est vraie, alors la question que vous posez est décidable.$\le 1$$< 1$

Enfin, à moins que P = NP, le JSR ne soit pas approximable en temps polynomial (au sens précis défini dans cet article ).

Par conséquent, l'une des réponses ci-dessus qui prétend qu'un algorithme efficace doit être fausse.

Du côté positif, il existe plusieurs algorithmes (par exemple basés sur une programmation semi-définie) pour approximer le JSR. Les différents algorithmes sont livrés avec différentes garanties de performances. Voir par exemple les éléments suivants (sans vergogne par moi - même et mes collègues - mais aussi voir les références qui y sont ).

Dans plusieurs cas particuliers, la question que vous posez est le temps polynomial décidable. Par exemple, lorsque les matrices sont symétriques, ou de rang 1, ou si elles font la navette.

Enfin, un excellent livre sur le sujet est le suivant .

Edit: Cette réponse est malheureusement incorrecte. L'erreur est mise en évidence ci-dessous. L'argument fonctionne si nous sommes autorisés à transposer les matrices.

Nous commençons par prouver un lemme.

Lemme. Soit une matrice n × n et soit N la matrice n × n avec celles sur la diagonale secondaire. Si A N t et N t A sont nilpotents pour tout t ≥ 0 alors A = 0 . Conclusion correcte: A est triangulaire supérieur avec des zéros sur la diagonale. (La conclusion originale est retrouvée si on nous permet aussi de multiplier par les puissances de la transposition de N. )$A$$n\times n$$N$$n\times n$$AN^t$$N^tA$$t \geq 0$$A = 0$$A$$N$

Preuve. Supposons par exemple que , et écrivons A = ( a b c d e f g h i )$n = 3$ On commence par calculer A N 2 : A N 2 = ( 0 0 a 0 0 d 0 0 g ) . Cette matrice est sous forme triangulaire, et donc si A N 2 est nilpotent alors g = 0 . Continuez avec 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$ Encore une fois la matrice est sous forme triangulaire, et donc siAN1est nilpotent alorsd=h=0. Continuant, AN0=( a b c 0 e f 0 0 i ). Comme précédemment, nous concluons 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}.$$ , et donc A est triangulaire supérieur avec des zéros sur la diagonale.$a = e = i = 0$$A$

Si nous considérons maintenant place, alors nous concluons que A est triangulaire inférieur avec des zéros sur la diagonale. En fait, nous ne recevons rien de nouveau de considérer N t A . Donc 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$. Laisser$V_i$ être un espace vectoriel sur lequel $A_1 A_2 \neq A_2 A_1$; Notez que$\dim V_i > 1$ puisque $0$fait la navette avec tout. Limité à$V_i$, $A_1 = N$ et $A_2 \neq 0$. Par conséquent, le lemme implique que pour certains$t \geq 0$, Soit $A_2 A_1^t$ ou $A_1^t A_2$ n'est pas nul, et donc la propriété P échoue clairement.

En résumé, la propriété P est valable si toutes les matrices sont nilpotentes et toutes font la navette.