The problem takes as input an $m \times 2n$ matrix $A$ over $\mathbb{F}_2$.
Optimization version: find a subset of exactly $n$ columns so that the corresponding submatrix (taking only selected columns) has minimum rank over $\mathbb{F}_2$.
Decisional version: given the matrix $A$ and an integer $k$, is there a subset of $n$ columns of rank less than $k$ over $\mathbb{F}_2$.?
This problem seems NP-hard. The question is: why?