Apa kerumitan untuk memeriksa apakah sebuah matriks dapat didiagonisasi?

13

Diberi matriks A dengan entri rasional. Apa kompleksitas untuk memeriksa A yang dapat didiagonalisasi?n×nAA

Saya menduga bahwa ini dapat dilakukan dalam P, tetapi saya tidak tahu referensi apa pun. Namun, pertanyaan yang lebih menarik adalah, adakah kelas kompleksitas yang lebih baik untuk menangkap masalah ini?

Bimbingan / komentar apa pun dipersilahkan! Terima kasih.

cc.complexity-theory linear-algebra matrices amatrix
sumber
Dengan menghitung dan memfaktorkan polinom karakteristik, Anda dapat memeriksa dalam waktu polinom apakah matriks dapat didiagonalisasi. Saya tidak tahu batas yang lebih baik untuk masalah ini.
Bruno
7
@ Bruno apakah Anda mengasumsikan bahwa sebuah matriks dapat didiagonalkan jika memiliki nilai eigen yang berbeda? Ini tidak benar, itu adalah kondisi yang memadai tetapi tidak perlu. Matriks identitas adalah contoh tandingan.
Tyson Williams
@TysonWilliams: Saya mengasumsikan fakta yang setara bahwa sebuah matriks dapat didiagonalisasi jika polinomial karakteristiknya adalah produk dari faktor linier yang berbeda. Tentu saja, kesetaraan tidak berlaku untuk polinom karakteristik tetapi polinom minimal ...
Bruno
4
Untuk mengkompensasi kesalahan saya, berikut ini adalah referensi untuk algoritma waktu polinomial untuk menghitung polinomial minimal, dari mana Anda dengan mudah memperoleh (atau mengekstrak) algoritma untuk memeriksa kemampuan didiagonalisasi: Pada perhitungan polinomial minimum, vektor siklik, dan bentuk frobenius , oleh Daniel Augot dan Paul Camion.
Bruno
3
Anda dapat menghitung bentuk kanonik Jordan dari matriks rasional dalam waktu polinomial: worldscientific.com/doi/abs/10.1142/S0129054194000165
Robin Kothari

Jawaban: