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.


  • $\begingroup$ 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.$ $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – Jorge Fernández Hidalgo Aug 7 '14 at 19:18
  • $\begingroup$ Correct all operations happen in $\mathbb{F}_2$. $\endgroup$ – John Machacek Aug 8 '14 at 1:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.