# Proof that the linear kernel is a kernel, understanding the math

I can't seem to wrap my head around the following proof.

I want to show that the linear kernel is a kernel because its Gram matrix is positive semi-definite.

There is plenty of information on the internet, but I don't understand the last step:
linear kernel: $k(x,x')=<x,x>=\sum_{a=0}^N x_ax_a'$
$$\sum_{i,j} c_i c_j k(x_i,x_j) \ge 0$$
$$\sum_{i,j} c_i c_j k(x_i,x_j) = \sum_{i,j} c_i c_j <x_i,x_j> =\sum_{i,j} c_i c_j \sum_{a=0}^N x_ax_a'=\sum_{i,j} \sum_{a=0}^N c_i x_ac_jx_a'$$ So far so good. But now, why can I say that this is equal to: $$||\sum_{i} \sum_{a=0}^N c_i x_a||^2 \ge 0$$ The $\ge$ is clear just why is the formula transformed in that way?

A similar approach for the dot-product is shown here: click
Thanks a lot!

First, your definition should be corrected as $$k(x, x') = \langle x, x\color{red}{'}\rangle = \sum_{a = 1}^N x_a x_a'.$$ The problem of your derivation is that you didn't distinguish $x_i = (x_{i,1}, \ldots, x_{i,N})^T$ and $x_j = (x_{j, 1}, \ldots, x_{j, N})^T$ very clearly. Let's say you have $p$ vectors $\{x_1, \ldots, x_p\}$ under consideration. It follows that (what you provided was actually incorrect): \begin{align} & \sum_{i, j} c_i c_j k(x_i, x_j) \\ = & \sum_{i = 1}^p \sum_{j = 1}^p c_i c_j \sum_{a = 1}^N x_{i,a}x_{j, a} \\ = & \sum_{i = 1}^p \sum_{j = 1}^p \sum_{a = 1}^N c_i x_{i,a} c_j x_{j, a} \\ = & \sum_{a = 1}^N \left(\sum_{i = 1}^p c_i x_{i, a}\right) \left(\sum_{j = 1}^p c_j x_{j, a}\right) \qquad \text{ change the order of summation}\\ = & \sum_{a = 1}^N \left(\sum_{i = 1}^p c_i x_{i, a}\right)^2 \geq 0. \qquad i, j \text{ are just dummy indices} \end{align}

• Hi thanks for your answer, for me, the last step is not really obvious because $x_i$ and $x_j$ can be different for example $(1, 2, 3)$ and $(-5, 8, 9)$ and then we can't just square them.
– flow
May 29, 2018 at 13:45
• @flow Both $i$ and $j$ belong to the set $\{1, 2, \ldots, p\}$. The example you gave doesn't meet this condition. To give you a clearer picture, what we did here is similar to write the sum $1 + 2 + 3$ as $\sum_{i = 1}^3 i$ or $\sum_{j = 1}^3 j$. May 29, 2018 at 14:19
• Ok yes $i$ and $j$ belonging to the same set but these are the indices can I be sure that both $x$ are the same because you mentioned above we have $x$ and $x^{\prime}$, because if then I don't understand why we need this whole proof then if would be obvious in the beginning because, $c_i$ and $c_j$ are above $1$ in my definition.
– flow
May 29, 2018 at 14:39

If you don't mind matrix notation, let $X$ be the $n \times p$ matrix of observations. Each of the $p$ vectors is a column of $X$. Then the kernel condition is:

$$c'(X'X)c$$ for an arbitrary vector $c$ of length $p$.

$$c'(X'X)c = (Xc)'Xc$$

Recall that $Xc$ is an $n \times 1$ vector, say $(u_1, u_2, \ldots, u_N)$, and the RHS of the previous equation is:

$$\sum_{i=1}^N u_i^2 \geq 0$$

Your goal was to show that it is positive semidefinite, and the square of a real number is non-negative.

The first one uses an abbreviated notation for the double sum over $i$ and $j$, but they are dummy variables over the same interval, so we can remove one of these and square what we have left (noting that the $c_i$ are scalars and can be rearranged).

• Sure! But why is the last statement equal to the previous one? After all, I'm saying that $\sum c_jx_a'$ is equal to $\sum c_ix_a$ Nov 20, 2015 at 21:55
• This is a little brief for what we typically want from an answer here. Given that the OP is still confused, can you expand this a little? Nov 20, 2015 at 22:11
• I'm on a phone so its hard to type LaTeX, but "the first one" refers to the penultimate equation (RHS of the last bit that was "so far so good". Nov 20, 2015 at 22:19