Independent-entry coordinates, convexity and Lipschitz constants

Let $n\ge 1$ be an integer and $N=\left(\genfrac{}{}{0px}{}{n}{2}\right)$. Label the coordinates of $x\in {\mathbb{R}}^N$ by pairs $1\le i<j\le n$. Let ${\mathrm{Sym}}_n$ be the real symmetric $n\times n$ matrices, and define $T:{\mathbb{R}}^N\to {\mathrm{Sym}}_n$ by $T(x{)}_{ij}=T(x{)}_{ji}=x_{ij}$ for $i<j$ and $T(x{)}_{ii}=0$.

Use the Euclidean coordinate norm $\mathrm{\parallel }x{\mathrm{\parallel }}_2=({\sum }_{i<j}{x}_{ij}^2{)}^{1\mathrm{/}2}$ and distance $\mathrm{\parallel }x-y{\mathrm{\parallel }}_2$. For a real matrix $A$, its Frobenius norm is $\mathrm{\parallel }A{\mathrm{\parallel }}_F=({\sum }_{i,j}{A}_{ij}^2{)}^{1\mathrm{/}2}$, and its operator norm is $\mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}={\max }_{\mathrm{\parallel }v{\mathrm{\parallel }}_2=1}\mathrm{\parallel }Av{\mathrm{\parallel }}_2$. These conventions give $\mathrm{\parallel }T(x)-T(y){\mathrm{\parallel }}_F^2=2\mathrm{\parallel }x-y{\mathrm{\parallel }}_2^2$.

For a fixed real $n\times n$ matrix $C$, define $f_C(x)=\mathrm{\parallel }T(x)-C{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}$. A function $f$ is convex if $f((1-t)x+ty)\le (1-t)f(x)+tf(y)$ for $0\le t\le 1$, and is $L$-Lipschitz in this coordinate metric if $\mathrm{\mid }f(x)-f(y)\mathrm{\mid }\le L\mathrm{\parallel }x-y{\mathrm{\parallel }}_2$ for all $x,y$. The function $f_C$ is convex and has least Lipschitz constant $L_n=\sqrt{2(n-1)\mathrm{/}n}$; for $n=1$ this constant is zero. Restrictions to coordinate boxes retain this upper bound, although their least constant can be smaller.

Symmetric matrices are Euclidean under the Frobenius norm

The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖

Convex and strictly convex functions on Euclidean convex sets

Lipschitz map, α-Hölder map for rational 0 < α ≤ 1, and contraction

The coordinate formulas determine a unique linear map $T$. The Frobenius identity follows by counting each off-diagonal entry twice, equivalently by the symmetric-vectorization isometry Symmetric matrices are Euclidean under the Frobenius norm. The operator norm is defined by The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖; the Euclidean triangle inequality and homogeneity imply its triangle inequality and homogeneity. Thus the norm of an affine matrix-valued map is convex, and the reverse triangle inequality gives $\mathrm{\mid }{f}_C(x)-f_C(y)\mathrm{\mid }\le \mathrm{\parallel }T(x-y){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}$.

For $z\in {\mathbb{R}}^N$, the matrix $T(z)$ is self-adjoint by In an orthonormal basis, self-adjoint means conjugate-transpose symmetry and normal means commuting with the conjugate transpose. The real spectral theorem Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis gives a unit eigenvector $v$ whose eigenvalue has absolute value $\mathrm{\parallel }T(z){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}$: expand unit vectors in an orthonormal eigenbasis to obtain this norm formula. By Cauchy–Schwarz Cauchy-Schwarz |⟨ x,y⟩| ≤ ‖ x‖₂‖ y‖₂ with its equality case, the triangle inequality for ‖·‖₂, the parallelogram law and polarisation, $\mathrm{\mid }{v}^{T}T(z)v\mathrm{\mid }\le \mathrm{\parallel }z{\mathrm{\parallel }}_2(4{\sum }_{i<j}{v}_i^2{v}_j^2{)}^{1\mathrm{/}2}$. Since ${\sum }_i{v}_i^2=1$, the squared second factor is $2(1-{\sum }_i{v}_i^4)\le 2(n-1)\mathrm{/}n$; the last inequality is Cauchy–Schwarz applied to $(v_i^2)$ and the all-ones vector. Therefore $\mathrm{\parallel }T(z){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le L_n\mathrm{\parallel }z{\mathrm{\parallel }}_2$, establishing the stated Lipschitz bound.

For $n\ge 2$, take $z_{ij}=1$ for every $i<j$. Then $T(z)=J-I$, where $J$ is the all-ones matrix. It has eigenvalue $n-1$ on the all-ones vector and eigenvalue $-1$ on its orthogonal complement, so $\mathrm{\parallel }T(z){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\mathrm{/}\mathrm{\parallel }z{\mathrm{\parallel }}_2=(n-1)\mathrm{/}\sqrt{n(n-1)\mathrm{/}2}=L_n$. For any fixed $C$, the reverse triangle inequality gives $f_C(tz)\ge t\mathrm{\parallel }T(z){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}-\mathrm{\parallel }C{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}$ for $t>0$, while $f_C(0)=\mathrm{\parallel }C{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}$. Dividing $f_C(tz)-f_C(0)$ by $t\mathrm{\parallel }z{\mathrm{\parallel }}_2$ and letting $t\to \mathrm{\infty }$ shows that no smaller global Lipschitz constant works. For $n=1$, the coordinate space has one point and $T=0$, so the least constant is zero.