retagged by
846 views
1 votes
1 votes
We have $m$ sets $A_1,A_2,A_3 \text{ to } A_m$.  All $A_i \subseteq [n]$ where $ [n] = \{1,2,3, \dots n \}.$ Given that $|A_i| = \text{odd number}$ and $|A_i \cap A_j| = \text{even number }\forall i \neq j$. Show that $m \leq n$.
retagged by

1 Answer

Best answer
5 votes
5 votes
Consider a special matrix $D$, $D$ has $m$ columns (one column for each set) and $n$ rows (for every number from $[n]$ ) such that-

$D_{ij} = \left\{\begin{matrix} 1 & \text{if } i \in A_j & & \\ 0& \text{otherwise}& & \end{matrix}\right.$ i.e  $D_{ij} $ indicates presence/absence of $i^\text{th}$ element in  $j^\text{th}$ set.

Now consider $D^TD$ and convince yourself that diagonal entries of $D^TD$ represents $|A_i |$ and non diagonal entries represents $|A_i \cap A_j|$.

$D^TD = \begin{pmatrix} .& & & & & & |A_i \cap A_j| \\ & .& & & & & \\ & & .& & & & \\ & & & |A_i|& & & \\ & & & &. & &\\ & & & & &.& \\ & & & & & & \end{pmatrix} = \begin{pmatrix} .& & & & & & \text{even}\\ & .& & & & & \\ & & .& & & & \\ & & & \text{odd}& & & \\ & & & &. & &\\ & & & & &.& \\ & & & & & & \end{pmatrix}$

Notice that:  $\operatorname{rank}(D^TD)\leq \operatorname{rank}(D)$ $ \le n$

$\Big ( \because \small {\operatorname{rank}(AB)\leq min(\operatorname{rank}(A),\operatorname{rank}(B))  \text{ and }  \operatorname{rank} A_{m\text{x}n} \le\min(m,n) }\Big) $

 

Claim:  $\operatorname{rank}(D^TD)= m  \text{ i.e } { det(D^TD) \neq 0}$

This claim follows $m \le n$.

proof - By design we see that $D^TD \equiv I \text{ mod  }2$,

So,  $\operatorname {det}(D^TD) \equiv \operatorname {det}(I) =1 \text{ mod }2 $

$\Rightarrow \operatorname {det}(D^TD)  \neq 0$
selected by

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
1 answer
3
dd asked Apr 27, 2018
384 views
Consider the sets $A_1, A_2, A_3 \dots A_m$. Prove that the number of distinct sets of the form $A_i \oplus A_j$ is at least $m$.
0 votes
0 votes
0 answers
4
dd asked Apr 27, 2018
353 views
Consider the sets $A_1, A_2, A_3 \dots A_m$ each a subset of size $k$ of $\{1,2,3, \dots , n\}$. If in a 2-colouring of $\{1,2,3, \dots , n\}$ no set $A_i$ is monoch...