5 Miscellaneous

Theorem 7.6.1 (Oddtown Theorem).label Let $[n]\define \curl{1,2,...,n}$ and $\F\suf\cali{P}([n])$ be a family such that $\abs{A}\congruent{1}{2}$ for all $A\in\F$ and $\abs{A\cap B}\congruent{0}{2}$ for all $A\neq B\in \F$. Then $\abs{F}\leq n$.

Proof. For each $A\in \F$ consider the indicator associated with $A$, $\indi{A}\in \bb{F}^{n}_{2}$ defined by

\begin{align*}\indi{A}(i)\define \begin{cases}1&i\in A\\ 0&i\nin A\end{cases}\end{align*}

Observe that $\indi{A}\cd \indi{B}=\abs{A\cap B}$ so the hypothesis is equivalent to

(1)
$\indi{A}\cd \indi{A}\congruent{1}{2}$
(2)
$\indi{A}\cd\indi{B}\congruent{0}{2}$

for all $A\neq B\in\F$. If there is a linear relation over $\bb{F}_{2}$ then

\begin{align*}0=\sums{}{A\in\cali{F}}c_{A}\indi{A}\end{align*}

Using (2) we have for each $B\in\F$

\begin{align*}0=\parens{\sums{}{A\in\cali{F}}c_A\indi{A}}\cd\indi{B}=\parens{\sums{}{A\in\cali{F}}c_A(\indi{A}\cd\indi{B})}=c_{B}\indi{B}\cd\indi{B}=c_{B}\end{align*}

showing that

\begin{align*}\abs{\F}\leq \dim_{\bb{F}_2}(\bb{F}_{2}^{n})=n\end{align*}

We shall now provide a proof over $\Q$ or any field of characteristic $0$ (as $\Q$ embeds there). For each $A\in \F$ consider the indicator associated with $A$, $\indi{A}\in \Q^{n}$ defined by

\begin{align*}\indi{A}(k)\define \begin{cases}1&k\in A\\ 0&K\nin A\end{cases}\end{align*}

Observe that $\indi{A}\cd \indi{B}=\abs{A\cap B}$ so the hypothesis is equivalent to

(1)
$\indi{A}\cd \indi{A}\congruent{1}{2}$
(2)
$\indi{A}\cd\indi{B}\congruent{0}{2}$

for all $A\neq B\in\F$. Let $m=\abs{\cali{F}}$ and write $\cali{F}=\curl{A_1,...,A_m}$. Let the matrix $M$ whose $k^{th}$ column is $\indi{A_k}$ with the canonical identification of $\indi{A}\bij (\indi{A}(\el))\in \Q^{n}$ where $\el\in[n]$ then $X\define M^{T}M$ is the matrix such that $X_{ij}=\abs{A_i\cap A_j}$. By (1) and (2)

\begin{align*}\det(X)\equiv\det(I_{k})\congruent{1}{2}\end{align*}

in particular $\det(X)\neq 0$. We conclude

\begin{align*}\abs{\cali{F}}=k=\text{rank}(X)\leq \text{rank}(M)\leq n\end{align*}

$\square$

Theorem 7.6.2 (Odd Oddtown).label Let $\cali{F}\suf\cali{P}([n])$ be a family such that for all $A\neq B\in\cali{F}$

(a)
$\abs{A}\congruent{0}{2}$
(b)
$\abs{A\cap B}\congruent{1}{2}$

then

(1)
$\abs{\F}\leq n+1$
(2)
$\abs{\F}\leq n$

Proof. Using the same set up as Oddtown Theorem 7.6.1 over $\bb{F}_{2}$ we have the hypothesis is equivalent to

(1)
$\indi{A}\cd \indi{A}\congruent{0}{2}$
(2)
$\indi{A}\cd\indi{B}\congruent{1}{2}$

We now define a new family $\cali{F}'\suf\cali{P}([n+1])$ by

\begin{align*}\F'\define \curl{A'=A\cup \curl{n+1}:A\in\F}\end{align*}

which satisfies Oddtown Theorem 7.6.1 so $\abs{F}=\abs{F'}\leq n+1$. If there is a linear relation over $\bb{F}_{2}$ that is not the trivial relation then fix $B\in\F$ we have

\begin{align*}0=\sums{}{A\in\F}c_{A}\indi{A}\cd\indi{B}=\sums{}{A\neq B\in\F}c_{A}\end{align*}

Let $C\neq B\in\F$ then over $\bb{F}_{2}$

\begin{align*}0=\sums{}{A\neq B\in\F}c_{A}+\sums{}{A\neq C\in\F}c_{A}=\sums{}{A\neq B,C\in\F }2c_{A}+c_{C}+c_{B}=0+c_{C}+c_{B}\end{align*}

Hence $c_{B}=c_{C}$ for any $B,C\in\F$ and so $c_{A}=1$ for all $A\in\F$ and

\begin{align*}0=\sums{}{A\in\F}\indi{A}\end{align*}

Taking dot product with $\indi{B}$ again we see

\begin{align*}0=\sums{}{A\neq B\in\F }1=\abs{\F}-1\end{align*}

showing that $\abs{\F}$ is odd. Observe that

\begin{align*}\indi{A}\cd\indi{[n]}=\sums{n}{i=1}\indi{A}(i)=\abs{A}=0\end{align*}

so for each $A\in\F$ we have

\begin{align*}\indi{A}\in V\define \curl{x\in\bb{F}^n_2:x\cd\indi{[n]}=0}\end{align*}

where $V$ is the subspace of vectors with even number of $1$ in coordinates and $\dim V=n-1$ as the kernel of the linear functional $x\mto x\cd\indi{[n]}$. Using the trick of $\F'$ we consider

\begin{align*}\indi{A'}=(\indi{A},1)\in V\op \bb{F}_{2}\end{align*}

and using the hypothesis we have

(1)
$\indi{A'}\cd \indi{A'}\congruent{1}{2}$
(2)
$\indi{A'}\cd\indi{B'}\congruent{0}{2}$

So $\curl{\indi{A'}:A'\in\F'}$ is linearly independent over $\bb{F}_{2}$ and we conclude

\begin{align*}\abs{F}=\abs{F'}\leq\dim(V\op \bb{F}_{2})=(n-1)+1=n\end{align*}

as desired.$\square$

Lemma 7.6.3.label Let $R$ be a unital ring, $M$ be a left $R$-module, $\p:M\to R$ be an $R$-linear map and suppose there exists $e\in M$ such that $\p(e)=1_{R}$ then $M=\ker\p\op Re$

Proof. Let $m\in M$ then consider $m_{0}\define m-\p(m)e$

\begin{align*}\p(m)=\p(m-\p(m)e+\p(m)e)=\parens{\p(m)-\p(m)\p(e)}+\p(m)\p(e)\in \ker\p+Re\end{align*}

If $r e\in\ker\p$ for some $r\in R$ then

\begin{align*}0=\p(re)=r\p(e)=r\end{align*}

showing the sum is direct.$\square$

Direct References

circleTheorem 7.6.1: Oddtown Theorem

The Eigenspace

5 Miscellaneous

Post a Comment

Direct References

The Eigenspace

Direct References