I'm studying graph theory and the follow question is driving me crazy. Any hint in any direction would be appreciated.
Here is the question:
Let $G = G[X, Y]$ be a bipartite graph in which each vertex in $X$ is of odd degree. Suppose that any two distinct vertices of $X$ have an even number of common neighbours. Show that $G$ has matching covering every vertex of $X$.
On
The first section of this PDF (Lecture 1 from the HS11 class "Linear Algebra Methods in Combinatorics" by Penna and Hruz at ETH Zürich) gives a brief solution of the Clubs of Oddtown problem mentioned by Gerry Myerson in the comments; this PDF ("Linear Methods in Discrete Mathematics" by Dan Farkas) gives a much more extensive introduction to the necessary linear algebra and goes on to deal with much more difficult problems as well.
Let $A$ be the adjacency matrix of $G$, with rows indexed by $X$ and columns by $Y$. The material in the references (specifically, the analysis of the Oddtown problem) shows that the rows of $A$ are linearly independent as vectors in $\Bbb F_2^{|Y|}$, so the rank of $A$ is $|X|$. $A$ therefore contains an $|X|\times|X|$ invertible submatrix $B$. I’ve not entirely thought through the details, but I’d try to show that this submatrix must contain a permutation matrix, which will give you the desired matching. It may be useful to row-reduce $B$; note that this is exceptionally simple over $\Bbb F_2$.
Added: Just look at the determinant of $B$ as defined by the Leibniz formula: one of the terms must be non-zero.
Hint for one possible solution:
Consider the adjacency matrix $M\in\Bbb F_2^{|X|\times|Y|}$ of the bipartite graph, i.e. $$M_{x,y}:=\left\{ \begin{align} 1 & \text{ if }x,y \text{ are adjacent} \\ 0 & \text{ else} \end{align} \right. $$ then try to prove, it has rank $|X|$, and then, I think, using Gaussian elimination (perhaps only on the selected linearly independent columns) would produce a proper matching..