# Odd town Even town explanation.

I am struggling to understand the solution to the following problem: If $\mathcal F\subset 2^{[n]}$ such that for each $F_1$ and $F_2$ in $\mathcal F$ we have $|F_1|,|F_2|\equiv 1 \bmod 2$ and $|F_1\cap F_2|\equiv 0 \bmod 2$ then $|\mathcal F|\leq n$

the part of the proof I don't get is to which vector space the elements of $\mathcal F$ are being translated (I don't know much linear algebra, so I need an explicit explanation of the underlying sets of both the vector and the field and how addition and product works.

I would also like the proof that the elements of $\mathcal F$ are independent in this vector space. Thank you very much beforehand.

Regards.

• When you say "part of the proof" it suggests you're trying to follow a proof already given somewhere. If so, the vector space is likely defined in that proof. If not, maybe it's $(\mathbb{Z}_2)^n.$ – coffeemath Aug 7 '14 at 12:12

Note: The question is missing the assumption that $|F|$ is odd for every $F \in \mathcal{F}$.

We consider the vector space $\mathbb{F}_2^n$ where $\mathbb{F}_2 = \{0,1\}$ is the field with 2 elements. Given our collection of subsets $\mathcal{F} \subset 2^{[n]}$ for any $F \in \mathcal{F}$ we associate $F$ to the vector $v_F \in \mathbb{F}_2^n$ defined by $v_F = (v_{F,1}, \dots v_{F,n})$ where for each $1 \leq i \leq n$ we have $v_{F,i} = 1$ if $i \in F$ and $v_{F,i}=0$ if $i \not\in F$. We can treat this vector space like any other coordinate space; we have a scalar multiplication and componentwise addition.

Now we will show the vectors $\{v_F : F \in \mathcal{F}\}$ are linearly independent. Note for distinct $F_1, F_2 \in \mathcal{F}$ we have $|F_1 \cap F_2| = v_{F_1} \cdot v_{F_2} = 0 \in \mathbb{F}_2$ by the assumption $|F_1 \cap F_2|$ is even. Here $\cdot$ denotes the dot product. Assume we have some linear combination $w$ which equals zero given by $$w = \sum_{F \in \mathcal{F}} a_F v_F = 0.$$

Now for each $G \in \mathcal{F}$ we have

$$w\cdot v_G = \sum_{F \in \mathcal{F}} a_F (v_F \cdot v_G) = a_G = 0$$

here we use that $v_G \cdot v_G = |G| = 1 \in \mathbb{F}_2$ while $v_G \cdot v_F = |G \cap F| = 0 \in \mathbb{F}_2$ when $F \ne G$. So, in any zero linear combination all coefficients must be zero, therefore the vectors $\{v_F : F \in \mathcal{F}\}$ are linearly independent. It follows immediately that that $|\mathcal{F}| \leq n$ since $\mathbb{F}_2^n$ is an $n$-dimensional space.

• ok, I think I got it, but just to make sure, When taking the dot product all of the operations happen in $\mathbb F_2$ right? – Jorge Fernández Hidalgo Aug 7 '14 at 19:18
• Correct all operations happen in $\mathbb{F}_2$. – John Machacek Aug 8 '14 at 1:03