Matrices with distinct columns

Question

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 }.$$

Answer 1

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.