Past exam of the mathematics course of the University of Cambridge / 2018 / iii / Paper 339 / 2 / b / Solution

Use the spectral theorem for real symmetric matrices to write $X^{\ast }=V\Lambda V^T$, with $V$ orthogonal and $\Lambda$ diagonal and nonnegative. For any sign vector, ${\xi }_j^2=1$, soThis is an exact identity for every sign choice. Put $M(\xi )={\max }_i|a_i^T\hat{x}(\xi )|$. When $M>0$, the Rademacher rounding for a semidefinite relaxation givesHence $x(\xi )$ is feasible. In the finite spanning case from part (a), $\mathrm{tr}{X}^{\ast }>0$ makes $\hat{x}\ne 0$, and the spanning condition then gives $M>0$. If a nonzero $\hat{x}$ instead had $M=0$, it would be an unbounded feasible direction rather than a vector to divide by zero.