wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> All lights on puzzle
        
(Message started by: Aryabhatta on Sep 24^th, 2004, 8:40am)

Title: All lights on puzzle
Post by Aryabhatta on Sep 24^th, 2004, 8:40am

Here is an interesting problem which is sort of related to the Communist graph problem mentioned by baudolino in the 'Socialist graph' thread.

You have a set of n bulbs and n switches. Switch i controls a fixed set of bulbs B_i. Each set B_i satisfies the following: (For convenience, asssume the bulbs are numbered 1 to n too)

1) i [in] B_i
2) j [in] B_i if and only if i [in] B_j

Initially all bulbs are off. Show that by toggling some set of switches one can turn on all the bulbs.

Title: Re: All lights on puzzle
Post by baudolino on Sep 24^th, 2004, 8:10pm

In terms of graphs, the problem becomes:

G graph. Let A be the adjacent matrix associated to G. Consider the matrix I+A, where I is the identity matrix. Prove that there is a subset of rows such that the sum of the rows (as a vector with entries in Z/2Z) is the vector (1,1,1,...,1).

Without loss of generality, G can be assumed connected.
The problem follows immediately if I+A is nonsingular in Z/2Z.
I did not get anywhere when I+A is singular ( exactly when -1 is a graph eigenvalue).

Title: Re: All lights on puzzle
Post by Aryabhatta on Sep 25^th, 2004, 1:36pm

on 09/24/04 at 20:10:13, baudolino wrote:

In terms of graphs, the problem becomes:
Without loss of generality, G can be assumed connected.
The problem follows immediately if I+A is nonsingular in Z/2Z.
I did not get anywhere when I+A is singular ( exactly when -1 is a graph eigenvalue).

Yes. We need to show that there is some x such that x + Ax = J where J = a column of all 1's. It is an interesting approach and I am sure a proof using Linear Algebra can be found.

There is also a non-Linear Algebra proof of this.

I think this problem is equivalent to the Communist graph problem, with initial values all 0 and final values all 1.

Title: Re: All lights on puzzle
Post by Aryabhatta on Sep 25^th, 2004, 6:08pm

Here is a Linear Algebra proof of this due to Noga Alon.

:[hide]

First some definitions and theorems.
Let V be a vector space over a field [bbf]. (Assume it is actually a subspace of a larger space)

Define Ortho(V) to be the set of all vectors orthogonal to each vector of V.

i.e Ortho(V) = {x | x^Ty = 0, [forall] y [in] V}

It can be shown that

Theorem1: if W = Ortho(V), then V = Ortho(W).
(I won't prove this here).

This implies the following.

Corollary1: If a [notin] V, then there is a vector w orthogonal to each element of V but not orthogonal to a.
(V is a sub space of a larger vector space)

Proof: Follows easily from Theorem 1.

Note that the above is valid for any field.

From now on the field is [bbf]₂.

Let A be a symmetric NxN matrix. Let the ij^th entry be a_ij. Consider the diagonal of A,
d = (a₁₁,a₂₂,...,a_NN)

For any vector v, we have that

v^TAv = d^Tv. (since r² = r and r + r = 0 in [bbf]₂)

Let [bbr](A) be the space spanned by the rows of A.

Proposition1: d [in] [bbr](A).

Proof: Assume d [notin] [bbr](A). Then by Corollary1 of Theorem 1, we have that there is some w orthogonal to the rows of A but not to d. For this w, Aw = 0.
Now w^TAw = d^Tw. Since Aw = 0, we have that RHS is also 0, i.e d is orthogonal to w.
Contradiction. Hence d [in] [bbr](A).

In the case of our problem, d is (1,1,....,1).

All can I say about this proof: WOW! :o
[/hide]

Title: Re: All lights on puzzle
Post by Aryabhatta on Sep 26^th, 2004, 2:53pm

Here is a hint for a proof which does not use Linear Algebra.

:[hide]

First prove the following result:
G is a connected graph. Let V(G) be the vertex set of G.

Show that V(G) can be decomposed into two disjoint sets V₁ and V₂ such that:

i) [forall] x [in] V₁, the cardinality of S = {y| y [in] V₁ and (x,y) is an edge of G} is even.
ii) [forall] x [in] V₂, the cardinality of S = {y| y [in] V₂ and (x,y) is an edge of G} is even.

i.e V₁ and V₂ each span even degree subgraphs of G.

Note: we don't care about the edges going from V₁ to V₂

The above result can be proved by using Linear Algebra too!

:[/hide]

Title: Re: All lights on puzzle
Post by baudolino on Sep 27^th, 2004, 7:11am

1st proof is nice. Very nice.

Maybe because I usually avoid Z/2Z, theorem 1 was not trivial to me. The theorem follows from the dimension equality dim V + dim V^[perp] = dim U, where V [subseteq] U. The equality follows if you consider the composition i^* [circ] B, where B : V ---> V^* is the isomorphism induced by the nondegenerate bilinear form, i^* : V^* ---> U^* is the dual of the inclusion i : U ---> V, and [circ] is the composition sign. The function i^* [circ] B is surjective and its kernel is U^[perp], so the equality follows from the usual dim (kernel f) + dim(image f) = dim(domain f).

My initial failed attempt was to prove theorem 1 directly, through a study of the nonedegenerate symmetric bilinear forms over Z/2Z. Given such a form B over U and a subspace V [subseteq] U, I tried to look for a normal form for B relative to a base of vectors of U that extends a base of vectors of V. I quickly got into trouble when the restriction of the form B to V is degenerate (exactly when V [cap] V^[perp] is nonempty). The most interesting examples are when B is a symmetric nonsingular matrix with 0s on the diagonal. What is the normal form of such matrices B? Such matrices are equivalent (via adjacent matrices) to graphs. If B and B' are two such similar matrices, what is the relation between their associated graphs? What is the relation between the graph associated to B and the graph associated to its normal form?

Title: Re: All lights on puzzle
Post by Aryabhatta on Sep 27^th, 2004, 8:06pm

on 09/27/04 at 07:11:57, baudolino wrote:

1st proof is nice. Very nice.

Maybe because I usually avoid Z/2Z, theorem 1 was not trivial to me. The theorem follows from the dimension equality dim V + dim V^[perp] = dim U, where V [subseteq] U.

Isn't dim(V) + dim(V^[perp]) = dim(U) valid for any finite field? I don't think there is anything special about [bbf]₂.

Sorry, I don't know much about Bilinear forms, the book I have discusses only real spaces. I will have to search for one which discusses an arbitrary field. Some of the theorems valid for real spaces are not valid for finite fields. For instance, V [cap] V^[perp] = {0} is valid for real spaces, but need not be true for spaces over finite fields.

Title: Re: All lights on puzzle
Post by Aryabhatta on Sep 29^th, 2004, 3:30pm

Is this thread dead? :-/

Title: Re: All lights on puzzle
Post by Aryabhatta on Oct 21^st, 2004, 8:45pm

Alright, before this thread passes away, here is a solution which does not use Linear Algebra.

The Hint was:

First prove the following result:
G is a connected graph. Let V(G) be the vertex set of G.

Show that V(G) can be decomposed into two disjoint sets V1 and V2 such that:

i) [forall] x [in] V1, the cardinality of S = {y| y [in] V1 and (x,y) is an edge of G} is even.
ii) [forall] x [in] V2, the cardinality of S = {y| y [in] V2 and (x,y) is an edge of G} is even.

Let us see how this hint helps in proving what we want.

We can map our problem to:

Given a graph G. Initial values of vertices are 0. We can pick a vertex and flip (0 to 1, 1 to 0) the values of that vertex and its neighbours. Is it possible to make all vertices 1?

So for turning on all the lights, we are looking for a subset X of the vertices of the graph such that, every vertex not in X is incident to an odd number of vertices of X and every vertex in X is incident to an even number of vertices of X.

Here is how we can use the hint result. To every vertex of even degree of G, add an edge to a new vertex N (N is same for all) to get G'. This makes all the vertices of G' of odd degree. By the result of the hint, this graph has a partition into two sets X and Y such that any vertex in X is incident to and even number of vertices of X. Any vertex in Y is incident to an even number of vertices in Y.

Suppose N is in Y. Consider X. every vertex in X is incident to an even number of vertices in X. Every vertex in Y is incident to an odd number of vertices in X. So that is what we wanted!
Note, we don't care about N.

Here is one way of proving the hint.

We prove by induction in the number of vertices of G.
Base cases are trivial.

Suppose we are given G(V,E) with n+1 vertices. Suppose G has all vertices of even degree. Then we are done by taking X = V and Y = [phi].

So suppose there is a vertex o, which is of odd degree.
Let o₁, o₂,..., o_k be the neighbours of o in G. Consider the graph G' which is formed as follows. if o_i and o_j have an edge in G. delete that. if o_i and o_j are not adjacent, join them by an edge.

Delete o.

Apply induction hypothesis on G'. Say we get X and Y.
o must be incident (in G) to an even number of vertices in one of X or Y, say X. Add o to X. Delete the edges which we had added between neighbours of o and add back the edges which we had deleted.

It is not difficult to show that this partition: X U {o} and Y is what we are looking for.