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

19

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.A1,A2,,Ak

Oznacza to dokładnie to, co myślisz: powiemy, że zestaw macierzy {A1,,Ak} ma właściwość polegającą na tym, że wszystkie jego produkty ostatecznie są równe zeru, jeśli nie istnieje nieskończona sekwencja i1,i2,i3 , wszystko w , takie, że dla wszystkich .A i 1 A i 2A i l0 l{1,,k}

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

robinson
źródło
Potrzebujesz pewnej właściwości zbieżności na zbiorze macierzy, aby upewnić się, że nieskończony produkt jest zdefiniowany.
András Salamon
Czy działasz w polu skończonym lub liczbach całkowitych z nieograniczonym wzrostem? = 1 przypadek jest ciekawy w jego własnym prawie. Używając liczb całkowitych od -100 do 100 w matrycy 5x5, jaka jest najwyższa moc, jaką możesz uzyskać, zanim się wyzeruje? k
Chad Brewbaker
2
@YuvalFilmus - Uważam, że różni się od śmiertelności. Niech wymiary macierzy wynoszą , abyśmy mieli tylko liczby, i załóżmy, że A 0 = 0 , A 1 = 1 . Śmiertelny? Tak, ponieważ A 0 = 0 . Każdy produkt jest równy zero? Nie: nie produkt 1 1 1 . Z drugiej strony, jeśli A 0 = 0 , A 1 = 0, to masz sekwencję, która jest zarówno śmiertelna, a każdy produkt jest równy zero. 1A0=0,A1=1A0=0111A0=0,A1=0
robinson
1
@ChadBrewbaker - Myślałem, że wpisy macierzy są tylko liczbami całkowitymi. Przypuszczam, że jest interesujące z punktu widzenia: ile operacji potrzebujesz, aby sprawdzić, czy macierz jest nilpotentna? Zauważ, że jeśli A jest zerowy, to łatwo zauważyć, że A n = 0, gdzie n jest wymiarem A, więc prawdopodobnie można go rozwiązać, podnosząc logarytm macierzowy n razy. Nie mam pojęcia, czy to najlepsze, co możesz zrobić. k=1AAn=0nAlogn
robinson
1
Co ciekawe, tylko w: arxiv.org/abs/1306.0729 . Zamiast pytać, czy wszystkie produkty są ostatecznie zerowe, pytają, czy jakiś produkt jest ostatecznie pozytywny. Pokazują, że problem jest NP-trudny (a przynajmniej tak to wyciągam ze streszczenia).
Joshua Grochow

Odpowiedzi:

17

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.ZA1,,ZAkZAjaO~(n2)ω)ω

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.ZAZAjaZAjaZAN.N.ZA

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 T.ZAn{1,,k}ZA1,,ZAknk{1,,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.ZAjaT.T.N.T.ZA

Odwrotna jest również prawdą, ponieważ każdy element jest liniową kombinacją produktów z A í .ZAZAja

Następnie zauważ, że jest subalgebrą macierzy n × n , a zatem ma wymiary skończone.ZAn×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 An 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 =ZAjaO~(n2)ω)n2)ciemnyZAn2)n×nZA .ZAn=0

Joshua Grochow
źródło
2
Czy uważasz, że istnieje sposób, aby to pokazać bez stosowania jakichkolwiek zasad wyboru (nawet takich słabych jak lemat Königa, co odpowiada )? ACω
András Salamon
2
@Andras: Powiedziałbym, że to pytanie do Chrisa Conidisa. Studiował takie pytania w (obliczalnej) matematyce odwrotnej. Zapytam go i wskażę tutaj.
Joshua Grochow
1
@robinson: 1) Tak, problem jest rozstrzygalny, w rzeczywistości w czasie gdzie ω jest wykładnikiem mnożenia macierzy. Wynika to z rozwiązywania układów równań liniowych nad Q podczas przeprowadzania wyszukiwania algebry liniowej w pierwszej kolejności. 2) Tak, zwykłe pojęcie podstawy przy oglądaniu macierzy jako wektorów w Q n 2 (lub powyżej R lub C ). O(n2)ω)ωQQn2)Rdo
Joshua Grochow
1
Zaczynasz na bazie z A . Teraz można spróbować znaleźć macierze i B B takie, że B lub B nie znajduje się w przestrzeni B . Jeśli ci się powiedzie, dodaj produkt do B i kontynuuj. W przeciwnym razie, mnożąc każdą matrycę w odstępie B od dowolnego skończonego produktu z matryc w A zawsze kończy się w odstępie B . Ponieważ wymiar Algebra jest ograniczona, gdy kończy się proces (w co najwyżej n 2 etapach). bZAZAZAbbABBABBBABn2
Yuval Filmus
1
@robinson: Nie. Jeśli algebra jest zerowa, to każdy element algebry jest zerowy. Jeśli więc znajdziesz jakiś element inny niż zerowy, to algebra nie jest zerowa (a wtedy istnieją nieskończone iloczyny twoich macierzy, które nigdy nie są zerowe).
Joshua Grochow
6

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ą!

leonid gurvits
źródło
5

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

Amir Ali Ahmadi
źródło
Proszę przeczytać formalne oświadczenie, które zadałem - nie jest to równoważne z podjęciem decyzji, czy JSR jest ściśle mniejsze niż jeden. Być może wprowadzony w błąd tytuł pytania. Krótko mówiąc, pytam o każdy produkt równy zero w skończonym czasie , a nie w sensie asymptotycznym.
robinson
2
Pytanie, które zadajesz, jest znacznie prostsze. Następujące elementy są równoważne: (i) Warunek, który zdefiniujesz (ii) Wszystkie produkty skończone są zerowe (iii) JSR = 0 (iv) Wszystkie produkty o długości n są zerowe (n jest wymiarem, jest to niezależne od liczby macierze k). Ostatni warunek w oczywisty sposób implikuje rozstrzygalność, a jeśli tak, to możesz sprawdzić warunek w czasie wielomianowym. Zobacz rozdział 2.3.1 książki Jungers, do której link znajduje się na końcu mojego postu. Przepraszam za myślenie, że masz na myśli wersję asymptotyczną. (Zostałem wprowadzony w błąd zwrotem „wszystkie produkty ostatecznie mają zero”).
Amir Ali Ahmadi
W którym przypadku @AmirAliAhmadi nie obejmuje odpowiedzi Joshua Grochow?
Suresh Venkat
2
Wydaje mi się, że tak, z innym algorytmem niż to, co mam na myśli. (Ponownie przepraszam za myśl, że pytanie brzmiało: „czy wszystkie produkty są zbieżne do zera” (tj. JSR <1?), Których rozstrzygalność jest otwarta.) Istnieje kilka różnic w odpowiedzi Jozuego. (1) W równoważności (i) - (iv) w moim poprzednim komentarzu, nie sądzę, że należy stosować lemię Koniga. (2) Nie rozumiem, dlaczego bierze liniowe kombinacje macierzy. (3) Kopiuję poniżej prosty alternatywny algorytm z rozdziału 2.3.1 książki Jungersa, przypisany tam Leonidowi Gurvitsowi.
Amir Ali Ahmadi
4
[Kontynuacja z wyżej ...] Wszystko, czego potrzebujemy, aby sprawdzić, czy wszystkie produkty o długości są równe zeru, ale istnieje k n takie macierze. Aby tego uniknąć, iteracyjnie zdefiniuj następujące macierze: X 0 = I , X j = k i = 1 A T i X j - 1 A i . Następnie trzeba X n = Σ A  produkt o długości n A T A . Macierz ta może być obliczona przez k nnknX0=ja, Xjot=ja=1kZAjaT.Xjot-1ZAjaXn=ZA iloczyn długości nZAT.ZAknmnożenia macierzy i wynosi zero wtedy i tylko wtedy, gdy wszystkie produkty o długości są zerowe. n
Amir Ali Ahmadi
0

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 0ZAn×nN.n×nZAN.tN.tZAt0 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. )ZA=0ZAN.

Dowód. Załóżmy na przykład, że , i napisz A = ( a b cn=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 = ( 0

ZA=(zabdoremifasolhja),N.=(010001000).
ZAN.2)
ZAN.2)=(00za00re00sol).
ZAN.2)sol=0ZAN.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=e
ZAN.1=(0zab0remi0solh)=(0zab0remi00h).
ZAN.1re=h=0
ZAN.0=(zabdo0mifa00ja).
, a więc A jest górnym trójkątnym z zerami na przekątnej.za=mi=ja=0ZA

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.2)ZA,N.1ZA,N.0ZAZAN.tZAZA=0

ZA1,,ZAkja1,[k]ZAja1ZAjam=0mZAjaZA1ZA2)ZA2)ZA1ZA1V.1V.tV.jaZA1ZA2)ZA2)ZA1ciemnyV.ja>10V.jaZA1=N.ZA2)0t0ZA2)ZA1tZA1tZA2)

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

Yuval Filmus
źródło
4
N.2)ZAsol=0N.1ZAre=h=0N.0ZAza=mi=ja=0ZAZA
Rzeczywiście, ta odpowiedź jest nieprawidłowa. Jeśli nikt inny tego nie zrobi, opublikuję kontrprzykład zarówno do lematu, jak i do ostatecznego stwierdzenia, kiedy dzisiaj wrócę do domu.
robinson
5
Jak zwykle dzieje się tak, gdy coś jest przedmiotem roszczenia, ale nie udowodniono, że dowód się nie udaje. No cóż ...
Yuval Filmus
1
ZA0=(010001000),ZA1=(011000000)
Można sprawdzić, czy każdy produkt o wystarczającej długości tych dwóch macierzy ma wartość zero, ale nie zamieniają się, a druga nie jest równa zero.
robinson