2
$\begingroup$

Let $E_1, ..., E_n$ be non empty finite sets. Show that the matrix $A = (A_{ij})_{1 \leq i, j \leq n}$ defined by $A_{ij} = \dfrac{|E_i \cap E_j|}{|E_i \cup E_j|}$, is positive semi-definite.

This is part 5 of Exercise 1 in http://members.cbio.mines-paristech.fr/~jvert/svn/kernelcourse/homework/2019mva/hw.pdf .

I start with the definition but it doesn't seem very promising. Any hint, please?

$\endgroup$
  • 3
    $\begingroup$ If any two of the sets are empty then the corresponding coefficient is not defined. If the one set is disjoint from all the others, then its corresponding row and column are zero, so the matrix is not positive definite. $\endgroup$ – Servaes Mar 9 '19 at 18:53
  • $\begingroup$ You are correct, I've corrected the problem accordingly. $\endgroup$ – SiXUlm Mar 9 '19 at 21:14
  • $\begingroup$ Could the semi-definite positiveness be connected to the submodularity mentionned in the following answer : math.stackexchange.com/q/182384 ? $\endgroup$ – Jean Marie Mar 9 '19 at 23:09
  • $\begingroup$ Let $E$ be the union of the $E_i$. For each $e \in E$, define the matrix $B_e = \left( \dfrac{\left[e \in E_i \cap E_j\right]}{\left|E_i \cup E_j\right|} \right)_{i, j \in \left[n\right]}$, where square brackets stand both for the Iverson bracket and for $\left[n\right] := \left\{1,2,\ldots,n\right\}$. Clearly, $A = \sum_{e \in E} B_e$. Are the $B_e$ still positive semidefinite? This would likely be easier if true. After all, for each $e \in E$, the matrix $B_e$ is just a blown-up matrix with entries $\dfrac{1}{\left|E_i \cup E_j\right|}$. $\endgroup$ – darij grinberg Mar 10 '19 at 3:01
  • $\begingroup$ Even stronger: For any $e \in E$ and $t \in \mathbb{R}_+$, let $C_{e,t}$ be the matrix $\left(\left[e \in E_i \cap E_j\right] t^{\left|E_i \cup E_j\right|}\right)_{i, j \in \left[n\right]}$. Is $C_{e,t}$ nonnegative semidefinite for $0 < t < 1$ ? If it is, then so is $B_e$, since $B_e = \int_0^1 \left(C_{e,t}/t\right) dt$. $\endgroup$ – darij grinberg Mar 10 '19 at 3:08
4
$\begingroup$

Assume the sets $E_i$ are all non-empty. By deleting rows and columns of $A$ if needed one can reduce to the case where the $E_i$ are all distinct.

Write $$A_{ij}= \frac{|E_i\cap E_j|}{|E_i\cup E_j|} = \frac{|E_i\cap E_j|}{|E_i|+|E_j|-|E_i\cap E_j|} = \frac{e_{ij}}{e_i+e_j-e_{ij}} $$ where $e_i$ is shorthand for $|E_i|$ and so on. Then $$A_{ij}= \frac{e_{ij}}{e_i+e_j} \left( 1 + r_{ij} + r_{ij}^2 + r_{ij}^3 + \cdots\right)\tag{*}$$ where $r_{ij}= e_{ij}/(e_i+e_j).$ The distinctness hypothesis implies $|r_{ij}|<1$ and so the convergence of the geometric series in (*).

The matrix with entries $e_{ij}$ is a Gram matrix and hence positive semidefinite. The matrix with entries $1/(e_i+e_j) = \int_0^\infty e^ {-x|E_i|} e^{-x|E_j|} \,dx$ is also a Gram matrix so it too is psd. Schur's product theorem tells us that their elementwise product $r_{ij}$ is thus also psd. By Schur again, all the summand matrices in (*) are psd. So the sum, $A$, is psd.

Examples (where all the $E_i$ are equal, so all $A_{ij}=1$, say) show that positive semi definite cannot be replaced by positive definite as in an earlier form of the problem statement. I suppose that strict positive definiteness holds in the reduced case, but I don't see an argument. Numerical experiments show that the matrix $(r_{ij})$ is not strictly positive definite when (for example) the $E_i$ are all the 2-element subsets of $[4]$. The same experiments however do show $A$ strictly positive definite.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your solution. I've edited the question because I didn't state it correctly. $\endgroup$ – SiXUlm Mar 9 '19 at 21:28
  • $\begingroup$ Thanks for the clarification. I've just found out that you talked about Schur product theorem. $\endgroup$ – SiXUlm Mar 9 '19 at 21:35
  • $\begingroup$ [+1] Very smart ! $\endgroup$ – Jean Marie Mar 9 '19 at 22:37
  • $\begingroup$ Why is $(e_{ij})=(|E_i\cap E_j|)$ a Gram matrix? $\endgroup$ – William McGonagall Feb 14 at 12:32
  • $\begingroup$ @WilliamMcGonagall Because $e_{ij}=\langle v_i,v_j\rangle$, where $v_r$ denotes the vector whose $k$-th component is $1$ exactly when $k\in E_r$, and zero otherwise, and so on. $\endgroup$ – kimchi lover Feb 14 at 14:21
1
$\begingroup$

The following proof is inspired by my answer to math.stackexchange question https://math.stackexchange.com/q/1340405/, which in turn is inspired by the probabilistic method from extremal combinatorics. It is fully elementary and almost combinatorial ("almost" because it involves a simple limit argument at one point).

We begin with notations:

Let $\mathbb{N}$ be the set $\left\{ 0,1,2,\ldots\right\} $.

For each $n\in\mathbb{N}$, let $\left[ n\right] $ denote the set $\left\{ 1,2,\ldots,n\right\} $.

We also recall the following simple fact (Lemma 5 in my answer to math.stackexchange question https://math.stackexchange.com/q/1340405/):

Lemma 1. Let $Q$ be a finite totally ordered set. Let $J$ be a subset of $Q$. Let $r\in J$. Let $S$ be the set of all permutations of $Q$. Then, \begin{equation} \left\vert \left\{ \sigma\in S\ \mid\ \sigma\left( r\right) >\sigma\left( j\right) \text{ for all }j\in J\setminus\left\{ r\right\} \right\} \right\vert =\dfrac{\left\vert S\right\vert }{\left\vert J\right\vert }. \end{equation}

Now, I shall prove a first positive definiteness statement:

Theorem 2. Let $n\in\mathbb{N}$. Let $E_{1},E_{2},\ldots,E_{n}$ be $n$ finite sets. Let $x_{1},x_{2},\ldots,x_{n}$ be $n$ real numbers. Then, \begin{align} \sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\dfrac{x_{u}x_{v} }{\left\vert E_{u}\cup E_{v}\right\vert +1}\geq0. \end{align}

Proof of Theorem 2. Fix some object $r$ that belongs to none of the sets $E_{1},E_{2},\ldots,E_{n}$. Let $Q$ be the set $E_{1}\cup E_{2}\cup\cdots\cup E_{n}\cup\left\{ r\right\} $. This is a finite set (since the sets $E_{1},E_{2},\ldots,E_{n},\left\{ r\right\} $ are finite). We fix some total order on $Q$.

Let $S$ be the set of all permutations of $Q$. This $S$ is a finite nonempty set (of size $\left\vert Q\right\vert !$). Thus, $\left\vert S\right\vert $ is a positive integer.

If $u\in\left[ n\right] $ and $\sigma\in S$, then we say that $\sigma$ is $u$-friendly if we have $\left( \sigma\left( r\right) >\sigma\left( j\right) \text{ for all }j\in E_{u}\right) $. Now, we claim the following:

For any $u\in\left[ n\right] $ and $v\in\left[ n\right] $, we have \begin{equation} \left\vert \left\{ \sigma\in S\ \mid\ \sigma\text{ is }u\text{-friendly and }v\text{-friendly}\right\} \right\vert =\dfrac{\left\vert S\right\vert }{\left\vert E_{u}\cup E_{v}\right\vert +1}. \label{darij1.pf.t2.1} \tag{1} \end{equation}

[Proof of \eqref{darij1.pf.t2.1}: Fix $u\in\left[ n\right] $ and $v\in\left[ n\right] $. Define a subset $J$ of $Q$ by $J=E_{u}\cup E_{v} \cup\left\{ r\right\} $. (This is well-defined, since the definition of $Q$ shows that $E_{u}$, $E_{v}$ and $\left\{ r\right\} $ are subsets of $Q$.)

The object $r$ belongs to none of the sets $E_{1},E_{2},\ldots,E_{n}$. Thus, in particular, $r$ belongs neither to $E_{u}$ nor to $E_{v}$. In other words, $r\notin E_{u}\cup E_{v}$. This yields \begin{align} E_{u}\cup E_{v}=\underbrace{\left( E_{u}\cup E_{v}\cup\left\{ r\right\} \right) }_{=J}\setminus\left\{ r\right\} =J\setminus\left\{ r\right\} . \end{align} Also, $r\in J$; thus, $\left\vert J\setminus\left\{ r\right\} \right\vert =\left\vert J\right\vert -1$. Now, from $E_{u}\cup E_{v}=J\setminus\left\{ r\right\} $, we obtain $\left\vert E_{u}\cup E_{v}\right\vert =\left\vert J\setminus\left\{ r\right\} \right\vert =\left\vert J\right\vert -1$, so that $\left\vert J\right\vert =\left\vert E_{u}\cup E_{v}\right\vert +1$.

For each $\sigma\in S$, we have the following chain of logical equivalences: \begin{align*} & \ \left( \sigma\text{ is }u\text{-friendly and }v\text{-friendly}\right) \\ & \Longleftrightarrow\ \underbrace{\left( \sigma\text{ is }u\text{-friendly} \right) }_{\substack{\Longleftrightarrow\ \left( \sigma\left( r\right) >\sigma\left( j\right) \text{ for all }j\in E_{u}\right) \\\text{(by the definition of "}u\text{-friendly")}}}\wedge\underbrace{\left( \sigma\text{ is }v\text{-friendly}\right) }_{\substack{\Longleftrightarrow\ \left( \sigma\left( r\right) >\sigma\left( j\right) \text{ for all }j\in E_{v}\right) \\\text{(by the definition of "}v\text{-friendly")}}}\\ & \Longleftrightarrow\ \left( \sigma\left( r\right) >\sigma\left( j\right) \text{ for all }j\in E_{u}\right) \wedge\left( \sigma\left( r\right) >\sigma\left( j\right) \text{ for all }j\in E_{v}\right) \\ & \Longleftrightarrow\ \left( \sigma\left( r\right) >\sigma\left( j\right) \text{ for all }j\in\underbrace{E_{u}\cup E_{v}}_{=J\setminus \left\{ r\right\} }\right) \\ & \Longleftrightarrow\ \left( \sigma\left( r\right) >\sigma\left( j\right) \text{ for all }j\in J\setminus\left\{ r\right\} \right) . \end{align*} Hence, \begin{align*} & \left\vert \left\{ \sigma\in S\ \mid\ \sigma\text{ is }u\text{-friendly and }v\text{-friendly}\right\} \right\vert \\ & =\left\vert \left\{ \sigma\in S\ \mid\ \sigma\left( r\right) >\sigma\left( j\right) \text{ for all }j\in J\setminus\left\{ r\right\} \right\} \right\vert \\ & =\dfrac{\left\vert S\right\vert }{\left\vert J\right\vert }\qquad\left( \text{by Lemma 1}\right) \\ & =\dfrac{\left\vert S\right\vert }{\left\vert E_{u}\cup E_{v}\right\vert +1}\qquad\left( \text{since }\left\vert J\right\vert =\left\vert E_{u}\cup E_{v}\right\vert +1\right) . \end{align*} This proves \eqref{darij1.pf.t2.1}.]

Now, for each $\sigma\in S$, we have \begin{align*} & \left( \sum_{\substack{u\in\left[ n\right] ;\\\sigma\text{ is }u\text{-friendly}}}x_{u}\right) ^{2}\\ & =\left( \sum_{\substack{u\in\left[ n\right] ;\\\sigma\text{ is }u\text{-friendly}}}x_{u}\right) \left( \sum_{\substack{u\in\left[ n\right] ;\\\sigma\text{ is }u\text{-friendly}}}x_{u}\right)\\ & =\left( \sum_{\substack{u\in\left[ n\right] ;\\\sigma\text{ is }u\text{-friendly} }}x_{u}\right) \left( \sum_{\substack{v\in\left[ n\right] ;\\\sigma\text{ is }v\text{-friendly}}}x_{v}\right) \\ & \qquad\left( \begin{array} [c]{c} \text{here, we have renamed the summation}\\ \text{index }u\text{ as }v\text{ in the second sum} \end{array} \right) \\ & =\sum_{\substack{u\in\left[ n\right] ;\\\sigma\text{ is }u\text{-friendly} }}\sum_{\substack{v\in\left[ n\right] ;\\\sigma\text{ is }v\text{-friendly} }}x_{u}x_{v}. \end{align*} Summing up these equalities over all $\sigma\in S$, we obtain \begin{align*} & \sum_{\sigma\in S}\left( \sum_{\substack{u\in\left[ n\right] ;\\\sigma\text{ is }u\text{-friendly}}}x_{u}\right) ^{2}\\ & =\underbrace{\sum_{\sigma\in S}\sum_{\substack{u\in\left[ n\right] ;\\\sigma\text{ is }u\text{-friendly}}}\sum_{\substack{v\in\left[ n\right] ;\\\sigma\text{ is }v\text{-friendly}}}}_{=\sum\limits_{u\in\left[ n\right] } \sum\limits_{v\in\left[ n\right] }\sum\limits_{\substack{\sigma\in S;\\\sigma\text{ is }u\text{-friendly}\\\text{and }v\text{-friendly}}}}x_{u}x_{v}\\ & =\sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\underbrace{\sum _{\substack{\sigma\in S;\\\sigma\text{ is }u\text{-friendly}\\\text{and }v\text{-friendly}}}x_{u}x_{v}}_{=\left\vert \left\{ \sigma\in S\ \mid \ \sigma\text{ is }u\text{-friendly and }v\text{-friendly}\right\} \right\vert \cdot x_{u}x_{v}}\\ & =\sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] } \underbrace{\left\vert \left\{ \sigma\in S\ \mid\ \sigma\text{ is }u\text{-friendly and }v\text{-friendly}\right\} \right\vert } _{\substack{=\dfrac{\left\vert S\right\vert }{\left\vert E_{u}\cup E_{v}\right\vert +1}\\\text{(by \eqref{darij1.pf.t2.1})}}}\cdot x_{u}x_{v}\\ & =\sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\dfrac{\left\vert S\right\vert }{\left\vert E_{u}\cup E_{v}\right\vert +1}\cdot x_{u}x_{v}\\ & =\left\vert S\right\vert \cdot\sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\dfrac{x_{u}x_{v}}{\left\vert E_{u}\cup E_{v}\right\vert +1}. \end{align*} Hence, \begin{align} \left\vert S\right\vert \cdot\sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\dfrac{x_{u}x_{v}}{\left\vert E_{u}\cup E_{v}\right\vert +1} =\sum_{\sigma\in S}\underbrace{\left( \sum_{\substack{u\in\left[ n\right] ;\\\sigma\text{ is }u\text{-friendly}}}x_{u}\right) ^{2}}_{\substack{\geq 0\\\text{(since squares are nonnegative)}}}\geq0. \end{align} We can divide this inequality by $\left\vert S\right\vert $ (since $\left\vert S\right\vert $ is a positive integer). We thus obtain \begin{align} \sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\dfrac{x_{u}x_{v} }{\left\vert E_{u}\cup E_{v}\right\vert +1}\geq0. \end{align} This proves Theorem 2. $\blacksquare$

Now, we apply the tensor power trick. The first step is to replace the $1$ in Theorem 2 by a small rational number $1/m$:

Corollary 3. Let $n\in\mathbb{N}$. Let $E_{1},E_{2},\ldots,E_{n}$ be $n$ finite sets. Let $x_{1},x_{2},\ldots,x_{n}$ be $n$ real numbers. Let $m$ be a positive integer. Then, \begin{align} \sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\dfrac{x_{u}x_{v} }{\left\vert E_{u}\cup E_{v}\right\vert +1/m}\geq0. \end{align}

Proof of Corollary 3. For each $i\in\left[ n\right] $, we define a finite set $B_{i}$ by $B_{i}=E_{i}\times\left\{ 1,2,\ldots,m\right\} $. Then, for every $u\in\left[ n\right] $ and $v\in\left[ n\right] $, we have \begin{align*} & \underbrace{B_{u}}_{\substack{=E_{u}\times\left\{ 1,2,\ldots,m\right\} \\\text{(by the definition of }B_{u}\text{)}}}\cup\underbrace{B_{v} }_{\substack{=E_{v}\times\left\{ 1,2,\ldots,m\right\} \\\text{(by the definition of }B_{v}\text{)}}}\\ & =\left( E_{u}\times\left\{ 1,2,\ldots,m\right\} \right) \cup\left( E_{v}\times\left\{ 1,2,\ldots,m\right\} \right) \\ & =\left( E_{u}\cup E_{v}\right) \times\left\{ 1,2,\ldots,m\right\} \end{align*} and therefore \begin{align} \left\vert B_{u}\cup B_{v}\right\vert & =\left\vert \left( E_{u}\cup E_{v}\right) \times\left\{ 1,2,\ldots,m\right\} \right\vert =\left\vert E_{u}\cup E_{v}\right\vert \cdot\underbrace{\left\vert \left\{ 1,2,\ldots ,m\right\} \right\vert }_{=m}\nonumber\\ & =\left\vert E_{u}\cup E_{v}\right\vert \cdot m. \label{darij1.pf.c3.1} \tag{2} \end{align} But Theorem 2 (applied to $B_{i}$ instead of $E_{i}$) yields \begin{equation} \sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\dfrac{x_{u}x_{v} }{\left\vert B_{u}\cup B_{v}\right\vert +1}\geq0. \label{darij1.pf.c3.2} \tag{3} \end{equation} For each $u\in\left[ n\right] $ and $v\in\left[ n\right] $, we have \begin{align*} \dfrac{x_{u}x_{v}}{\left\vert B_{u}\cup B_{v}\right\vert +1} & =\dfrac {x_{u}x_{v}}{\left\vert E_{u}\cup E_{v}\right\vert \cdot m+1}\qquad\left( \text{by \eqref{darij1.pf.c3.1}}\right) \\ & =\dfrac{1}{m}\cdot\dfrac{x_{u}x_{v}}{\left\vert E_{u}\cup E_{v}\right\vert +1/m}. \end{align*} Adding up these equalities for all $u\in\left[ n\right] $ and $v\in\left[ n\right] $, we obtain \begin{align*} \sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\dfrac{x_{u}x_{v} }{\left\vert B_{u}\cup B_{v}\right\vert +1} & =\sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\dfrac{1}{m}\cdot\dfrac{x_{u}x_{v}}{\left\vert E_{u}\cup E_{v}\right\vert +1/m}\\ & =\dfrac{1}{m}\cdot\sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\dfrac{x_{u}x_{v}}{\left\vert E_{u}\cup E_{v}\right\vert +1/m}. \end{align*} Thus, \eqref{darij1.pf.c3.2} rewrites as \begin{align} \dfrac{1}{m}\cdot\sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\dfrac{x_{u}x_{v}}{\left\vert E_{u}\cup E_{v}\right\vert +1/m}\geq0. \end{align} We can multiply this inequality by $m$ (since $m$ is positive), and thus obtain \begin{align} \sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\dfrac{x_{u}x_{v} }{\left\vert E_{u}\cup E_{v}\right\vert +1/m}\geq0. \end{align} This proves Corollary 3. $\blacksquare$

The second part of the tensor power trick is to let $m\rightarrow\infty$:

Theorem 4. Let $n\in\mathbb{N}$. Let $E_{1},E_{2},\ldots,E_{n}$ be $n$ nonempty finite sets. Let $x_{1},x_{2},\ldots,x_{n}$ be $n$ real numbers. Then, \begin{align} \sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\dfrac{x_{u}x_{v} }{\left\vert E_{u}\cup E_{v}\right\vert }\geq0. \end{align}

Proof of Theorem 4. First of all, we notice that $E_{u}\cup E_{v}$ is a nonempty finite set whenever $u\in\left[ n\right] $ and $v\in\left[ n\right] $ (since $E_{1},E_{2},\ldots,E_{n}$ are nonempty finite sets), and thus its size $\left\vert E_{u}\cup E_{v}\right\vert $ is a positive integer. Thus, all the fractions $\dfrac{x_{u}x_{v}}{\left\vert E_{u}\cup E_{v}\right\vert }$ in Theorem 4 are well-defined.

Now, consider a positive integer $m$ going to infinity. Then, $\lim \limits_{m\rightarrow\infty}\dfrac{r}{q+1/m}=\dfrac{r}{q}$ for every real $r$ and every positive real $q$. Hence, \begin{align} \lim\limits_{m\rightarrow\infty}\dfrac{x_{u}x_{v}}{\left\vert E_{u}\cup E_{v}\right\vert +1/m}=\dfrac{x_{u}x_{v}}{\left\vert E_{u}\cup E_{v} \right\vert } \end{align} for every $u\in\left[ n\right] $ and $v\in\left[ n\right] $. Adding up these equalities for all $u\in\left[ n\right] $ and $v\in\left[ n\right] $, we obtain \begin{align} \sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\lim \limits_{m\rightarrow\infty}\dfrac{x_{u}x_{v}}{\left\vert E_{u}\cup E_{v}\right\vert +1/m}=\sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\dfrac{x_{u}x_{v}}{\left\vert E_{u}\cup E_{v}\right\vert }. \end{align} Hence, \begin{align*} \sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\dfrac{x_{u}x_{v} }{\left\vert E_{u}\cup E_{v}\right\vert } & =\sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\lim\limits_{m\rightarrow\infty}\dfrac {x_{u}x_{v}}{\left\vert E_{u}\cup E_{v}\right\vert +1/m}\\ & =\lim\limits_{m\rightarrow\infty}\underbrace{\sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\dfrac{x_{u}x_{v}}{\left\vert E_{u}\cup E_{v}\right\vert +1/m}}_{\substack{\geq0\\\text{(by Corollary 3)}}}\geq \lim\limits_{m\rightarrow\infty}0=0. \end{align*} This proves Theorem 4. $\blacksquare$

Now, let us recall the Iverson bracket notation:

Definition. We shall use the Iverson bracket notation: If $\mathcal{A}$ is any statement, then $\left[ \mathcal{A}\right] $ stands for the integer $ \begin{cases} 1, & \text{if $\mathcal{A}$ is true;}\\ 0, & \text{if $\mathcal{A}$ is false} \end{cases} $ (which is also known as the truth value of $\mathcal{A}$). For instance, $\left[ 1+1=2\right] =1$ and $\left[ 1+1=1\right] =0$.

Corollary 5. Let $n\in\mathbb{N}$. Let $E_{1},E_{2},\ldots,E_{n}$ be $n$ nonempty finite sets. Let $e$ be any object. Let $x_{1},x_{2},\ldots,x_{n}$ be $n$ real numbers. Then, \begin{align} \sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\dfrac{\left[ e\in E_{u}\cap E_{v}\right] }{\left\vert E_{u}\cup E_{v}\right\vert }x_{u} x_{v}\geq0. \end{align}

Proof of Corollary 5. For every $u\in\left[ n\right] $ and $v\in\left[ n\right] $, we have \begin{align*} \left[ e\in E_{u}\cap E_{v}\right] & =\left[ e\in E_{u}\text{ and }e\in E_{v}\right] \\ & \qquad\left( \text{since }e\in E_{u}\cap E_{v}\text{ holds if and only if }\left( e\in E_{u}\text{ and }e\in E_{v}\right) \right) \\ & =\left[ e\in E_{u}\right] \cdot\left[ e\in E_{v}\right] \end{align*} (because the rule $\left[ \mathcal{A}\text{ and }\mathcal{B}\right] =\left[ \mathcal{A}\right] \cdot\left[ \mathcal{B}\right] $ holds for any two statements $\mathcal{A}$ and $\mathcal{B}$) and therefore \begin{align*} \dfrac{\left[ e\in E_{u}\cap E_{v}\right] }{\left\vert E_{u}\cup E_{v}\right\vert }x_{u}x_{v} & =\dfrac{\left[ e\in E_{u}\right] \cdot\left[ e\in E_{v}\right] }{\left\vert E_{u}\cup E_{v}\right\vert } x_{u}x_{v}\\ & =\dfrac{\left( \left[ e\in E_{u}\right] x_{u}\right) \cdot\left( \left[ e\in E_{v}\right] x_{v}\right) }{\left\vert E_{u}\cup E_{v} \right\vert }. \end{align*} Adding up these equalities for all $u\in\left[ n\right] $ and $v\in\left[ n\right] $, we obtain \begin{align*} & \sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\dfrac{\left[ e\in E_{u}\cap E_{v}\right] }{\left\vert E_{u}\cup E_{v}\right\vert } x_{u}x_{v}\\ & =\sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\dfrac{\left( \left[ e\in E_{u}\right] x_{u}\right) \cdot\left( \left[ e\in E_{v}\right] x_{v}\right) }{\left\vert E_{u}\cup E_{v}\right\vert }\geq0 \end{align*} (by Theorem 4, applied to $\left[ e\in E_{i}\right] x_{i}$ instead of $x_{i}$). This proves Corollary 5. $\blacksquare$

We next recall a classical fact (I refer to it as "counting by roll call"):

Lemma 6. Let $Q$ be a finite set. Let $F$ be a subset of $Q$. Then, \begin{align} \left\vert F\right\vert =\sum_{e\in Q}\left[ e\in F\right] . \end{align}

Proof of Lemma 6. The sum $\sum_{e\in Q}\left[ e\in F\right] $ has exactly $\left\vert F\right\vert $ many addends equal to $1$ (namely, all the addends corresponding to $e\in F$), while all its remaining addends are $0$ and thus do not influence its value. Hence, $\sum_{e\in Q}\left[ e\in F\right] =\left\vert F\right\vert \cdot1=\left\vert F\right\vert $. This proves Lemma 6. $\blacksquare$

Theorem 7. Let $n\in\mathbb{N}$. Let $E_{1},E_{2},\ldots,E_{n}$ be $n$ nonempty finite sets. Let $x_{1},x_{2},\ldots,x_{n}$ be $n$ real numbers. Then, \begin{align} \sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\dfrac{\left\vert E_{u}\cap E_{v}\right\vert }{\left\vert E_{u}\cup E_{v}\right\vert }x_{u} x_{v}\geq0. \end{align}

Proof of Theorem 7. Let $Q$ be the set $E_{1}\cup E_{2}\cup\cdots\cup E_{n} $. This is a finite set (since the sets $E_{1},E_{2},\ldots,E_{n}$ are finite).

Fix $u\in\left[ n\right] $ and $v\in\left[ n\right] $. Then, $E_{u}\cap E_{v}$ is a subset of $Q$ (since $Q=E_{1}\cup E_{2}\cup\cdots\cup E_{n}$). Hence, Lemma 6 (applied to $F=E_{u}\cap E_{v}$) yields \begin{align} \left\vert E_{u}\cap E_{v}\right\vert =\sum_{e\in Q}\left[ e\in E_{u}\cap E_{v}\right] . \end{align} Thus, \begin{align} \dfrac{\left\vert E_{u}\cap E_{v}\right\vert }{\left\vert E_{u}\cup E_{v}\right\vert }x_{u}x_{v} & =\dfrac{\sum_{e\in Q}\left[ e\in E_{u}\cap E_{v}\right] }{\left\vert E_{u}\cup E_{v}\right\vert }x_{u}x_{v}\nonumber\\ & =\sum_{e\in Q}\dfrac{\left[ e\in E_{u}\cap E_{v}\right] }{\left\vert E_{u}\cup E_{v}\right\vert }x_{u}x_{v}. \label{darij1.pf.t7.1} \tag{4} \end{align}

Now, forget that we fixed $u$ and $v$. We have \begin{align*} & \sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\underbrace{\dfrac {\left\vert E_{u}\cap E_{v}\right\vert }{\left\vert E_{u}\cup E_{v}\right\vert }x_{u}x_{v}}_{\substack{=\sum_{e\in Q}\dfrac{\left[ e\in E_{u}\cap E_{v}\right] }{\left\vert E_{u}\cup E_{v}\right\vert }x_{u}x_{v}\\\text{(by \eqref{darij1.pf.t7.1})}}}\\ & =\sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\sum_{e\in Q}\dfrac{\left[ e\in E_{u}\cap E_{v}\right] }{\left\vert E_{u}\cup E_{v}\right\vert }x_{u}x_{v}=\sum_{e\in Q}\underbrace{\sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] }\dfrac{\left[ e\in E_{u}\cap E_{v}\right] }{\left\vert E_{u}\cup E_{v}\right\vert }x_{u}x_{v} }_{\substack{\geq0\\\text{(by Corollary 5)}}}\\ & \geq\sum_{e\in Q}0=0. \end{align*} This proves Theorem 7. $\blacksquare$

We are now ready for the original question:

Corollary 8. Let $n\in\mathbb{N}$. Let $E_{1},E_{2},\ldots,E_{n}$ be $n$ nonempty finite sets. Let $A$ be the $n\times n$-matrix $\left( \dfrac{\left\vert E_{u}\cap E_{v}\right\vert }{\left\vert E_{u}\cup E_{v}\right\vert }\right) _{u,v\in\left[ n\right] }\in\mathbb{R}^{n\times n}$. Then, $A$ is positive semidefinite.

Proof of Corollary 8. For every $u\in\left[ n\right] $ and $v\in\left[ n\right] $, we have $\dfrac{\left\vert E_{u}\cap E_{v}\right\vert }{\left\vert E_{u}\cup E_{v}\right\vert }=\dfrac{\left\vert E_{v}\cap E_{u}\right\vert }{\left\vert E_{v}\cup E_{u}\right\vert }$ (since $E_{u}\cap E_{v}=E_{v}\cap E_{u}$ and $E_{u}\cup E_{v}=E_{v}\cup E_{u}$). Thus, the matrix $A$ is symmetric. Hence, in order to prove that $A$ is positive semidefinite, it suffices to show that $x^{T}Ax\geq0$ for any vector $x\in\mathbb{R}^{n}$. So let us do this.

Fix $x\in\mathbb{R}^{n}$. We must show that $x^{T}Ax\geq0$. Write the vector $x\in\mathbb{R}^{n}$ in the form $x=\left( x_{1},x_{2},\ldots,x_{n}\right) ^{T}$ for some real numbers $x_{1},x_{2},\ldots,x_{n}$. Then, the definition of $A$ yields \begin{align} x^{T}Ax=\sum_{u\in\left[ n\right] }\sum_{v\in\left[ n\right] } \dfrac{\left\vert E_{u}\cap E_{v}\right\vert }{\left\vert E_{u}\cup E_{v}\right\vert }x_{u}x_{v}\geq0 \end{align} (by Theorem 7). This completes our proof of Corollary 8. $\blacksquare$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.