I'm trying to calculate $sdp(C_5) =\max\{\frac{1}{2}\sum_{i=1}^4(1-X_{i,i+1}) \mid X \text{ PSD}, X_{ii}=1 \forall i\in [5]\}$ analytically.
I've already bounded it:
- As $\begin{pmatrix}1 & -\frac{1}{2} & 0&0&-\frac{1}{2}\\ -\frac{1}{2}&1 & -\frac{1}{2}&0&0\\ 0&-\frac{1}{2}&1 & -\frac{1}{2}&0\\ 0&0&-\frac{1}{2}&1 & -\frac{1}{2}\\ -\frac{1}{2}&0&0 & -\frac{1}{2}&1\\ \end{pmatrix}$ is feasible, we know $sdp(C_5) \geq \frac{15}{4}$.
- Now, every principal submatrix of $X$ is necesairly also SDP, in order for $X$ to be SDP, so we need $\begin{pmatrix}1&x\\ x&1\end{pmatrix}$ to be SDP also. we know the eigenvalues are of the form $\lambda = 1 \pm \sqrt{x^2}$, so we know $-1\leq x\leq 1$ and therefore $sdp(C_5) \leq 5$.
Where do I go from here. I was thinking something with the schur complement, but that would result in even more unknowns and long, useless equations.
Is it even possible to calculate this analytically? Because i've tried finding the minimal $y$ for which $\begin{pmatrix}1 & -1 & z\\ -1 & 1&y\\z&y&1\end{pmatrix}$ is PSD, without any clear luck.
Who is my nerdy hero that can save me from the dungeon of unknowingness?
Consider $$Z = \begin{bmatrix} 1 & -1 & 1 & -1 & 1 \\ -1 & 1 & -1 & 1 & -1 \\ 1 & -1 & 1 & -1 & 1 \\ -1 & 1 & -1 & 1 & -1 \\ 1 & -1 & 1 & -1 & 1 \end{bmatrix} \succeq 0.$$ To see that $Z$ is PSD, note that it is rank $1$. Also note that $Z$ is optimal for your problem. This is because your problem is minimizing the sum of elements on the first off diagonal. Matrix $Z$ has every such element as $-1$. This is optimal, since every such element is bounded by the unit diagonal constraints, i.e., $$\begin{bmatrix} 1 & x \\ x & 1 \end{bmatrix} \succeq 0 \iff |x| \leq 1 \Longrightarrow x \geq -1.$$