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