Complexidade de decidir se uma matriz é totalmente regular

Uma matriz é chamada totalmente regular se todas as suas submatrizes quadradas tiverem classificação completa. Tais matrizes foram usadas para construir superconcentradores. Qual é a complexidade de decidir se uma determinada matriz é totalmente regular sobre os racionais? Sobre campos finitos?

Mais geral, chame uma matriz de totalmente regular se todas as suas submatrizes quadradas de tamanho, no máximo, k tiverem uma classificação completa. Dada uma matriz e um parâmetro k , qual é a complexidade de decidir se a matriz é totalmente k- regular?$k$$k$$k$$k$

O artigo Vandermonde Matrices, NP-Completeness e Transversal Subspaces [ps] de Alexander Chistov, Hervé Fournier, Leonid Gurvits e Pascal Koiran pode ser relevante para a sua pergunta (embora ela não responda).

Eles provar o -completeness do seguinte problema: Dado um n × m matriz sobre Z ( n ≤ m ), decidir se existe um n x n submatriz cujo determinante desaparece.$\mathsf{NP}$$n\times m$$\mathbb Z$$n\le m$$n\times n$

Sim, o problema é essencialmente equivalente ao (General Position) no Alexander Chistov, Hervé Fournier, Leonid Gurvits e Pascal Koiran papel .

Considere uma matriz A , n < m . Sem perda de generalidade, suponha que a classificação ( A ) = n e as primeiras n colunas de A sejam independentes: A = [ B | D ] , onde B é uma matriz n × n não singular . Agora, A contém uma submatriz singular n × n se e somente se B - 1$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$ não é totalmente regular.

Há outro problema NP-Complete no mesmo espírito: para uma matriz quadrada decidir se todas as suas principais submatrizes (isto é, linhas e colunas do mesmo conjunto) são não singulares. Outro fato curioso: a soma dos quadrados dos determinantes de todas as sub-matrizes quadradas é fácil (apenas Det (I + AA ^ {T})), mas a soma dos valores absolutos é # P-Completa.