Symmetric: K(x, z) = K(z, x)Positive semi-definite: for any finite set of points {x1, x2, ..., xn}, the corresponding kernel matrix K must be symmetric and positive semi-definite