Let $V$ be the set of $k$ by $n$ matrices ($k<n$) with entries in $\mathbb{C}$, and let $\mathbb{C}[V]$ denote the set of polynomial functions on $V$. For any subset $I \subseteq [n] = \{1,2,\dotsc, n\}$ with size $k$ let $e_I$ be the function which evaluates the determinant of the $k$ by $k$ submatrix found by taking only columns indexed by elements of $I$.

Let $A$ be a $k$ by $n$ matrix. It's well known that $$e_I(A) = 0 \text{ for all } I \subseteq [n], |I|=k \Rightarrow \operatorname{rank}(A)<k.$$ Moreoever, one can find an example of a matrix $A_I$ for which $e_J(A_I) \neq 0$ if and only if $I=J$, so no proper subset of $S:=\{e_I: I \subseteq [n], |I|=k\}$ suffices to check the rank of $A$.

If we allow linear combinations of the elements of $S$ we can sometimes get away with fewer functions. The smallest nontrivial example arises when $k=2$, $n=4$. There we have the Plücker relation $$e_{1,2}e_{3,4}-e_{1,3}e_{2,4}+e_{1,4}e_{2,3} = 0.$$ This implies that the vanishing of $$\{e_{1,2}-e_{3,4},e_{1,3},e_{2,4},e_{1,4},e_{2,3}\}$$ is sufficient to show a $2$ by $4$ matrix has rank $<2$.

Let's call a set of linear combinations of $e_I$ with the property above a "rank-detecting set", and write $\beta(k,n)$ for the size of the smallest rank detecting set for $k$ by $n$ matrices. Clearly $\beta(k,n) \leq \binom n k$. It's quite easy to show that $\beta(n-1,n) = n$, and the example above shows that $\beta(2,4) \leq 5$.

Have you come across this notion before? Is anything known in general about the numbers $\beta(k,n)$?

`\binom n k`

or, if you want a bigger version, $\dbinom n k$`\dbinom n k`

, not as $\begin{pmatrix} n \\ k \end{pmatrix}$`\begin{pmatrix} n \\ k \end{pmatrix}`

. $\endgroup$