19
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 7
    $\begingroup$ An elementary question: what do you mean when you say regular matrix? Thanks! $\endgroup$
    – Henry Yuen
    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$
    – Sasho Nikolov
    Apr 16, 2012 at 23:21
  • 5
    $\begingroup$ Indeed, there are three different meanings of regular: en.wikipedia.org/wiki/Regular_matrix $\endgroup$
    – Suresh Venkat
    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$
    – Sasho Nikolov
    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
    Apr 23, 2012 at 6:39

3 Answers 3

Reset to default
13
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 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$
    – Markus Bläser
    Apr 18, 2012 at 22:45
6
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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