Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Let $A_1 , . . . , A_m$ and $B_1 , . . . , B_m$ be subsets of $[n]$ such that $| A_i ∩ B_i |$ is odd for all $i$ and $| A_i ∩ B_j |$ is even for all $i \neq j$ . Show that $m ≤ n$.
I've tried using proof by contradiction but not success - any help greatly appreciated, thanks!
The question looks like it's asking to be recast as a linear algebra problem. Consider the field with two elements, $\mathbb F_2$, and the vector space $\mathbb F_2^n$.
Interpret a subset $X$ of $[n]$ as the vector $x = (x_1, x_2, \ldots x_n)$ where $x_i$ is $1$ iff $i \in X$. Define the usual bilinear form $\langle \cdot \rangle : \mathbb F_2^n \times \mathbb F_2^n \to \mathbb F_2$:
$$\langle x , y \rangle = \sum_{i=1}^n x_iy_i$$
Let $X, Y \subseteq [n]$, and let their corresponding vectors in $\mathbb F_2^n$ be $x$ and $y$ respectively. Then $|X \cap Y|$ is even if and only if $\langle x, y \rangle = 0$.
Now consider the given $A_1, \ldots, A_m$ and $B_1, \ldots, B_m$. Let their corresponding vectors be $a_1, \ldots, a_m$ and $b_1, \ldots, b_m$. We know that for all $i,j$, we have $\langle a_i, b_j \rangle$ is $1$ if $i=j$ and $0$ otherwise.
Claim: $(a_1, \ldots, a_m)$ is linearly independent.
Proof: Suppose we have
$$s_1a_1 + s_2a_2 + \cdots + s_ma_m = 0$$
with each $s_i \in \mathbb F_2$. Then applying $\langle \cdot, b_i \rangle$ on both sides, we get $s_i = 0$. This holds for all $i$, and so the linear independence is established.
Since we have a linearly independent set of size $m$ in a vector space of dimension $n$, we get $m \leq n$.
