Let $k(.,.)$ be a function that takes two vectors as input and outputs a scalar as follows \begin{align} \mathcal{k}(x,y) = \exp\left(\frac{\xy\_2^2}{2}\right) \end{align} where $\x\_2$ denotes the $2$norm. Now, let $x_1,\dots,x_m$ be $m$ vectors in $\mathbb{R}^d$. Let me define the $m \times m$ matrix $\mathbf{K}$ such that its entries are given as \begin{align} \mathbf{K}_{ij} = \mathcal{k}(x_i,x_j) \end{align} For any vector $x$, let me define the $m\times 1$ vector $\mathcal{K}_x$ as \begin{align} \mathcal{K}_x = \begin{bmatrix} \mathcal{k}(x,x_1) \\ \vdots \\ \mathcal{k}(x,x_m) \end{bmatrix} \end{align} Now I am curious if following inequality holds true for every $x\in\mathbb{R}^d$ \begin{align} \mathcal{K}_x^T\mathbf{K}^{1}\mathcal{K}_x \leq 1 \end{align}
2 Answers
The radial basis function kernel $\mathcal{k}(x,y) = \exp\left(\frac{\xy\_2^2}{2\sigma^2}\right)$ is a positive definite kernel. So, $M=\begin{bmatrix}\textbf{K}&\mathcal{K}_x\\\mathcal{K}_x^T&1\end{bmatrix} $ is a positive definie matrix. Hence, the Schur complement of the block $1$ of the matrix $M$ is also a positive definie matrix. That is $1\mathcal{K}_x^T\mathbf{K}^{1}\mathcal{K}_x \geq 0$. Q.E.D.
A less elegant way to prove this would be to note that
$$(\mathbf K^{1}\mathcal{K}_x)_i = \sum_jK^{1}_{ij}K_{jx}= \begin{cases} 1 & i=x\\ 0 & i \not = x \end{cases}, $$
which is exactly $e_x$, the vector with a 1 in the $x$ coordinate and 0s elsewhere. We then remember that $\mathcal{K}_x$ is less than 1 in each component since $e^{y} \leq 1$ for all $y \in [0,\infty]$ and then this gives us that $$\mathcal{K}_x^T\mathbf K^{1}\mathcal{K}_x = \mathcal{K}_x^Te_x = k(x,x) = 1, $$
so the inner product is in fact 1. This generalizes to all invertible symmetric matrices with all diagonal elements $\leq$ 1.

$\begingroup$ The first formula in your answer has both its equalities wrong. $\endgroup$– Alex M.Commented Jun 6 at 10:04
