Your problem is know known as the MinRank problem : given a linear subspace $V$ of matrices and an integer $r$, determine the locus where of matrices of your subspace $V$ of rank less than $r$. r$, or decide if it is empty or not. Over finite fields, the decision problem to just decide is this locus is empty or not is known as being to be NP-Hard. You might 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 formulation formulations of the problem in term of polynomial systems, the first one being the formulation of the previous answer by Dima Pasechnik. 1 Your problem is know as the MinRank problem : given a linear subspace of matrices and an integer$r$, determine the locus where of matrices of your subspace of rank less than$r\$. Over finite fields, the problem to just decide is this locus is empty or not is known as being NP-Hard.