Kompleksitas memutuskan apakah sebuah matriks benar-benar teratur

Matriks disebut benar-benar teratur jika semua submatrians kuadratnya memiliki peringkat penuh. Matriks seperti itu digunakan untuk membangun superkonsentrator. Apa kompleksitas memutuskan apakah matriks yang diberikan benar-benar teratur di atas rasionalitas? Lebih dari bidang yang terbatas?

Lebih umum, panggil sebuah matriks yang sama sekali reguler jika semua ukuran persegi dari kebanyakan memiliki peringkat penuh. Diberikan matriks dan parameter , apa kompleksitas menentukan apakah matriks tersebut benar-benar reguler?$k$$k$$k$$k$

Makalah Vandermonde Matriks, NP-Kelengkapan, dan Subruang Transversal [ps] oleh Alexander Chistov, Hervé Fournier, Leonid Gurvits dan Pascal Koiran mungkin relevan dengan pertanyaan Anda (meskipun tidak menjawabnya).

Mereka membuktikan -kelengkapan dari masalah berikut: Diberikan matriks lebih dari ( ), putuskan apakah ada submatrix yang determinannya menghilang.$\mathsf{NP}$$n\times m$$\mathbb Z$$n\le m$$n\times n$

Ya, masalah Anda pada dasarnya setara dengan satu (Posisi Umum) di Alexander Chistov, Hervé Fournier, Leonid Gurvits dan kertas Pascal Koiran .

Pertimbangkan matriks , . Tanpa kehilangan sifat umum, asumsikan bahwa dan yang pertama$n \times m$$A$$n < m$$\text{rank}(A) = n$$n$$A$$A =[B\ |\ D]$$B$$n \times n$$A$$n \times n$$B^{-1}D$

Ada masalah NP-Lengkap lain dalam semangat yang sama: untuk matriks kuadrat untuk memutuskan apakah semua submatrices utamanya (yaitu baris dan kolom dari set yang sama) adalah nonsingular. Fakta aneh lainnya: jumlah kuadrat dari determinan semua submatrices persegi itu mudah (hanya Det (I + AA ^ {T})), tetapi jumlah nilai absolutnya adalah # P-Complete.