$N$ lights are off. There are $N$ switches. Switch $i$ controls light $i$, and it may control other lights in addition to light $i$. The switches and lights are interlocked (if switch $i$ can turn on light $j$, switch $j$ can also turn on light $i$). Proves that there must be a way to turn on all lights.
I tried to express the lights and switches relationship into a matrix. For sure, it is symmetric, and I cannot move on. I tried induction, but I've got no idea. Any ideas?
I first saw this solution in Algebraic Combinatorics: Walks, Trees, Tableaux, and More by Richard Stanley, page 238. He says that a special case of this problem, where the switches are on an $m\times n$ grid and each switch is connected to its orthogonal neighbors, was open for "many years". This seems to suggest this problem is pretty hard, but perhaps knowing that the correct approach is linear algebra for general graphs makes it considerably easier. I give a pretty thorough outline below, with some gaps for you to fill in.
Consider the adjacency matrix $A$, where $A_{i,j}=1$ if the switch for light $i$ also controls light $j$, and $0$ otherwise. This means $A$ is symmetric with ones on the diagonal. We view the entries of $A$ as elements of $\mathbb Z/2\mathbb Z$.
Let $\bf 1$ be the all-ones column vector. In order to prove you can turn on all the lights, you need to show that $\bf 1$ is in the image of $A$. To do this, we use this fact from linear algebra:
$\text{im }A=(\text{ker }A^\top)^\perp$.
This means that in order to show ${\bf 1}\in \text{im }A$, it suffices to show that $\bf 1$ is orthogonal to every vector in the null space of $A^\top$, which is just $A$.
To this end, let $z$ be any vector in $\text{ker A}$, so $Az=0$. We need to show $z^\top{\bf 1}=0$. If you write $A=I+B$, with $I$ the identity matrix and $B$ a symmetric matrix with zeroes on the diagonal, then $$ 0=z^\top Az=z^\top Iz+z^\top Bz $$ Now, you can then show that
$z^\top Bz=0$, and
$z^\top Iz=z^\top {\bf 1}$,
so the above implies $z$ is orthogonal to $\bf 1$, which is what we wanted. I leave proving the last two bullets as an exercise to the reader.
$\text{im }A=(\text{ker }A^\top)^\perp$ is usually stated in the context of inner product spaces over $\Bbb R$ or $\Bbb C$, but it works just as well for $(\Bbb Z/2\Bbb Z)$-matrices, where the "inner product" is defined to be $\langle v,w\rangle= v^\top w$ for column vectors $v,w$. Here is the proof, behind a spoiler in case you want to try to figure it out yourself.
$\newcommand{\im}{\operatorname{im}}\newcommand{\ker}{\operatorname{ker}}$ First, we show $\im A\subseteq (\ker A^\top)^\perp$. Let $y\in \im A$, so that $y=Ax$ for some $x$, and let $z\in \ker A^\top$, so that $A^\top z=0$. Then $$z^\top y=z^\top (Ax)=(A^\top z)^\top y=0y=0,$$ proving $y$ is orthogonal to every vector in $\ker A^\top$, so $\im A\subseteq (\ker A^\top)^\perp$. You then prove equality by counting dimensions, since $$\dim(\im A)=n-\dim (\ker A^T)=n-(n-\dim((\ker A^\top)^\perp))=\dim((\ker A^\top)^\perp).$$The first equation is the rank-nullity theorem, and the second is $\dim V=n-\dim V^\perp$, applied to $V=\ker A^\top$. The equation $\dim V=n-\dim V^\perp$ follows by applying the rank-nullity theorem to a matrix whose rows form a basis for $V$.
