# Hamming distance of binary strings

Assume I have all possible $2^N$ binary strings of length $N$ as rows in a matrix $M$, i.e., $M \in \{0,1\}^{{2^N}\times N}$. I'm interested in the column-wise Hamming distances of $M$ and its properties.

Obviously, for all $N > 1$, the hamming distance $d_h$ of any two selected columns of $M$ is $>0$, i.e., $d_h(a,b) > 0$ where $a, b$ are two distinct columns of $M$.

Also, if $N = 3$ then $d_h(a,b) = 4$. Similary, if $N = 4$ then $d_h(a,b) = 8$. In general is it the case that for $N>1$, $d_h(a,b) = 2^{N-1}~\forall a \neq b$?

Also, what if in an iterative manner I start selecting a row randomly and removing it from $M$. Hence at iteration $t$, I have randomly selected and removed $t$ binary strings from $M$. I'm trying to show that as $t$ increases $d_h$ decreases at the worst case scenario.

Will the following statement be precise in explaning this: $\exists a,b$ such that $lim_{t\to N} d_h(a,b)=0$. Also, it may be obvious, but how can I approach to prove the above statement more formally?

If you take any two columns, half their entries will match and half will not match. So since you have $2^N$ strings, that means hamming distance is $2^{N-1}$.
Similarly remove the half of strings that have a '0' in one fixed position. Then the hamming distance will be $2^{N-2}$.
• I see! Thanks! Can I derive a bound (a worst case scenario) on $d_h$ if I randomly remove $T$ strings? – Kenshin Mar 18 '15 at 22:16