Unexpected Linear Algebra: Oddtown

Once upon a time, there was a town of n people. These people were bored, so they formed m 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 m \leq n.

I claim even more! I claim that this is a Linear Algebra problem.


Many conditions involve parity, so it makes sense to think in \mathbb{F}_2. We want to encode the giving information with vectors!

For i = 1,2,\dots, m let v_i \in \mathbb{F}_2^n. Each of these vectors holds information of a club. For v_i let

j\text{'th component of } v_i = \begin{cases} 1 \quad &\text{person } j \text{ is in club } i \\ 0 &\text{else} \end{cases}

For instance, v_2 = (1,1,0,1,0) 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 m \leq n. Possibly v_1, v_2, \dots, v_m are linearly independent! As \dim \left( \mathbb{F}_2^n \right) = n we would immediately get m \leq n.
  • 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 \mathbb{F}_2, so

  • Quantity \langle v_i, v_i \rangle counts the number of people in club i and takes mod 2. Since we know it’s odd, we get \langle v_i, v_i \rangle = 1.
  • Quantity \langle v_i, v_j \rangle counts the number of people in common in club i and j and takes mod 2. We know it’s odd, so \langle v_i, v_j \rangle = 0 for i \neq j.

We are almost done. In fact, we have (kind of) shown that the vectors form an orthonormal basis in \mathbb{F}_2^n. Suppose that a_1, a_2, \dots, a_n \in \mathbb{F}_2 satisfy

a_1v_1 + a_2v_2 + \dots + a_mv_m = 0.

Taking the dot product with v_i shows

0 = a_1 \langle v_1, v_i \rangle + a_2 \langle v_2, v_i \rangle + \dots + a_m \langle v_m, v_i \rangle = a_i \langle v_i, v_i \rangle = a_i.

Thus a_1 = a_2 = \dots = a_m = 0, so the vectors v_1, v_2, \dots, v_m are linearly independent and we are done!

 

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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