Singular 0/1-matrices, and the hyperplanes spanned by random 0/1-vectors

NEW

Problem: Let $C^d=\{0,1\}^d\subset \mathbb R^d$. Reconstruct the literal question as follows: for $d\ge0,\ r\ge1$, choose $V_1,\dots,V_r$ independently uniformly from $C^d$, repetitions allowed, and compute

$$E_{d,r}:=\mathbb E\bigl|C^d\cap \operatorname{aff}_{\mathbb R}(V_1,\dots,V_r)\bigr|.$$

The affine span is over $\mathbb R$. A different conditioned model, e.g. distinct or affinely independent vertices, would be a different problem.

Result: Let $M$ be a random $r\times d$ $0/1$-matrix and let $\mathbf 1_r=(1,\dots,1)^T$. Then

$$\boxed{\; E_{d,r} = 2^d\,\Pr\bigl(\mathbf 1_r\notin \operatorname{col}_{\mathbb R}(M)\bigr) = 2^{d-rd}\#\{M\in\{0,1\}^{r\times d}: \rank[M\ \mathbf 1_r]=\rank M+1\}. \;}$$

More explicitly, if $\mathcal L_r=\{\operatorname{span}_{\mathbb R}S:S\subseteq C^r\}$, ordered by inclusion, and $\mu$ is its finite-poset Möbius function, then

$$E_{d,r} = 2^d \sum_{\substack{W\in\mathcal L_r\\ \mathbf 1_r\notin W}} \sum_{U\le W} \mu(U,W) \left(\frac{|U\cap C^r|}{2^r}\right)^d .$$

Proof. For fixed $x\in C^d$, complement the coordinates where $x_j=1$. This is an affine automorphism of the cube sending $x$ to $0$ and preserving the joint distribution of the $V_i$. Hence

$$E_{d,r}=\sum_{x\in C^d}\Pr(x\in \operatorname{aff}(V_i)) =2^d\Pr(0\in \operatorname{aff}(V_i)).$$

Writing the $V_i$ as the rows of $M$,

$$0\in \operatorname{aff}(V_i) \iff \exists \lambda\in\mathbb R^r:\ M^T\lambda=0,\ \mathbf 1_r^T\lambda=1.$$

This holds iff the functional $\lambda\mapsto \mathbf 1_r^T\lambda$ is nonzero on $\ker M^T$, equivalently iff

$$\mathbf 1_r\notin (\ker M^T)^\perp=\operatorname{col}_{\mathbb R}(M).$$

That gives the rank/count formula. The Möbius formula follows because the columns of $M$ are iid uniform in $C^r$, and for $W\in\mathcal L_r$,

$$\Pr(\operatorname{span}\{X_1,\dots,X_d\}\subseteq W) =\left(\frac{|W\cap C^r|}{2^r}\right)^d,$$

then invert on the finite poset $\mathcal L_r$.

Verification audit: the proof uses only iid uniform vertices, real affine span, and finite-poset Möbius inversion; the degenerate case $d=0$ gives $E_{0,r}=1$, as required.

Citation: Problem source: Thomas Voigt and Günter M. Ziegler, “Singular $0/1$-matrices, and the hyperplanes spanned by random $0/1$-vectors,” Combin. Probab. Comput. 15 (2006), 463–471; arXiv:math/0308050. The formula above is proved here; the stronger asymptotic singularity-probability questions discussed there are separate.