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

  • $\begingroup$ 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). $\endgroup$ – Felix Goldberg Nov 1 '12 at 11:19
  • $\begingroup$ @Felix, I guess not, since all $n\times m$ matrix has rank less or equal to $n$. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ @Lierre, thank you Lierre, notice here we consider the rank is $n$ over $n\times m$ matrices space, isn't this constraint helpful? $\endgroup$ – gondolf Nov 1 '12 at 11:15
  • $\begingroup$ @gondolf — That is certainly a simplifying constraint, but I think the difficulty remains essentially the same. $\endgroup$ – 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$

| cite | improve this answer | |
  • $\begingroup$ And this one can do (in principle!) using Groebner bases. $\endgroup$ – Mariano Suárez-Álvarez Nov 1 '12 at 4:16
  • $\begingroup$ @Dima @Mariano, thank you for your answer, this seems very complicated. Is there any simpler characterization? $\endgroup$ – gondolf Nov 1 '12 at 5:45
  • $\begingroup$ 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. $\endgroup$ – Dima Pasechnik Nov 1 '12 at 6:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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