Intereting Posts

Why is the Jordan Curve Theorem not “obvious”?
Can the irrationality of the square root of 2 be proved by using Dirichlet's theorem on primes in an arithmetic progression?
Homology groups of a tetrahedron
Find all different integer exponents
What is a Primitive Atomic Formula?
Are Vitali sets dense in [0,1)?
Why is $l^\infty$ not separable?
If two measures agree on generating sets, do they agree on all measurable sets?
If $d>1$ is a squarefree integer, show that $x^2 – dy^2 = c$ gives some bounds in terms of a fundamental solution.
Probability of Drawing a Card from a Deck
Short proof for the non-Hamiltonicity of the Petersen Graph
Evaluating $\int_0^\infty x^2e^{-\alpha x^2}dx$ and $\int_0^\infty xe^{-\alpha x^2} dx$ knowing $\int_0^\infty e^{-\alpha x^2}dx$
Characterization convex function.
Proving tautologies using semantic definitions
The use of log in the Mean density of the nontrivial zeros of the Riemann zeta function (part 2)

Let $E$ be a set of cardinality $n$. Suppose $M_1, M_2, .. , M_m$ are

distinct proper subsets of $E$ such that for each pair of distinct elements $x_1, x_2\in E$, there is exactly one $M_i\supseteq\{x_1,x_2\}$. Prove that $m \ge n$.

It’s obvious $n$ has to be greater or equal to $3$. Also, for $n=3$, it’s easy to prove it, but I have no idea how to extend it. I think a proof using induction by $n$ is possible.

- What is the number of invertible $n\times n$ matrices in $\operatorname{GL}_n(F)$?
- Problem with counting method - full house
- $m \times n$ persons stand in $m$ rows and $n$ columns
- Total number of solutions of an equation
- Lines in the plane and recurrence relation
- Counting certain paths in a complete graph

- To show that $S^\perp + T^\perp$ is a subset of $(S \cap T)^\perp$
- $m\times n$ matrix with an even number of 1s in each row and column
- How to prove the cofactor formula for determinants, using a different definition of the determinant?
- pseudo-primality and test of Solovay-Strassen
- Implicit line equation
- Flipping heads 10 times in a row
- Find a non-zero integer matrix $X$ such that $XA=0$ where $X,A,0$ are all $4 \times 4$
- Number of Ways to Fill a Matrix with symbols subject to Weird contsraint.
- First Course in Linear algebra books that start with basic algebra?
- If $AB=I_n$ and $BA=I_m$ then $n=m$.

**Solution for general case**

Let $E=\{1,2,\ldots, n\}$. Define column vectors $v_j=(v_{ij})^T$ with $v_{ij}= \mathbf{1}_{M_j}(i)$ which gives $1$ if $i\in M_j$ and $0$ otherwise. Then $M=(v_{ij})$ is an $n\times m$ matrix consisting of $0$, $1$ entries. Our goal is to prove that $\mathrm{rank}(M)=n$. We will show this by proving that the rows of $M$ are linearly independent. Then the columns $v_j$ form an spanning set for $\mathbb{R}^n$ and it will follow that $m\geq n$.

According to the assumptions, for each $i$, there are at least two sets $M_{j_1}$ and $M_{j_2}$ such that $i\in M_{j_1}\cap M_{j_2}$. Otherwise, the pairs $\{i,1\}$, $\ldots$, $\{i,n\}$ are all included in one set $M_k$ which gives $M_k=E$. Thus, we see that any row of $M$ contains at least two $1$’s.

Consider a $n\times n$ matrix $MM^T$. If $MM^T$ is nonsingular then the rows of $M$ are linearly independent. For the proof, let $M^T x = 0$ for some $x\in\mathbb{R}^n$. Then $MM^T x = 0$. Since $MM^T$ is nonsingular, $x=0$. Write the rows of $M$ as $R_1, \ldots , R_n$. Then $MM^T = (b_{ij})$ with the dot product $b_{ij}=R_i\cdot R_j$.

Since any row has at least two $1$’s, we have $b_{ii}\geq 2$. Since any pair $\{i, j\}$ with $i \neq j$ is in exactly one $M_k$, we have $b_{ij}=1$ for $i\neq j$. Writing the determinant as a multlinear function on columns, we obtain that $$\det MM^T \geq 1+n.$$

Therefore we conclude that $MM^T$ is nonsingular, and we are done.

**Proof of the determinant inequality**

Let $A=(a_{ij})$ be a $n\times n$ matrix with $a_{ij} = 1$ for $i\neq j$, and $a_{ii}\geq 2$. Then $\det A \geq 1+n$. For the proof, let $J=(1, 1, \ldots, 1)^T$, and write the determinant as a multilinear function on columns:

$$

\begin{align}

\det A &= \det \left((a_{11}-1) e_1 + J, \ldots, (a_{nn}-1)e_n + J\right)\\

&=\det \left((a_{11}-1)e_1, \ldots, (a_{nn}-1)e_n \right) \\ &+ \sum_{j=1}^n \det \left((a_{11}-1)e_1, \ldots, J (j-\textrm{th column}), \ldots, (a_{nn}-1)e_n \right)\\

&=\prod_{i=1}^n (a_{ii}-1) + \sum_{j=1}^n \frac{\prod_{i=1}^n (a_{ii}-1)}{a_{jj}-1}\geq 1 + n.

\end{align}$$

**An Example for $n=4$**

An example of such matrix $M$ is

$$

M=\begin{pmatrix} 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1

\end{pmatrix}, \ \ \

MM^T=\begin{pmatrix} 3 & 1 & 1 & 1 \\ 1 & 2 & 1 & 1 \\ 1 & 1 & 3 & 1 \\ 1 & 1 & 1 & 2 \end{pmatrix}, \ \ \ \det MM^T = 16.$$

**Possibility of $m=n$**

Note that it is possible to have $n$ distinct subsets $M_1, \ldots, M_n$ satisfying the requirements. Let $M_1=\{2,3,\ldots, n \}$, $M_2=\{1,2\}$, $M_3=\{1,3\}$, $\ldots$, $M_n = \{1, n\}$.

Here is a rather long proof.

From the condition, we find that for any two sets $M_i,M_j$ then $|M_i \cap M_j|\le 1$. Let $E= \{ 1,2, \cdots , n \}$ and $a_i \; (1 \le i \le n)$ be number of sets $M_j$ so that $i \in M_j$ then $a_i \ge 2$. Thus, $$\sum_{i=1}^n \binom{a_i}{2} = \sum_{1 \le i<j \le n}|M_i \cap M_j| = \binom m2-L,$$

where $L$ is number of pairs of sets $(M_i,M_j)$ so $|M_i \cap M_j|=0$.

Now, consider an arbitrary set $M_l= \{ x_1,x_2, \cdots , x_h \}$ then the total numbers of sets $M_j \; (1 \le j \le m)$ so that $|M_j \cap M_l| =1$ is $\displaystyle \sum_{i=1}^h a_{x_i}-|M_l|+1$. Thus, $\displaystyle \sum_{i=1}^h a_{x_i}-|M_l|+1=m-l_l$, where *$l_i$ is number of sets $M_j$ so $|M_j \cap M_i|=0$*.

Thus, similarly, by considering all set $M_i= \{ y_1, \cdots , y_l \}$ so that $1 \in M_i$ we find $\displaystyle \sum_{i=1}^l a_{y_i}-|M_i|+1 = m-l_i$. We add all of these to get

$$a_{1}^2+\sum_{i=2}^na_i – \sum_{1 \in M_i}|M_i|+a_1 = ma_1-\sum_{1 \in M_i} l_i, \qquad (1)$$

which is deduced from the fact that $|M_a \cap M_b| \le 1$ so in all $M_i \; (1 \in M_i)$ then if $j \in M_h \; (1 \in M_h, j \ne 1)$ then $j \not\in M_k \; (1 \in M_k, k \ne h)$. This also follows that $ \displaystyle \sum_{j \in M_i}|M_i|=a_j+n-1.$ Thus, $(1)$ is equivalent to $$a_1^2+\sum_{i=2}^na_i-n+1 = ma_1-\sum_{1 \in M_i} l_i.$$

Hence,

$$ \begin{array}{c} \displaystyle \sum_{i=1}^na_i^2+(n-1)\sum_{i=1}^na_i-n^2+n = m\sum_{i=1}^na_i-\sum_{i=1}^m|M_i|l_i,

\\ \displaystyle \sum_{i=1}^n (a_i^2-a_i)-n(n-1)+\sum_{i=1}^m|M_i|l_i = (m-n)\sum_{i=1}^na_i.

\\ \displaystyle (m-n)(m+n-1)-2L+\sum_{i=1}^m|M_i|l_i = (m-n)\sum_{i=1}^na_i,

\\ \displaystyle \sum_{i=1}^m|M_i|l_i-2L = (m-n) \left( \sum_{i=1}^na_i-m-n+1 \right). \end{array}$$

Since $\displaystyle\sum_{i=1}^ml_i=2L$ and $|M_i| \ge 2$ so $LHS \ge 2L \ge 0$. Hence, if $m<n$ then $\sum_{i=1}^na_i \le m+n-1$. But we also have $a_i \ge 2$ so $\displaystyle 2n \le \sum_{i=1}^na_i \le m+n-1$ implying $m \ge n+1$, a contradiction.

Thus, $m \ge n$.

Take $E = \{ x_1, x_2\}$.

There exist a set $M_{1,2}$ such that $x_1, x_2 \in M_{1,2}$.

But then $M_{1,2} = E$. This is a direct contradiction to the theorem.

Thus this doesn’t work for $n<3$.

- Convergence of exponential Brownian martingale to zero almost surely
- System of differential equations, pure imaginary eigenvalues, show that the trajectory is an ellipse.
- Examples of comma categories
- Prove that $\sqrt5 – \sqrt3$ is Irrational
- Amount of real numbers, in a given sequence, whose fractional part lies in a given closed interval
- combinatorial geometry: covering a square
- Definition of $\operatorname{arcsec}(x)$
- Defining the number $ e $
- Lagrange multipliers finding the maximum and minimum.
- Induction proof. Explain in detail why it’s incorrect
- If $n-1$ is $f(n)$-smooth, $n$ is prime infinitely often. What is the best $f$?
- Primitive binary necklaces
- About the ways prove that a ring is a UFD.
- The extension of a premeasure on a semiring $J$ to the borel sets
- To check convergence\divergence of infinite series $\frac 1{2^1} +\frac{1}{3^2}+ \frac 1{2^3} +\frac 1{3^4}\ldots$