Lights out and Matrices over Z_2

A couple days ago, one of my friends challenged me to solve a riddle posted by spanish newspaper El País. The riddle consisted in explaining why in a 24x24 board, there are impossible configurations of the game Lights Out (you can play it here)

It had two parts:

• the first one was to find an impossible configuration, that is, a configuration of lit squares on the board that was impossible to reach starting from a dark board (equivalently, a starting configuration for which you can't turn the lights out).
• the second was to show that at least half of the possible configurations on the board are impossible. 

The first part requires a bit of trial and error, but one can find it. The second part obviously implies the first, and also is more interesting. 

One trick to attack the problem is to think about it in the general case, on a $n\times n$ board. You quickly realize that the $1\times 1$, $2\times 2$, and $3\times 3$ have no impossible configurations, that is, you can reach any configuration starting from a dark board.

Why is 24 so special then? First of all, notice that since the squares only have two states (on or off), the only thing that determines the state of a square is the parity of the number of times that it has been pushed. More over, we can reduce this to either 0 or 1.

Checking the above set up, one can see that pressing the squares with 1's, we end up with a dark board when $n=4$. Hence, there are two different pushing patterns (this and all 0's) which lead to a dark board. This means that every possible configuration of lights can be achieve at least twice with different pushing patterns (adding the above pushing pattern to any other will make to end up with the same light configuration).

Thus the $4\times 4$ case is the first one to have impossible configurations, and actually, at most half of the possible light configurations are possible.

It is not difficult to see that this pattern can be used to treat bigger boards.

For example, the above configuration with lead to a dark $9\times 9$ board. In general, this is possible for $n=5k+4$. Therefore $n=24$ will have the same behavior.

Now, this whole thing smells a lot like linear transformations of vector spaces. And indeed, a nice way to attack the problem is using this language.

Let $p=(p_1,p_2,\dots, p_{n\times n})$ (yes, $n\times n$) be the vector of pushing parity for an $n\times n$ board, were we read the pattern right to left, top to bottom. Thus the dark pushing pattern for the $4\times 4$ is

$$p=(0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0).$$

Let $A$ be the $n^2 \times n^2$ matrix that gives the light configuration obtained by the $p$ pushing pattern, i.e. $(Ap)^T$ is a vector giving the state of a square (on or off). We use the same convention for reading out this vector.

Hence, a number $n$ will lead to impossible configurations if and only if $A$ is non-invertible. To be more rigorous, we have the following:

$V$ is the vector space $(\mathbb{Z}_2)^{n^2}$ with $\mod 2$ addition, and $A$ is the matrix from $V$ to $V$ containing the rules of the game.

This matrix can be  written in block form as the symmetric tridiagonal matrix

$$A=\begin{pmatrix}B & I_n & 0 & \cdots & 0\\ I_n & B & I_n & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & 0 & \cdots & B\end{pmatrix}$$

with $I_n$ the $n\times n$ identity matrix and $B=I_n+U_n+L_n$, where $L_n,U_n$ are the lower and upper shift matrices.

Therefore, there are impossible configurations if and only if $\det (A)=0$. Since $B, I_n$ commute with each other, we can calculate the determinant in block form.

Here is a list of the first few determinants

n	det(A) (block polynomial)	det (A)
1	I	1
2	B^2 – I	-3=1
3	B^3 - 2*B	-7=1
4	B^4 - 3*B^2 + I	0
5	B^5 - 4*B^3 + 3*B	0
6	B^6 - 5*B^4 + 6*B^2 – I	2197=1
7	B^7 - 6*B^5 + 10*B^3 - 4*B	-34391=1
8	B^8 - 7*B^6 + 15*B^4 - 10*B^2 + I	-4002939=1
9	B^9 - 8*B^7 + 21*B^5 - 20*B^3 + 5*B	0

Notice that the coefficients of the block polynomials are Pascal's triangle's. 

Hence, we can see that (as expected) $n=9$ gives impossible configurations, however the unexpected $n=5$ appears, so another set of values for $n$ will lead to impossible configurations $n=6k+5$. 

A good question would be to find all such possible $n$ leading to impossible configurations, but that might be a task for another time. 

Lastly, in order to solve the game for any of the possible $n$'s, the only thing needed is to compute $A^{-1}$ and apply it to the configuration, obtaining the pushing pattern.