Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices

NEW

Problem: Natural formalization: let $A\in\{\pm1\}^{n\times n}$ be a Hadamard-type sign matrix with rectangle discrepancy

$$\operatorname{disc}(A)=\max_{R,C}\left|\sum_{i\in R,j\in C}A_{ij}\right|\le n^{3/2}.$$

In each round Unbalancer chooses a previously unchosen $-1$-entry of $A$, and Balancer chooses a previously unchosen $+1$-entry. After $t$ rounds, define the game discrepancy

$$\Delta_t=\max_{R,C}\left|\,|B_t\cap(R\times C)|-|U_t\cap(R\times C)|\,\right|.$$

The question asks whether Balancer has a strategy ensuring $\Delta_t<s^{3/4}$ after $s$ moves. There is a minor ambiguity whether $s=t$ counts rounds or $s=2t$ counts individual moves; the counterexample below covers both.

Result: No. Take the Sylvester Hadamard matrix $H$ of order $32$, indexed by $x,y\in\mathbb F_2^5$, with

$$H_{x,y}=(-1)^{x\cdot y}.$$

It is Hadamard, and for all row/column sets $R,C$,

$$\left|\sum_{x\in R,y\in C}H_{x,y}\right| =|1_R^T H1_C| \le \|1_R\|_2\|H1_C\|_2 \le \sqrt{|R|}\sqrt{32|C|} \le 32^{3/2}.$$

So it satisfies the stated Hadamard discrepancy hypothesis.

Let Unbalancer choose nine distinct $-1$-entries in the single row $x=e_1$; there are $16$ such columns, namely those with $y_1=1$. Let $C$ be those nine columns. Whatever Balancer does, Balancer can choose only $+1$-entries of $H$, and every cell in $\{e_1\}\times C$ is a $-1$-entry. Hence

$$B_9\cap(\{e_1\}\times C)=\varnothing,\qquad |U_9\cap(\{e_1\}\times C)|=9.$$

Therefore

$$\Delta_9\ge 9.$$

If $s$ counts rounds, then $9>9^{3/4}$. If $s$ counts individual moves, then after $18$ moves,

$$9>18^{3/4}$$

since $9^4=6561>18^3=5832$. Thus Balancer cannot maintain discrepancy below $s^{3/4}$.

This is not merely an endpoint or strict-inequality defect; the obstruction is concentration of Unbalancer’s choices in one row.

Citation: No known literature resolution used; this is an elementary counterexample to the natural formalization of the stated game.