How do I prove such a kernel is positive semi definite?$K(x, y) = \min(x, y) - xy$ over $[0, 1]$ For such a kernel:
$$K(x, y) = \min(x, y) - xy \text{ over } [0, 1] \times [0, 1].$$
How can I prove that it's positive semi definite? I know how to prove $\min(x, y)$ is PSD but I think $-xy$ is NSD, so can't use the closure property here. Is there a good approach?
 A: To show that $K(x, y)$ is semi-positive definite (PSD), it is sufficient to show that for any $n$ and $x_1, \ldots, x_n \in [0, 1]$, the Gram matrix $G = (K(x_i, x_j)) \in \mathbb{R}^{n \times n}$ is PSD. To this end, we use the following two properties in linear algebra:

*

*For $a_i \in [0, 1], i = 1, \ldots, n$, the matrix $A = (\min(a_i, a_j)) \in \mathbb{R}^{n \times n}$ is PSD.

*If two matrices $M_1$ and $M_2$ are PSD, then their Hadamard product $M_1 \circ M_2$ is also PSD.

If we can prove $1$ and $2$, then $M_1 = (\min(x_i, x_j)) \geq 0$, $M_2 = (\min(1 - x_i, 1 - x_j)) \geq 0$ and $G = M_1 \circ M_2$  together imply that $G \geq 0$.  This completes the proof.

Proof of 1. Since $\min(a_i, a_j) = \int_0^1 I_{(0, a_i]}(t)I_{(0, a_j]}(t)dt$, where $I_A(\cdot)$ stands for the indicator function (writing the entry $a_{ij}$ in appropriate integral form is a routine way to prove the positive definiteness of $A$, here is another example), for any $z := (z_1, \ldots, z_n) \in \mathbb{R}^n$, it follows that
\begin{align}
 & z'Az \\
=& \sum_i\sum_j z_iz_j\min(a_i, a_j) \\
=& \sum_i\sum_j z_iz_j\int_0^1 I_{(0, a_i]}(t)I_{(0, a_j]}(t)dt \\
=& \int_0^1 \sum_i z_i I_{(0, a_i]}(t)\sum_j z_j I_{(0, a_j]}(t)dt \\
=& \int_0^1\left(\sum_i z_i I_{(0, a_i]}(t)\right)^2dt \geq 0.
\end{align}
This proves that $A$ is PSD.
Proof of 2. The result is known as Schur product theorem, and the proof can be found in the same link.
A: Thanks to hint from jbowman. Here's my thought:
Since K(x, y) is guaranteed to be greater than or equal to 0, all elements in the Gram matrix will be greater than or equal to 0. Then all eigen values of the Gram matrix will be non-negative, so kernel K is PSD.
Edit:
Yes you guys are right, I seriously have to pick up my linear algebra.
To show that 1 - max(x, y) is PSD. We can treat that as we do to min(x, y), 1 - max(x, y) over [0, 1] is equivalent to $\int_0^11_{t>x}1_{t>y}dt$
\begin{eqnarray*}
\sum_{i, j}c_ic_j\int_0^11_{t>x}1_{t>y}dt&=&\int_0^1(\sum_1^nc_i1_{t>x})(\sum_1^nc_j1_{t>y})dt\\&=&\int_0^1Z^2(t)dt\\&\geq&0
\end{eqnarray*}
Hope I didn't mess up anything this time.
