Cat quiz (to solve with the determinant)

Consider $100$ cats and $100$ food bowls containing cat food of $100$ different brands.

Every cat likes an odd amount of brands.

For each two cats, there is an even amount of brands both cats like.

Show that one can distribute the $100$ food bowls to the $100$ cats such that every cat is happy.

Hint: It's a determinant exercise over the field $\mathbb{F}_2 = \mathbb{Z}/2\mathbb{Z}= \{ [0],[1] \}$.

How can this be done using the determinant? Thanks in advance!

Solution 1:

Let $M$ be the $100 \times 100$ matrix over $\mathbb{F}_2$ that has, at index $(i, j)$, a $1$ if cat $i$ likes food brand $j$ and a $0$ otherwise. Now, I like to see the Leibniz expansion of the determinant as a sum of products over certain "paths" through this matrix. Really, the problem is to show that at least one of these paths has all ones---that is, has non-zero product. This is certainly the case if the determinant of the whole matrix is non-zero. Can you see why this must be true?

One approach: Apply Gaussian elimination. Note that elementary operations on the rows of $M$ preserve the property that every row has an odd number of ones and every pair of rows share an even number of ones, but a matrix in reduced echelon form with this property can't be singular.

A better approach suggested by @omnomnomnom: check that $M M^T = I$.