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

1 Answer

+2 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 ago by Boss (15.5k points)
selected ago by
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

Related questions

0 votes
2 answers
1
+2 votes
2 answers
3
asked Nov 27, 2015 in Set Theory & Algebra by Prasanna Active (4.6k points) | 152 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

34,769 questions
41,727 answers
118,865 comments
41,379 users