# 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!