The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
387 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$.
asked in Set Theory & Algebra by Veteran (57.6k points)
retagged by | 387 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

1 Answer

+5 votes
Best answer
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 (16.7k points)
selected by
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 ?

\line(1,0){250}

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.

Related questions

0 votes
2 answers
4
+4 votes
2 answers
7
asked Nov 27, 2015 in Set Theory & Algebra by Prasanna Active (4.8k points) | 197 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,276 questions
49,767 answers
164,264 comments
65,853 users