Linear Kernel

k(x, y) = x\cdot y

Given the kernel

k(x_i, x_j) = x_i \cdot x_j

, we need to prove

\sum_{i=1}^n \sum_{j=1}^n c_i c_j k(x_i, x_j) \geq 0

\sum_{i=1}^n \sum_{j=1}^n c_i c_j (x_i \cdot x_j)

Rearrange terms using the bilinearity of the dot product:

\sum_{i=1}^n \sum_{j=1}^n c_i c_j (x_i \cdot x_j) = \left( \sum_{i=1}^n c_i x_i \right) \cdot \left( \sum_{j=1}^n c_j x_j \right)

\text{Let } v = \sum_{i=1}^n c_i x_i: \left( \sum_{i=1}^n c_i x_i \right) \cdot \left( \sum_{j=1}^n c_j x_j \right) = v \cdot v

Simplify using the definition of the Euclidean norm:

v \cdot v = \|v\|^2 \geq 0

Therefore, for any

c

and

x

\sum_{i=1}^n \sum_{j=1}^n c_i c_j k(x_i, x_j) \geq 0.