1
$\begingroup$

I'm trying to calculate $sdp(C_5) =\max\{\frac{1}{2}\sum_{i=1}^5(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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.