# 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}= \{ , \}$$.

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

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$$.
• Rather than applying Gaussian elimination to $M$, simply note that $M^2 = I$. – Omnomnomnom Jan 22 at 17:04
• I guess what I was going for is an "every cat happy" distribution corresponds to the existence of a permutation matrix $P$ such that the diagonal of $MP$ contains all $1$s, but this is really just another version of your argument. And well spotted with $MM^T$; I somehow was thinking that $M$ is a symmetric matrix which of course it isn't. – Omnomnomnom Jan 22 at 17:19
• @ChristopherGadzinski "Can you see why this must be the case?" It's because if the determinant is not $0$, the matrix has a full rank, thus the column vectors are linearly independent and each row vector contains at least one $1$, because there would be zero row otherwise, which can't be the case if the determinant isn't $0$, right? I do not see why $MM^T=I$ holds, however. – marymk Jan 22 at 21:22
• @marymk: Re: "I do not see why $MM^T=I$ holds": Let $A = MM^T$. Then $a_{ij} = \sum_{k=1}^{100} m_{ik}m_{jk}$, which is the number of cat-food brands that cats i and j both like. If i and j are the same, then it's the number of cat-food brands liked by a single cat, which the problem specifies is always an odd number; if i are j are different, then it's the number of cat-food brands liked by two different cats, which the problem specifies is always an even number. Since we're working in $\mathbb{F}_2$, all odd numbers equal 1 and all even numbers equal 0; so, $A = I$. – ruakh Jan 23 at 7:28