+1 vote
99 views
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$.
edited ago | 99 views
+1
$A_{1}=\left \{ 1 \right \}$

$A_{2}=\left \{ 1,2 \right \}$

$A_{3}=\left \{ 1,2,3 \right \}$

Now, given that $|A_{i}|$ is odd number

So, value of $i$ is 1 or 3

Now we know , a set can contain even number of elements, if an odd number set is subtracted from another odd number set

or,

an even number set is subtracted from another even number set

Now, $||A_{i}|\cap|A_{j}| |=$even number

that means j value could be 1 or 3

Here n is largest number of that set

So, if n=3, m could be 1 or 3

So, $m\leq n$
0
nice question

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$
answered ago by Boss (15.5k points)
selected ago
0

plz explain more

why u taken $D^{T}D$?

and how r u convincing diagonal entries of $D^{T}D$ represents |Ai|

0
You did with the most generic method. thanks