Odd goings on
Published:
This problem is from Puzzle Toad.
Problem
There’re $n$ people, whose friendship can be seen as an undirected simple graph $G(V,E)$. Now for any subset $S \subset V$, there’s a person (in $S$ or out of $S$), who has odd number of friends among the people in $S$.
If $n$ is even then if $G=K_n$ the condition is satisfied. Now show $n$ can’t be odd.
Sol
A equivalent statement is: if $n$ is odd, for any graph, there exists such a set $S$. We can further describe it into linear algebra form. Let $M$ be the adjacency matrix of $G$, which is symmetric, with every entry $0$ or $1$, and diagonal entries $0$s.
So a set $S$ satisfying the condition in the statement, is equivalent to the $s_{th}$ rows for all $s \in S$ gives a $XOR$ sum (or sum in $F_2$) $0$. Then, there exists some $S$ if and only if the rows in the matrix $M$ is linearly independent (in $F_2$), moreover, it is equivalent to the determinant of the matrix in $F_2$ is non-zero.
Now let’s directly calculate the determinant. since $1=-1$ in $F_2$, we can ignore the sign, then we know the determinant is:
\[\sum_{permutation \ p} \prod_i M_{i,p(i)}.\]And we know by the symmetry of $M$:
\[\prod_i M_{i,p(i)} = \prod_i M_{p(i),i} = \prod_j M_{j,p^{-1}(j)}.\]Moreover, in the sum, we only considers $p$ such that for all $i$, $p(i) \ne i$ since the diagonal entries are all $0$s. For these permutations, $p \ne p^{-1}$ since we can’t arrange $n$ points into $2$-cycles. Thus, we can make pairs for $p$ and $p^{-1}$. The product for these pairs are all the same, so they all sums to $0$. Therefore, we know the determinant, as a sum of the pairs’ sums, is always $0$.
Then, the rows in $M$ are linearly dependent and there’s such an $S$, which proves the statement.
I thought it need to be explained in matrix form and linear dependency should be proved. However, I failed to think about the determinant.