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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.