Linear Algebra Methods in Combina­torics

Some questions about families of sets are hard to attack by direct counting, yet fall apart once each set is written as a vector. I introduce the linear algebra method in combinatorics through the Oddtown problem: in a town of n residents, every club has an odd number of members and any two clubs share an even number. How many clubs can there be? Viewed as vectors over the field with two elements, the clubs turn out to be linearly independent, so there are at most n of them. Similar dimension arguments give short proofs of bounds for other problems about set systems, and I show a few of them.