Jaka jest złożoność sprawdzenia, czy macierz można diagonalizować?

Biorąc pod uwagę macierzy z racjonalnym pozycji. Jaką złożoność sprawdzenia można diagonalizować? $n\times n$ $A$ $A$

Podejrzewam, że można to zrobić w P, ale nie znam żadnego odniesienia. Bardziej interesujące jest jednak pytanie, czy istnieje jakaś lepsza klasa złożoności, aby uchwycić ten problem?

Wszelkie wskazówki / komentarze są mile widziane! Dzięki.

cc.complexity-theory linear-algebra matrices amatrix
źródło

Obliczając i faktoryzując charakterystyczny wielomian, możesz sprawdzić w czasie wielomianowym, czy macierz jest diagonalizowalna. Nie znam lepszych granic tego problemu.

Bruno,

@Bruno zakładasz, że macierz jest diagonalizowalna, jeśli ma wyraźne wartości własne? To nie jest prawda, jest to warunek wystarczający, ale niekonieczny. Macierz tożsamości jest kontrprzykładem.

Tyson Williams,

@TysonWilliams: Zakładałem równoważny fakt, że macierz jest diagonalna, jeśli jej charakterystyczny wielomian jest iloczynem wyraźnych czynników liniowych. Oczywiście równoważność nie dotyczy charakterystycznego wielomianu, ale minimalny wielomian ...

Bruno

Aby zrekompensować mój błąd, tutaj znajduje się odwołanie do algorytmu wielomianu czasowego do obliczenia minimalnego wielomianu, z którego łatwo można uzyskać (lub wyodrębnić) algorytm do sprawdzania przekątności: przy obliczaniu minimalnych wielomianów, wektorów cyklicznych i postaci frobeniusa przez Daniel Augot i Paul Camion.

Bruno,

Można obliczyć Jordan kanoniczną postać racjonalnego matrycy w czasie wielomianowym: worldscientific.com/doi/abs/10.1142/S0129054194000165

Robin KOTHARI

Jaka jest złożoność sprawdzenia, czy macierz można diagonalizować?

Odpowiedzi: