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

Dada uma matriz com entradas racionais. Qual é a complexidade para verificar é diagonalizável? $n\times n$ $A$ $A$

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.

cc.complexity-theory linear-algebra matrices 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

@ 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

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

Você pode calcular a forma canônica Jordan de uma matriz racional em tempo polinomial: worldscientific.com/doi/abs/10.1142/S0129054194000165

Robin Kothari

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

Respostas: