# Matrices with distinct columns

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

• Which are the columns and which are the rows? – Wlod AA Nov 30 '18 at 5:02
• Maybe I misunderstand your question, but the columns are vertical and rows horizontal. – Puck Rombach Nov 30 '18 at 5:09
• When the first index $\ i\$ of $\ a_{i\ j}\$ is fixed, is it the $i$-th column or the $i$-th raw? – Wlod AA Nov 30 '18 at 5:22
• That would be $i$th row. – Puck Rombach Nov 30 '18 at 5:24
• Thank you. Euclidean xy are usually different from matrix xy, but not always, I think. I felt always uneasy about that xy business. – Wlod AA Nov 30 '18 at 5:27

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.