next up previous
Next: About this document ... Up: Hadamard Matrices Previous: Discrepancy and Ramsey Theory

Gale-Berlekamp Switching Game

Let $A=(a_{i,j})$ be a matrix with entries $\pm1$. The first player sets the initial entries of $A$. Subsequently the second player may switch any row or column (multiply the row or column by $-1$) and repeat this operation any number of times. The second player's ``score'' is the quantity $\vert\sum_{i,j\in [n]} a_{i,j}\vert$ which the second player wishes to maximize. The second player's gain is the first player's loss (zero-sum game), so the first player's goal is to keep the second player's score low. Let $m(n)$ denote the score an optimal Player 2 can achieve against an optimal Player 1.
% latex2html id marker 536
Prove that $m(n)=\Theta (n^{3/2})$... is negative. Use the
Central Limit Theorem for the analysis. \end{exercise}

Laszlo Babai 2003-06-19