# Complexity of deciding whether a matrix is totally regular

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?

-
An elementary question: what do you mean when you say regular matrix? Thanks! –  Henry Yuen Apr 16 '12 at 23:03
do you mean that every submatrix is non-singular? i recall there was a similar question that i can't find right now –  Sasho Nikolov Apr 16 '12 at 23:21
Indeed, there are three different meanings of regular: en.wikipedia.org/wiki/Regular_matrix –  Suresh Venkat Apr 17 '12 at 1:58
regular = full rank, I edited the question –  Markus Bläser Apr 17 '12 at 10:46
ah, found the related question: cstheory.stackexchange.com/questions/10962/…. your question fits more closely the comment I made there: this is an easier variant of the (wide open AFAIK) question of testing the restricted isometry party. –  Sasho Nikolov Apr 17 '12 at 15:14
show 1 more comment

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.
Thanks, Bruno! Can't we reduce the problem of your answer to my problem by a randomized reduction (over the rationals)? Just add $m-n$ random rows. If the new matrix is not totally regular, then it contains a singular $n \times n$-submatrix in the first $n$ rows with high probability. Ah, no. The submatrix could be smaller. But maybe one can make this work... –  Markus Bläser Apr 18 '12 at 22:45