17
$\begingroup$

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!

$\endgroup$
17
$\begingroup$

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$.

$\endgroup$
  • 5
    $\begingroup$ Rather than applying Gaussian elimination to $M$, simply note that $M^2 = I$. $\endgroup$ – Omnomnomnom Jan 22 at 17:04
  • 2
    $\begingroup$ Ah yes, that's much better! $\endgroup$ – Christopher Gadzinski Jan 22 at 17:04
  • 3
    $\begingroup$ 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. $\endgroup$ – Omnomnomnom Jan 22 at 17:19
  • $\begingroup$ @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. $\endgroup$ – marymk Jan 22 at 21:22
  • 4
    $\begingroup$ @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$. $\endgroup$ – ruakh Jan 23 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.