Given a family of matrices $M$ with entries in $\mathbb{F}_2$ find the subset $N \subseteq M $ such that the rank of the matrix $$A = \sum_{m \in N}m $$ is minimal.
I am wondering if anyone have seen this kind of problem or anything related before. It could of course also be viewed as some kind of graph problem so it might have be studied in that contexts as well.
This is a homogeneous variant of the minrank problem over $\mathbb{F}_2$. We looked at it in the following paper: M. Bläser et al, "On the Orbit Closure Containment Problem and Slice Rank of Tensors", SODA 2021, 2565—2584. It is NP-hard to decide if the minimal rank is 1, and it is also NP-hard to decide for $n$ matrices of size $(2n+1)\times (2n+1)$ if the rank is less than half of the size.
Similar problems are also used in cryptography (see for example Faugère et al, "Cryptanalysis of MinRank", CRYPTO 2008), but they are usually nonhomogeneous (there is one matrix you must take).
