Once upon a time, there was a town of people. These people were bored, so they formed clubs. Coincidentally, every club has an odd number of members, and every two clubs have an even number of members in common (boyfriend and girlfriend liked to join the same club!).
I claim that
I claim even more! I claim that this is a Linear Algebra problem.
Many conditions involve parity, so it makes sense to think in We want to encode the giving information with vectors!
For let Each of these vectors holds information of a club. For let
For instance, indicates that there are five people (it’s a small town!) and person 1, 2, 4 have joined club 2.
We have translated the problem into the language of linear algebra. The next task is to figure out what the remaining conditions mean.
- The claim was Possibly are linearly independent! As we would immediately get
- Wishful thinking lets us hope that the given parity conditions (odd number of members in clubs and even number of people in common) imply linear independency!
The key idea: Dot product! We are working in so
- Quantity counts the number of people in club i and takes mod 2. Since we know it’s odd, we get
- Quantity counts the number of people in common in club i and j and takes mod 2. We know it’s odd, so for
We are almost done. In fact, we have (kind of) shown that the vectors form an orthonormal basis in Suppose that satisfy
Taking the dot product with shows
Thus so the vectors are linearly independent and we are done!