see [@Cit:tsp_asymm]). The ordering $ \sigma $ can be represented as a unique permutation matrix $ P $. Note, however, that due to the underlying cyclic symmetry, multiple orderings – corresponding to different permutation matrices – have the same cost.

There are several equivalent ways to define the cost function of the TSP. The authors restrict themselves to the trace[^2] formulation. Let $ \mathcal{P}_n $ denote the set of all $ n \times n $ permutation matrices, then the TSP can be written as a combinatorial optimization problem of the form $$\label{eq:TSPCost}
    \min_{P \in \mathcal{P}_n} \mbox{tr} \left( A^T P^T B P \right),$$ where $ A = D $ and $ B = T $. Here, $ T $ is defined to be the adjacency matrix of the cycle graph of length $ n $.

One uses the undirected cycle graph adjacency matrix for symmetric TSPs and the one corresponding to the directed cycle graphs for asymmetric TSPs. The matrices are defined as, $$\label{eq:tmatrix}
    T_\text{dir} = \begin{pmatrix}
        0 & 1 &   &  &   \\
          & 0 & 1 &  &   \\
          &   & \ddots & \ddots &  \\
          &   &   & 0  & 1 \\
        1 &   &   &  & 0
    