1
$\begingroup$

You're given a $0-1$ $n\times n$ matrix such that for every distinct columns $C_i$ and $C_j$, $d_H(C_i,C_j)\gt 2t$ for some $t$. What could be said about the Hamming distances of the rows? It it true for instance that there are two distinct rows $R_k$ and $R_l$ that satisfy $d_H(R_k,R_l)\lt n-t$?

$\endgroup$
1
$\begingroup$

The condition on the columns implies that $2t < n$. Suppose that the condition on the rows is not satisfied. The rows therefore form a code of minimal distance at least $n-t > n/2$ of size $n$. The Plotkin bound implies that unless $n-t$ is extremely close to $n/2$, such a code cannot exist. If $t$ is very close to $n/2$, however, the columns form a code of minimal distance close to $n$, which is again ruled out by the Plotkin bound (except perhaps for very small $n$).

I'll let you fill up the details and check for which $n$ this argument works.

| cite | improve this answer | |
$\endgroup$

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.