# Rows and columns permutation of SDP variable $X\in\mathbf{S}^n$

We know the standard form of SDP is

\begin{equation}\label{eq:ex_m} \begin{aligned} & {\underset{X}{\min}} & & \mbox{tr}(CX)\\ & \text{s.t.} & & \mbox{tr}(A_iX)=b_i, \ \ i=1,\cdots,p \\ & & & X\succeq0 \end{aligned} \end{equation}

Now, if I consider the following

\begin{equation} \begin{aligned} & {\underset{X}{\min}} & & \mbox{tr}(CX)\\ & \text{s.t.} & & \mbox{tr}(A_iX)=b_i, \ \ i=1,\cdots,p \\ & & & EXE\succeq0, \end{aligned} \end{equation}

where $$E$$ is a permutation matrix which permutes row and column. For example, permute row $$i$$ and row $$j$$, column $$i$$ and column $$j$$ with $$i < j$$. So $$E$$ is a orthogonal matrix. Note that, in this case, $$E = E^{-1} = E^T$$

I roughly ran a few examples, it seems that we can get the same cost. Not quite sure.

Q: Will we get the same cost and solution from both SDPs?

That is because $$EXE = E^{-1}XE$$, which is similar to $$X$$. Therefore their eigenvalues are identical (see https://en.wikipedia.org/wiki/Matrix_similarity#Properties), so the constraints $$X \succeq 0$$ and $$EXE \succeq 0$$ are equivalent, in exact arithmetic.
• $X \succeq 0$ means that $X$ is symmetric, and has all eigenvalues nonnegative. Because $X$ has the same eigenvalues as $EXE$, and $EXE$ is symmetric, that is the same as requiring all eigenvalues of $EXE$ to be nonnegative, which is what the constraint $EXE \succeq 0$ does. May 3, 2019 at 0:02