A matrix is called totally regular if all its square submatrices have full rank. Such matrices were used to construct superconcentrators. What is the complexity of deciding whether a given matrix is totally regular over the rationals? Over finite fields?More general, call a matrix totally $k$-regular if all its square submatrices of size at most $k$ have full rank. Given a matrix and a parameter $k$, what is the complexity of deciding whether the matrix is totally $k$-regular?
Complexity of deciding whether a matrix is totally regular
cc.complexity theory;reference request;linear algebra;matrices
The paper Vandermonde Matrices, NP-Completeness, and Transversal Subspaces [ps] by Alexander Chistov, Herv Fournier, Leonid Gurvits and Pascal Koiran may be relevant to your question (though it does not answer it).They prove the $\mathsf{NP}$-completeness of the following problem: Given an $n\times m$ matrix over $\mathbb Z$ ($n\le m$), decide whether there exists a $n\times n$ submatrix whose determinant vanishes. 