Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 339 / 2

Split the sign vector as $x=(p^T,q^T{)}^T$. Multiplication of the two off-diagonal blocks givesbecause the two terms are the same real scalar. The map $(p,q)\mapsto x$ is a bijection between the feasible sign choices. ThereforeThis is the symmetric lifting of bipartite binary quadratic optimization to binary quadratic optimization. The factor $1/2$ is necessary: otherwise the two blocks would double the objective. No positive semidefiniteness of $A$ is assumed; generally its off-diagonal structure makes its quadratic form indefinite.

Every feasible sign vector gives the rank-one matrix $X=x{x}^T$. It is a positive semidefinite matrix, since $u^{T}Xu=(u^{T}x{)}^2\ge 0$, and $X_{ii}=x_i^2=1$. The matrix trace identity givesThus all original feasible objectives appear among the relaxed ones, provingThe semidefinite relaxation of binary quadratic optimization drops the rank-one requirement and keeps the elliptope constraints.

An optimal relaxed matrix exists. The feasible set is nonempty, since it contains $I$, and closed. Its two-by-two principal minors give $|X_{ij}{|}^2\le X_{ii}{X}_{jj}=1$, so it is bounded and therefore compact. The linear objective attains its maximum. Also $\mathrm{tr}(AI)=0$ and hence $p_{\mathrm{SDP}}^{\ast }\ge 0$, including the zero-objective case.

Write a test vector as $(u,v)$ and put $s={\sum }_i{u}_i$, $t={\sum }_j{v}_j$. Its quadratic form against the block-constant matrix isSince $a\ge |b|$, both $a$ and $a-|b|$ are nonnegative, andEquivalently it isTherefore the bipartite block-constant positive semidefinite matrix satisfies $\boxed{\left(\begin{array}{cc}a{J}_{n,n}& b{J}_{n,m}\\ b{J}_{m,n}& a{J}_{m,m}\end{array}\right)⪰0}$.

For positive block sizes, the condition is also necessary: choose $s=t$ and $s=-t$ to obtain $a+b\ge 0$ and $a-b\ge 0$. Equality is allowed, and vectors whose sums vanish in both blocks lie in the kernel. Positive semidefiniteness, rather than positive definiteness, is the conclusion.

For each coefficient index $k\ge 0$, let $H_k$ have constant diagonal blocks $f_{k}J$ and cross blocks $g_{k}J$. The preceding block-constant argument gives $H_k⪰0$. Define the Hadamard powers $X^{\circ k}$, withThis is the constant entrywise power, including at zero entries; it is not the identity matrix. Repeated use of the Schur product theorem shows $X^{\circ k}⪰0$ for every $k\ge 0$.

Applying the Schur product theorem again makes every summand $H_k\circ X^{\circ k}$ positive semidefinite. The partial sums are positive semidefinite, and their entrywise limit is exactly $Y$. In finite dimension this is a matrix-norm limit; the positive semidefinite cone is closed. ConsequentlyEndpoint convergence follows from the stated expansions on the full interval: $f_k\ge 0$ and $\sum f_k=f(1)<\infty$, while $\sum |g_k|\le \sum f_k$. Thus the expansions converge absolutely at every matrix entry. This is coefficient-dominated entrywise positivity.

The coefficient condition must include index zero. We interpret the PDF's $\mathbb{N}$ accordingly. If it means only positive integers and no condition is imposed on $f_0,g_0$, the assertion is false: take $n=m=1$, $X=0$, $f=-1$ and $g=0$. All positive-index inequalities hold, but $Y=-I_2$.

Put $t=\log (1+\sqrt{2})=\mathrm{arsinh}(1)$, so $c_K=2t/\pi$. The power series coefficients of the hyperbolic sine preprocessing areThus $f_j=|g_j|$ for every $j\ge 0$, and the series converge on the full interval. Applying coefficient-dominated entrywise positivity gives $Y⪰0$.

Every diagonal entry belongs to one of the diagonal blocks and equals $f(X_{ii})=f(1)=\sinh t$. Because $e^t=1+\sqrt{2}$ and $e^{-t}=\sqrt{2}-1$, this is $(e^t-e^{-t})/2=1$. ThereforeThe matrix lies in the elliptope and admits a Gram matrix representation by unit vectors. This preprocessing is the Krivine rounding scheme; the equality of absolute coefficients is what preserves positive semidefiniteness even though the cross-block sine coefficients alternate in sign.

The Gram matrix representation and $Y_{ii}=1$ give $\Vert v_i{\Vert }_2=1$. For a standard Gaussian random vector $Z$, each $⟨v_i,Z⟩$ is a standard normal scalar, so the zero event has probability zero. Choose either sign convention at zero; the resulting vector is almost surely a feasible sign vector. Consequently $y^{T}Ay\le v^{\ast }$ almost surely.

The Gaussian sign-correlation identity givesThe last equality uses symmetry of the real matrices. HenceThe inverse sine is applied entrywise, not through spectral matrix functional calculus.

For completeness, the correlation coefficient identity has a geometric proof. If the angle between two unit vectors is $\theta$, the isotropic Gaussian random vector direction in their two-dimensional span gives opposite signs on angular sectors with probability $\theta /\pi$. Thus the sign product has expectation $1-2\theta /\pi =(2/\pi )\arcsin (\cos \theta )$. Parallel and antiparallel pairs give the endpoint values $1$ and $-1$ directly. This is Gaussian hyperplane rounding, and needs no independence between the rounded coordinates.

The Krivine rounding constant has $t=c_K\pi /2=\log (1+\sqrt{2})<\pi /2$. Since $|X_{ij}|\le 1$, the principal real inverse sine satisfieson every cross-block entry. The matrix $A$ has zero diagonal blocks, so those cross blocks are the only contributors to its Frobenius inner product with $\arcsin [Y]$. Explicitly,No analogous identity is needed for the diagonal blocks involving $\sinh$.

Combining with the preceding expectation formula and optimality of $X$ gives the bipartite sign rounding boundAt least one feasible rounded outcome attains at least this expectation. This is an expectation-based approximation guarantee for the specific bipartite sign problem; no claim is made that $c_K$ is the largest possible constant. The inequalities remain valid when the optimal objective is zero.