Qual é a complexidade para verificar se uma matriz é Diagonalizável?

13

Dada uma matriz com entradas racionais. Qual é a complexidade para verificar é diagonalizável?A An×nAA

Suspeito que isso possa ser feito em P, mas não conheço nenhuma referência. No entanto, uma pergunta mais interessante é: existe alguma classe de complexidade melhor para capturar esse problema?

Qualquer orientação / comentário é bem-vindo! Obrigado.

amatrix
fonte
Ao calcular e fatorar o polinômio característico, é possível verificar no tempo polinomial se a matriz é diagonalizável. Não conheço limites melhores para esse problema.
1111 Bruno
7
@ Bruno, você está assumindo que uma matriz é diagonalizável se tiver valores próprios distintos? Isso não é verdade, é uma condição suficiente, mas não necessária. Uma matriz de identidade é um contra-exemplo.
Tyson Williams
@TysonWilliams: Eu estava assumindo o fato equivalente de que uma matriz é diagonalizável se seu polinômio característico é um produto de fatores lineares distintos. Claro, a equivalência não se sustenta para o polinômio característico, mas o polinômio mínimo ...
de Bruno
4
Para compensar meu erro, aqui está uma referência para um algoritmo de tempo polinomial para calcular o polinômio mínimo, a partir do qual você obtém (ou extrai) facilmente um algoritmo para verificar a diagonalizabilidade: No cálculo de polinômios mínimos, vetores cíclicos e formas de frobênio , por Daniel Augot e Paul Camion.
1174 Bruno
3
Você pode calcular a forma canônica Jordan de uma matriz racional em tempo polinomial: worldscientific.com/doi/abs/10.1142/S0129054194000165
Robin Kothari

Respostas: