Something similar came up in an old exam. Can you prove or disprove (with a counterexample) the following:
Let $k(x,y)$ be a symmetric function, with $x,y \in \mathbb{R}^d$, $k:\mathbb{R}^{d\times 2} \to \mathbb R$
For $x_1,…,x_n \in \mathbb{R}^d$, let G be defined as:
\begin{equation*}
G_{x_1,..,x_n} =
\begin{pmatrix}
k(x_1, x_1) & k(x_1,x_2) & \cdots & k(x_1,x_n) \\
k(x_2, x_1) & k(x_2,x_2) & \cdots & k(x_2,x_n) \\
\vdots & \vdots & \ddots & \vdots \\
k(x_m, x_1) & k(x_m,x_2) & \cdots & k(x_m,x_n)
\end{pmatrix}
\end{equation*}
Now lets assume that for each two vectors $x_1,x_2 \in \mathbb{R}^d$ it holds that $G_{x_1,x_2}$ is positive semi-definite, with:
\begin{equation*}
G_{x_1,x_2} =
\begin{pmatrix}
k(x_1, x_1) & k(x_1,x_2) \\
k(x_2, x_1) & k(x_2,x_2) \\
\end{pmatrix}
\end{equation*}
Does it follow that $G_{x_1,..,x_n}$ is positive semi definite for any $n$ vectors $x_1,..,x_n$ ?
I'm pretty sure this is not true but couldn't find a counterexample.
Remark : This would essentially mean that $k$ is a kernel and $G$ is the corresponding Gram Matrix.
Best Answer
For $x,y\in\mathbb R^d$ let $$k(x,y)=\begin{cases}1 & x=y\\-1& x\ne y\end{cases}.$$ Then, if your $x_i$ vectors are distinct, your $2\times2$ matrices are all $\pmatrix{1&-1\\-1&1}$ and all the larger ones contain as submatrices the non-psd matrices $\pmatrix{1&-1&-1\\-1&1&-1\\-1&-1&1}$.
In this example the $k$ function is discontinuous. But it is easy to find continuous $k$ that contain this same behavior at selected combinations of $x_i$ vectors.