Lights out game on hexagonal grid

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.

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.