# Proof that the linear kernel is a kernel

I'm having trouble trying to show that the linear kernel is a kernel because its Gram matrix is symmetric and positive semi-definite. Can anyone help me?

I assume you mean a kernel of the form $$K(\boldsymbol{x},\boldsymbol{y}) = \boldsymbol{x}^{T}\boldsymbol{y}$$ where we have $$\boldsymbol{x}, \boldsymbol{y} \in \mathbb{R}^{d}$$. We need to show symmetry and positive definiteness of the function.
1. $$\textit{Symmetry: }$$ This is easy and follows directly from the symmetry of the dot product: $$K(\boldsymbol{x}, \boldsymbol{y}) = \boldsymbol{x}^{T}\boldsymbol{y} = \boldsymbol{y}^{T}\boldsymbol{x} = K(\boldsymbol{y}, \boldsymbol{x})$$
2. $$\textit{Positive-Definiteness: }$$ We need to prove that for every $$\boldsymbol{c} \in \mathbb{R}^{n}$$ and for any set of observations $$\boldsymbol{x}_1, \dots, \boldsymbol{x}_n \in \mathbb{R}^{d}$$, it holds: $$\sum_{i=1}^{n}\sum_{j=1}^{n}c_ic_jK(\boldsymbol{x}_i, \boldsymbol{x}_j) \geq 0$$ Plugging in the specific form of our kernel we see that $$\sum_{i=1}^{n}\sum_{j=1}^{n}c_ic_j\boldsymbol{x}_i^{T} \boldsymbol{x}_j = \left(\sum_{i=1}^{n}c_i\boldsymbol{x}_i\right)^{T}\left(\sum_{j=1}^{n}c_j \boldsymbol{x}_j\right) = {||}\sum_{i=1}^{n}c_i\boldsymbol{x}_i{||}_2^{2} \geq 0$$ where we used the double sum property $$\left(\sum_{i=1}^{n}a_i\right)\left(\sum_{i=1}^{n}b_i\right) = \sum_{i=1}^{n}\sum_{j=1}^{n}a_ib_j$$ This shows the positive definiteness of $$K$$ and hence $$K$$ is a kernel.
If you have a kernel with a bias $$\beta>0$$ $$K_{\beta}(\boldsymbol{x},\boldsymbol{y}) = \boldsymbol{x}^{T}\boldsymbol{y} + \beta$$ we can just reduce the problem to the above kernel $$K$$ by augmenting $$\boldsymbol{x}$$ with the coordinate $$\sqrt{\beta}$$.
Notice that $$\beta>0$$ is necessary, otherwise we don't get a kernel since $$K_{\beta}(\boldsymbol{0},\boldsymbol{0}) = \beta <0$$ violates positive definiteness. Hence the square-root $$\sqrt{\beta}$$ is well-defined.