Prove a matrix is positive semi-definite

Question

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.

Answer 1

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

Answer 2

This is not a complete proof but might give some idea:

If you let me put one extra condition on the sets $A_i$, then there is a simple proof for that based on Gershgorin circle theorem and diagonally dominant matrices:

A Hermitian diagonally dominant matrix $A$ with real non-negative diagonal entries is positive semidefinite.

If there is an extra condition that satisfies (2) below, then we can apply the above theorem. For example, we assume that $A_i$ s are disjoint.

1- The matrix is real and symmetric.

2 - The matrix is diagonally dominant: $ G_{ii} \geq \sum_{j\neq i} G_{ij}$. Because for each $i$,

$$ |A_i| \geq \sum_{j\neq i}|A_i \cap A_j| \Rightarrow2^{|A_i|} \geq \sum_{j \neq i} 2^{|A_i\cap A_j|} $$

So the matrix is positive semidefinite.

$A_i$'s don't have be disjoint to satisfy (2), we can make a stronger condition so that it could still satisfy (2).