# Matrix subspace with full rank

Suppose two integers $n< m$, and one is given a matrix subspace of $n\times m$ complex matrices, says $S$.

I am asking for algorithms or conditions which can answer the following question:

Whether every non-zero element of $S$ has rank $n$?

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$.

• My first thought was that this looks awfully similar to the Flanders theorem and its generalizations and I was about to ask whether you can allow rank $\leq n$ instead of precisely $n$. Can you? (I guess not). – Felix Goldberg Nov 1 '12 at 11:19
• @Felix, I guess not, since all $n\times m$ matrix has rank less or equal to $n$. – gondolf Nov 1 '12 at 11:23

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.

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 » ( http://dx.doi.org/10.1145%2f1837934.1837984 )

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.

• @Lierre, thank you Lierre, notice here we consider the rank is $n$ over $n\times m$ matrices space, isn't this constraint helpful? – gondolf Nov 1 '12 at 11:15
• @gondolf — That is certainly a simplifying constraint, but I think the difficulty remains essentially the same. – Lierre Nov 2 '12 at 8:38

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$

• And this one can do (in principle!) using Groebner bases. – Mariano Suárez-Álvarez Nov 1 '12 at 4:16
• @Dima @Mariano, thank you for your answer, this seems very complicated. Is there any simpler characterization? – gondolf Nov 1 '12 at 5:45
• no, that's basically as simple as it gets in general. You can do some ad hoc things like finding invertible $n\times n$ (resp. $m\times m$) matrices $U$ and $V$ so that $U\dot S\dot V$ looks simpler than $S$, and so that the system of polynomial equations gets sparser. – Dima Pasechnik Nov 1 '12 at 6:04