## Lamps and switches

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

- Switch controls lamp (and maybe other lamps too), and using it you change the status of the lamps it controls.
- Switch controls lamp if and only if switch controls lamp .

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 where is the field with two elements. For each switch consider the vector such that the th component of is if and only if switch controls lamp .

Consider now the square matrix obtained by adjoining these vectors which is a symmetric matrix. Define the linear operator . If we denote by the vector of ones, then it suffices to prove that there exists a vector such that . This is equivalent to , which we would like to prove in the following way.

Denote 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 . For these fields, the inner product must be a bilinear symmetric form, which is non-singular, i.e. . Our inner product has the required properties. Therefore, for any subspace we have . The implication is obvious, therefore, to prove that we will prove that . 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 then which is equivalent to . Therefore .

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

Awesome post. Really enjoyed reading it.

I’m glad to hear that. Thanks 🙂