probability, random vector 0 1 vectors We count in GF(2). Let A be the non-zero matrix $n \times n$. We take
vectors $x,y\in \{0,1\}^n$ independently uniformly randomly. Prove that
$Pr_{x,y}[x^TAy\neq 0]\geq \frac{1}{4}$.
Do you have any thoughts? No ideas from me so far, I update if thought of something.
John

Choose some $(i,j)$ such that $A_{ij}=1$ and let $z=((x_k)_{k\ne i},(y_k)_{k\ne j})$, then
$$
x^TAy=x_iy_j+\alpha(z)x_i+\beta(z)y_j+\gamma(z),
$$
for some explicit functions $\alpha$, $\beta$ and $\gamma$. For every fixed $u$ in $\{0,1\}^{n-1}\times\{0,1\}^{n-1}$, the set $\{(x,y)\mid z=u\}$ has four points and the values of $x^TAy$ on these points are
$$
\gamma(u),\quad\gamma(u)+\beta(u),\quad\gamma(u)+\alpha(u),\quad\gamma(u)+\beta(u)+\alpha(u)+1.
$$
For every $u$, at least one of these is $\ne0$ hence the probability that $x^TAy\ne0$ when restricted to this set is at least $\frac14$. More formally,
$$
P[x^TAy\ne0\mid z]\geqslant\tfrac14\quad\text{almost surely},
$$
and in particular, $P[x^TAy\ne0]=E[P[x^TAy\ne0\mid z]]\geqslant\tfrac14$.
The inequality is optimal since, if exactly one entry of $A$ is not zero, say $A_{ij}=1$, then $x^TAy=x_iy_j$, which has probability exactly $\frac14$ to be $\ne0$.
