Suppose that you have $n$ switches, numbered from $1$ to $n$, connected to $n$ light bulbs, also numbered from $1$ to $n$. They are connected in the sense that turning a switch reverses the state of all light bulbs connected to that switch. There are two tules
- the $k^{\text{th}}$ switch is connected to the $k^{\text{th}}$ light bulb;
- if the $k^{\text{th}}$ switch is connected to the $m^{\text{th}}$ light bulb, then the $m^{\text{th}}$ switch is connected to the $k^{\text{th}}$ light bulb.
Suppose that all the light bulbs are off. Prove that it is possible to turn all the lights on.
I was able to see that this can be seen as linear algebra problem over $\mathbb{F}_2$:
Consider a symmetric bilinear form $\langle\cdot,\cdot\rangle$ on ${\mathbb{F}_2}^n$ such that, for any vector $e_k$ from the canonical basis, $\langle e_k,e_k\rangle=1$. Consider also the linear form$$\begin{array}{rccc}\alpha\colon&{\mathbb{F}_2}^n&\longrightarrow&\mathbb{F}_2\\&(x_1,\ldots,x_n)&\mapsto&\displaystyle\sum_{k=1}^nx_k.\end{array}$$Prove that there is a vector $v\in{\mathbb{F}_2}^n$ such that $\alpha=\langle\cdot,v\rangle$.
I think I like to think of this in terms of matrices and vectors. All coefficients in $\mathbb{F}_2$, of course. So we are given a symmetric matrix $A$, with all $1$ on the diagonal, and need to show that the vector $e=(1,\ldots,1)^T$ belongs to the range of $A$.
Now consider a vector $z$ in the null space of $A$, and let $I\subseteq\{1,\ldots,n\}$ be the set of indices for which $z_i=1$. Then $z^TAz$ counts the number modulo $2$ of $1$ entries among the $a_{ij}$ for which $i,j\in I$. So there must be an even number of $1$ entries. But there are an even number of off-diagonal $1$ entries among those, because of the symmetry. There is a $1$ in every diagonal entry, and it follows from $z^TAz=0$ that $I$ has an even number of elements.
We have just shown that, if $z$ is in the null space of $A$, then $e^Tz=0$. But linear algebra tells us that the range of $A$ is the orthogonal complement of the null space of $A^T=A$, so $e$ is in the range of $A$.