= Solution
Use the <spectral theorem for real symmetric matrices> to write $X^*=V\Lambda V^T$, with $V$ orthogonal and $\Lambda$ diagonal and nonnegative. For any sign vector, $\xi_j^2=1$, so
$$
\|\widehat x(\xi)\|_2^2=\xi^T\Lambda\xi=\sum_j\lambda_j=\operatorname{tr}X^*.
$$
This is an exact identity for every sign choice. Put $M(\xi)=\max_i|a_i^T\widehat x(\xi)|$. When $M>0$, the <Rademacher rounding for a semidefinite relaxation> gives
$$
|a_i^Tx(\xi)|=\frac{|a_i^T\widehat x(\xi)|}{M}\le1,\qquad
\boxed{\|x(\xi)\|_2^2=\frac{\operatorname{tr}X^*}{M(\xi)^2}.}
$$
Hence $x(\xi)$ is feasible. In the finite spanning case from part (a), $\operatorname{tr}X^*>0$ makes $\widehat x\ne0$, and the spanning condition then gives $M>0$. If a nonzero $\widehat x$ instead had $M=0$, it would be an unbounded feasible direction rather than a vector to divide by zero.
Back to article page
