I'm trying to solve the following problem:
Let $\mathcal{A}, \mathcal{B} \subset \mathcal{P}(n)$ be two set systems such that $|A \cap B|$ is even for each $A \in \mathcal{A}, B \in \mathcal{B}$. Prove that $|\mathcal{A}||\mathcal{B}| \le 2^n$.
My idea for solving it is to construct an injection $f: \mathcal{A} \times \mathcal{B} \to \mathcal{P}(n)$, and I think the function given by $(A, B) \mapsto A \cup B$ should work. However, I am unsure how to prove this.
I've been looking at the symmetric difference of two sets in $\mathcal{A}$ to try and help with this (because I was given a hint to use this), but I can't make this work.
Does anybody have any clues?
This can be proved using linear algebra over the field of two elements, $GF(2).$ Sets form a vector space over $GF(2)$ where symmetric difference is the vector addition. Suppose there are $k$ linearly independent sets in $\mathcal A.$ Let $\mathcal A'$ be a complementary vector space, so it has dimension $n-k.$ Each set $B\in\mathcal B$ defines a linear map $\mathcal A'\to GF(2)$ by $S\mapsto |S\cap B|$ mod $2.$ If $B,B'\in\mathcal B$ satisfy $|S\cap B|=|S\cap B'|$ mod $2$ for all $S\in\mathcal A',$ then by linearity and the fact that $|S\cap B|=|S\cap B'|$ mod $2$ for all $S\in\mathcal A$ we know that $|S\cap B|=|S\cap B'|$ mod $2$ for all $S.$ In particular $|\{i\}\cap B|=|\{i\}\cap B'|$ mod $2$ for all elements $i,$ which implies $B=B'.$ So the sets in $\mathcal B$ map injectively to the vector space of linear maps $\mathcal A'\to GF(2),$ which has dimension $n-k.$ So $|\mathcal A|\cdot|\mathcal B|\leq 2^k2^{n-k}=2^n.$