<p>Yes, your problem is essentially equivalent to the one (General Position) in the Alexander Chistov, Hervé Fournier, Leonid Gurvits and Pascal Koiran <a href="http://perso.ens-lyon.fr/pascal.koiran/Publis/lip.02-31.ps">paper</a>.</p>

<p>Consider an $n \times m$ matrix $A$, $n &lt; 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. </p>

CC BY-SA 3.0
2014-02-21T01:06:07.667Z
2014-02-21T02:43:57.577Z
2014-02-21T02:43:57.577Z
leonid gurvits
<p>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.</p>

CC BY-SA 3.0
2014-02-21T01:14:38.173Z
2014-02-21T16:37:49.007Z
2014-02-21T16:37:49.007Z
leonid gurvits
<p>The paper <strong>Vandermonde Matrices, NP-Completeness, and Transversal Subspaces</strong> <a href="http://perso.ens-lyon.fr/pascal.koiran/Publis/lip.02-31.ps">[ps]</a> by Alexander Chistov, Hervé Fournier, Leonid Gurvits and Pascal Koiran may be relevant to your question (though it does not answer it).</p>

<p>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. </p>

CC BY-SA 3.0
2012-04-18T22:45:33.763Z
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
CC BY-SA 3.0
2012-04-17T07:48:04.197Z
2012-04-17T07:48:04.197Z
Bruno
<p>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?</p>

<p>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?</p>

CC BY-SA 3.0
2012-04-16T23:03:20.273Z
An elementary question: what do you mean when you say regular matrix? Thanks!
Henry Yuen
CC BY-SA 3.0
2012-04-16T23:21:43.947Z
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
CC BY-SA 3.0
2012-04-17T01:58:58.360Z
Indeed, there are three different meanings of regular: http://en.wikipedia.org/wiki/Regular_matrix
Suresh Venkat
CC BY-SA 3.0
2012-04-17T10:46:13.633Z
regular = full rank, I edited the question
Markus Bläser
CC BY-SA 3.0
2012-04-17T15:14:38.703Z
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
CC BY-SA 3.0
2012-04-23T06:39:41.423Z
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
<cc.complexity-theory><reference-request><linear-algebra><matrices>
Complexity of deciding whether a matrix is totally regular
Markus Bläser
# Complexity of deciding whether a matrix is totally regular

(Asked by: username_0 on 2012-04-16)

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?

**Tags:** cc.complexity-theory, reference-request, linear-algebra, matrices

> **Comments:**
> **username_1**: An elementary question: what do you mean when you say regular matrix? Thanks!  
> **username_2**: do you mean that every submatrix is non-singular? i recall there was a similar question that i can't find right now  
> **username_3**: Indeed, there are three different meanings of regular: http://en.wikipedia.org/wiki/Regular_matrix  
> **username_0**: regular = full rank, I edited the question  
> **username_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.  
> **username_4**: 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.  

---

## 3 answers

### Answer by username_6 on 2012-04-17. Score: 13 | Accepted answer

The paper **Vandermonde Matrices, NP-Completeness, and Transversal Subspaces** [[ps]](http://perso.ens-lyon.fr/pascal.koiran/Publis/lip.02-31.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.

> **Comments:**
> **username_0**: Thanks, username_6! 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...  

---

### Answer by username_5 on 2014-02-21. Score: 6

Yes, your problem is essentially equivalent to the one (General Position) in the Alexander Chistov, Hervé Fournier, Leonid Gurvits and Pascal Koiran [paper](http://perso.ens-lyon.fr/pascal.koiran/Publis/lip.02-31.ps).

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.


---

### Answer by username_5 on 2014-02-21. Score: 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.


---

