Matrix subspace with full rank - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T06:04:57Z http://mathoverflow.net/feeds/question/111098 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/111098/matrix-subspace-with-full-rank Matrix subspace with full rank gondolf 2012-11-01T03:10:30Z 2012-11-05T00:53:00Z <p>Suppose two integers $n&lt; m$, and one is given a matrix subspace of $n\times m$ complex matrices, says $S$.</p> <p>I am asking for algorithms or conditions which can answer the following question:</p> <p>Whether every non-zero element of $S$ has rank $n$?</p> <p>Notice that any $n\times m$ complex matrix has rank less or equal to $n$, here we want the rank of the space is exactly $n$.</p> http://mathoverflow.net/questions/111098/matrix-subspace-with-full-rank/111106#111106 Answer by Dima Pasechnik for Matrix subspace with full rank Dima Pasechnik 2012-11-01T04:11:02Z 2012-11-01T04:11:02Z <p>An obvious answer is to look at the $n\times n$ minors. At least one of them must be non-zero for a nonzero element of $S$. Assuming that your subspace is given parametrically, i.e. you have $S=${$\sum t_{ij} S_{ij}$}, for $S_{ij}\in \mathbb{C}^{n\times m}$, $1\leq i\leq n$, $1\leq j\leq m$. Then you have to check that the only solution of the system of equations $$\det (\sum t_{ij} S_{ij})_J, \quad J\in \binom{[1..m]}{n},$$ where $A_J$ denotes the $n\times n$-minor corresponding to the columns in the set $J$, in $t_{ij}$, which take values in $\mathbb{C}^{n\times m}$, is $(t_{ij})=0$</p> http://mathoverflow.net/questions/111098/matrix-subspace-with-full-rank/111119#111119 Answer by Lierre for Matrix subspace with full rank Lierre 2012-11-01T07:19:51Z 2012-11-01T10:41:34Z <p>Your problem is known as the MinRank problem : given a linear subspace $V$ of matrices and an integer $r$, determine the locus of matrices of $V$ of rank less than $r$, or decide if it is empty or not. Over finite fields, the decision problem is known to be NP-Hard.</p> <p>You may find this paper interesting : Jean-Charles Faugère, Mohab Safey El Din, Pierre-Jean Spaenlehauer, « Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology » ( <a href="http://dx.doi.org/10.1145%2f1837934.1837984" rel="nofollow">http://dx.doi.org/10.1145%2f1837934.1837984</a> )</p> <p>They explore to different formulations of the problem in term of polynomial systems, the first one being the formulation of the previous answer by Dima Pasechnik.</p>