В чем сложность проверить, является ли матрица диагонализируемой?

Дана матрица с рациональными элементами. В чем сложность проверки диагонализируемой? $n\times n$ $A$ $A$

Я подозреваю, что это может быть сделано в P, но я не знаю никаких ссылок. Однако, более интересный вопрос, есть ли лучший класс сложности для решения этой проблемы?

Любое руководство / комментарий приветствуется! Благодарю.

cc.complexity-theory linear-algebra matrices amatrix
источник

Вычисляя и разлагая характеристический полином, вы можете проверить за полиномиальное время, является ли матрица диагонализуемой. Я не знаю лучших границ для этой проблемы.

Бруно

@ Бруно, вы предполагаете, что матрица диагонализируема, если она имеет различные собственные значения? Это не правда, это достаточное, но не необходимое условие. Тождественная матрица является контрпримером.

Тайсон Уильямс

@TysonWilliams: я предполагал эквивалентный факт, что матрица диагонализируема, если ее характеристический многочлен является продуктом различных линейных факторов. Конечно, эквивалентность имеет место не для характеристического полинома, а для минимального полинома ...

Бруно

Для того, чтобы компенсировать свою ошибку, вот ссылка для полиномиального алгоритма времени , чтобы вычислить минимальный многочлен, из которого легко получить (или выписку) алгоритм для проверки диагонализуемости: О вычислении минимальных многочленов, циклических векторов и фробениусовых форм , путь Даниэль Ауго и Пол Камион.

Бруно

Вы можете вычислить иорданскую каноническую форму рациональной матрицы за полиномиальное время: worldscientific.com/doi/abs/10.1142/S0129054194000165

Робин Котари,

В чем сложность проверить, является ли матрица диагонализируемой?

Ответы: