Sprawdzanie, czy wszystkie produkty z zestawu matryc ostatecznie są równe zero

Jestem zainteresowany następującym problemem: podano całkowitą macierze 1 , 2 , ... , k zdecydować, czy każdy nieskończony iloczyn tych macierzy ostatecznie równa macierzy zerowej.$A_1,A_2, \ldots, A_k$

Oznacza to dokładnie to, co myślisz: powiemy, że zestaw macierzy $\{A_1, \ldots, A_k\}$ ma właściwość polegającą na tym, że wszystkie jego produkty ostatecznie są równe zeru, jeśli nie istnieje nieskończona sekwencja $i_1, i_2, i_3\ldots$ , wszystko w , takie, że dla wszystkich .A i 1 A i 2 ⋯ A i l ≠ 0 $\{1, \ldots, k\}$

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

Czy badano wcześniej problem decydowania o tym, czy każdy produkt ostatecznie równa się zero? Czy to jest rozstrzygalne?

Wydaje się, że może to być związane ze śmiertelnością macierzy, co jest nierozstrzygalne, ale nie widzę wyraźnego związku.

Twoje pytanie jest równoważna czy 1 , ... , k wygenerować nilpotent algebry , który z kolei jest równoznaczne z każdego z A i będącego nilpotent . Stąd nie tylko jest to rozstrzygalne, ale w czasie ˜ O ( n 2 ω ), gdzie ω jest wykładnikiem mnożenia macierzy.$A_1, \dotsc, A_k$$A_i$$\tilde O(n^{2 \omega})$$\omega$

Niech być asocjacyjne algebra generowana przez A í , to znaczy wziąć wszystkie liniowe kombinacje z A í oraz ich wszystkich skończonych produktów. A nazywa się nilpotentem, jeśli istnieje taki N , że każdy iloczyn N elementów A wynosi zero.$\mathcal{A}$$A_i$$A_i$$\mathcal{A}$$N$$N$$\mathcal{A}$

Po pierwsze, zobaczmy, dlaczego twój stan sugeruje, że jest bezsilny. Wynika to z lemat königa (zwartość): każdy łańcuch o długości n nad alfabetem { 1 , ... , k } odpowiada iloczynowi A 1 , ... , k długości n w sposób oczywisty. Zastanówmy się nad nieskończonym k- drzewem zakorzenionym, którego węzły są naturalnie w bijective korespondencji z łańcuchami powyżej { 1 , … , k } . Zastanów się nad pod drzewem $\mathcal{A}$$n$$\{1, \dotsc, k\}$$A_1, \dotsc, A_k$$n$$k$$\{1, \dotsc, k\}$$T$składająca się z tych węzłów, gdzie odpowiednie produktem jest różna od zera. Lemat Koniga mówi, że jeśli T jest nieskończony, to ma nieskończoną ścieżkę (dokładnie naruszającą twoją własność), stąd T jest skończony. Możemy zatem przyjąć N być maksymalna długość dowolny ciąg w T . Zatem twoja własność sugeruje, że A nie jest silna.$A_i$$T$$T$$N$$T$$\mathcal{A}$

Odwrotna jest również prawdą, ponieważ każdy element jest liniową kombinacją produktów z A í .$\mathcal{A}$$A_i$

Następnie zauważ, że jest subalgebrą macierzy n × n , a zatem ma wymiary skończone.$\mathcal{A}$$n \times n$

Wreszcie: algebra asocjacyjna o skończonych wymiarach w charakterystycznym zeru ma podstawę elementów nilpotentnych (dojazdy lub nie - to jest część, która stoi w sprzeczności z odpowiedzią Yuvala) i jest nilpotentna (patrz np. Tutaj ).

Dlatego, aby rozwiązać swój problem, znaleźć podstawę do asocjacyjnej algebry generowanej przez (przy wersji liniowy Algebra przeszukiwanie wszerz) i sprawdzić, że każda macierz w bazie jest nilpotent. Górna granica ˜ O ( n 2 ω ) pochodzi z rozwiązania układu równań liniowych w n 2 zmiennych w poszukiwaniu szerokości pierwszego. Ponieważ dim A ≤ n 2 BFS nie może trwać bardzo długo, a ponieważ są to n × n macierzy, aby sprawdzić, czy macierz A nie jest silna, wystarczy sprawdzić, czy A n$A_i$$\tilde O(n^{2\omega})$$n^2$$\dim \mathcal{A} \leq n^2$$n \times n$$A$ .$A^n = 0$

Mam algorytm wieloczasowy dla tego (raczej trywialnego problemu) problemu, tj. Do sprawdzenia, czy wspólny promień widmowy (JSR) wynosi zero, czy nie, w 1995 r .: http://en.wikipedia.org/wiki/Joint_spectral_radius

Historia stojąca za algorytmem jest z grubsza następująca: Blondel i Tsitsiklis błędnie stwierdzili, że dla macierzy boolowskich sprawdzanie, czy JSR <1 jest NP-HARD. Dla dowolnego zestawu macierzy liczb całkowitych JSR ma wartość zero lub większą lub równą 1. Tak więc kontrprzykładem ich instrukcji był mój algorytm (patrz errata na ich papierze). Główny morał: najpierw skonsultuj się z Wikipedią!

Pytanie, które zadajesz, jest dokładnie równoważne z decyzją, czy łączny promień widmowy (JSR) zestawu macierzy jest ściśle mniejszy niż jeden. Rozstrzygalność tego pytania pozostaje otwarta od dłuższego czasu. (W teorii sterowania jest to równoważne z rozstrzygalnością stabilności przełączanych układów liniowych przy arbitralnym przełączaniu).

Następujący wariant twojego pytania jest nierozstrzygalny: biorąc pod uwagę skończony zestaw macierzy kwadratowych, zdecyduj, czy wszystkie produkty pozostaną ograniczone; patrz tutaj .

Nierozstrzygalność powyższego pozostaje ważna, nawet jeśli masz tylko 2 macierze o rozmiarze 47x47: patrz tutaj .

W języku JSR kwestia testowania „jest JSR ?” jest nierozstrzygalny (patrz odnośniki powyżej), ale rozstrzygalność testu „czy JSR < 1 ?” jest otwarte. To ostatnie pytanie jest związane z tak zwaną „hipotezą racjonalnej skończoności”: Jeśli hipoteza racjonalnej skończoności jest prawdziwa, to pytanie, które zadajesz, jest rozstrzygalne.$\le 1$$< 1$

Wreszcie, chyba że P = NP, JSR nie może być przybliżony w czasie wielomianowym (w dokładnym znaczeniu zdefiniowanym w tym artykule ).

W rezultacie jedna z odpowiedzi powyżej, która twierdzi, że skuteczny algorytm musi być fałszywa.

Po stronie pozytywnej istnieje kilka algorytmów (np. Opartych na programowaniu półfinałowym) do przybliżania JSR. Różne algorytmy mają różne gwarancje wydajności. Zobacz np. Następujące (bezwstydnie ja i moi koledzy - ale zobacz także odniesienia w nich ).

W kilku szczególnych przypadkach zadawane pytanie dotyczy czasu wielomianowego. Na przykład, gdy macierze są symetryczne, zajmują jedną pozycję lub jeśli dojeżdżają do pracy.

Wreszcie świetna książka na ten temat jest następująca .

Edycja: Ta odpowiedź jest niestety niepoprawna. Błąd jest podświetlony poniżej. Argument działa, jeśli możemy transponować macierze.

Zaczynamy od udowodnienia lematu.

Lemat. Niech będzie macierzą n × n i niech N będzie macierzą n × n z macierzami na wtórnej przekątnej. Jeżeli A N t i N t A są zerowe dla wszystkich t ≥ $A$$n\times n$$N$$n\times n$$AN^t$$N^tA$$t \geq 0$ to . Prawidłowy wniosek: A jest górnym trójkątnym z zerami na przekątnej. (Pierwotny wniosek można odzyskać, jeśli możemy również pomnożyć przez uprawnienia transponowania N. )$A = 0$$A$$N$

Dowód. Załóżmy na przykład, że , i napisz A = ( a b $n = 3$ Zaczynamy od obliczenia A N 2 : A N 2 = ( 0 0 a 0 0 d 0 0 g ) . Ta macierz ma kształt trójkąta, więc jeśli A N 2 jest zerowy, to g = 0 . Kontynuuj z 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$ Ponownie macierz ma kształt trójkątny, więc jeśliAN1jest zerowy, tod=h=0. Kontynuując, AN0=( a b c 0 e f 0 0 i ). Tak jak poprzednio, dochodzimy do wniosku, żea= $$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}.$$ , a więc A jest górnym trójkątnym z zerami na przekątnej.$a = e = i = 0$$A$

Jeśli weźmiemy teraz pod uwagę , to dochodzimy do wniosku, że A jest dolnym trójkątem z zerami na przekątnej. W rzeczywistości, nie mamy nic nowego z uwzględnieniem N T A . Dlatego 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$

Podsumowując, właściwość P utrzymuje, że wszystkie macierze są zerowe i wszystkie dojeżdżają do pracy.