1
$\begingroup$

Is it correct that for any uniformly, independently chosen vectors $r,s \in \mathbb{Z}_2^m$ and for any $0 \neq D \in \mathbb{Z}_2^{m \times m}$, we have that $Pr_{r,s}\left[r^T\cdot D \cdot s \neq 0 \right] \geq \frac{1}{4}$? If so, how would I go about proving this?

Thanks!

1 Answers 1

3

Yes. Since $D$ is nonzero, its kernel is a proper subspace of $\mathbb{Z}_2^m$, and so contains at most half of $\mathbb{Z}_2^m$, and so the probability that $Ds=0$ is at most $1/2$. If $Ds \neq 0$, then $v \mapsto v^T D s$ is a nonzero linear map from $\mathbb{Z}_2^m$ to $\mathbb{Z}_2$, and so its kernel contains exactly half of $\mathbb{Z}_2^m$, so (since $r$ and $s$ are independent) the probability that $r^T D s=0$ given that $Ds \neq 0$ is exactly $1/2$. Thus the unconditional probability that $r^T D s \neq 0$ is at least $1/2 \cdot 1/2=1/4$,