Number of ones in Binary matrix multiplication 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.
 A: By induction:
You've checked the base case manually.
Suppose true for $n$. In the case $n+1$, we select nonzero $v \neq w$. $v$ differs from $w$ in at least one entry, say the $i$th entry. Consider the vectors $\tilde{v}, \tilde{w}$ that have their $i$th entry deleted:
\begin{align}
\tilde{v} &= (v_1, \dots, v_{i-1}, v_{i+1},\dots, v_{n+1})
\\
\tilde{w} &= (w_1, \dots, w_{i-1}, w_{i+1},\dots, w_{n+1})
\end{align} 

Case1
Suppose $\tilde{v} \neq \tilde{w}$. Then the induction hypothesis applies and the element-wise product of $A_n \tilde{v}$ with $A_n \tilde{w}$ has $2^{n-2}$ entries that are 1. 
$A_{n+1}$ can be created by forming the matrix 
\begin{align}
\begin{pmatrix}
A_n \\
A_n
\end{pmatrix}
\end{align}
and then inserting an $i$-th column with $n$ entries that are 0 and $n$ entries that are 1. Convince yourself that this enumerates exactly all of the rows of $A_{n+1}$ (possibly permuted, but this won't change our conclusions). 
For the $n$ rows where the $i$th entry of $A_{n+1}$ is 0, nothing has changed from the $n$ case when we calculate $A_n \tilde{v}$ and $A_n \tilde{w}$ - we will still get $2^{n-2}$ entries that are 1 in the element-wise product.
For the $n$ rows where the $i$th entry of $A_{n+1}$ is 1, we have to do a little more work. Since $v$ and $w$ differ in the $i$-th entry, without loss of generality, assume that $v_i = 0, w_i = 1$. Then we have for an arbitrary $j$th row of this part of $A_{n+1}$
\begin{align}
(A_n \tilde{v})_j &= 0 \implies  (A_{n+1} v)_j = 0
\\
(A_n \tilde{v})_j &= 1 \implies  (A_{n+1} v)_j = 1
\\
(A_n \tilde{w})_j &= 0 \implies  (A_{n+1} w)_j = 1
\\
(A_n \tilde{w})_j &= 1 \implies  (A_{n+1} w)_j = 0
\end{align}
Lemma: I claim that $2^{n-1}$ entries of $A_n \tilde{v}$ were 1. 
Since we know that $2^{n-2}$ entries of $A_n \tilde{v}$ and $A_n \tilde{w}$ were simultaneously 1, this means that $2^{n-2}$ entries of $A_n \tilde{v}$ were 1 while $A_n \tilde{w}$ was 0. Then these are precisely the entries where $A_{n+1} v$ and $A_{n+1} w$ are simultaneously 1. This means that we have $2^{n-2}$ entries of the element-wise product that are 1, from the rows of $A_{n+1}$ where column $i$ is 1.
Altogether, if I can prove my Lemma, combining the count from the rows of $A_{n+1}$ where column $i$ is 0 and 1, we have $2^{n-2}+2^{n-2} = 2^{(n+1)-2}$ entries of the element-wise product that are 1, as desired.

Proof of Lemma: 
$\tilde{v}$ has, say $k$ entries that are 1. Then we are interested in rows of $A_n$ with an odd number of 1's that coincide with the entries of $v$ that are 1. There are 
\begin{align}
\begin{pmatrix}
k \\
1
\end{pmatrix}
\end{align}
$k$-tuples that have precisely a single 1 in them,
\begin{align}
\begin{pmatrix}
k \\
3
\end{pmatrix}
\end{align}
$k$-tuples that have precisely three 1's in them, etc. So there are 
\begin{align}
2^{n-k}
\sum\limits_{j=0}^{2j+1 \leq k}
\begin{pmatrix}
k \\
2j+1
\end{pmatrix}
=
2^{n-1}
\end{align}
rows in $A_n$that produce an odd number when multiplied by $\tilde{v}$. The factor $2^{n-k}$ appeared because $2^{n-k}$ entries of $v$ are zero and so having a 0 or a 1 in the corresponding column of a row of $A_n$ doesn't matter, meaning that both situations are counted. 

Case 2
Suppose $\tilde{v} = \tilde{w}$. Then $A_n \tilde{v} = A_n \tilde{w}$ and by the above lemma, $2^{n-1}$ entries of the element-wise product are 1. When we construct $A_{n+1}$ as in Case 1 above, again without loss of generality, $v_i = 0, w_i = 1$, because they must differ in this entry. 
All the rows where $A_{n+1}$ has a 0 in the $i$th column reduce to the $A_n$ case and so we have $2^{n-1}$ entries of the element-wise product that are 1. 
All the rows where $A_{n+1}$ has a 1 in the $i$th column cannot have $A_{n+1} v = A_{n+1} w$ (because all entries of $v$ and $w$ are equal, except the $i$th) and so these rows cannot give 1's in the element-wise product. 
This gives the total count of $2^{(n+1)-2}$ 1's in the element-wise product, as desired.

By the way, I believe your question is equivalent to the statement

Let $X$ be a set with $|X| = n$. Let $A,B \subseteq X$. Then there are
  $2^{n-2}$ sets $Y\subseteq X$ such that $|A \cap Y|$ and $|B \cap Y|$
  are odd.

Perhaps someone can find a shorter or more elegant proof using this observation.
