What is the probability that two products are equal? Consider a square $n$ by $n$ matrix $A$ and two vectors $v$, $w$ of dimension $n$. The entries of $A$, $v$ and $w$ are either $-1$ or $1$ with equal probability and are i.i.d. and all three are independent. 

What is the probability that $Av = Au$?

 A: Let $\mathcal{F}$ be the collection of random $n$ dimensional vectors whose components taking value either -1 or 1 with equal probability and are i.i.d.
It is clear all the row vectors of $A$ belongs to $\mathcal{F}$ are independent from
each other. If $\tilde{u}, \tilde{v}$ are any realizations of the two random vectors $u, v \in \mathcal{F}$ (i.e. any two fixed vectors whose components taking value either -1 or 1),  we will have:
$$\begin{align}
\text{Prob}\left[\;A\tilde{u} = A\tilde{v} \mid A \in \mathcal{F}^n \;\right]
&= \text{Prob}\left[\; \omega^t \tilde{u} = \omega^t \tilde{v} \mid \omega \in \mathcal{F} \;\right]^n\\
&= \text{Prob}\left[\; \omega^t (\tilde{u} - \tilde{v}) = 0   \mid \omega \in \mathcal{F} \;\right]^n
\end{align}
$$
Let $u = (u_1, \ldots, u_n)$, $v = (v_1, \ldots, v_n)$ and $\omega = ( \omega_1, \ldots, \omega_n )$ be the decomposition of the three random vectors $u, v, \omega$ into its 
components. Let $\;\theta(u,v) = \left| \{ u_i \ne v_i : 1 \le i \le n \}\right|\;$ be the random variable of the number of components of $u$ different from that of $v$. It is clear $$\text{Prob}\big[\;\theta(u,v) = k \mid u, v \in \mathcal{F}\;\big] = 2^{-n}\binom{n}{k}$$
Furthermore, if $u_i = v_i$ for a particular $i$, then whether $\omega^t (u - v) = 0$ or not is independent of the value of $\omega_i$. 
In order for $\omega^t(u - v) = 0$, among those $i$ where $u_i \ne v_i$, the number of $i'$ which satisfy $\omega_{i'} = u_{i'}$ need to equal to the number of $i''$ which satisfy $\omega_{i''} = v_{i''}$. This leads to
$$\text{Prob}\big[\;\omega^t (u - v) = 0 \mid \theta(u, v) = k; u, v, \omega \in \mathcal{F}\;\big]
= \begin{cases}2^{-k}\binom{k}{k/2},& k \text{ even }\\0,& k \text{ odd}\end{cases}$$
This leads to
$$\text{Prob}\big[\;A u = A v \mid \theta(u, v) = k; u, v \in \mathcal{F}, A \in \mathcal{F}^n\;\big]
= \begin{cases} 2^{-nk}\binom{k}{k/2}^n,& k \text{ even }\\0,& k \text{ odd}\end{cases}$$
From this, we find
$$\text{Prob}\big[\;A u = A v \mid u, v \in \mathcal{F}, A \in \mathcal{F}^n\;\big]  = \sum_{k=0}^{\lfloor n/2 \rfloor} 2^{-n(2k+1)} \binom{n}{2k}\binom{2k}{k}^n$$
