Show whether matrix is positive semidefinite or not

Background and motivation: When creating a Mercer Kernel Function we need to show that the Gram matrix defined by the function is positive semidefinite.

Let $A_1, \ldots, A_n$ be subsets of $\{0, 1, \ldots, D\}$. Let $S(X)$ be the smallest $k$ elements of the set $X$. so with $k= 3$ we have $S(\{5,7,1,2,8,3\}) = \{1,2,3\}$.

Let's construct a matrix $G$ with $$ G_{i,j} = |S(A_i)\cap S(A_j)\cap S(A_i\cup A_j)| = |S(A_i)\cap S(A_j)\cap S(S(A_i)\cup S(A_j))| $$

(The last equality is pretty intuitive and easy to show). Is $G$ Positive semidefinite? $D$, $n$ and $k$ are all given positive integers. It is clear that $G$ is symmetric with only positive entries.

For inspiration it is pretty easy to show that the matrix $M$ defined by $M_{i,j} = |S(A_i) \cap S(A_j)|$ is Positive semidefinite. Create a vector $v_i$ that has $v_{i,j} = 1$ if $j\in S(A_i)$ and $0$ otherwise. each $v_i$ is then a $D+1$ dimensional vector and we have $M_{i,j} = \langle v_i, v_j\rangle$, so $M$ is the product of a matrix and its transpose.

Solution 1:

$G$ is positive semidefinite for $n = 2$.

Proof: The principal minors of $G$ are $|S(A_1)|$, $|S(A_2)|$ and $|S(A_1)||S(A_2)| - |S(A_1) \cap S(A_2) \cap S(A_1 \cup A_2)|^2$. All principal minors are nonnegative, so $G$ is positive semidefinite.

($|S(A_1)||S(A_2)| - |S(A_1) \cap S(A_2) \cap S(A_1 \cup A_2)|^2 \geq |S(A_1)||S(A_2)| - |S(A_1)||S(A_2)| = 0$)

Some numerical testing suggests that $G$ is always positive semidefinite, but I don't know how to prove it in higher dimensions.