# 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
• 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
• Over finite fields, testing if an $n\times k$ matrix is $k$-regular is equivalent to checking whether an $n\times k$ code generator matrix has minimum distance $n-k+1$ (i.e., whether it is MDS). Even constant factor approximations for finding the minimum code distance are hard. Check this paper ee.ucr.edu/~dumer/ieee49-1-03-np.pdf and the references inside. – Dimitris Apr 23 '12 at 6:39

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
Consider an $n \times m$ matrix $A$, $n < m$. Without loss of generality, assume that $\text{rank}(A) = n$ and the first $n$ columns of $A$ are independent: $A =[B\ |\ D]$, where $B$ is a nonsingular $n \times n$ matrix. Now, $A$ contains a singular $n \times n$ submatrix if and only if $B^{-1}D$ is not totally regular.