\end{pmatrix} \; \text{ or } \;
    T_\text{undir} = \begin{pmatrix}
        0 & 1 &   &  & 1 \\
        1 & 0 & 1 &  &   \\
          & \ddots  & \ddots & \ddots &  \\
          &   & 1 & 0  & 1 \\
        1 &   &   & 1 & 0
    \end{pmatrix}.$$ The work in [@Cit:TSP_sahai] focuses on the undirected version of the TSP. By relaxing the TSP problem to the manifold of orthogonal matrices (since permutation matrices are orthogonal matrices restricted to $0$ or $1$ entries), one can use the two sided Procrustes problem to solve the problem exactly, as outlined in the theorem below.

Given two symmetric matrices $ A $ and $ B $, whose eigenvalues are distinct, let $ {A = V_A \Lambda_A V_A^T} $ and $ B = V_B \Lambda_B V_B^T $ be eigendecompositions, with $ \Lambda_A = \diag\left(\lambda_{A}^{(1)}, \dots, \lambda_{A}^{(n)}\right) $, $ \Lambda_B = \diag\left(\lambda_{B}^{(1)}, \dots, \lambda_{B}^{(n)}\right) $, and $ \lambda_{A}^{(1)} \geq \dots \geq \lambda_{A}^{(n)} $ as well as $ \lambda_{B}^{(1)} \geq \dots \geq \lambda_{B}^{(n)} $. Then every orthogonal matrix $ P^* $ which minimizes $$\min_{P \in \mathcal{O}_n} || A - P^T B P ||_F
\label{eq:RelTSPCost}$$ has the form $$P^* = V_B S V_A^T,$$ where $ S 