matriks serupa

Mengingat dua matriks A dan B , masalah memutuskan apakah terdapat permutasi matriks P sehingga B = P - 1 A P setara dengan (Grafik isomorfisma). Tetapi jika kita mengendurkan P menjadi matriks yang tidak dapat dibalik, lalu apa kerumitannya? Apakah ada batasan lain pada matriks P yang dapat dibalik , selain sebagai permutasi, yang menghubungkan masalah ini dengan atau masalah-masalah sulit lainnya?$n \times n$$A$$B$$P$$B = P^{-1}AP$GI$P$$P$GI

Matriks A dan B yang elemen-elemennya dalam bidang F serupa (dalam F ) jika dan hanya jika mereka memiliki bentuk normal Frobenius yang sama . Menurut pencarian cepat, tampaknya bahwa bentuk normal Frobenius dari n × n matriks dapat dihitung dengan O ( n ³ ) operasi lapangan [Sto98], dan bahwa ini dapat ditingkatkan untuk sesuatu yang sebanding dengan kompleksitas perkalian matriks [ Sto01].

[Sto98] Arne Storjohann. Algoritma O ( n ³ ) untuk bentuk normal Frobenius. Dalam Prosiding Simposium Internasional 1998 tentang Komputasi Simbolik dan Aljabar (ISSAC) , hlm. 101–105, Agustus 1998. DOI: 10.1145 / 281508.281570 .

[Sto01] Arne Storjohann. Perhitungan deterministik dari bentuk Frobenius. Dalam Simposium IEEE ke-42 tentang Yayasan Ilmu Komputer (FOCS) , hlm. 368-377, Oktober 2001. DOI: 10.1109 / SFCS.2001.959911 .

Memang ada batasan lain pada yang menghubungkan masalah ini dengan GI. Sebagai contoh, jika seseorang mensyaratkan bahwa P menjadi produk Kronecker (tensor) P 1 ⊗ P 2 ⊗ P 3 , maka masalah yang dihasilkan adalah sekeras kesetaraan dari tensor 3-valent, yang kira-kira sama kompleksitasnya dengan Linear Code Equivalence, yang pada gilirannya diketahui sebagai GI-keras (tetapi tidak diketahui setara dengan GI).$P$$P$$P_1 \otimes P_2 \otimes P_3$

Sudut pandang lain pada pertanyaan Anda, yang mungkin menjelaskan situasi umum, adalah sebagai berikut. Untuk setiap aksi grup pada himpunan X n (satu untuk setiap n ), kita dapat bertanya tentang kerumitan dalam menentukan apakah dua titik x , y ∈ X n berada dalam G n -orbit yang sama; sebut ini masalah orbit untuk tindakan (kelompok) tersebut. Pertanyaan Anda pada dasarnya adalah tentang kerumitan masalah orbit yang dapat diutarakan sebagai berikut: diberi tindakan linier dari grup G n pada ruang vektor V $G_n$$X_n$$n$$x,y \in X_n$$G_n$$G_n$$V_n$ , mempertimbangkan masalah orbit$G_n$$X_n = V_n \otimes (V_n)^*$ .

$G_n = S_n$$V_n = \mathbb{R}^n$$G_n = \text{GL}_n(\mathbb{F})$$V_n = \mathbb{F}^n$$G_n = \text{GL}_a \times \text{GL}_b \times \text{GL}_c$$V_n = \mathbb{F}^{a} \otimes \mathbb{F}^b \otimes \mathbb{F}^c$