Exercise 12.13: From Sets to Power Sets
Rewrite \begin{equation} k’(A, B) = 1_A^\T k(A, B) 1_B \end{equation} where $1_A$ denotes the vector of $|A|$ ones. Then note that \begin{align} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j k’(A_i, A_j) &= \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j 1_{A_i}^\T k(A_i, A_j) 1_{A_j} \newline &= \begin{bmatrix} \alpha_1 1_{A_1} \newline \vdots \newline \alpha_n 1_{A_n} \end{bmatrix}^\T \begin{bmatrix} k(A_1, A_1) & \cdots & k(A_1, A_n) \newline \vdots & \ddots & \vdots \newline k(A_n, A_1) & \cdots & k(A_n, A_n) \end{bmatrix} \begin{bmatrix} \alpha_1 1_{A_1} \newline \vdots \newline \alpha_n 1_{A_n} \end{bmatrix} \ge 0 \end{align} by positive definiteness of $k$.