Linear Algebra Text Problem

Question

We have specified number of light bulbs. In addition to the array there are buttons. Pressing the button changing state of light bulbs which are connected to the switch. It is known that for each set of lamps exist button that is connected with the odd-number of bulbs from this set. Prove that properly pressing the buttons we can turn off all bulbs.

Very nice task, but hard. I think that I can make a $Z^n$ space of bulbs, but how to prove that we have a basis of it? Or that's not a correct way?

I'm looking for hints.

Can you explain what you mean by " It is known that for each set of lamps are connected with the odd-number of bulbs." — Calvin Lin, Jan 09 '13 at 09:59
Let me describe. For each non-empty set of bulbs, we have a set of buttons which are connected with odd number of bulbs from this set. — Jonny, Jan 09 '13 at 10:35
Are you familiar with vector spaces over finite fields (such as the integers mod 2)? — Erick Wong, Jan 09 '13 at 10:36
Yes. I'm familiar with linear spaces over finite/infinite fields. — Jonny, Jan 09 '13 at 10:39

Erick Wong · Accepted Answer · 2013-01-09T18:24:12.620

3

Hint: The "odd number of bulbs from a set" can be rephrased in terms of a dot product over $GF(2)$. If there were a non-empty set of bulbs with even-sized connections to all buttons, this would give you a non-zero vector in the nullspace of a certain matrix...

More hints: If you fix an ordering of the bulbs and represent any set of bulbs as a $\{0,1\}$-vector, then the dot product of two vectors (each representing a set) is equal to the size of the intersection of the corresponding two sets. In particular, modulo $2$, this dot product is zero or non-zero according to whether the intersection is odd or even.

edited Jan 09 '13 at 18:24

answered Jan 09 '13 at 10:51

Erick Wong

25,198
3
37
91

How is definied GF(2)? – Jonny Jan 09 '13 at 11:54
1

I don't follow, can you please some more details ? – Belgi Jan 09 '13 at 12:59
1

@Jonny $GF(2)$ is one of the names for the finite field of integers modulo $2$. You might have seen it denoted $\mathbb F_2$ or $\mathbb Z/2\mathbb Z$, for instance. – Erick Wong Jan 09 '13 at 18:25
Thank You for explanation. – Jonny Jan 09 '13 at 23:22

Linear Algebra Text Problem

1 Answers1

Linked