# Lights out game on a grid

Let $G$ be a graph, let $A$ be the adjacency matrix of $G$. Solve the equation $Ax=b$ in $F_{2}$.

The problem is equivalent to the lights out game. Each vertex has state $0$ or $1$. Activate a vertex flips the state of itself and all its neighbors. Find a set of activation that turns all state into $0$.

Originally I thought this problem can be solved in $O(n_{ω/2})$ when $G$ is planar graph on $n$ vertices by nested dissection. However, only recently I found out the matrix must be non-singular [1]. Therefore, nested dissection does not apply. In particular, even grid graphs can have singular adjacency matrix. For example, a $2×3$ grid.

If the graph is a $n×n$ grid, then solving the linear system takes $O(n_{6})$ time. Recently, I saw an $O(n_{3})$ time solution. The solution by Zheng Wang and can be seen here(in Chinese). Here I gave my interpretation of the algorithm.

# 1 The algorithm

Given a $n×n$ grid graph. Let $v_{i,j}$ be the node on the $i$th row and $j$th column. Let $b_{i,j}$ be the state of the vertex $v_{i,j}$ in the input. Each state is in $F_{2}$. If we activates a node, the state of the node and its neighbors change by $1$. The set of activated node is called the activation set.

We are interested in finding an activation set $S$, such the state of all nodes after activate $S$ is $0$.

Let $S$ be a activation set, and $S_{1}⊆S$ to be the activation set of the first row.

$S_{1}$ uniquely determines $S$. Moreover, One can compute $S$ from $S_{1}$ in $O(n_{2})$ time.

Indeed, consider we’ve applied the activation to the nodes in $S_{1}$. For any vertex in row $1$. If it $0$, then the remaining neighbor (on the second row) cannot be activated. If it is $1$, then the remaining neighbor has to be activated. This allows us to compute the activation pattern for the second row. We can apply induction to obtain the activation pattern for each row is determined by the previous row.

Naively, by the above theorem, we can obtain a $O(2_{n}n_{2})$ time algorithm by trying all possible $S_{1}$ until we find one that works.

Wang realized the proof of the theorem actually allows us to solve for $S_{1}$ directly. In the beginning, we don’t know what $S_{1}$ should be, but we do know its relations with $S$. The high level idea is a $3$ step process.

- Express the activation state of $v_{i,j}$ as a linear combination of the activation state of $v_{1,j}$ for all $i,j$. This allows us to express $S$ parametrized by $S_{1}$.
- Solve for a $S_{1}$ by setting up a system of linear equations with the activation states of the last row.
- Using $S_{1}$ to obtain $S$.

Formally, we create formal variables $Z={z_{1},…,z_{n}}$. Here $z_{i}$ is an indicator variable that represents if $v_{1,i}∈S_{1}$. Let $D[i,j]$ be a linear combination of $Z$, such that it evaluates to $1$ if $v_{i,j}∈S$ and $0$ otherwise.

We compute $D[i,j]$ through dynamic programming. First, set $D[1,j]=z_{j}$ for all $j$. For each $i$ and $j$, $D[i+1,j]=1+D[i,j−1]+D[i,j]+D[i,j+1]+D[i−1,j]+b_{i,j}$. We can compute $D[i,j]$ in $O(n)$ time. Computing all $D[i,j]$ for $i≥2$ takes $O(n_{3})$ time.

At this point, we have expressed if $v_{i,j}∈S$ through a linear combination of $Z$. How do we find a $S_{1}$ that works? The idea is to consider the linear relations defined by $D[n,1],…,D[n,n]$. We can see it is of the following form.

$D[n,1]D[n,2]⋮D[n,n] =C_{1,1}z_{1}+…+C_{1,n}z_{n}+u_{1}=C_{2,1}z_{1}+…+C_{2,n}z_{n}+u_{2}⋮=C_{m,1}z_{1}+…+C_{m,n}z_{n}+u_{n}. $

If we solve the equation $Cz=u$, we find $z_{1},…,z_{n}$, which implies we find $S_{1}$. Note $C$ is just a $n×n$ matrix, solving the equation takes $O(n_{3})$ time. Now, we use the theorem again to find the entire activation set $S$ through $S_{1}$ in $O(n_{2})$ time.

Building the table $D$ takes $O(n_{3})$ time, solving $Cz=u$ also takes $O(n_{3})$ time, compute $S$ from $S_{1}$ takes $O(n_{2})$ time. The total running time is $O(n_{3})$.

However, why is this algorithm correct? Zheng did not provide a proof, hence leaving a gap to fill.

# 2 Remarks

One can see this is similar to the light chasing technique. There is no need to access a precomputed lookup table, since we compute the correct first row on the fly.

One can generalize this further. We can obtain $O(m_{2}n)$ running time for a $m×n$ grid, where $m≤n$. Also, there is no reason we have to work in $F_{2}$, any field is fine.

Let $G$ be a $m×n$ grid and $A$ is a matrix where the non-zero entries are precisely the position of $1$s in the adjacency matrix of $G$. Finding $Ax=b$ can be done in $O(m_{2}n)$ time.

How can this be generalized to other graphs?

Turns out this is related to the zero forcing set [2]. Consider the vertices are colored
black and white. If a black vertex has only a single white neighbor,
color the white neighbor black. If eventually all vertices become black,
then we say the set of black vertices in the beginning is a *zero
forcing set*. The *zero forcing number* of $G$ is the size of the smallest zero forcing
set of $G$.

Let $G$ be a graph with $m$ edges and $A$ is a matrix where the non-zero entries are precisely the position of $1$s in the adjacency matrix of $G$. If we are given a zero forcing set of size $k$. Finding $Ax=b$ can be done in $O(km+k_{ω})$ time.

Jianbo Wang, Siyun Zhou and I wrote up a paper on this. We also improved the running time for solving the $n×n$ grid lights out game to $O(n_{ω}gn)$.

Unfortunately, minimum (weighted) zero forcing set is NP-hard to find [3]. It is also very large for simple graphs. Caterpillars have a $Ω(n)$ size zero forcing set.

Is this a new viable algorithm for solving system of linear equations?

The zero forcing number is at least the pathwidth [3], which is in turn at least the treewidth, which implies there are good separators. This should mean nested dissection is better than this zero forcing number algorithm for non-singular matrices.

# References

**Matrix sparsification and nested dissection over arbitrary fields**, Journal of the ACM. 60 (2013) 1–18 10.1145/2508028.2505989.

**Zero forcing sets and the minimum rank of graphs**, Linear Algebra and Its Applications. 428 (2008) 1628–1648 10.1016/j.laa.2007.10.009.