By a theorem of Goldman and Tucker it is known that if a linear program (LP) has a finite valued optimal solution, then there is an optimal primal/dual pair $(x,z)$ satisfying not only *complementary slackness* (i.e. $x\_iz\_i=0$), but also *strict complementary slackness* (i.e. *exactly one* of $x\_i$ and $z\_i$ vanishs). 


It is known that this property does not carry over to semidefinite programs (SDP). This means, if $(X,Z)$ is an optimal primal/dual pair of an SDP, where $X,Z\in\Bbb R^{n\times n}$ are symmetric positive semi-definite matrices, then we have complementarity (i.e. $XZ=0$), but in general no strict complementarity $\def\rank{\mathrm{rank}}\rank(X)+\rank(Z)=n$.


Now, I am especially interested in **SDPs with finite valued optimal solutions and zero duality gap**. Is there anything more we can say about strict complementary slackness in the case of strong duality? I actually have never seen an example where it fails, i.e. an example with above properties where all optimal primal/dual pairs $(X,Z)$ lack strict complementarity.


Most of my knowledge about strict complementarity comes from [1] where it is shown that it is a generic property (holds for almost all SDPs in a precise sense). Besides this, strict complementarity was mostly assumed to prove other properties.


[1] [F. Alizadeh, J.A. Haeberly, M.L. Overton: Complementarity and nondegeneracy in semidefintie programming](https://cs.nyu.edu/media/publications/TR1995-681.pdf)



Strict complementary slackness for semidefinite programs with strong duality
Studying certain semidefinite programs arising in spectral graph theory, I discovered a semi-definite primal/dual pair satisfying strong duality but not strict complementarity.


Let $E=\{12,23,34\}$ (the edge set of the path graph $P\_3$) and $E^{ij}:=(\mathbf e\_i-\mathbf e\_j)^\top(\mathbf e\_i-\mathbf e\_j)$. We use the inner product $
\def\<{\langle}\def\>{\rangle}\<X,Y\>:=\mathrm{tr}(XY)$ on the space of symmetric matrices $\mathbf S^n$.


$$
\llap{\mathrm{(P)}\qquad}
\boxed{\begin{array}{rlr}
p^\*=\max & \sum\_{ij\in E} w\_{ij} \\
\mathrm{s.t.} & I-\sum\_{ij\in E} w\_{ij}E^{ij} \succeq0 \\
 & w\_{ij}\ge 0,\quad ij\in E
\end{array}}$$


$$
\llap{\mathrm{(D)}\qquad}
\boxed{\begin{array}{rlr}
d^\*=\min & \mathrm{tr}(X) \\
\mathrm{s.t.} & \<X,E^{ij}\>\ge 1,\quad ij\in E \\
 & X\succeq 0
\end{array}}$$


The common optimal value is $p^\*=d^\*=1$, obtained for


$$w\_{12}=w\_{34}=\frac12,\quad w\_{23}=0,$$


$$X=\frac14\begin{pmatrix}
\phantom+1 & -1 & \phantom+1 & -1 \\
-1 & \phantom+1 & -1 & \phantom+1 \\
\phantom+1 & -1 & \phantom+1 & -1 \\
-1 & \phantom+1 & -1 & \phantom+1
\end{pmatrix} 
= \frac14 (\phantom+1,-1,\phantom+1,-1)^\top(\phantom+1,-1,\phantom+1,-1).$$


Both are the unique solutions of their respective problem (this can easily be seen when interpreting $\mathrm{(D)}$ as an embedding problem, but I will leave this out here). As seen, the dual positive semi-definite matrix $X$ has rank $1$. However, the corresponding matrix


$$Z:=I-\sum\_{ij\in E} w\_{ij}E^{ij} = 
\frac12 \begin{pmatrix} 
1 & 1 & & \\
1 & 1 & & \\ 
 & & 1 & 1 \\
 & & 1 & 1
\end{pmatrix}$$


is of rank $2$. Hence $\mathrm{rank}(X)+\mathrm{rank}(Z)=3<4$ and strict complementarity is not satisfied.


