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

19

Jestem zainteresowany następującym problemem: podano całkowitą macierze 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 . $\{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$

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.

linear-algebra decidability

— 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

$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

. Śmiertelny? Tak, ponieważ

. Każdy produkt jest równy zero? Nie: nie produkt

. Z drugiej strony, jeśli

to masz sekwencję, która jest zarówno śmiertelna, a każdy produkt jest równy zero.

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

jest zerowy, to łatwo zauważyć, że

gdzie

jest wymiarem

więc prawdopodobnie można go rozwiązać, podnosząc

macierzowy

razy. Nie mam pojęcia, czy to najlepsze, co możesz zrobić.

k = 1

$k=1$

A

$A$

A^{n} = 0

$A^n = 0$

n

$n$

A

$A$

\log n

$\log n$

— 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

17

Twoje pytanie jest równoważna czy wygenerować nilpotent algebry ~~, który z kolei jest równoznaczne z każdego z~~ ~~będącego nilpotent~~ . Stąd nie tylko jest to rozstrzygalne, ale w czasie 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 , to znaczy wziąć wszystkie liniowe kombinacje z oraz ich wszystkich skończonych produktów. nazywa się nilpotentem, jeśli istnieje taki , że każdy iloczyn elementów 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 nad alfabetem odpowiada iloczynowi długości w sposób oczywisty. Zastanówmy się nad nieskończonym drzewem zakorzenionym, którego węzły są naturalnie w bijective korespondencji z łańcuchami powyżej . 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 jest nieskończony, to ma nieskończoną ścieżkę (dokładnie naruszającą twoją własność), stąd jest skończony. Możemy zatem przyjąć być maksymalna długość dowolny ciąg w . Zatem twoja własność sugeruje, że 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 . $\mathcal{A}$ $A_i$

Następnie zauważ, że jest subalgebrą macierzy , 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 pochodzi z rozwiązania układu równań liniowych w zmiennych w poszukiwaniu szerokości pierwszego. Ponieważ BFS nie może trwać bardzo długo, a ponieważ są to macierzy, aby sprawdzić, czy macierz jest silna, wystarczy sprawdzić, czy $A_i$ $\tilde O(n^{2\omega})$ $n^2$ $\dim \mathcal{A} \leq n^2$ $n \times n$ $A$ . $A^n = 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}_{ω}

$\text{AC}_\omega$

— 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

podczas przeprowadzania wyszukiwania algebry liniowej w pierwszej kolejności. 2) Tak, zwykłe pojęcie podstawy przy oglądaniu macierzy jako wektorów w

(lub powyżej

lub

).

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

Zaczynasz na bazie

z

. Teraz można spróbować znaleźć macierze

i

takie, że

lub

nie znajduje się w przestrzeni

. Jeśli ci się powiedzie, dodaj produkt do

i kontynuuj. W przeciwnym razie, mnożąc każdą matrycę w odstępie

od dowolnego skończonego produktu z matryc w

zawsze kończy się w odstępie

. Ponieważ wymiar Algebra jest ograniczona, gdy kończy się proces (w co najwyżej

etapach).

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: 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 ?” 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 .

— 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

takie macierze. Aby tego uniknąć, iteracyjnie zdefiniuj następujące macierze:

. Następnie trzeba

. Macierz ta może być obliczona przez

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$ mnożenia macierzy i wynosi zero wtedy i tylko wtedy, gdy wszystkie produkty o długości

są zerowe.

n

$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ą i niech będzie macierzą z macierzami na wtórnej przekątnej. Jeżeli i są zerowe dla wszystkich $A$ $n\times n$ $N$ $n\times n$ $AN^t$ $N^tA$ $t \geq 0$ to . Prawidłowy wniosek: 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 ) $A = 0$ $A$ $N$

Dowód. Załóżmy na przykład, że , i napisz $n = 3$ Zaczynamy od obliczenia : Ta macierz ma kształt trójkąta, więc jeśli jest zerowy, to . Kontynuuj z :

ZA = (\begin{matrix} za & b & do \\ re & mi & fa \\ sol & h & ja \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$

ZA {N.}^{2)} = (\begin{matrix} 0 & 0 & za \\ 0 & 0 & re \\ 0 & 0 & sol \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$

Ponownie macierz ma kształt trójkątny, więc jeśli

jest zerowy, to

. Kontynuując,

Tak jak poprzednio, dochodzimy do wniosku, że

ZA {N.}^{1} = (\begin{matrix} 0 & za & b \\ 0 & re & mi \\ 0 & sol & h \end{matrix}) = (\begin{matrix} 0 & za & b \\ 0 & re & mi \\ 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$

ZA {N.}^{0} = (\begin{matrix} za & b & do \\ 0 & mi & fa \\ 0 & 0 & ja \end{matrix}) .

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

, a więc

jest górnym trójkątnym z zerami na przekątnej.

a = e = i = 0

$a = e = i = 0$

A

$A$

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

— Yuval Filmus
źródło

4

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$

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

{ZA}_{0} = (\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix}), {ZA}_{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}$ 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