3
$\begingroup$

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

$\endgroup$
2
  • $\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$ Nov 1, 2012 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, 2012 at 11:23

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2012 at 11:15
  • $\begingroup$ @gondolf — That is certainly a simplifying constraint, but I think the difficulty remains essentially the same. $\endgroup$
    – Lierre
    Nov 2, 2012 at 8:38
1
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ And this one can do (in principle!) using Groebner bases. $\endgroup$ Nov 1, 2012 at 4:16
  • $\begingroup$ @Dima @Mariano, thank you for your answer, this seems very complicated. Is there any simpler characterization? $\endgroup$
    – gondolf
    Nov 1, 2012 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$ Nov 1, 2012 at 6:04

Your Answer

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

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