= Solution
Let $J=\mathbf1\mathbf1^T$ be the <all-ones matrix>. Every feasible block <matrix> in the first formulation has $t\geq1$, because its principal $2\times2$ <submatrix> on indices $0,i$ is $\begin{pmatrix}t&1\\1&1\end{pmatrix}$ and is a <positive semidefinite matrix>. In particular, $t>0$.
By the <Schur complement>,
$$
\begin{pmatrix}t&\mathbf1^T\\\mathbf1&Z\end{pmatrix}\succeq0
\quad\Longleftrightarrow\quad
Z-\frac1tJ\succeq0.
$$
Set $U=tZ-J$. Then $U\succeq0$, $U_{ii}=t-1$, and $U_{ij}=-1$ on every <edge>. Conversely, for a feasible $(t,U)$ in the second formulation, its nonnegative diagonal gives $t\geq1$, and $Z=(U+J)/t$ has $Z_{ii}=1$, $Z_{ij}=0$ on <edges>, and $Z-J/t=U/t\succeq0$.
Both transformations preserve the objective $t$. Hence the two <semidefinite programs> defining the <complement theta number> have the same feasible objective values and the same minimum.
Back to article page
