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