Kompleksitas powering matriks

Biarkan menjadi matriks integer persegi, dan misalkan $M$ $n$ menjadi bilangan bulat positif. Saya tertarik pada kompleksitas masalah keputusan berikut:

Apakah entri kanan atas positif? $M^n$

Perhatikan bahwa pendekatan yang jelas dari iterasi persegi (atau perhitungan eksplisit lainnya) mengharuskan kita untuk berpotensi menangani bilangan bulat dari besarnya eksponensial ganda, yaitu, memiliki banyak bit secara eksponensial. Namun masalah mudah terlihat berada di kelas "PosSLP" Allender et al. ( "Pada Kompleksitas Analisis Angka", SIAM J. Komputasi 38 (5) ), dan oleh karena itu di tingkat keempat hierarki penghitungan .

1) Apakah mungkin untuk menempatkan masalah powering matriks ini di kelas kompleksitas yang lebih rendah?

2) Jika tidak, mungkinkah PosSLP-keras?

3) Saya terutama tertarik pada masalah powering matriks untuk matriks dimensi rendah, yaitu hingga dan termasuk matriks 6x6. Mungkinkah kompleksitasnya lebih rendah untuk matriks seperti itu?

cc.complexity-theory linear-algebra matrices Joel
sumber

Bukankah seharusnya judul diubah menjadi "Complexity of matrix powering"? Matriks eksponensial (lihat misalnya en.wikipedia.org/wiki/Matrix_exponential ) secara umum dipahami sebagai "A = exp (B)" untuk matriks A, B.

Martin Schwarz

Saya akan mengeditnya. itu poin yang bagus, @MartinSchwarz

Suresh Venkat

Jika Anda mengubah matriks menjadi bentuk PDP-1 (yang untuk matriks kecil dan daya n yang cukup tinggi dapat dianggap konstan), maka Anda dapat mengetahui tanda setiap entri dari entri diagonal secara sepele. Maka mudah untuk mengetahui dua perkalian matriks yang tersisa.

Robert Mason

@ Robert Mason: Saya tidak yakin apa yang Anda sarankan. Jika D adalah bentuk kanonik Jordan dari M, sehingga M ^ n = P ^ (- 1) D ^ n P, maka entri D biasanya berupa bilangan aljabar kompleks, jadi apa yang Anda maksud dengan "tanda" mereka? Saya setuju Anda dapat menghitung D dan P dalam waktu polinomial (dengan asumsi representasi standar dari angka aljabar), tetapi ekspresi yang Anda dapatkan untuk entri kanan atas M ^ n = P ^ (- 1) D ^ n P akan menjadi ekspresi melibatkan berbagai nomor aljabar yang dinaikkan ke kekuatan n, dan saya tidak melihat bagaimana Anda dapat menentukan tanda ekspresi ini secara efisien.

Joel

@ Robert Mason: Saya masih tidak mengerti - bagaimana / mengapa ini efisien untuk matriks yang dapat dibalik? (Dan kebetulan, "sebagian besar" matriks tidak dapat dibalik, bukan sebaliknya.)

Joel

Kompleksitas powering matriks

Jawaban: