¿Cuál es la complejidad para verificar si una matriz es Diagonalizable?

13

Dada una matriz A con entradas racionales. ¿Cuál es la complejidad para verificar que A es diagonalizable?norte×norteUNUN

Sospecho que esto se puede hacer en P, pero no conozco ninguna referencia. Sin embargo, una pregunta más interesante es, ¿hay alguna clase de complejidad mejor para capturar este problema?

Cualquier orientación / comentario es bienvenido! Gracias.

cc.complexity-theory linear-algebra matrices amatrix
fuente
Al calcular y factorizar el polinomio característico, puede verificar en tiempo polinómico si la matriz es diagonalizable. No conozco mejores límites para este problema.
Bruno
77
@Bruno, ¿está asumiendo que una matriz es diagonalizable si tiene valores propios distintos? Esto no es cierto, es una condición suficiente pero no necesaria. Una matriz de identidad es un contraejemplo.
Tyson Williams
@TysonWilliams: Estaba asumiendo el hecho equivalente de que una matriz es diagonalizable si su polinomio característico es un producto de distintos factores lineales. Por supuesto, la equivalencia no es válida para el polinomio característico, sino para el polinomio mínimo ...
Bruno
44
Para compensar mi error, aquí hay una referencia para un algoritmo de tiempo polinomial para calcular el polinomio mínimo, del cual puede obtener (o extraer) fácilmente un algoritmo para verificar la diagonalización: en el cálculo de polinomios mínimos, vectores cíclicos y formas frobenius , por Daniel Augot y Paul Camion.
Bruno
3
Puede calcular la forma canónica de Jordan de una matriz racional en tiempo polinómico: worldscientific.com/doi/abs/10.1142/S0129054194000165
Robin Kothari

Respuestas: