Saya tertarik pada masalah berikut: diberikan matriks bilangan bulat memutuskan apakah setiap produk tak terbatas dari matriks ini akhirnya sama dengan nol matriks.
Ini berarti persis seperti yang Anda pikirkan: kami akan mengatakan serangkaian matriks memiliki properti yang semua produknya akhirnya sama dengan nol jika tidak ada urutan tak terbatas , semuanya dalam \ {1, \ ldots, k \} , sedemikian rupa sehingga A_ {i_1} A_ {i_2} \ cdots A_ {i_l} \ neq 0 untuk semua l .
Apakah masalah memutuskan apakah setiap produk akhirnya sama dengan nol telah dipelajari sebelumnya? Apakah itu decidable?
Sepertinya itu mungkin terkait dengan kematian matriks, yang tidak dapat diputuskan, tapi saya tidak melihat hubungan yang jelas.
linear-algebra
decidability
Robinson
sumber
sumber
Jawaban:
Pertanyaan Anda setara dengan apakah menghasilkan aljabar nilpotentSEBUAH1, ... , Ak SEBUAHsaya HAI~( n2 ω) ω
, yang pada gilirannya setara dengan masing-masingyang nilpotent. Oleh karena itu tidak hanya decidable, tetapi dalam waktu di mana adalah eksponen dari perkalian matriks.Ai˜ O ( n 2 ω ) ωBiarkan menjadi aljabar asosiatif yang dihasilkan oleh : yaitu, ambil semua kombinasi linier dari dan semua produk hingga. disebut nilpotent jika ada beberapa sedemikian sehingga setiap produk dari elemen adalah nol.A i A i A N N ASEBUAH SEBUAHsaya SEBUAHsaya SEBUAH N N SEBUAH
Pertama, mari kita lihat mengapa kondisi Anda menyiratkan bahwa tidak berguna. Ini mengikuti dari Konig's Lemma (kekompakan): setiap string panjang atas alfabet sesuai dengan produk dengan panjang dengan cara yang jelas. Pertimbangkan pohon berakar -ary yang tak terbatas , yang simpul-simpulnya secara alami dalam korespondensi bijektif dengan string di atas . Pertimbangkan sub-tree terdiri dari simpul-simpul di mana produk yang sesuai dari adalah nol. Lemma Konig mengatakan bahwa jika n { 1 , ... , k } A 1 , ... , A kSEBUAH n { 1 , ... , k } SEBUAH1, ... , Ak k { 1 , ... , k } T A i T T N T An k { 1 , ... , k } T SEBUAHsaya T tidak terbatas, maka ia memiliki jalur tanpa batas (persis melanggar properti Anda), maka adalah terbatas. Kita kemudian dapat mengambil menjadi panjang maksimum string apapun dalam . Jadi, properti Anda menyiratkan bahwa bernilai.T N T SEBUAH
Kebalikannya juga benar, karena setiap elemen dari adalah kombinasi linear dari produk-produk dari .A iSEBUAH SEBUAHsaya
Selanjutnya, perhatikan bahwa adalah subalgebra dari matriks, dan karenanya adalah dimensi hingga. n × nSEBUAH n × n
Akhirnya: aljabar asosiatif dimensi terbatas dalam karakteristik nol memiliki dasar elemen nilpoten (komuter atau tidak - ini adalah bagian yang bertentangan dengan jawaban Yuval) jika itu nilpoten (lihat, misalnya, di sini ).
Dengan demikian, untuk menyelesaikan masalah Anda, temukan dasar untuk aljabar asosiatif yang dihasilkan oleh (oleh versi aljabar linier dari pencarian pertama yang luas) dan periksa bahwa setiap matriks dalam basis tidak ada potensi. Batas atas berasal dari penyelesaian sistem persamaan linear dalam variabel dalam pencarian pertama yang luasnya. Sebagai BFS tidak dapat bertahan lama, dan karena ini adalah matriks untuk memeriksa apakah matriks nilpoten, hanya perlu memeriksa bahwa .˜ O ( n 2 ω ) n 2 dim A ≤ n 2 n × n A A n = 0SEBUAHsaya HAI~( n2 ω) n2 redupSEBUAH≤ n2 n × n SEBUAH SEBUAHn= 0
sumber
Saya mendapat algoritma poli-waktu untuk masalah (masalah agak sepele) ini, yaitu untuk memeriksa apakah jari-jari spektral gabungan (JSR) adalah nol atau tidak, pada tahun 1995: http://en.wikipedia.org/wiki/Joint_spectral_radius
Kisah di balik algoritma kira-kira sebagai berikut: Blondel dan Tsitsiklis salah menyatakan bahwa untuk matriks boolean memeriksa apakah JSR <1 adalah NP-HARD. Untuk setiap set matriks bilangan bulat JSR adalah eter nol atau lebih besar atau sama dengan 1. Jadi contoh yang berlawanan dengan pernyataan mereka adalah algoritme saya (lihat errata di kertasnya). Moral utama: lihat dulu Wikipedia!
sumber
Pertanyaan yang Anda ajukan persis sama dengan memutuskan apakah jari-jari spektral gabungan (JSR) dari set matriks benar-benar kurang dari satu. Decidability dari pertanyaan ini tetap terbuka untuk beberapa waktu sekarang. (Dalam teori kontrol, ini setara dengan decidability stabilitas sistem linear yang diaktifkan di bawah arbitrary switching.)
Varian berikut dari pertanyaan Anda diketahui tidak dapat diputuskan: Dengan serangkaian matriks persegi yang terbatas, putuskan apakah semua produk tetap terikat; lihat di sini .
Keragu-raguan dari hal di atas tetap berlaku bahkan jika Anda hanya memiliki 2 matriks ukuran 47x47: lihat di sini .
Dalam bahasa JSR, pertanyaan tentang pengujian "apakah JSR ?" tidak dapat diputuskan (lihat referensi di atas), tetapi kesesuaian pengujian "apakah JSR ?" terbuka. Pertanyaan terakhir terkait dengan apa yang disebut "dugaan keterbatasan rasional": Jika dugaan keterbatasan rasional itu benar, maka pertanyaan yang Anda ajukan dapat dipilih.< 1≤1 <1
Akhirnya, kecuali P = NP, JSR tidak dapat diperkirakan dalam waktu polinomial (dalam arti yang tepat didefinisikan dalam makalah ini ).
Akibatnya, salah satu jawaban di atas yang mengklaim algoritma yang efisien harus salah.
Di sisi positif, ada beberapa algoritma (misalnya berdasarkan pemrograman semidefinite) untuk mendekati JSR. Algoritme yang berbeda datang dengan jaminan kinerja yang berbeda. Lihat misalnya berikut ini (tanpa malu-malu oleh saya dan rekan saya - tetapi lihat juga referensi di dalamnya ).
Dalam beberapa kasus khusus, pertanyaan yang Anda tanyakan adalah waktu polinomial yang dapat ditentukan. Misalnya, ketika matriks simetris, atau peringkat satu, atau jika mereka bepergian.
Akhirnya, buku yang bagus tentang hal ini adalah sebagai berikut .
sumber
Sunting: Sayangnya jawaban ini salah. Kesalahan disorot di bawah ini. Argumen itu berfungsi jika kita diizinkan untuk mengubah matriks.
Kami mulai dengan membuktikan lemma.
Kata pengantar singkat. Misalkan menjadi matriks dan misalkan menjadi matriks dengan yang ada di diagonal sekunder. Jika dan adalah nol untuk semua maka . Kesimpulan yang benar: adalah segitiga atas dengan nol pada diagonal. (Kesimpulan asli dipulihkan jika kita juga diizinkan untuk menggandakan dengan kekuatan transpos )n ×A N n × nn×n N n×n N t A t ≥ 0 A = 0 A NANt NtA t≥0 A=0 A N
Bukti. Misalkan misalnya bahwa , dan tulis Kita mulai dengan menghitung : Matriks ini berbentuk segitiga, dan jika nilpoten maka . Lanjutkan dengan : A = ( a b c d e f g h i ) ,n=3 AN2AN2=( 0 0 a 0 0 d 0 0 g ). AN2g= b 0 d e 0 0 h ). AN1N
Jika sekarang kita mempertimbangkan sebagai gantinya, maka kami menyimpulkan bahwa adalah segitiga yang lebih rendah dengan nol pada diagonal. Sebenarnya, kami tidak mendapatkan sesuatu yang baru dari mempertimbangkan . Karena itu .N2A,N1A,N0A A NtA A=0 □
Beginilah buktinya jika versi asli dari lemma itu benar. Sekarang kembali ke masalah yang dihadapi. Katakanlah bahwa matriksmemenuhi properti P jika untuk setiap urutan tanpa batas, kami memilikiuntuk beberapa. Jika salah satu dari matriksadalah tidak nilpoten properti maka P jelas gagal, sehingga menganggap bahwa semua matriks yang nilpotent. Jika semua matriks bepergian maka properti P dengan jelas dipegang, jadi misalkan. Ubah dasar sehinggadalam bentuk normal Jordan, dan biarkan dekomposisi yang sesuai dari ruang vektor menjadii 1 , … ∈ [ k ] A i 1 ⋯ A i m = 0 m A iA1,…,Ak i1,…∈[k] Ai1⋯Aim=0 m Ai A1A2≠A2A1 A1 V1⊕⋯⊕Vt . Biarkan menjadi ruang vektor di mana ; perhatikan bahwa sejak dengan segalanya. Terbatas untuk , dan . Karenanya, lemma menyiratkan bahwa untuk beberapa , baik atau tidak , dan oleh karena itu properti P jelas gagal.Vi A1A2≠A2A1 dimVi>1 V i A 1 = N A 2 ≠ 0 t ≥ 0 A 2 A t 10 Vi A1=N A2≠0 t≥0 A2At1 At1A2
Ringkasnya, properti P berlaku jika semua matriks nilpoten dan semuanya berpindah-pindah.
sumber