Skip to main content
2 of 2
typos

Take the SDP program

\begin{align*} \min~& x_3\\ s.t.~& X = \begin{bmatrix} x_1 & x_2 & 0 & 0 \\ x_2 & 0 & 0 & 0 \\ 0 & 0 & x_2 & 0 \\ 0 & 0 & 0 & x_3-2 \\ \end{bmatrix}\succeq \mathbf{0}\\ &x_1,~x_2,~x_3\in\mathbf{R} \end{align*} Its dual can be written as follows (see below why). \begin{align*} \max~& 2z_{44}\\ s.t.~& Z= \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & a^2+\Delta^2& 0 & a \\ 0 & 0 & 0 & 0 \\ 0 & a & 0 & 1 \\ \end{bmatrix}\\ &Z\succeq 0 \end{align*}

Now notice that any feasible solution $\mathbf{x}$ of the primal satisfies $x_2=0$ because of the zero situated at position $(2,2)$; recall that any SDP matrix $A$ such that $A_{ii}=0$ has only zeros on row and column $i$.

Now check that $X$ and $Z$ share the eigenvector $ \left[\begin{smallmatrix} 0 & 0 & 1 & 0 \\ \end{smallmatrix} \right]^\top$ with eigenvalue 0, which actually answers the question. No linear combination of the rows of $X$ and $Z$ that can be equal to this eigenvector, i.e., the rows of $X$ and $Z$ do not cover the whole space $\implies rank(X)+rank(Z)<n$.

The only detail that remains to be filled is to show that the above expression of the dual is correct. Any feasible $Z$ satisfies $z_{11}=0$ because the coefficient of $x_1$ is zero in the primal objective function. This forces row 1 and column 1 of $Z$ to have only zeros. The dual constraint corresponding to $x_2$ is $2z_{12}+z_{33}=0$; since $z_{12}=0$, we have $z_{13}=0$. The dual constraint corresponding to $x_3$ imposes $z_4=1$. There is no constraint on $z_{24}=a$; $z_{22}$ needs to be greater than or equal to $a^2$ so as to have a non-negative principal minor corresponding to rows/columns 2 and 4; we can write $z_{22}=a^2+\Delta^2$. Finally, both programs have objective value 2.