Złożoność zasilania macierzy

Niech będzie kwadratową macierzą liczb całkowitych, a niech będzie liczbą całkowitą dodatnią. Interesuje mnie złożoność następującego problemu decyzyjnego: $M$ $n$

Czy prawy górny wpis dodatni? $M^n$

Zauważ, że oczywiste podejście iterowanego kwadratu (lub innego jawnego obliczenia) wymaga od nas potencjalnie obsługi liczb całkowitych o podwójnie wykładniczej wielkości, tj. Mających wykładniczo wiele bitów. Jednak problem można łatwo dostrzec w klasie „PosSLP” Allendera i wsp. ( „O złożoności analizy numerycznej”, SIAM J. Comput. 38 (5) ), a zatem na czwartym poziomie hierarchii liczenia .

1) Czy można umieścić ten problem zasilania macierzy w niższej klasie złożoności?

2) Jeśli nie, to czy może być trudne PosSLP?

3) Szczególnie interesuje mnie problem zasilania macierzy dla matryc niskowymiarowych, tj. Do matryc 6x6 włącznie. Czy złożoność może być mniejsza dla takich matryc?

cc.complexity-theory linear-algebra matrices

— Joel
źródło

Czy tytuł nie powinien zostać zmieniony na „Złożoność zasilania macierzy”? Potęgowanie macierzy (patrz np. En.wikipedia.org/wiki/Matrix_exponential ) jest ogólnie rozumiane jako „A = exp (B)” dla macierzy A, B.

— Martin Schwarz

Zmienię to. to dobry punkt, @MartinSchwarz

— Suresh Venkat

Jeśli przekształcisz macierz w postać PDP-1 (która dla małej matrycy i wystarczająco wysokiej mocy n można uznać za stałą), możesz poznać znak każdego wpisu przekątnych w trywialny sposób. Następnie łatwo jest ustalić pozostałe dwa mnożenia macierzy.

— Robert Mason

@Robert Mason: Nie jestem do końca pewien, co sugerujesz. Jeśli D jest kanoniczną postacią M Jordana, więc M ^ n = P ^ (- 1) D ^ n P, wówczas wpisy D będą zwykle złożonymi liczbami algebraicznymi, więc co rozumiesz przez ich „znak”? Zgadzam się, że możesz obliczać D i P w czasie wielomianowym (zakładając standardowe reprezentacje liczb algebraicznych), ale wyrażenie, które otrzymujesz dla prawego górnego wpisu M ^ n = P ^ (- 1) D ^ n P będzie wyrażeniem z udziałem różnych liczb algebraicznych podniesionych do potęgi n, i nie widzę, jak można skutecznie określić znak tego wyrażenia.

— Joel

@Robert Mason: Nadal nie rozumiem - jak / dlaczego jest to skuteczne w przypadku odwracalnych matryc? (Nawiasem mówiąc, „większość” matryc jest odwracalna, a nie odwrotnie.)

— Joel

$k = 2,3$ $\mathsf{P}$

— SamiD
źródło

Nie mogłem się oprzeć opublikowaniu tego! :-)

— SamiD,