Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 14 down vote favorite

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?

share|improve this question
5  
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
4  
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
2  
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

1 Answer

up vote 9 down vote

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.

share|improve this answer
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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