Quelle est la complexité pour vérifier si une matrice est diagonalisable?

Soit une matrice avec des entrées rationnelles. Quelle est la complexité de vérifier que est diagonalisable? $n\times n$ $A$ $A$

Je soupçonne que cela peut être fait en P, mais je ne connais aucune référence. Cependant, une question plus intéressante est: existe-t-il une meilleure classe de complexité pour capturer ce problème?

Tout conseil / commentaire est le bienvenu! Merci.

cc.complexity-theory linear-algebra matrices amatrix
la source

En calculant et en factorisant le polynôme caractéristique, vous pouvez vérifier en temps polynomial si la matrice est diagonalisable. Je ne connais pas de meilleures limites pour ce problème.

Bruno

@Bruno supposez-vous qu'une matrice est diagonalisable si elle a des valeurs propres distinctes? Ce n'est pas vrai, c'est une condition suffisante mais non nécessaire. Une matrice d'identité est un contre-exemple.

Tyson Williams

@TysonWilliams: Je supposais le fait équivalent qu'une matrice est diagonalisable si son polynôme caractéristique est un produit de facteurs linéaires distincts. Bien sûr, l'équivalence ne

Bruno

Pour compenser mon erreur, voici une référence pour un algorithme de temps polynomial pour calculer le polynôme minimal, à partir duquel vous pouvez facilement obtenir (ou extraire) un algorithme pour vérifier la diagonalisation: sur le calcul des polynômes minimaux, des vecteurs cycliques et des formes de Frobenius , par Daniel Augot et Paul Camion.

Bruno

Vous pouvez calculer la forme canonique de Jordan d'une matrice rationnelle en temps polynomial: worldscientific.com/doi/abs/10.1142/S0129054194000165

Robin Kothari

Quelle est la complexité pour vérifier si une matrice est diagonalisable?

Réponses: