19

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?

Markus Bläser
  • 2,938
  • 18
  • 19
  • 7
    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
  • 5
    Indeed, there are three different meanings of regular: http://en.wikipedia.org/wiki/Regular_matrix – Suresh Venkat Apr 17 '12 at 01:58
  • regular = full rank, I edited the question – Markus Bläser Apr 17 '12 at 10:46
  • 2
    ah, found the related question: http://cstheory.stackexchange.com/questions/10962/constructing-vectors-in-general-position. 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
  • 1
    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 http://www.ee.ucr.edu/~dumer/ieee49-1-03-np.pdf and the references inside. – Dimitris Apr 23 '12 at 06:39

3 Answers3

13

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.

Bruno
  • 4,449
  • 33
  • 45
  • 1
    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
6

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.

Sasho Nikolov
  • 18,189
  • 2
  • 67
  • 115
leonid gurvits
  • 251
  • 2
  • 2
3

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.

leonid gurvits
  • 251
  • 2
  • 2