0

Consider a binary matrix $\mathbf A_n$ corresponding to values $0$ to $2^n-1$ where each row represents a length $n$ binary representation of a real number. For example, for $n=3$ we have

$\mathbf A_3=\begin{bmatrix} 0 & 0 & 0\\ 1 & 0 & 0\\ 0 & 1 & 0\\ 1 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 1\\ 0 & 1 & 1\\ 1 & 1 & 1 \end{bmatrix}.$

Consider two arbitrary non-zero binary vectors $\mathbf v_1, \mathbf v_2$ of length $n$ (column vector) such that $\mathbf v_1\neq\mathbf v_2$. Now, assume $\mathbf u_1=\mathbf A\mathbf v_1$ (mod $2$) and $\mathbf u_2=\mathbf A\mathbf v_2$ (mod $2$) . I can verify for an arbitrary $n$ that $\mathbf u_1.^*\mathbf u_2$ (element-wise multiplication) has always $2^{n-2}$ ones. For example, for $\mathbf A_5$ and $$ \mathbf v_1=\begin{bmatrix}0,\ 0,\ 1,\ 1,\ 1\end{bmatrix}^T, \mathbf v_2=\begin{bmatrix}0,\ 1,\ 0,\ 0,\ 0\end{bmatrix}^T $$ We have $$ \mathbf u_1.^*\mathbf u_2=\begin{bmatrix} 0\ 0\ 0 \ 0 \ 0 \ 0\ 1 \ 1\ 0 \ 0 \ 1 \ 1 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0\ 1\ 1\ 0 \ 0 \ 0\ 0 \ 0\ 0 \ 0 \ 0 \ 0 \ 0\ 1\ 1\end{bmatrix}^T $$ of length $2^5$ which has $2^{5-2}=8$ ones. I am looking for an analytical way to prove this.

nOp
  • 179

2 Answers2

0

We can start by observing that $\mathbf u_i$ has $2^{n-1}$ 1s because if we take any set bit of $\mathbf v_i$ we can pair up the rows of $\mathbf A_n$ which differ in that bit and the corresponding rows of $\mathbf v_i$ will also differ.

So essentially what we want to do is show that the different $\mathbf u_i$ are independent.

We can use the same approach, doubled up. Let $x_1$ be the index of a bit which is set in $\mathbf v_1$ but not in $\mathbf v_2$, and $x_2$ vice versa. Group the rows of $\mathbf A_n$ into groups of four such that in each group they differ only in those two indices. Then two of the corresponding rows of each $\mathbf u_i$ will be 0 and two will be 1, but the index which determines the parity is different, so exactly one of the four has a double-1.

Peter Taylor
  • 13,425
0

Let us choose random row vector $x_i$ of $A_n$ uniformly at random. Then $x_i \cdot v_1$ is $0$ or $1$ with equal probability and similarly for $v_2$. Since both situations are independent, the probability that both are one is equal to $\frac{1}{4}$. And therefore the number of positions where both $u$s are one is equal to $\frac{1}{4} \cdot 2^n=2^{n-2}$.

Bartek
  • 2,475