[Math] Finding minimum distance from a large parity check matrix

Question

Let $C$ be the linear code that has parity check matrix formed from all possible columns of weight 3 and length 5. We want to show that $d_{H}(C)=4$.

My first instinct would be to show that $d_{H}(C)\geq 4$ by showing no set of $3$ columns sum to $0$, but this would require $10 \choose 3$ checks, so is obviously unfeasible.

Answer 1

showing no set of $3$ columns sum to $0$, but this would require $10 \choose 3$ checks, so is obviously unfeasible.

Actually, that's the way. Assume that there exists such three columns : $a + b + c = 0 \implies a+b=c$

But that's impossible:

Let $t$ be the positions where $a$ and $b$ have an one in common. Then $w(a+b)=w(a)+w(b)-2 t = 6 -2t$ which is even for any $t$. Then $w(c) \ne 3$.

Of course, you must also discard the case where there are less that 3 columns that sum to $0$, but that's easy.