Subset $A_1,..A_m$ of $\{1,2,...n\}$ where $|A_i|$ is even $\forall i$ and $|A_i \cap A_j|$ is odd when $i \neq j$, prove $m \leq n$

84 Views Asked by At

I'm struggling to figure out the best way to prove some extremal combinatoric ideas. If I have a set $\{1,2,...,n\}$ a collection of subsets $A_1, A_2,...A_m$ where $|A_i|$ is even $\forall i$ and $|A_i \cap A_j|$ is odd when $i \neq j$, then how should prove that $m\leq n$? I understand the proof that uses linear algebra to prove that if I had two subsets $A_1,..A_m$ and $B_1,..B_m$ and the same constraints but for $|A \cap B|$ but I am struggling to see how I can leverage this proof to show it for just $A$.