## Lamps and switches

We have $n$ lamps and $n$ switches such that the following conditions hold:

1. Switch $i$ controls lamp $i$ (and maybe other lamps too), and using it you change the status of the lamps it controls.
2. Switch $i$ controls lamp $j$ if and only if switch $j$ controls lamp $i$.

Prove that if in the beginning all the lamps are off, there exist some switches which pressed simultaneously turn on all the lamps.

Solution: This problem admits a very cool solution using linear algebra. All we need to do is to create a good model of the problem in some vector space. For this, consider the vector space $\Bbb{F}_2^n$ where $\Bbb{F}_2$ is the field with two elements. For each switch $i$ consider the vector $t_i \in \Bbb{F}_2^n$ such that the $j$th component of $t_i$ is $1$ if and only if switch $i$ controls lamp $j$.

Consider now the square matrix obtained by adjoining these vectors $A=(t_1 |t_2 |...|t_n)$ which is a symmetric matrix. Define the linear operator $T : \Bbb{F}_2^n \to \Bbb{F}_2^n,\ Tv=Av$. If we denote by $u=(1,1,...,1)$ the vector of ones, then it suffices to prove that there exists a vector $v$ such that $Av=u$. This is equivalent to $u \in Im T$, which we would like to prove in the following way.

Denote $(x,y)=x_1y_1+...+x_ny_n$ the usual inner product bilinear form. This is not an inner product in the usual sense, but there exists a theory for vector spaces over fields which are not $\Bbb{R},\Bbb{C}$. For these fields, the inner product must be a bilinear symmetric form, which is non-singular, i.e. $(x,u)=0,\ \forall x \Rightarrow u=0$. Our inner product has the required properties. Therefore, for any subspace $S \leq \Bbb{F}_2^n$ we have $S=(S^\perp)^\perp$. The implication $A\subset B \Rightarrow B^\perp \subset A^\perp$ is obvious, therefore, to prove that $u \in ImT$ we will prove that $(ImT)^\perp \subset u^\perp$. For references for the general inner product, see Jack E. Graver – An Alternative Approach to the Dimension Theorem for Inner Product Spaces, The American Mathematical Monthly. August-September 1987, Volume 94, Number 7.

To do this, see that if $v \in (Im T)^\perp$ then $(v,Av)=0$ which is equivalent to $v_1+v_2+...+v_n=(v,u)=0$. Therefore $v \in u^\perp$.

This completely solves the problem. To see an alternative approach, check out this link.