Column-overlap formula for the zero-sum ℓ1 coefficient

Let $z\in H$ with $\mathrm{\parallel }z{\mathrm{\parallel }}_1=1$. Write $z=z^{+}-z^{-}$ coordinatewise, where $z_i^{+}=\max (z_i,0)$ and $z_i^{-}=\max (-z_i,0)$. Since ${\sum }_i{z}_i=0$, the positive and negative masses agree, and their sum is one; hence ${\sum }_i{z}_i^{+}={\sum }_i{z}_i^{-}=1\mathrm{/}2$. Therefore $u=2z^{+}$ and $v=2z^{-}$ are probability vectors and $Pz=(Pu-Pv)\mathrm{/}2$.

We have $Pu={\sum }_j{u}_j{p}_j$ and $Pv={\sum }_k{v}_k{p}_k$. Thus $Pz=\frac{1}{2}{\sum }_{j,k}{u}_j{v}_k(p_j-p_k)$. The coefficients $u_j{v}_k$ are nonnegative and sum to one, so the triangle inequality gives $\mathrm{\parallel }Pz{\mathrm{\parallel }}_1\le \frac{1}{2}{\max }_{j,k}\mathrm{\parallel }{p}_j-p_k{\mathrm{\parallel }}_1$. Taking the supremum over such $z$ proves the upper bound.

If $n\ge 2$ and the maximum is positive, a maximizing pair has $j\mathrm{\ne }k$; if the maximum is zero, any distinct pair maximizes it. Choose such a distinct pair and set $z=(e_j-e_k)\mathrm{/}2$. Then $z\in H$, $\mathrm{\parallel }z{\mathrm{\parallel }}_1=1$, and $Pz=(p_j-p_k)\mathrm{/}2$, so the supremum is at least $\frac{1}{2}{\max }_{j,k}\mathrm{\parallel }{p}_j-p_k{\mathrm{\parallel }}_1$. If $n=1$, both sides are zero by definition. This proves the first equality.

For two nonnegative probability columns $a,b$, $\mathrm{\mid }{a}_i-b_i\mathrm{\mid }=a_i+b_i-2\min (a_i,b_i)$. Summing gives $\frac{1}{2}\mathrm{\parallel }a-b{\mathrm{\parallel }}_1=1-{\sum }_i\min (a_i,b_i)$. Apply this to every pair of columns; taking the maximum of the left side is one minus the minimum overlap on the right.

If $n\ge 2$, [F2] bounds every norm in the defining supremum by one, so $0\le \delta (P)\le 1$; if $n=1$, $\delta (P)=0$ by definition. For nonzero $z\in H$, apply the definition of $\delta (P)$ to $z\mathrm{/}\mathrm{\parallel }z{\mathrm{\parallel }}_1$ and use homogeneity; for $z=0$ the inequality is immediate. Thus $\mathrm{\parallel }Pz{\mathrm{\parallel }}_1\le \delta (P)\mathrm{\parallel }z{\mathrm{\parallel }}_1$ on all of $H$.