← Lights Out and Snake Lemma
mainENG.tex
\def\pgfsysdriver{pgfsys-dvipdfmx.def} % ★PGFドライバを強制
\documentclass{amsart}
\usepackage[left=2cm, right=2cm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{amsfonts, amsthm, amssymb, mathtools,etoolbox}
\usepackage{blindtext}
\usepackage[colorlinks=true, urlcolor=blue, linkcolor=blue, citecolor=blue]{hyperref}
\usepackage{tikz,tikz-cd}
\usepackage{cleveref}
\usepackage{array}
\usepackage{quiver}
\usepackage[style=alphabetic,sorting=nyt]{biblatex}
\renewbibmacro{in:}{}
% \addbibresource{biblio.bib}
\addbibresource{CommonBiblio20240922.bib}
\tikzset{pullback/.style={minimum size=1.2ex,path picture={
\draw[opacity=1,black,-,#1] (-0.5ex,-0.5ex) -- (0.5ex,-0.5ex) -- (0.5ex,0.5ex);%
}}}
\usetikzlibrary{calc}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[subsection]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{todo}[theorem]{Todo}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{claim}{Claim}[theorem]
\crefname{claim}{Claim}{Claims}
\renewcommand{\theclaim}{\thetheorem.\alph{claim}}
\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{puzzle}[theorem]{Puzzle}
\newtheorem{idea}[theorem]{Idea}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{answer}[theorem]{Answer}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\dq}[1]{``#1"}
\newcommand{\memo}[1]{\textcolor{red}{memo: #1}}
% \newcommand{\invmemo}[1]{\textcolor{blue}{memo: #1}}
\newcommand{\invmemo}[1]{}
\newcommand{\horamemo}[1]{\textcolor{green!70!black}{hora: #1}}
\newcommand{\para}[1]{\paragraph{\textbf{#1}}}
\newcommand{\F}{\mathbb{F}}
\renewcommand{\L}{\mathcal{L}}
\newcommand{\id}{\mathrm{id}}
\newcommand{\op}{\mathrm{op}}
\newcommand{\ob}{\mathrm{ob}}
\newcommand{\Sh}{\mathbf{Sh}}
\newcommand{\Cont}{\mathbf{Cont}}
\newcommand{\Func}[2]{[#1,#2]}
\newcommand{\abs}[1]{\left|#1\right|}
\newcommand{\demph}[1]{\textit{#1}}
\font\maljapanese=dmjhira at 2.5ex
\newcommand{\yo}{\textrm{\!\maljapanese\char"48}}
\newcommand{\Pow}{\mathcal{P}}
\newcommand{\cod}{\mathrm{cod}}
\newcommand{\Image}{\mathrm{Im}}
% \newcommand{\SolExt}{\mathrm{SolExt}}
\newcommand{\Solvable}{\mathrm{Solvable}}
\newcommand{\Vect}{\mathbf{Vect}}
% \DeclareMathOperator{\ker}{ker}
\DeclareMathOperator{\coker}{coker}
\DeclareMathOperator{\Ker}{Ker}
\DeclareMathOperator{\Coker}{Coker}
\DeclareMathOperator{\corank}{corank}
\DeclareMathOperator{\rank}{rank}
\title{Turning lights out with the snake lemma \memo{AI-translated!!}}
\author{Kyosuke Higashida, Ryuya Hora}
% \address{ZEN University, Tokyo, Japan}
% \email{ryuya\_hora@zen.ac.jp}
\date{\today}
\subjclass[2020]{}
\keywords{h}
\begin{document}
% \begin{abstract}
% \end{abstract}
\maketitle
\tableofcontents
\subsection*{Acknowledgement}
The second-named author would like to thank his supervisor Ryu Hasegawa for helpful discussions and suggestions.
He was supported by JSPS KAKENHI Grant Number JP24KJ0837 and FoPM, WINGS Program, the University of Tokyo.
\subsection*{An incomplete survey}
In 1989, \cite{sutner1989linear} showed that on any finite graph, it is always possible to turn all lights on starting from the all-off configuration.
In that paper, this problem is referred to as the \dq{All-Ones Problem}.
The approach is quite interesting: the author reduces the problem to the \dq{Garden of Eden problem} for cellular automata.
(A \emph{Garden of Eden} for a self-map $f \colon X \to X$ simply means an element of $X \setminus \Image(f)$;
it is called so because such elements cannot be reached by $f$.)
After this reduction, the rest is handled by linear algebra.
In 1998, \cite{anderson1998turning} solved the two-dimensional Lights Out puzzle using linear algebra
(though only considering vertical and horizontal neighbors, excluding the diagonal ones).
This paper only treats the case $n,m = 5$\footnote{More precisely, it lists numerical results for smaller $n$
without giving general rules.} but has been cited over a hundred times.
A detailed history of the study of Lights Out is given in the 2013 survey paper \cite{fleischer2013survey}.
In particular, it has attracted attention from the viewpoints of graph theory, algorithmic theory,
and cellular automata theory.
The citation list of this paper shows that research on this topic is still ongoing —
indeed, a new preprint appeared just last month \cite{forrest2025lights}.
(It is not clear whether our discussion would be of interest to that community,
but I believe that the connection between the $\F_4$-invariant and homological algebra in our rule
is worth investigating — though we have not yet surveyed it.
Rather, this topic seems to be naturally related to the context of graph Laplacians.
In the field of “differential geometry on graphs,” similar matrices are used in homological contexts.
For example, \cite{jekel2018algebraic} studies analogous structures using homological algebra
and was published in the \emph{SIAM Journal on Discrete Mathematics}.)
\section{One-Dimensional Lights Out}
\subsection{Problem and a Solution via Finite-Field Invariants}
\begin{problem}
$n$ lamps are arranged in a line. When you press one of the $n$ lamps, the on/off state of that lamp and of its neighbors are toggled. (Pressing an endpoint toggles $2$ lamps; pressing a non-endpoint toggles $3$ lamps.)
\begin{enumerate}
\item Determine all $n$ for which it is possible to turn all lights off starting from any initial configuration.
\item Given an initial configuration, is there a method to decide whether one can turn all lights off?
\end{enumerate}
\end{problem}
\begin{center}
\href{https://editor.p5js.org/hora/full/RSb6d6oJT}{[Playable button \url{https://editor.p5js.org/hora/full/RSb6d6oJT}]}
\end{center}
\begin{answer}
We split the discussion into the following two steps.
\begin{enumerate}
\item First, analyze the rule under which the two endpoints are \emph{not} allowed to be pressed.
\item Next, revisit the problem under the rule that allows the endpoints to be pressed.
\end{enumerate}
\begin{enumerate}
\item \textbf{First: the rule where the endpoints cannot be pressed.}
Label the $n$ lamps by $0,\dots,n-1$, and assign to blinking patterns elements of $\F_4=\F_2[\omega]$ as follows.
\begin{description}
\item[{$\F_4$-invariant}] Assign $\omega^i\in \F_4$ to the $i$-th lamp, and sum these values over all lamps that are on (see Figure \ref{fig:F4Invariant}).
\end{description}
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[x=1cm,y=1cm]
% ---- 設定 ----
\def\n{12} % 箱の個数
\def\w{1.2} % 箱の幅
\def\h{0.8} % 箱の高さ
% ---- ランプパターン ----
% 1=点灯, 0=消灯
\def\lamppattern{{1,1,0,1,1,1,0,0,1,0,0,1}}
% 計算式の位置
\def\yFormula{-0.8}
% ---- 本体 ----
\foreach \i in {1,...,\n}{
\pgfmathsetmacro{\x}{(\i-1)*\w}
\draw (\x,0) rectangle ++(\w,\h);
% 周期3でラベル (1, ω, ω^2) → 常に箱の中に表示
\pgfmathtruncatemacro{\r}{mod(\i-1,3)}
\ifcase\r
\node at (\x+0.5*\w,0.5*\h) {$1$};
\def\val{$1$}
\or
\node at (\x+0.5*\w,0.5*\h) {$\omega$};
\def\val{$\omega$}
\or
\node at (\x+0.5*\w,0.5*\h) {$\omega^2$};
\def\val{$\omega^2$}
\fi
% ランプ状態取得
\pgfmathparse{\lamppattern[\i-1]}
\ifnum\pgfmathresult=1
% 点灯ランプ
\fill[yellow] (\x+0.5*\w, \h+0.5) circle (0.2);
\draw (\x+0.5*\w, \h+0.5) circle (0.2);
% 下の式に値を出力
\node at (\x+0.5*\w,\yFormula) {\val};
% プラス記号（最後以外）
\ifnum\i<\n
\node at (\x+\w,\yFormula) {$+$};
\else
\node at (\x+\w,\yFormula) {\hspace{30pt}$=\omega^2$};
\fi
\else
% 消灯ランプ
\draw (\x+0.5*\w, \h+0.5) circle (0.2);
% 下は空欄（プラスも書かない）
\fi
}
\end{tikzpicture}
\caption{An example of the $\F_4$-invariant}
\label{fig:F4Invariant}
\end{figure}
Then pressing any lamp with $0<i<n-1$ adds $\omega^{i-1}+\omega^{i}+\omega^{i+1}=0$ to the $\F_4$-invariant, so (as the name suggests) the $\F_4$-invariant is indeed invariant under such moves.
In fact, the condition that the $\F_4$-invariant equals $0$ is necessary and sufficient for solvability (i.e., for turning all lights off). Necessity is immediate from invariance. For sufficiency, use a greedy procedure: if the invariant is $0$, let $i$ be the leftmost lit lamp and press $i+1$. This clearly clears everything except possibly the rightmost two lamps; those two entries form an $\F_2$-basis of $\F_4$, so by the invariant-$0$ condition they end up off automatically once the rest has been cleared.
\item \textbf{Next: the rule where endpoints may be pressed.}
To avoid handling endpoints as exceptions, adjoin one lamp on the left and one on the right, for a total of $n+2$ lamps indexed by $0\le i\le n+1$. Allow pressing any $i$ with $0<i<n+1$. This reduces the problem to the first part and asks: “Given a blinking pattern on $n$ lamps, can we choose the two new endpoint lamps so that the total $\F_4$-invariant becomes $0$?”
For $n=0,1$ the question is trivial, so assume $n\ge2$. On the middle $n$ lamps every element of $\F_4$ can occur, so the question becomes: “For which $n$ do the two endpoint values $1$ and $\omega^{n+1}$ span $\F_4$ as an $\F_2$-vector space?” This holds exactly when $n+1\not\equiv 0\pmod 3$, i.e.\ when $n\equiv 0,1\pmod 3$. Moreover, when $n\equiv 2\pmod 3$, solvability is equivalent to the $\F_4$-invariant (computed on the original length-$n$ configuration) lying in $\F_2\subset \F_4$.
\end{enumerate}
\end{answer}
For later reference, we record the solvability criterion.
\begin{proposition}[Solvability criterion]\label{prop:OnedimChecking}
For a given lamp configuration $a=(a_i)_{i=1}^n\in \F_2^n$, the following are equivalent:
\begin{itemize}
\item $a$ is solvable (all lights can be turned off);
\item the $\F_4$-invariant $\sum_i a_i \omega^i\in \F_4$ lies in the $\F_2$-linear span $\langle 1, \omega^{n+1}\rangle\subset \F_4$ generated by the endpoint values.
\end{itemize}
\end{proposition}
\subsection{As the Rank of a Linear Map}\label{ssec:LinearRankSolution}
View the problem as a rank question for a linear self-map. Identify the standard basis $e_1,\dots,e_n$ of $\F_2^n$ with the lamps $1,\dots,n$, and define
\[
\phi_n\colon \F_2^n \to \F_2^n,\qquad
\phi_n(e_i)=
\begin{cases}
e_1+e_2 &(i=1),\\[2pt]
e_{i-1}+e_i+e_{i+1} &(1<i<n),\\[2pt]
e_{n-1}+e_n &(i=n).
\end{cases}
\]
For example, the matrix of $\phi_5$ is
\[
\begin{pmatrix}
1&1&0&0&0\\
1&1&1&0&0\\
0&1&1&1&0\\
0&0&1&1&1\\
0&0&0&1&1\\
\end{pmatrix}.
\]
The lamp-solvability problem is equivalent to any of the following:
\begin{itemize}
\item the $n$-lamp Lights Out is solvable from every initial configuration;
\item $\phi_n$ is surjective;
\item $\phi_n$ is an isomorphism;
\item every configuration is solvable in an essentially unique way.
\end{itemize}
\begin{lemma}\label{lem:CokerExpression}
$\Coker\phi_n$ classifies equivalence classes of configurations modulo the move relation; hence $\#\Coker \phi_n=2^{\corank \phi_n}$.
\end{lemma}
Our discussion shows that
\begin{equation}\label{eq:OneDimensioncorank}
\corank \phi_n =
\begin{cases}
0&(n\not \equiv 2 \!\!\!\pmod 3),\\
1&(n \equiv 2 \!\!\!\pmod 3).
\end{cases}
\end{equation}
\subsection{Structural Understanding of the \texorpdfstring{$\F_4$}{F4}-Invariant and the Rank}\label{ssec:StructualOneDim}
We reduced the discussion of the \textbf{bulk} (length-$n$ sequences) by first \textbf{extending to all} $n+2$ lamps and finally \textbf{restricting to the edge} so that the outcome depends only on the two endpoint $\F_4$-values. This can be organized in the following diagram (in the category $\Vect_{\F_2}$):
\[
\begin{tikzcd}[row sep=30pt]
0 & {\F_2^{2(=\textrm{edge})}} & {\F_2^{n+2(=\textrm{all})}} & {\F_2^{n(=\textrm{bulk})}} & 0 \\
0 & {\F_4} & {\F_4} & 0 & 0
\arrow[from=1-1, to=1-2]
\arrow[tail, from=1-2, to=1-3]
\arrow["{\tau_{\mathrm{edge}}}", from=1-2, to=2-2]
\arrow[two heads, from=1-3, to=1-4]
\arrow["\tau", two heads, from=1-3, to=2-3]
\arrow[from=1-4, to=1-5]
\arrow[from=1-4, to=2-4]
\arrow[from=2-1, to=2-2]
\arrow["{=}"{description}, no head, from=2-2, to=2-3]
\arrow[from=2-3, to=2-4]
\arrow[from=2-4, to=2-5]
\end{tikzcd}
\]
The top short exact sequence merely appends the two endpoints to a length-$n$ sequence. The bottom trivial sequence records the $\F_4$-invariant; it appears on the left two spots because we care about the invariant for \emph{edge} and for \emph{all} (not for bulk)\footnote{In the original proof, the invariant is evaluated precisely there: whether things vanish in \emph{all} is solvability itself, and the final step inspects the dimension of the edge invariant. In \emph{bulk} it only appears via the question “can we extend to \emph{all} so that the invariant becomes $0$?”.}. Here $\tau$ is the map taking the $\F_4$-invariant, and $\tau_{\textrm{edge}}$ is its restriction to the endpoints.
Apply the snake lemma to this diagram. Computing kernels and cokernels columnwise (right, middle, left) yields
\[
\begin{tikzcd}[row sep=30pt]
0 & \Ker \tau_{\mathrm{edge}} & {
\Solvable
} & {\F_2^{n(=\textrm{bulk})}} \\
0 & {\F_2^{2(=\textrm{edge})}} & {\F_2^{n+2(=\textrm{all})}} & {\F_2^{n(=\textrm{bulk})}} & 0 \\
0 & {\F_4} & {\F_4} & 0 & 0 \\
& \Coker \tau_{\mathrm{edge}} & 0 & 0 & 0
\arrow[from=1-1, to=1-2]
\arrow[tail, from=1-2, to=1-3]
\arrow[tail, from=1-2, to=2-2]
\arrow["{\sigma_n}", from=1-3, to=1-4]
\arrow[tail, from=1-3, to=2-3]
\arrow["{=}"{description}, no head, from=1-4, to=2-4]
\arrow["\delta"{description, pos=0.6}, dotted, two heads, from=1-4, to=4-2]
\arrow[from=2-1, to=2-2]
\arrow[tail, from=2-2, to=2-3]
\arrow["{\tau_{\mathrm{edge}}}", from=2-2, to=3-2]
\arrow[two heads, from=2-3, to=2-4]
\arrow["\tau", two heads, from=2-3, to=3-3]
\arrow[from=2-4, to=2-5]
\arrow[from=2-4, to=3-4]
\arrow[from=3-1, to=3-2]
\arrow["{=}"{description}, no head, from=3-2, to=3-3]
\arrow[two heads, from=3-2, to=4-2]
\arrow[from=3-3, to=3-4]
\arrow[from=3-4, to=3-5]
\end{tikzcd}
\]
\begin{description}
\item[Right column] Trivial: the kernel is $\F_2^n$ and the cokernel is $0$.
\item[Middle column] This is the essential part for the invariant. The cokernel is $0$ (for $n\ge2$ the map $\tau$ is surjective), while $\Ker \tau$ is the space of length-$(n+2)$ configurations with zero invariant, i.e.\ precisely those configurations clearable using only bulk moves; denote it by $\Solvable$.
\item[Left column] This is where the congruence class $n\equiv 2\pmod 3$ shows up; we compute it shortly.
\end{description}
Our invariant argument focuses on the natural map (denoted $\sigma_n\colon \Solvable \to \F_2^n$ in the diagram). (Its relation to $\phi_n$ appears in Remark \ref{rem:RelationWithPhi}.) An initial configuration in $\F_2^n$ is solvable iff it extends to some solvable length-$(n+2)$ configuration, i.e.\ iff it lies in $\Image(\sigma_n)$. By Lemma \ref{lem:CokerExpression} and the snake lemma we get
\[
\Coker\sigma_n \cong \Coker \tau_{\mathrm{edge}}.
\]
The right-hand side is the cokernel of the explicit $\F_2$-linear map $\tau_{\mathrm{edge}}\colon \F_2^2\to \F_4$ sending the basis elements $e_0,e_{n+1}$ to $1,\omega^{n+1}\in \F_4$. Thus
\[
\dim_{\F_2}\Ker \tau_{\mathrm{edge}} = \dim_{\F_2}\Coker \tau_{\mathrm{edge}} =
\begin{cases}
0 &(n\not \equiv 2 \!\!\!\pmod 3),\\
1 &(n\equiv 2 \!\!\!\pmod 3),
\end{cases}
\]
recovering the counting in \eqref{eq:OneDimensioncorank}.
\begin{remark}[Where is $\phi_n$?]\label{rem:RelationWithPhi}
Acting by the bulk move space $\F_2^{n}$ on the all-off state yields a linear map $\alpha:\F_2^{n}\to \Ker\tau$. This is an isomorphism, and via the identification $\F_2^{n}\cong \Ker\tau$ the maps $\phi_n$ and $\sigma_n$ correspond.
Indeed, both spaces have dimension $n$ (see the exact rows above). That $\alpha$ is injective follows from a simple combinatorial argument by scanning from the leftmost lamp.
\end{remark}
\subsection{Understanding Solvability via the Connecting Homomorphism}
How does Proposition \ref{prop:OnedimChecking} arise? This is precisely the completeness part of the snake-lemma sequence. For a configuration $a=(a_i)\in \F_2^n$,
\[
\text{$a$ is solvable} \iff a\in \Image(\sigma_n) \iff \delta(a)=0.
\]
The left equivalence is the invariant argument; the right equivalence is exactly the statement that the connecting homomorphism vanishes on the image. Unwinding definitions, the condition $\delta(a)=0$ says:
\begin{itemize}
\item the $\F_4$-invariant $\sum_i a_i \omega^i\in \F_4$ lies in the $\F_2$-span $\langle1,\omega^{n+1}\rangle\subset \F_4$ of the two endpoint values,
\end{itemize}
which is exactly Proposition \ref{prop:OnedimChecking}. The construction of $\delta$ proceeds by alternating “down, left, down, left, down” in the diagram; the only nontrivial step is the final “down,” which tests membership in $\Image(\tau_{\mathrm{edge}})=\langle1,\omega^{n+1}\rangle\subset\F_4$.
\newpage
\section{Two-Dimensional Lights Out}
\begin{problem}[Two-dimensional case] \quad (The $d$-dimensional case is analogous.)
Let $n,m\ge2$ be integers. $n \times m$ lamps are arranged in a rectangle. Pressing any lamp toggles that lamp and its neighbors.
\begin{enumerate}
\item Determine all pairs $(n,m)$ such that every initial configuration is solvable.
\item For given $n,m$, determine the number of equivalence classes under the move relation.
\item Given an initial configuration, is there a method to decide whether one can turn all lights off?
\end{enumerate}
\end{problem}
\begin{center}
\href{https://editor.p5js.org/hora/sketches/G6H7A2lv5}{[Playable button \url{https://editor.p5js.org/hora/sketches/G6H7A2lv5}]}
\end{center}
\subsection{As the Rank of a Tensor Product Map}
Parts (1) and (2) can be computed succinctly using tensors. We use the following linear-algebra fact.
\begin{lemma}\label{lem:corankCalculus}
For linear maps over a field $K$, $f_0\colon V_0 \to W_0$ and $f_1\colon V_1 \to W_1$,
\[
\rank(f_0\otimes f_1) = \rank(f_0)\cdot \rank(f_1).
\]
\end{lemma}
Together with $\rank f + \corank f = \dim_K(\cod f)$, this also yields $\corank$ for tensor products.
\begin{answer}[A short answer for (1) and (2)]
By the method of Subsection \ref{ssec:LinearRankSolution} we reduce to the one-dimensional case. Consider
\[
\phi_{n,m} \colon \F_2^{nm}\to \F_2^{nm},\qquad
\phi_{n,m}(e_{i,j}) \coloneqq \sum_{1\leq i',j'\leq n,\; |i-i'|\leq 1,\; |j-j'|\leq 1} e_{i',j'}.
\]
We need $\corank\phi_{n,m}$. Then
\[
\#\text{(equivalence classes)} \;=\; 2^{\corank\phi_{n,m}},\qquad
\text{and}\qquad
\text{(1) asks for } \corank\phi_{n,m}=0.
\]
Identifying standard bases shows $\phi_{n,m}\cong \phi_n\otimes \phi_m$, hence
\[
\rank (\phi_{n,m}) = \rank (\phi_{n}\otimes \phi_{m}) = \rank (\phi_{n})\cdot \rank(\phi_{m}),
\]
and
\begin{align*}
\corank (\phi_{n,m})
&= nm- \rank (\phi_{n})\cdot \rank( \phi_{m})\\
&= nm- (n-\corank \phi_{n})\cdot (m-\corank \phi_{m})\\
&= m\cdot \corank \phi_{n}+ n\cdot\corank \phi_{m} - \corank \phi_{n}\cdot\corank \phi_{m}.
\end{align*}
Using \eqref{eq:OneDimensioncorank} we obtain:
\begin{proposition}\label{prop:CountingTwoDim}
\[
\#\text{(equivalence classes)} =
\begin{cases}
1 &(n,m \not \equiv 2 \!\!\!\pmod 3),\\
2^n &(n \not \equiv 2 \!\!\!\pmod 3,\ \ m \equiv 2 \!\!\!\pmod 3),\\
2^m &(n \equiv 2 \!\!\!\pmod 3,\ \ m \not \equiv 2 \!\!\!\pmod 3),\\
2^{\,n+m-1} &(n,m \equiv 2 \!\!\!\pmod 3).
\end{cases}
\]
\end{proposition}
In particular, every configuration is solvable iff $n,m \not \equiv 2 \pmod 3$.
\end{answer}
\subsection{A Structural Analysis}
The previous proof is concise and quantitative (it counts classes). Here we aim for a more structural understanding. Using invariants we also capture shortest solutions and an explicit solvability test. The content parallels Subsection \ref{ssec:StructualOneDim}.
As in the one-dimensional case, extend to $(1+n+1)\times(1+m+1)$ and restrict moves to the interior cells only.
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[x=1.4cm,y=-1.2cm] % draw rows from top to bottom
% ====== basic settings ======
\def\nr{4} % rows
\def\nc{6} % columns
\def\rad{0.14} % lamp radius
% ====== lamp pattern (row-major; 1=on, 0=off) ======
\def\lamppattern{%
1,0,1,0,1,0,%
0,1,0,1,0,1,%
1,1,0,0,1,0,%
0,0,1,1,0,1%
}
% ====== row/column labels (edit as needed) ======
\def\rowsums{$0$, $0$, $\omega^2$, $1$}
\def\colsums{$\omega$, $\omega$, $0$, $\omega^2$, $\omega^2$, $\omega$}
% ====== cells and lamps ======
\foreach[count=\k from 1] \lamp in \lamppattern {
% recover (i,j) from k
\pgfmathtruncatemacro{\i}{ceil(\k/\nc)}
\pgfmathtruncatemacro{\j}{mod(\k-1,\nc)+1}
\pgfmathsetmacro{\x}{\j}
\pgfmathsetmacro{\y}{\i}
% show 1, ω, ω^2 according to (i+j+1) mod 3
\pgfmathtruncatemacro{\m}{mod(\i+\j+1,3)}
\ifcase\m
\node at (\x,\y) {$1$};
\or
\node at (\x,\y) {$\omega$};
\or
\node at (\x,\y) {$\omega^2$};
\fi
% lamp state
\ifnum\lamp=1
\fill[yellow] (\x,\y-0.45) circle (\rad);
\draw (\x,\y-0.45) circle (\rad);
\else
\draw (\x,\y-0.45) circle (\rad);
\fi
}
% ====== row labels (right side) ======
\pgfmathsetmacro{\xlab}{\nc + 0.8}
\foreach[count=\ri from 1] \rtext in \rowsums {
\node at (\xlab,\ri) {\rtext};
}
% ====== column labels (bottom) ======
\pgfmathsetmacro{\ylab}{\nr + 0.8}
\foreach[count=\cj from 1] \ctext in \colsums {
\node at (\cj,\ylab) {\ctext};
}
\end{tikzpicture}
\end{figure}
\begin{lemma}\label{lem:TwoDimBulk}
With interior-only moves, a configuration is solvable iff the $\F_4$-invariant is $0$ on every row and on every column.
\end{lemma}
More precisely: assigning $\omega^{i+j}\in \F_4$ to cell $(i,j)$, the sum of these values over the lit cells in each fixed row and in each fixed column must vanish.
\begin{proof}
Exactly as in one dimension. Necessity follows since these $\F_4^{(\text{rows}+\text{columns})}$-valued quantities are invariant under interior moves. For sufficiency, greedily push lit cells into the bottom two rows and the rightmost two columns; the invariant forces the rest to clear.
\end{proof}
Thus (1) reduces to: given an interior pattern $(a_{i,j})_{0<i<n+1,\,0<j<m+1}$, does there exist an extension $(a_{i,j})_{0\le i\le n+1,\,0\le j\le m+1}$ such that the $\F_4$-invariant vanishes on all $n+2$ rows and all $m+2$ columns?
\begin{remark}[Concrete description of $\tau$]\label{rem:ConcreteDescriptionOfTau}
Viewing lamp configurations as elements of the $\F_2$-space of dimension $(n+2)(m+2)$, our invariant is the $\F_2$-linear map
\[
\tau\colon \F_{2}^{(n+2)(m+2)} \to \F_4^{n+2}\times \F_4^{m+2},
\]
where for $(a_{i,j})_{i,j}$ we set
\begin{equation}\label{eq:x}
x_i \coloneqq \sum_{j=0}^{m+1} a_{i,j} \,\omega^{i+j},
\end{equation}
\begin{equation}\label{eq:y}
y_j \coloneqq \sum_{i=0}^{n+1} a_{i,j} \,\omega^{i+j}.
\end{equation}
(We regard $a_{i,j}\in\F_2\subset \F_4$.)
\end{remark}
As before we work in $\Vect_{\F_2}$ and draw the diagram
\[
\begin{tikzcd}[row sep=30pt]
0 & {\F_2^{2n+2m+4(=\textrm{edge})}} & {\F_2^{(n+2)(m+2)(=\textrm{all})}} & {\F_2^{nm(=\textrm{bulk})}} & 0 \\
0 & {\F_4^{n+2} \times \F_4^{m+2}} & {\F_4^{n+2} \times \F_4^{m+2}} & 0 & 0
\arrow[from=1-1, to=1-2]
\arrow[tail, from=1-2, to=1-3]
\arrow["{\tau_{\mathrm{edge}}}", from=1-2, to=2-2]
\arrow[two heads, from=1-3, to=1-4]
\arrow["\tau", from=1-3, to=2-3]
\arrow[from=1-4, to=1-5]
\arrow[from=1-4, to=2-4]
\arrow[from=2-1, to=2-2]
\arrow["{=}"{description}, no head, from=2-2, to=2-3]
\arrow[from=2-3, to=2-4]
\arrow[from=2-4, to=2-5]
\end{tikzcd}
\]
(Unlike the 1D case, $\tau$ need not be surjective, so the arrow is not double-headed.)
Applying the snake lemma gives
\[
\begin{tikzcd}[row sep=30pt]
0 & \Ker \tau_{\mathrm{edge}} & {
\Solvable
} & {\F_2^{nm(=\textrm{bulk})}} \\
0 & {\F_2^{2n+2m+4(=\textrm{edge})}} & {\F_2^{(n+2)(m+2)(=\textrm{all})}} & {\F_2^{nm(=\textrm{bulk})}} & 0 \\
0 & {\F_4^{n+2} \times \F_4^{m+2}} & {\F_4^{n+2} \times \F_4^{m+2}} & 0 & 0\\
& \Coker \tau_{\mathrm{edge}} & ? & 0 & 0
\arrow[from=1-1, to=1-2]
\arrow[tail, from=1-2, to=1-3]
\arrow[tail, from=1-2, to=2-2]
\arrow["{\sigma_{n,m}}", from=1-3, to=1-4]
\arrow[tail, from=1-3, to=2-3]
\arrow["{=}"{description}, no head, from=1-4, to=2-4]
\arrow["\delta"{description, pos=0.6}, dotted, two heads, from=1-4, to=4-2]
\arrow[from=2-1, to=2-2]
\arrow[tail, from=2-2, to=2-3]
\arrow["{\tau_{\mathrm{edge}}}", from=2-2, to=3-2]
\arrow[two heads, from=2-3, to=2-4]
\arrow["\tau", from=2-3, to=3-3]
\arrow[from=2-4, to=2-5]
\arrow[from=2-4, to=3-4]
\arrow[from=3-1, to=3-2]
\arrow["{=}"{description}, no head, from=3-2, to=3-3]
\arrow[two heads, from=3-2, to=4-2]
\arrow[from=3-3, to=3-4]
\arrow[two heads, from=3-3, to=4-3]
\arrow[from=3-4, to=3-5]
\arrow[from=3-4, to=4-4]
\arrow[from=4-2, to=4-3]
\arrow[from=4-3, to=4-4]
\arrow[from=4-4, to=4-5]
\end{tikzcd}
\]
The right column is trivial; the left column will be computed later. The middle kernel equals the space of configurations clearable by interior moves, as in 1D. The new ingredient is the middle cokernel $\Coker\tau$.
\begin{lemma}
As an $\F_2$-vector space, $\Coker \tau \cong \F_4^2$.
\end{lemma}
\begin{proof}
First, $\corank \tau=\dim_{\F_2}\Coker\tau\le 4$ follows by inspecting the definition of $\tau$ (Remark \ref{rem:ConcreteDescriptionOfTau}). Given $(x_0,\dots,x_{n+1},y_0,\dots,y_{m+1})\in \F_4^{n+2}\times \F_4^{m+2}$, we can realize all entries except possibly $x_0,x_1$ by choosing $(a_{i,j})$ with $a_{i,j}=0$ for $i,j\ge3$, then solving for each column $j$ using that $\omega^{0+j},\omega^{1+j}$ form an $\F_2$-basis, and similarly for each row $i\ge2$ using $a_{i,0},a_{i,1}$ (the overlap prevents freely choosing $x_0,x_1$).
Next, define the $\F_4$-linear (hence $\F_2$-linear) map
\[
\alpha\colon \F_4^{n+2} \times \F_4^{m+2} \to \F_4,\qquad
\alpha(x_i,y_j)= \sum_i x_i - \sum_j y_j.
\]
Then $\alpha\circ\tau=0$ by Fubini-like cancellation:
\[
\alpha(\tau(a_{i,j}))=\sum_{i,j} a_{i,j}\omega^{i+j}-\sum_{j,i} a_{i,j}\omega^{i+j}=0.
\]
Using Frobenius ${(-)}^2\colon \F_4\to \F_4$, define the $\F_2$-linear (but not $\F_4$-linear) “twisted sum”
\[
\beta\colon \F_4^{n+2} \times \F_4^{m+2} \to \F_4,\qquad
\beta(x_i,y_j)= \sum_i x_i \omega^i - \sum_j y_j^2 \omega^{2j}.
\]
Again $\beta\circ\tau=0$. Thus
\[
\langle \alpha,\beta\rangle\colon \F_4^{n+2} \times \F_4^{m+2} \to \F_4^2
\]
factors through $\Coker\tau$. Surjectivity follows by restricting to variables $x_0,x_1$ with all other $x_i,y_j$ set to $0$, where the induced $\F_4$-linear map is represented by the invertible $2\times2$ matrix $\begin{psmallmatrix}1&1\\ 1&\omega\end{psmallmatrix}$.
\end{proof}
Hence we obtain
\[
\begin{tikzcd}[row sep=30pt]
0 & \Ker \tau_{\mathrm{edge}} & {
\Solvable
} & {\F_2^{nm(=\textrm{bulk})}} \\
0 & {\F_2^{2n+2m+4(=\textrm{edge})}} & {\F_2^{(n+2)(m+2)(=\textrm{all})}} & {\F_2^{nm(=\textrm{bulk})}} & 0 \\
0 & {\F_4^{n+2} \times \F_4^{m+2}} & {\F_4^{n+2} \times \F_4^{m+2}} & 0 & 0\\
& \Coker \tau_{\mathrm{edge}} & \F_4^2 & 0 & 0
\arrow[from=1-1, to=1-2]
\arrow[tail, from=1-2, to=1-3]
\arrow[tail, from=1-2, to=2-2]
\arrow["{\sigma_{n,m}}", from=1-3, to=1-4]
\arrow[tail, from=1-3, to=2-3]
\arrow["{=}"{description}, no head, from=1-4, to=2-4]
\arrow["\delta"{description, pos=0.6}, dotted, two heads, from=1-4, to=4-2]
\arrow[from=2-1, to=2-2]
\arrow[tail, from=2-2, to=2-3]
\arrow["{\tau_{\mathrm{edge}}}", from=2-2, to=3-2]
\arrow[two heads, from=2-3, to=2-4]
\arrow["\tau", from=2-3, to=3-3]
\arrow[from=2-4, to=2-5]
\arrow[from=2-4, to=3-4]
\arrow[from=3-1, to=3-2]
\arrow["{=}"{description}, no head, from=3-2, to=3-3]
\arrow[two heads, from=3-2, to=4-2]
\arrow[from=3-3, to=3-4]
\arrow["{\langle \alpha,\beta\rangle}", two heads, from=3-3, to=4-3]
\arrow[from=3-4, to=3-5]
\arrow[from=3-4, to=4-4]
\arrow[from=4-2, to=4-3]
\arrow[from=4-3, to=4-4]
\arrow[from=4-4, to=4-5]
\end{tikzcd}
\]
Therefore the desired quantity $\corank \sigma_{n,m}$ reduces to computing the left column
\[
\begin{tikzcd}
0\ar[r]&\Ker \tau_{\textrm{edge}}\ar[r, rightarrowtail]&\F_2^{2n+2m+4}\ar[r, "\tau_{\mathrm{edge}}"]&{\F_4^{n+2} \times \F_4^{m+2}} \ar[r, twoheadrightarrow]& \Coker \tau_{\mathrm{edge}} \ar[r]& 0 .
\end{tikzcd}
\]
One route is to note from the middle column that $\dim_{\F_2}\Solvable=nm$, reducing to $\dim\Ker \tau_{\textrm{edge}}$. Another is to use the snake-lemma exact sequence
\[
\begin{tikzcd}
\Solvable \ar[r, "\sigma_{n,m}"]
& {\F_2^{nm}}\ar[r, "\delta"] & \Coker \tau_{\mathrm{edge}} \ar[r, twoheadrightarrow]& \F_4^2 \ar[r]& 0
\end{tikzcd}
\]
and reduce to $\dim \Coker \tau_{\textrm{edge}}$. In either approach, an argument parallel to the 1D edge calculation—comparing weights $\omega^{i+j}$ on opposite sides—gives
\[
\dim_{\F_2}(\Ker \tau_{\textrm{edge}}) =
\begin{cases}
0 &(n,m \not \equiv 2 \!\!\!\pmod 3),\\
n &(n \not \equiv 2 \!\!\!\pmod 3,\ \ m \equiv 2 \!\!\!\pmod 3),\\
m &(n \equiv 2 \!\!\!\pmod 3,\ \ m \not \equiv 2 \!\!\!\pmod 3),\\
n+m-1 &(n,m \equiv 2 \!\!\!\pmod 3).
\end{cases}
\]
Since $\dim_{\F_2}\Solvable=\dim_{\F_2}\F_2^{nm}$, we also get $\dim_{\F_2}\Coker \sigma_{n,m}=\dim_{\F_2}\Ker \tau_{\textrm{edge}}$, recovering Proposition \ref{prop:CountingTwoDim}.
\subsection{Solvability via the Connecting Homomorphism}
Exactly as in the 1D case, for a pattern $a=(a_{i,j})\in \F_2^{nm}$ we have
\[
\text{$a$ is solvable} \iff a\in \Image(\sigma_{n,m}) \iff \delta(a)=0.
\]
Moreover, this controls shortest solutions:
\begin{description}
\item[$(n,m \not \equiv 2 \pmod 3)$] Every configuration is solvable, and the shortest solution is determined. Each initial pattern extends \emph{uniquely} to a solvable $(n+2)\times(m+2)$ pattern (dimension count or the fact that opposite blanks form an $\F_2$-basis of $\F_4$). Then greedily clear from the top-left using interior moves and push into the bottom two rows and rightmost two columns; the invariant forces the rest to vanish. No lamp is pressed twice and the solution is unique, hence shortest.
\item[$(n \not \equiv 2 \pmod 3,\ m \equiv 2 \pmod 3)$] Solvability is equivalent to: for every row, the interior $\F_4$-invariant equals an $\F_2$-multiple of the (coinciding) endpoint value in the extended configuration. If solvable, first zero the row invariants (there are $2^n$ choices; e.g.\ clear the entire leftmost column, which then determines the rest), then zero all column invariants (uniquely), and finally push to the bottom-right. This press-once algorithm is efficient, though not necessarily the absolute shortest among the $2^n$ choices.
\item[$(n \equiv 2 \pmod 3,\ m \not \equiv 2 \pmod 3)$] Symmetric to the previous case.
\item[$(n,m \equiv 2 \pmod 3)$] Proceed as follows. Among extensions to $(n+2)\times(m+2)$, first clear the entire first row and first column. Then adjust the remaining $n+m+1$ boundary lamps so that every row and column invariant becomes $0$. (This requires not only that each invariant be an $\F_2$-multiple of the edge value but also that the values coincide appropriately and differ from the bottom-right corner weight.) When possible, this adjustment is canonical and unique; failure indicates nonsolvability. If successful, push to the bottom-right to finish.
\end{description}
\printbibliography
\end{document}