2 trivial error fix; edited body

This is a crosspost from http://mathoverflow.net/questions/33911/, suggested by Kevin O'Bryant. I think it's relevant here. Everything below is verbatim from the earlier post.

My favorite application of linear algebra, as introduced to me by Fan Chung, is Oddtown (which I learned about from a manuscript of Lovasz, but may not be due to him).

The $n$ residents of Oddtown love to form clubs; call the family of these $\mathcal{F}$. If $F_1$ and $F_2$ are in $\mathcal{F}$, then $|F_1|$ must be odd (this is Oddtown!) and $|F_1 \cap F_2|$ must be even unless $F_1 = F_2$ ($\scriptsize{go\;Oddtown?}$). The question is, how many clubs may these $n$ people form?

The answer (taken from Tibor Szabó's lecture notes) is this:

Let $\mathcal{F} = {F_1,\ldots,F_m} \subseteq 2^{[n]}$ be a set of clubs in Oddtown. Let $\mathbf{v}_i \in \{0,1\}^n$ be the characteristic vector of $F_i$; the $j$th coordinate is 1 iff $j \in F_i$.

Note that $\mathbf{v}_i^T v_j \mathbf{v}_j = |F_i \cap F_j|$.

Now, $\mathbf{v}_1,\ldots,\mathbf{v}_n$ \mathbf{v}_1,\ldots,\mathbf{v}_m$is independent over$\mathbb{F}^n_2$: if$\lambda_1\mathbf{v}_1 + \cdots + \lambda_m\mathbf{v}_m = 0$, then for each$i$we have $$0 \;=\; (\lambda_1\mathbf{v}_1 + \cdots + \lambda_m\mathbf{v}_m)^T\mathbf{v}_i \;=\; \lambda_1\mathbf{v}_1^T\mathbf{v}_i + \cdots + \lambda_i\mathbf{v}_i^T\mathbf{v}_i + \ldots + \lambda_m\mathbf{v}_m^T\mathbf{v}_i \;=\; \lambda_i$$ Since$\mathbf{v}_1,\ldots,\mathbf{v}_m$are linearly independent vectors over$\mathbb{F}^n_2$,$m \leq n$, and Oddtown can have at most$n$clubs. 1 [made Community Wiki] This is a crosspost from http://mathoverflow.net/questions/33911/, suggested by Kevin O'Bryant. I think it's relevant here. Everything below is verbatim from the earlier post. My favorite application of linear algebra, as introduced to me by Fan Chung, is Oddtown (which I learned about from a manuscript of Lovasz, but may not be due to him). The$n$residents of Oddtown love to form clubs; call the family of these$\mathcal{F}$. If$F_1$and$F_2$are in$\mathcal{F}$, then$|F_1|$must be odd (this is Oddtown!) and$|F_1 \cap F_2|$must be even ($\scriptsize{go\;Oddtown?}$). The question is, how many clubs may these$n$people form? The answer (taken from Tibor Szabó's lecture notes) is this: Let$\mathcal{F} = {F_1,\ldots,F_m} \subseteq 2^{[n]}$be a set of clubs in Oddtown. Let$\mathbf{v}_i \in \{0,1\}^n$be the characteristic vector of$F_i$; the$j$th coordinate is 1 iff$j \in F_i$. Note that$\mathbf{v}_i^T v_j = |F_i \cap F_j|$. Now,$\mathbf{v}_1,\ldots,\mathbf{v}_n$is independent over$\mathbb{F}^n_2$: if$\lambda_1\mathbf{v}_1 + \cdots + \lambda_m\mathbf{v}_m = 0$, then for each$i$we have $$0 \;=\; (\lambda_1\mathbf{v}_1 + \cdots + \lambda_m\mathbf{v}_m)^T\mathbf{v}_i \;=\; \lambda_1\mathbf{v}_1^T\mathbf{v}_i + \cdots + \lambda_i\mathbf{v}_i^T\mathbf{v}_i + \ldots + \lambda_m\mathbf{v}_m^T\mathbf{v}_i \;=\; \lambda_i$$ Since$\mathbf{v}_1,\ldots,\mathbf{v}_m$are linearly independent vectors over$\mathbb{F}^n_2$,$m \leq n$, and Oddtown can have at most$n\$ clubs.