+1 vote
393 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$.
retagged | 393 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 by Boss (17.3k points)
selected
0

plz explain more

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

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

+2
You did with the most generic method. thanks
+1
Hi, $D^TD \equiv I \text{ mod }2$ , can you please explain on this ?

To me $det(D^TD)$ = (only one odd number)*(some integer) + (even) * (some integer) and this can not be $0$.
+2

srestha, Matrix D is an indicator matrix, where $D_i$ ($i^\text{th}$ column of $D$) is an Indicator vector for set $A_i$. Now if you want to know total number of elements in  $A_i$ (i.e. $|A_i|$) then just sum up all values of  $D_i$ , and if you want to know $|A_i \cap A_j|$ then first do element wise multiplication of $D_i$ and $D_j$ and sum all values of this vector.                                                                                                    And that's what $D^TD$ is doing between all two pairs of sets $A_i$ and $A_j$.

$\Big(D_i \odot D_j$ $($element wise product between $D_i$ and$D_j)$ is an indicator vector for set  $A_i \cap A_j$ $\Big)$

Can you take it from here ?

Debashish Deka, I am not sure if i got you. But If we perform $\text{ mod }2$ operation on each element of $D^TD$ then it will result into identity matrix $I_{m \text{x}m}$. (see this for similar calculation).   Basically Instead of finding exact value of $\operatorname{det} (D^TD)$, we are finding value of $\operatorname{det} (D^TD) \text{ mod }2$. Let  $\operatorname{det} (D^TD)$ is $x$ and we want to prove $x$ is not zero then we can also prove $x \text{ mod }2$ is not zero. $(x \text{ mod }2) \neq 0 \Rightarrow x \text{ is odd } \Rightarrow x\neq0$.                                                                                                  Now the question is, Can I take $\text{mod}$ inside  $\operatorname{det}$ operator ?, yes we can. because finding determinant is just sequence of some additions and multiplications. $\big(\operatorname{det} (D^TD) \text{ mod }2$ is equivalent to $\operatorname{det} (D^TD \text{ mod }2 ) \big)$

Anyway I have taken this solution from here.