Mostrar si la matriz es positiva semidefinite o no

Question

Antecedentes y motivación: Cuando la creación de un Mercer Núcleo de la Función que tenemos que mostrar que la matriz de Gram definido por la función es positiva semidefinite.

Deje $A_1, \ldots, A_n$ ser subconjuntos de a $\{0, 1, \ldots, D\}$. Deje $S(X)$ ser el más pequeño $k$ elementos de las $X$. así que con $k= 3$ tenemos $S(\{5,7,1,2,8,3\}) = \{1,2,3\}$.

Vamos a construir una matriz de $G$ con $$G_{i,j} = |S(A_i)\cap S(A_j)\cap S(A_i\copa A_j)| = |S(A_i)\cap S(A_j)\cap S(S(A_i)\cup S(A_j))|$$

(La última igualdad es bastante intuitivo y fácil de demostrar). Es $G$ Positivo semidefinite? $D$, $n$ y $k$ son todos los enteros positivos. Está claro que $G$ es simétrica con sólo positivo entradas.

La inspiración es bastante fácil demostrar que la matriz de $M$ definido por $M_{i,j} = |S(A_i) \cap S(A_j)|$ es Positivo semidefinite. Crear un vector $v_i$ que ha $v_{i,j} = 1$ si $j\in S(A_i)$ $0$ lo contrario. cada una de las $v_i$ es $D+1$ dimensiones del vector y tenemos $M_{i,j} = \langle v_i, v_j\rangle$, lo $M$ es el producto de una matriz y su transpuesta.

Answer 1

$G$ es positivo semidefinite para $n = 2$.

Prueba de ello: El director de menores de $G$ $|S(A_1)|$, $|S(A_2)|$ y $|S(A_1)||S(A_2)| - |S(A_1) \cap S(A_2) \cap S(A_1 \cup A_2)|^2$. Todos los principales menores de edad son no negativos, por lo $G$ es positivo 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$)

Algunos numéricos de las pruebas sugiere que $G$ siempre es positivo semidefinite, pero no sé cómo demostrarlo en las dimensiones superiores.