Intereting Posts

Boy Born on a Tuesday – is it just a language trick?
Proof that if $p\equiv3\,\left(\mbox{mod 4}\right)$ then $p$ can't be written as a sum of two squares
Do there exist two primes $p<q$ such that $p^n-1\mid q^n-1$ for infinitely many $n$?
How prove this inequality $\frac{2}{(a+b)(4-ab)}+\frac{2}{(b+c)(4-bc)}+\frac{2}{(a+c)(4-ac)}\ge 1$
Proving that $S=\{\frac{1}{n}:n\in\mathbb{Z}\}\cup\{0\}$ is compact using the open cover definition
Derivative of sinc function
Name for numbers expressible as radicals
EGF of rooted minimal directed acylic graph
Finding equation of an ellipsoid
Evaluating $\int_0^{\infty}\frac{e^{-x}}{1+x^2}dx$
generated sigma algebra from countable sub family's of a collection of subsets
Show that $\int_0^1\ln(-\ln{x})\cdot{\mathrm dx\over 1+x^2}=-\sum\limits_{n=0}^\infty{1\over 2n+1}\cdot{2\pi\over e^{\pi(2n+1)}+1}$ and evaluate it
A rigorous book on a First Course in linear algebra
When is the topological closure of an equivalence relation automatically an equivalence relation?
closed form of $\int_{0}^{2\pi}\frac{dx}{(a^2\cos^2x+b^2\sin^2x)^n}$

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.

- Computing the $n^{\textrm{th}}$ permutation of bits.
- Number of circuits that surround the square.
- Roots of polynomials on the unit circle
- Combination with repetitions.
- What is the probability that when you place 8 towers on a chess-board, none of them can beat the other.
- Count subsets of an i-set in two ways

- Distinguishable painted prisms with six colors (repetition allowed)
- Steiner triple system with $\lambda \le 1$
- If $A+A^T$ is negative definite, then the eigenvalues of $A$ have negative real parts?
- Showing ${1\over n}\sum|S_i|=O(\sqrt n)$ for $S_i\subset $, $|S_i\cap S_i|\le 1$ for $i\ne j$
- Writing up a rigorous solution for finding a basis for the $n \times n$ symmetric matrices.
- How to prove that the rank of a matrix is a lower semi-continuous function?
- Area of a parallelogram, vertices $(-1,-1), (4,1), (5,3), (10,5)$.
- Combinatorial proof that binomial coefficients are given by alternating sums of squares?
- Finding the dimension of the orthogonal complement
- Why is determinant a multilinear function?

**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$.

- Contour integral – $\int_C \frac{\log z}{z-z_0} dz$ – Contradiction
- Formalizing an idea
- Quotient of nilpotent group is nilpotent
- Intermediate fields Separable, Algebraic, or Splitting
- On the number of ways of writing an integer as a sum of 3 squares using triangular numbers.
- Number of birational classes of dimension d, geometric genus 0 varieties?
- We have sums, series and integrals. What's next?
- Expectation of the min of two independent random variables?
- Normal Operators: Meet
- What is the probability of rolling $n$ dice until each side appears at least once?
- Is $\mathbb{R}$ an algebraic extension of some proper subfield?
- Riemann sum on infinite interval
- Determinant identity: $\det M \det N = \det M_{ii} \det M_{jj} – \det M_{ij}\det M_{ji}$
- Expected number of trials before I get one of each type
- Proof that if $p\equiv3\,\left(\mbox{mod 4}\right)$ then $p$ can't be written as a sum of two squares