Proof of Positive Semidefinite Kernels on a Finite Set: Rank-One Decomposition and the Schur Product

We use the following items: Positive Semidefinite Kernel on a Finite Set §kernel; Sum over a Finite Index Set; claims 1 to 4 of Properties of a Sum over a Finite Index Set; Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §disjoint-union, Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §vanishing, Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §pairs and Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §conjugate; The Product of Two Sums over Finite Index Sets is a Sum over the Cartesian Product; claims 1 and 2 of Peeling an Element off a Finite Set, and Unions of Finite Sets; claims 2 and 3 of Basic Properties of Finite Sets; claims 1, 2 and 3 of Basic Properties of Initial Segments of the Natural Numbers; Finite Set; Characteristic Property of the Ordered Pair; Finite Sum Notation in a Field; claims 1, 3, 4 and 5 of Properties of Finite Sums; condition 1 of The Complex Numbers; claims 1 and 3 of Properties of Complex Conjugation and Modulus; claim 1 of Canonical Form and Arithmetic of Complex Numbers; Modulus of a Complex Number; Existence and Uniqueness of the Nonnegative Square Root; claim 5 of Elementary Arithmetic in an Ordered Field; claims 4, 6 and 8 of Elementary Order Arithmetic in an Ordered Field; claim 3 of Monotonicity of Squaring on the Nonnegative Elements of an Ordered Field; and Principle of Induction for the Natural Numbers.

Conventions. The notion of Positive Semidefinite Kernel on a Finite Set §kernel is used for every nonempty finite set $G$, not only for $F$. For an element $p$ of a Cartesian product $G\times G$ we write $p=(p_{1},p_{2})$, the components being unique by Characteristic Property of the Ordered Pair. For an arbitrary map $K:G\times G\to\mathbb{C}$ (positive semidefinite or not) and a map $z:G\to\mathbb{C}$ we use the same formula

as in Positive Semidefinite Kernel on a Finite Set §kernel. Conjugation commutes with sums, products and differences and fixes real numbers, by claim 1 of Properties of Complex Conjugation and Modulus; we use this silently in computations.

Step 1. (Finite sums of real numbers.) Let $N\in\mathbb{N}$ and let $a_{1},\dots,a_{N}$ be real numbers. The partial-sum map $\sigma:[N]\to\mathbb{R}$ of Finite Sum Notation in a Field for the field $\mathbb{R}$ satisfies $\sigma(1)=a_{1}$ and $\sigma(S(m))=\sigma(m)+a_{S(m)}$ whenever $S(m)\in[N]$; by condition 1 of The Complex Numbers these equations remain true when the additions are formed in $\mathbb{C}$, so by the uniqueness of the partial-sum map in Finite Sum Notation in a Field for the field $\mathbb{C}$, the finite sum $\sum_{k=1}^{N}a_{k}$ formed in $\mathbb{C}$ equals the one formed in $\mathbb{R}$. Consequently, if $0\le a_{k}$ for every $k\in[N]$, then $\sum_{k=1}^{N}a_{k}$ is a real number and is nonnegative, by claim 5 of Properties of Finite Sums.

Step 2. (Sums over one or two points.) Let $x$ be an object and $h:\{x\}\to\mathbb{C}$ a map. The set $\{x\}$ has $1$ element by claim 2 of Basic Properties of Finite Sets, so there is a bijection $\varphi:[1]\to\{x\}$; since $[1]=\{1\}$ by claim 2 of Basic Properties of Initial Segments of the Natural Numbers, $\varphi(1)=x$, and Sum over a Finite Index Set together with claim 1 of Properties of Finite Sums gives $\sum_{y\in\{x\}}h(y)=\sum_{k=1}^{1}h(\varphi(k))=h(x)$. Now let $P$ be a nonempty finite set and $f:P\to\mathbb{C}$ a map. (a) If $x\in P$ and $f(y)=0$ for every $y\in P$ with $y\ne x$, then $\sum_{y\in P}f(y)=\sum_{y\in\{x\}}f(y)=f(x)$, by the second part of Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §vanishing and the formula just proved. (b) If $x,x'\in P$ with $x\ne x'$ and $f(y)=0$ for every $y\in P\setminus\{x,x'\}$, then the set $D=\{x\}\cup\{x'\}\subseteq P$ is nonempty and finite by claim 1 of Peeling an Element off a Finite Set, and Unions of Finite Sets, so the second part of Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §vanishing, then Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §disjoint-union for the disjoint sets $\{x\}$ and $\{x'\}$, and the singleton formula give $\sum_{y\in P}f(y)=\sum_{y\in D}f(y)=f(x)+f(x')$.

Step 3. (Exchanging a sum over a finite set with a numerical sum.) Let $N\in\mathbb{N}$, let $P$ be a nonempty finite set, and let $g(k,p)\in\mathbb{C}$ be given for $k\in[N]$ and $p\in P$. We claim

The set $[N]$ is nonempty and finite and numerical sums over it agree with sums over the index set $[N]$, by claim 1 of Properties of a Sum over a Finite Index Set. By Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §pairs with $A=[N]$ and $B(k)=P$ for every $k$, the set of pairs being $[N]\times P$, the left side equals $\sum_{t\in[N]\times P}g(t)$, where $g(t)=g(k,p)$ for $t=(k,p)$. By claim 1 of Properties of a Sum over a Finite Index Set applied to each inner sum and Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §pairs with $A=P$ and $B(p)=[N]$, the right side equals $\sum_{t'\in P\times[N]}g(\theta(t'))$, where $\theta:P\times[N]\to[N]\times P$ is $\theta((p,k))=(k,p)$. The map $\theta$ is a bijection (its inverse is the analogous exchange of components, by Characteristic Property of the Ordered Pair), so claim 2 of Properties of a Sum over a Finite Index Set gives $\sum_{t'\in P\times[N]}g(\theta(t'))=\sum_{t\in[N]\times P}g(t)$, and the two sides agree.

Step 4. (Quadratic form of a rank-one kernel.) Let $G$ be a nonempty finite set, let $z,b:G\to\mathbb{C}$ be maps and put $s=\sum_{v\in G}z(v)\,b(v)$. We claim

and that $|s|^{2}$ is real and nonnegative. By Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §conjugate, $\overline{s}=\sum_{u\in G}\overline{z(u)}\,\overline{b(u)}$. By The Product of Two Sums over Finite Index Sets is a Sum over the Cartesian Product applied to the maps $u\mapsto\overline{z(u)}\,\overline{b(u)}$ and $v\mapsto z(v)b(v)$, the product $\overline{s}\,s$ is the sum on the left (after rearranging each term by commutativity), and $\overline{s}\,s=s\,\overline{s}=|s|^{2}$ by claim 3 of Properties of Complex Conjugation and Modulus. Finally $|s|$ is a nonnegative real number by Modulus of a Complex Number, so $|s|^{2}=|s|\,|s|$ is real and nonnegative by claim 5 of Elementary Arithmetic in an Ordered Field (multiply $0\le|s|$ by $|s|\ge0$).

Step 5. (Claim 1, sums of rank-one kernels.) Let $K(u,v)=\sum_{k=1}^{N}\overline{b_{k}(u)}\,b_{k}(v)$. For $u,v\in F$, claim 4 of Properties of Finite Sums gives $\overline{K(u,v)}=\sum_{k=1}^{N}b_{k}(u)\,\overline{b_{k}(v)}$, which equals $K(v,u)$ by commutativity of multiplication. Let $z:F\to\mathbb{C}$. For each $p\in F\times F$, claim 3 of Properties of Finite Sums gives $\overline{z(p_{1})}z(p_{2})K(p)=\sum_{k=1}^{N}g(k,p)$ with $g(k,p)=\overline{z(p_{1})}\,z(p_{2})\,\overline{b_{k}(p_{1})}\,b_{k}(p_{2})$. By Step 3 and then Step 4 (with $G=F$ and $b=b_{k}$),

a finite sum of nonnegative real numbers, hence real and nonnegative by Step 1. So $K$ is a positive semidefinite kernel on $F$.

Step 6. (Iterated form and point evaluations.) Let $G$ be a nonempty finite set and $K:G\times G\to\mathbb{C}$ a map. By Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §pairs with $A=G$ and $B(u)=G$ for every $u$ (the set of pairs being $G\times G$), and by claim 4 of Properties of a Sum over a Finite Index Set to take $\overline{z(u)}$ out of the inner sum,

(a) Let $u_{0}\in G$, $\alpha\in\mathbb{C}$, and let $z(u_{0})=\alpha$ and $z(u)=0$ for $u\ne u_{0}$. By Step 2(a) the inner sum is $\alpha K(u,u_{0})$ and then $Q_{K}(z)=\overline{\alpha}\,\alpha\,K(u_{0},u_{0})$. With $\alpha=1$ this gives $Q_{K}(z)=K(u_{0},u_{0})$; hence if $K$ is a positive semidefinite kernel, then $K(u_{0},u_{0})$ is real and nonnegative for every $u_{0}\in G$. (b) Let $u_{0},v_{0}\in G$ with $u_{0}\ne v_{0}$, let $\alpha,\beta\in\mathbb{C}$, and let $z(u_{0})=\alpha$, $z(v_{0})=\beta$ and $z(u)=0$ for $u\notin\{u_{0},v_{0}\}$. By Step 2(b), applied to the inner sums and then to the outer sum,

Step 7. (Restriction.) Let $K$ be a positive semidefinite kernel on a nonempty finite set $G$, and let $G'\subseteq G$ be nonempty. Then $G'$ is finite by claim 3 of Basic Properties of Finite Sets, and the restriction $K'$ of $K$ to $G'\times G'$ is a positive semidefinite kernel on $G'$. Indeed, $K'(v,u)=\overline{K'(u,v)}$ is inherited from $K$. Given $z':G'\to\mathbb{C}$, let $z:G\to\mathbb{C}$ agree with $z'$ on $G'$ and vanish on $G\setminus G'$. If $p\in G\times G$ is not in $G'\times G'$, then $z(p_{1})=0$ or $z(p_{2})=0$, so the term $\overline{z(p_{1})}z(p_{2})K(p)$ is $0$. As $G'\times G'$ is a nonempty subset of $G\times G$, the second part of Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §vanishing gives $Q_{K}(z)=\sum_{p\in G'\times G'}\overline{z'(p_{1})}\,z'(p_{2})\,K'(p)=Q_{K'}(z')$, which is therefore real and nonnegative.

Step 8. (Splitting off one point.) Let $K$ be a positive semidefinite kernel on a nonempty finite set $G$ and let $u_{0}\in G$. We show that there is a map $b:G\to\mathbb{C}$ such that $K'(u,v)=K(u,v)-\overline{b(u)}\,b(v)$ defines a positive semidefinite kernel on $G$ with $K'(u_{0},v)=K'(v,u_{0})=0$ for every $v\in G$. By Step 6(a), $c=K(u_{0},u_{0})$ is real and $0\le c$.

Case $c=0$. Take $b=0$, so $K'=K$; it suffices to show $K(u_{0},v)=0$ for every $v\in G$, because then $K(v,u_{0})=\overline{K(u_{0},v)}=0$ as well. For $v=u_{0}$ this is $c=0$. Let $v\ne u_{0}$, put $a=K(u_{0},v)$ and $e=K(v,v)$, which is real by Step 6(a), and suppose $a\ne0$. Then $|a|\ne0$ by claim 3 of Properties of Complex Conjugation and Modulus, so the real number $|a|^{2}=a\overline{a}$ is nonzero, and so is $2|a|^{2}$ since $2\ne0$ by claim 8 of Elementary Order Arithmetic in an Ordered Field. Let $t=(e+1)(2|a|^{2})^{-1}$, a real number, and apply Step 6(b) with $v_{0}=v$, $\alpha=-ta$ and $\beta=1$. Since $K(v,u_{0})=\overline{a}$ and $\overline{\alpha}=-t\overline{a}$,

But $0\le Q_{K}(z)$ by Positive Semidefinite Kernel on a Finite Set §kernel, while $-1<0$ by claims 6 and 4 of Elementary Order Arithmetic in an Ordered Field; this contradicts the antisymmetry of the order. Hence $a=0$.

Case $c\ne0$. Let $r$ be the nonnegative real number with $r^{2}=c$, given by Existence and Uniqueness of the Nonnegative Square Root; $r\ne0$ since $0\cdot0=0\ne c$, and $r^{-1}$ is real by claim 1 of Canonical Form and Arithmetic of Complex Numbers. Define $b(v)=r^{-1}K(u_{0},v)$ for $v\in G$. Then $b(u_{0})=r^{-1}rr=r$, which is real, and for $u\in G$ we have $\overline{b(u)}=r^{-1}\overline{K(u_{0},u)}=r^{-1}K(u,u_{0})$ by the Hermitian symmetry of $K$. Hence $K'(u_{0},v)=K(u_{0},v)-r\,r^{-1}K(u_{0},v)=0$ and $K'(u,u_{0})=K(u,u_{0})-r^{-1}K(u,u_{0})\,r=0$ for all $u,v\in G$. The map $K'$ is Hermitian: $K'(v,u)=\overline{K(u,v)}-\overline{\overline{b(u)}\,b(v)}=\overline{K'(u,v)}$. Now let $z:G\to\mathbb{C}$, put $s=\sum_{v\in G}z(v)b(v)$, and define $z':G\to\mathbb{C}$ by $z'(u_{0})=z(u_{0})-r^{-1}s$ and $z'(v)=z(v)$ for $v\ne u_{0}$. By claim 3 of Properties of a Sum over a Finite Index Set and Step 2(a) (for the map equal to $-r^{-1}s\,b(u_{0})$ at $u_{0}$ and to $0$ elsewhere),

Since $K(p)=K'(p)+\overline{b(p_{1})}\,b(p_{2})$ for every $p\in G\times G$, claim 3 of Properties of a Sum over a Finite Index Set and Step 4 (with $z'$ in place of $z$) give $Q_{K}(z')=Q_{K'}(z')+|0|^{2}=Q_{K'}(z')$. Finally, for $p\in G\times G$ with $p_{1}\ne u_{0}$ and $p_{2}\ne u_{0}$ we have $z'(p_{1})=z(p_{1})$ and $z'(p_{2})=z(p_{2})$, while for every other $p$ we have $K'(p)=0$; so the sums $Q_{K'}(z')$ and $Q_{K'}(z)$ agree term by term. Therefore $Q_{K'}(z)=Q_{K}(z')$, which is real and nonnegative. So $K'$ is a positive semidefinite kernel on $G$.

Step 9. (Claim 2, rank-one decomposition.) Let $A$ be the set of those $N\in\mathbb{N}$ such that for every set $G$ having $N$ elements and every positive semidefinite kernel $L$ on $G$ there are maps $b_{1},\dots,b_{N}:G\to\mathbb{C}$ with $L(u,v)=\sum_{k=1}^{N}\overline{b_{k}(u)}\,b_{k}(v)$ for all $u,v\in G$. (A set having $N$ elements is finite by Finite Set and nonempty, being the image of the nonempty set $[N]$, claim 1 of Basic Properties of Initial Segments of the Natural Numbers.) We verify the two hypotheses of Principle of Induction for the Natural Numbers for $A$.

$1\in A$: let $G$ have $1$ element, with bijection $\varphi:[1]\to G$. Since $[1]=\{1\}$ (claim 2 of Basic Properties of Initial Segments of the Natural Numbers), $G=\{g\}$ with $g=\varphi(1)$. Let $L$ be a positive semidefinite kernel on $G$. By Step 6(a), $L(g,g)$ is real and nonnegative; let $r$ be its nonnegative square root (Existence and Uniqueness of the Nonnegative Square Root) and $b_{1}(g)=r$. Then $\sum_{k=1}^{1}\overline{b_{k}(g)}\,b_{k}(g)=\overline{r}\,r=r^{2}=L(g,g)$, by claim 1 of Properties of Finite Sums; as $g$ is the only element of $G$, this is the required identity.

$N\in A$ implies $S(N)\in A$: let $G$ have $S(N)$ elements and let $L$ be a positive semidefinite kernel on $G$. By claim 2 of Peeling an Element off a Finite Set, and Unions of Finite Sets there are $G'\subseteq G$ with $N$ elements and $g_{0}\in G$ with $g_{0}\notin G'$ and $G=G'\cup\{g_{0}\}$. Step 8 with $u_{0}=g_{0}$ gives $b:G\to\mathbb{C}$ such that $L'(u,v)=L(u,v)-\overline{b(u)}b(v)$ is a positive semidefinite kernel on $G$ vanishing whenever $u=g_{0}$ or $v=g_{0}$. The set $G'$ is nonempty, so by Step 7 the restriction of $L'$ to $G'\times G'$ is a positive semidefinite kernel on $G'$, and as $N\in A$ there are maps $b'_{1},\dots,b'_{N}:G'\to\mathbb{C}$ with $L'(u,v)=\sum_{k=1}^{N}\overline{b'_{k}(u)}\,b'_{k}(v)$ for $u,v\in G'$. Since $[S(N)]=[N]\cup\{S(N)\}$ with $S(N)\notin[N]$ (claim 3 of Basic Properties of Initial Segments of the Natural Numbers), we may define $b_{k}:G\to\mathbb{C}$ for $k\in[S(N)]$ by $b_{k}=b'_{k}$ on $G'$ and $b_{k}(g_{0})=0$ for $k\in[N]$, and $b_{S(N)}=b$. Let $u,v\in G$. By claim 1 of Properties of Finite Sums,

If $u,v\in G'$, the sum over $k\in[N]$ is $L'(u,v)$. Otherwise $u=g_{0}$ or $v=g_{0}$; then every term of the sum over $k\in[N]$ is $0$, so the sum is $0$ (write each term as $0\cdot1$ and use claim 3 of Properties of Finite Sums with $\lambda=0$), and $L'(u,v)=0$ as well. In both cases the displayed sum equals $L'(u,v)+\overline{b(u)}b(v)=L(u,v)$. Hence $S(N)\in A$.

By Principle of Induction for the Natural Numbers, $A=\mathbb{N}$. Applied to the given $N$, the set $F$ and the kernel $K$, this is claim 2.

Step 10. (Claim 3, Schur product.) Let $K$ and $L$ be positive semidefinite kernels on $F$ and $M(u,v)=K(u,v)L(u,v)$. Since $F$ is nonempty and finite, it has $n$ elements for some $n\in\mathbb{N}$ (Finite Set), so by Step 9 there are $b_{1},\dots,b_{n}:F\to\mathbb{C}$ with $L(u,v)=\sum_{k=1}^{n}\overline{b_{k}(u)}\,b_{k}(v)$ for all $u,v\in F$. First, $M(v,u)=\overline{K(u,v)}\;\overline{L(u,v)}=\overline{M(u,v)}$. Next let $z:F\to\mathbb{C}$ and put $z_{k}(u)=z(u)\,b_{k}(u)$ for $k\in[n]$. For each $p\in F\times F$, claim 3 of Properties of Finite Sums gives

so by Step 3, $Q_{M}(z)=\sum_{k=1}^{n}Q_{K}(z_{k})$. Each $Q_{K}(z_{k})$ is real and nonnegative because $K$ is positive semidefinite, so $Q_{M}(z)$ is real and nonnegative by Step 1. Hence $M$ is a positive semidefinite kernel on $F$.