Lights out game on hexagonal grid

I greatly enjoyed the Lights Out game described here (I am sorry I had to link to an older page because some wikidiot keeps deleting most of the page).

Its mathematical analysis is here (it's just linear algebra)

Now I just discovered a hexagonal version:

Are there any mathematical results for this version of the game, before I dig in and start the analysis myself. I have the major references including

Turning Lights Out with Linear Algebra, by M. Anderson and T. Feil (1998). Math Magazine, vol. 71, no. 4, October 1998, pp. 300-303. It's here (thanks to J.M.).

Update: I've been playing with the iPhone T-Lights hexagonal versions. I can get most of them, except for the ones where the "template" is a Y shape. Any ideas?

-

Yes there are linear algebra and graph theoretic results for this game, for any arrangement of switches and starting from all off position.

Notice that you can construct a simple graph out of the arrangement of lights, by taking the lights to be vertices, and making them adjacent in the graph if they are neighbours.

Graph theoretic:

(This can found here: Problem 17 on http://books.google.com/books?id=e99fXXYx9zcC&pg=PA42)

Proposition A: Given a simple undirected graph $G(V,E)$, with vertex set $V$ and edge set $E$, we can partition $V$ into two sets $V_1$ and $V_2$ such that

$\forall y \in V_1, \ \ |\{ x: \{x,y\} \in E \wedge x \in V_1\}| = 0 \mod 2$
$\forall y \in V_2, \ \ |\{ x: \{x,y\} \in E \wedge x \in V_1\}| = 1 \mod 2$

i.e. any vertex in $V_1$ is incident to an even number of vertices in $V_1$ and any vertex not in $V_1$ (i.e. in $V_2$) is incident to an odd number of vertices in $V_1$.

$\circ$

So selecting the vertices in $V_1$ will turn on all the lights, if we start from the all off position.

Proof:

We tackle a closely related problem.

We first show that:

Proposition B: Given a simple undirected graph $G(V,E)$, there is a partition of the vertex set of $G$, $V = V_1 \cup V_2$ such that

$\forall y \in V_1, \ \ |\{ x: \{x,y\} \in E \wedge x \in V_1\}| = 0 \mod 2$
$\forall y \in V_2, \ \ |\{ x: \{x,y\} \in E \wedge x \in V_2\}| = 0 \mod 2$

i.e. Any vertex in $V_1$ is adjacent to an even number of vertices in $V_1$ and any vertex in $V_2$ is adjacent to an even number of vertices in $V_2$.

$\circ$

The proof of Proposition B is by induction on the number of vertices in $G$.

Base cases are easy.

Suppose $G$ has $n+1$ vertices. If all the vertices of $G$ have even degree, we are done, by taking $V_2 = \emptyset$.

Suppose $o$ is a vertex with odd degree and let $o_1, o_2, \cdots, o_k$ be the neighbours of $o$.

Form a graph $G'$ as follows: If $o_i$ and $o_j$ are adjacent in $G$, they are not adjacent in $G'$ and vice versa. Also delete $o$.

$G'$ is a graph with $n$ vertices.

Apply the induction hypothesis to $G'$. Say we get a partition $V' = X \cup Y$.

Now $o$ must be incident to an even number of vertices in one of $X$ or $Y$. Say $X$. Add $o$ to $X$ to get a partition for $G$. We can easily show that this partition of $G$ is what we need.

$\square$

Now to apply this to our problem (Proposition A):

Add a new vertex $N$ to G and make it adjacent to every vertex of even degree in $G$ to get a new graph $G'$.

Apply Proposition B to $G'$. Suppose the partition satisfying proposition B is $V = X \cup Y$. We can easily show that this is also the partition in $G$ (ignoring $N$) for proposition A.

Note: This not only proves the existence of a solution, but the induction proof actually gives you an O(n^3) time algorithm to find the solution.

Linear Algebra Proof due to Noga Alon:

Over $\mathbb{F}_2$, let $A$ by any $n\times n$ symmetric matrix. We can show that if $d$ is the diagonal vector of $A$, then $d$ is in the space spanned by the rows of $A$.

This follows from the identity (valid over $\mathbb{F}_2$) that

$v^{T}Av = d^{T}v$, where $u^{T}$ is the transpose of $u$.

Thus if $v$ is in the null space of $A$, then $d$ is orthogonal to $v$ and as a consequence, $d$ is in the row space of $A$.

We consider the matrix A to be $B+I$ where $B$ is the adjacency matrix of the corresponding graph we get, from the arrangement of the lights.

-
I've tried apply this theorem on the standard lights out and failed. Pressing all buttons in V1 failed to solve. Is there something missing? – John Smith Nov 21 '10 at 17:01
@John: What was the V1 you found? – Aryabhata Nov 21 '10 at 17:03
It was all the buttons except the edge buttons not in the corners. The reason I think there is something missing (or the theorem is for something else) is because the solution to the standard 5x5 case is very nonsymmetric. Look at it here: orion.math.iastate.edu:80/burkardt/puzzles/… – John Smith Nov 21 '10 at 17:49
That can't be the V1 in Proposition A. The corner buttons are adjacent to and even number of buttons in V1. – Aryabhata Nov 21 '10 at 17:56
I think you misunderstood. I did include the corner buttons. Let me try to draw V1: I go row by row. The X is the button I press, the - is the button I don't press x---x, -xxx- , -xxx- , -xxx- , x---x – John Smith Nov 21 '10 at 17:58

Here is another version of this game. You have a symmetric matrix $A$ over $GF(2)$ (i.e. $0,1$ with all computations done modulo $2$). Then you can show that the diagonal of $A$ is always in the range of $A$, and this is best possible in the sense that the range of $A$ could consist of only the zero vector and the diagonal of $A$.

I was actually given this "game" as a riddle, so I wouldn't ruin it for you with an answer.

EDIT: Here's my answer, which is probably very similar to Moron's proof. Of course Noga's proof is much neater, but it's not algorithmic (in any other respect it's much better).

-

I tried (and tried again) to improve the Wikipedia article but the edits were promptly reverted as if well-known solutions of Lights Out are "original research", despite providing several citations.

If any Stack Exchange members are Wikipedians who can assist in restoring the article, it would be greatly appreciated. Also, I would direct this request more appropriately if I could, but don't see a way to contact John Smith directly. Feel free to delete it.

-
I feel your pain. Someone on wikipedia is on a power trip. – John Smith Nov 28 '10 at 17:51
I sympathize greatly; I stopped trying to improve Wikipedia after a bunch of jerks undid all my edits. – J. M. Nov 29 '10 at 2:49