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

Możesz to zrobić w jednolitym NC, patrz:

G. Villard. Szybkie równoległe algorytmy redukcji macierzy do form kanonicznych. AAECC 8: 511-537, 1997. http://link.springer.com/article/10.1007%2Fs002000050089

— Markus Bläser
źródło