Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/iii/paper-339/2/a/solution
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 339 2 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-05
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!