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 jth 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.

  1. Chandrasekhar
    February 8, 2011 at 4:54 am

    Awesome post. Really enjoyed reading it.

    • February 8, 2011 at 11:09 am

      I’m glad to hear that. Thanks 🙂

  1. March 5, 2011 at 11:57 pm

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: