|
2
1
|
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$. |
||||||
|
|
4
|
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. |
|||
|
1
|
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$ |
|||||||||
|
