Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/iii/paper-339/2/a/solution

Let be the all-ones matrix. Every feasible block matrix in the first formulation has , because its principal submatrix on indices is and is a positive semidefinite matrix. In particular, .
By the Schur complement,
Set . Then , , and on every edge. Conversely, for a feasible in the second formulation, its nonnegative diagonal gives , and has , on edges, and .
Both transformations preserve the objective . Hence the two semidefinite programs defining the complement theta number have the same feasible objective values and the same minimum.

New to topics? Read the docs here!