Suppose we have a finite set $\Omega$ and a collection of subsets of $\Omega$, denoted by $\{A_1,…,A_n\}$.
Define $k(X,Y)=2^{|X\cap Y|}, \forall X,Y\subset \Omega$.
Define a $n\times n$ matrix $G$ by letting $G_{i,j}=k(A_i,A_j)$, i.e. $2^{|A_i\cap A_j|}.$
I need to show that $G$ is positive semi-definite.
To this end, I fix an $x\in \mathbb R^n$ and try to show that $x^T Gx \ge 0$.
When $n=2$, we can show that $x^T Gx$ is greater than a complete square which is nonnegative. But when $n\ge 3$, it seems like we can no longer use trivial inequalities to get a lower bound which is complete square. I get stuck here. Thanks for any help.
Best Answer
Let $\Omega=\{\omega_1,\omega_2,\ldots,\omega_m\}$ and $V\in\mathbb R^{m\times n}$ be the matrix such that $v_{ij}=1$ if $\omega_i\in A_j$, or $v_{ij}=0$ otherwise. The matrix $M=(|A_i\cap A_j|)_{i,j\in\{1,2,\ldots,n\}}$ is then identical to $V^TV$. Hence it is positive semidefinite.
Now denote the entrywise base-$b$ exponential of a matrix $X$ by $b^{\circ\,X}$ and the $r$-th entrywise power of $X$ by $X^{\circ\,r}$. Let $E$ be the all-one matrix. Then $$ 2^{\circ\,M}=e^{\circ\,M\log2} =E+M\log2+\frac{1}{2!}(M\log2)^{\circ\,2}+\frac{1}{3!}(M\log2)^{\circ\,3}+\cdots. $$ Hence it is PSD because $E$ is PSD and $(M\log2)^{\circ\,r}$, by Schur product theorem, is also PSD for each $r\ge1$.