Let $M$ be an $n \times m$ matrix over $\mathbb{F}\_2$ with no repeated columns, and suppose that $m \leq 2^{n-1}$: *i.e.*, it is possible to have a matrix with fewer rows that still has $m$ unique columns.


Is it always possible to find such a smaller matrix by taking a linear combination of the rows of $M$?


For example, $M=\pmatrix{1 & 0 & 0 \\ 0 & 1 &0 \\ 1 & 0 & 1}$ has distinct columns, but we can find a smaller matrix with distinct columns by taking 
$$\pmatrix{1 & 1 & 0 \\ 0 & 0 &1 }\pmatrix{1 & 0 & 0 \\ 0 & 1 &0 \\ 1 & 0 & 1} = \pmatrix{1 & 1 & 0 \\ 1 & 0 &1 }.$$



Matrices with distinct columns
It is the same as asking whether given $m\le 2^{n-1}$ distinct vectors $v\_j$ in $\mathbb F\_2^n$ you can find $n-1$ vectors $w\_1,\dots,w\_{n-1}$ such that for each $j\ne k$, we have $w\_\ell\cdot(v\_j-v\_k)\ne 0$ for some $\ell$. You are clearly in trouble if $v\_i-v\_j$ run over the entire $\mathbb F\_2\setminus\{0\}$ (and only then because you can represent any $1$-dimensional space as a solution of a system of $n-1$ linear equations). Unfortunately, the number of pairs can be large enough to make it possible if $n$ is large. Just take the union of 2 complementary subspaces of dimension about $n/2$ to get $m\approx 2^{n/2+1}$ vectors whose pairwise differences give you everything except $0$. So you are fine if $n=2,3$ or if $m\le 2^{n/2}$, say, but not in general.


