## Unbalancing Lights aka Gale-Berlekamp Switch Game

Posted: September 12, 2010 in Lectures, Probabilistic method

Image from gizmodo.com

This post is a short excerpt from lecture 3 and 4.

Let us consider the above “chessboard”-like switchboard. U see that there are switches on both sides. Each switch control its corresponding row or column… Should be quite clear from the diagram. So if u hit the switch, then all the “off” lights in the row/column will turn “on” and the “on” lights in the row/column will turn “off”. The goal is to: maximise the number of lights on, or minimise the lights off, or to maximise the difference between the lights on and off… all almost equivalent objectives…

Well… the game is also known as the GaleBerlekamp game (named after two famous combinatorial game theorists from UC Berkeley). n the game can be turned into a two player game with some variations.

I. Player A and B hit the switches in alternating turns. Player A will hit only the rows and Player B hit the columns. The player who cannot increase the number of lights on wins.

II. Player A sets the initial state of the lightbulbs and presents to Player B.  Player B will then try to maximise the number of lightbulbs to be switched on.

I found Variation I from this site, which reported on Microsoft ‘s Techfest in 2009. Havent really considered the solution.

Variation II was given as Homework II and interestingly uses Hadamard matrices.

Let us reformulate the problem. Consider the $n\times n$ matrix $A=(a_{ij})$ with $a_{ij}=\pm 1$.  Also consider the following numbers $x_1,\ldots ,x_n,y_1,\ldots ,y_n=\pm 1$.

Then $A$ is the initial state of the chessboard, where 1 indicates that the light is on and -1 indicates the light is off. If $x_i=-1$, then the switch for row $i$ is hit. Similarly, if $y_i=-1$, then the switch for column $i$ is hit.

So, the sum $\sum a_{ij}x_iy_j$ (we now call $\Delta$) is the difference between lights on and lights off. ie the quantity which we or Player B hopes to maximise.

Ok. Suppose a Hadamard matrix exist for $n$. So Player A will set the initial state of the chessboard accordingly and pass it to Player B. And… no matter what Player B do, $\Delta\le n^{\frac{3}{2}}$.

I’ll attempt to sketch a proof. So let $A$ be the chessboard / Hadamard matrix Player A pass to Player B.

First, we let Player B decide $x_1,\ldots, x_n, y_1, \ldots, y_n$ and then we consider the matrix $X=(x_{ij})$ where $X$ is a diagonal matrix with $x_{ii}=x_i$ and $Y$ is defined similarly. Then it’s not difficult to see that $XAY$ is the end state after the switches and that the resulting matrix is still a Hadamard matrix.

So, we just need to show that the sum of the entries of a Hadamard matrix does not exceed $n^{\frac{3}{2}}$. Well, let $c=(1,\ldots,1)$ and then $\Delta=cXc^T$. Then, using Cauchy Schwarz inequality and the fact that Hadamard matrices are orthogonal, we obtain our result (hands waving furiously…)

Anyway, the last para also gives a sketch of the proof of the Lindsey’s Lemma, which states that if we pick a $a\times b$ submatrix from a $n\times n$ Hadamard matrix, then the sum of the submatrix entries is $\le \sqrt{abn}$.

———————————–

Now… what can Player B hope to achieve? Well, if Player A just pass me a $n\times n$ matrix $A$ (need not be Hadamard), it turns out that Player B can always achieve $\Delta\ge (\sqrt{\frac{2}{\pi}}+o(1))n^{\frac{3}{2}}$.

Let Player B randomly choose $y_1,\ldots, y_n=\pm$ and let $R_i=\sum a_{ij}y_j$ and $R=\sum |R_i|$.

First, $E(|R_i|)=(\sqrt{\frac{2}{\pi}}+o(1))\sqrt{n}$, as it is a one-dimensional random walk (waving hands…)…

Then, $E(R)= E(|R_1|)+\ldots E(|R_n|)=(\sqrt{\frac{2}{\pi}}+o(1))n^{\frac{3}{2}}$

So, there exists $y_1,\ldots,y_n$ such that $R=|R_1|+\ldots+|R_n|\ge (\sqrt{\frac{2}{\pi}}+o(1))n^{\frac{3}{2}}$. So so so, we pick $x_i$ to have the same sign as $R_i$, ie $|R_i|=x_iR_i$. Then $\Delta=R$ and we are done.

Well, as the proof was poorly explained by me, it looks simple. But to come up with the $y_i$ to achieve the lower bound is not simple.

Here, we have a flash version of the game and it’s a $10\times 10$ version of it. (Note: the goal is to MINIMISE the lights ON…)

So, by the theorem / proposition, we can make sure less than 30 lights are on (less than 3 per row). Pls try and tell me a nice algorithm to achieve this…