Checking if a kernel is valid

Question

The kernel is $K(x,z) = \sum_{i=1}^D (x_i+z_i)$

My approach was trying to express $K = \phi(x)^T\phi(z) = (x_1 x_2 ... x_D \quad 1 1 ...1)(1 1 ...1\quad z_1 z_2 ... z_D )^T$ where $\phi$ is 2Dx1 and thus a Kernel.

The solution says:

K is not a kernel. Consider $x_1 = [1 \quad 0]^T \quad x_2 = [0 \quad 2]^T$. Their kernel matrix has eigenvalues −1 and 5.

What explains this discrepancy?

Answer 1

Your confusion is that you're using $\phi$ to denote two different mappings. The first one maps its input $v$ to the vector $\begin{pmatrix} v & \mathbf{1} \end{pmatrix}$, and the second one maps it to $\begin{pmatrix} \mathbf{1} & v \end{pmatrix}$. In the same way we can prove that $-1$ is the square of a real number: $-1 = x \cdot x = (-1) \cdot (+1)$.