Probability of $0,1$ vector and matrix multiplication Given a random $\{0,1\}$ vector $x\in \mathbb{R}^n$, prove if $AB\ne C$ then $P(ABx=Cx)\le \frac{1}{2}$ where $A\in \mathbb{R}^{m\times l}$, $B\in \mathbb{R}^{l\times n}$, and $C\in \mathbb{R}^{m\times n}$.
 A: Let $D := AB - C$, then $D$ is an $m\times n $ non-zero matrix. Define 
$$
\mathcal{X}: = \{ x = (x_1, ..., x_n) \in \{0,1\}^n: \ Dx = 0  \},
$$
we need to show that
$$
\tag{1} | \mathcal{X} | \leq 2^{n-1}.
$$
Since $D$ is non-zero, it has a non-zero row, and WLOG we will assume that $d: = (d_1,...,d_n)$ is the first row of $D$ which is not identically $0$.
For any $x \in \mathcal{X}$ we have $d\cdot x = 0 $ i.e. $d_1 x_1 + ...+d_n x_n = 0$.
WLOG we can assume that all components of $d$ are non-zero, since if say $d_n = 0$, then  for any $x \in \{0,1\}^n$ the last bit has no affect on its belonging to the set $\mathcal{X}$. Now assume $d_1 + ... +d_n \neq 0$ then, for any $x \in \mathcal{X}$ we have $1 - x \notin \mathcal{X}$ since
$$
\tag{2} d_1 (1 - x_1) + ... + d_n (1 - x_n ) = d_1 + ... + d_n - (d_1x_1 +...+d_nx_n) = d_1 + ... + d_ n \neq 0.
$$
Hence $(1)$ follows immediately since the mapping $x \mapsto 1 - x$ is one-to-one on $\{0,1\}^n$ . In case when $d_1 + ... +d_n = 0 $ let $1\leq k<n$ be the largest integer such that $d_1 + ... + d_k \neq 0$. Clearly such $k$ exists in view of the assumption that $d\neq 0$. Observe also that due to our assumption that none of $d_i $ is zero and $d_1 + ...+d_n = 0$ it follows that $ k = n - 1$. Thus we have
$$
\tag{3} d_1 + ... + d_n = 0 \ \ \ \text{ and } \ \ \ d_1 + ... + d_{n - 1} \neq 0.
$$
Take any $x\in \mathcal{X}$ and consider 2 cases:
Case 1. $x_n = 0 $.
In this case it follows from $(3)$ that $ (1 - x_1, ,..., 1 - x_{n - 1}, x_n) \notin \mathcal{X}$ similarly as we showed $(2)$. Thus we again eliminate at least half of the $\{0,1\}$ vectors having their last coordinate equal to $0$, from being in $\mathcal{X}$.
Case 2. $x_n \neq 0 $.
Here we have 
$$
d_1 x_1 + ... + d_{n-1} x_{n-1} + d_n = 0.
$$
For the $\{0,1\}$ vector $(1 - x_1, ...., 1 - x_{n-1}, 1)$ using $(3)$ we get
$$
d_1 (1 - x_1) + ... + d_{n-1} ( 1 - x_{n-1}) + d_n = d_1 + ... + d_n - (d_1x_1 + ...+d_{n-1} x_{n-1}) = - (d_1x_1 + ...+d_{n-1} x_{n-1}) = d_n \neq 0.
$$
Thus in case 2 as well, each $x\in \mathcal{X}$ can be put in one-to-one correspondence with a vector outside $\mathcal{X}$.
Combining Cases $1$ and $2$ we conclude $(1)$.
