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?

  • 7
    $\begingroup$ An elementary question: what do you mean when you say regular matrix? Thanks! $\endgroup$
    – Henry Yuen
    Commented Apr 16, 2012 at 23:03
  • $\begingroup$ do you mean that every submatrix is non-singular? i recall there was a similar question that i can't find right now $\endgroup$ Commented Apr 16, 2012 at 23:21
  • 5
    $\begingroup$ Indeed, there are three different meanings of regular: en.wikipedia.org/wiki/Regular_matrix $\endgroup$ Commented Apr 17, 2012 at 1:58
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Apr 17, 2012 at 15:14
  • 1
    $\begingroup$ 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. $\endgroup$
    – Dimitris
    Commented Apr 23, 2012 at 6:39

3 Answers 3


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.

  • 1
    $\begingroup$ 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... $\endgroup$ Commented Apr 18, 2012 at 22:45

Yes, your problem is essentially equivalent to the one (General Position) in the Alexander Chistov, Hervé Fournier, Leonid Gurvits and Pascal Koiran paper.

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.


There is another NP-Complete problem in the same spirit: for a square matrix to decide whether all its principal submatrices(i.e. rows and columns from the same set) are nonsingular. Another curious fact: sum of squares of determinants of all square submatrices is easy(just Det(I + AA^{T})), but the sum of absolute values is #P-Complete.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.