Proof that the product of a nonzero square matrix and a randomly chosen binary vector has a greater than 50% chance of being nonzero The claim is as follows:
Let $Y$ be any nonzero $n×n$ matrix, and let $x = (x_1, x_2, . . . , x_n)$ be a binary vector
in which the coordinates $x_1, . . . , x_n$ are chosen uniformly and independently at random
from the set $\{0, 1\}$. Let $z = Yx$. Then $P(z \neq 0) \geq 0.5$.
Intuitively, this seems like it should be the case, but how do you rigorously prove it?
 A: Since $Y$ is nonzero, we may assume its first column is nonzero. Partition $x$ as $\pmatrix{x_1\\ x'}$, where $x'$ has $n-1$ elements. For any fixed $x'$, since $Y$ has a nonzero first column, $Y\pmatrix{1\\ x'}$ and $Y\pmatrix{0\\ x'}$ cannot be both zero. Therefore $P(Yx\ne0\mid x')\ge\frac12$. Hence $P(Yx\ne0)=\sum_{x'}P(Yx\ne0\mid x')P(x')\ge\sum_{x'}\frac12P(x')=\frac12$.
A: Let $y$ be any non-zero row of $Y$.
Since $x$ is a $\{0,1\}^n$-valued random (column) vector whose components are $\mathbb{P}$-independent Bernoulli random variables of parameter $1/2$, the distribution of $x$ is the uniform on the Boolean hypercube $\{0,1\}^n$.
If follows that:
\begin{equation*}
\mathbb{P}[Yx\neq0]\ge\mathbb{P}[yx  \neq 0] = \frac{\big|\big\{ \sigma\in \{0,1\}^n : y \sigma \neq 0
 \big\}\big|}{|\{0,1\}^n|}  =  \frac{1}{2^n} \big|\big\{ \sigma\in \{0,1\}^n : y \sigma \neq 0
 \big\}\big| = (\star) \,.
\end{equation*}
Define $\varphi: \mathbb{R}^n\to\mathbb{R}, z\mapsto yz$. Being $y \neq 0$, $\varphi$ is a non-zero linear functional of $\mathbb{R}^n$. It follows that the equation $\varphi = 0$ determines a hyperplane of $\mathbb{R}^n$. Now, a hyperplane contains at most $2^{n-1}$ points of the Boolean hypercube $\{0,1\}^n$ (see the first part of the answer to this question to see why). It follows that
\begin{equation*}
(\star) = \frac{1}{2^n}\Big( 2^n - \big|\big\{ \sigma\in \{0,1\}^n : \varphi(\sigma)  = 0
 \big\}\big|\Big) \ge \frac{2^n - 2^{n-1}}{2^n} = \frac{1}{2} \,. 
\end{equation*}
