# Reducing the Hamiltonian cycle to the travelling salesman problem and self loops

If this is my adjacency matrix for the hamiltonian cycle: $$\begin{pmatrix}0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\\ 1&0&1&0\end{pmatrix}$$ Then a reduction algorithm to reduce this to a TSP problem is to introduce 1 anywhere an edge is missing and let pre-existing edges have a cost of zero (according to this), applying this yields: $$\begin{pmatrix}1&0&1&0\\ 0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\end{pmatrix}$$ Now I see that I have also introduced weighted-loops to my undirected graph, would asking whether this has a zero-cost salesman tour be equivalent to asking whether the unreduced version has a hamiltonian cycle, or should I maybe have something else on the diagonal of the reduced matrix?

Suppose your original graph $$G$$ has a Hamiltonian cycle $$C$$. Then the cost of the tour induced by $$C$$ in the new graph $$G'$$ you defined is indeed $$0$$ and conversely, any TSP tour of cost $$0$$ can only use edges of cost $$0$$ as you did not introduce any edges with a negative cost.
Adding the loops does not change this, so the reduction works out if we are willing to allow non-simple graphs which isn't done usually as the definition of the TSP asks for a tour visiting each vertex exactly once, i.e. no valid tour would include loop edges anyways. Given this, we also see that you can remove the loop edges in $$G'$$ to make it a simple graph to obtain an equally valid reduction. From a technical standpoint this doesn't make much of a difference but since people like simple graphs, I would personally prefer the reduction yielding a simple graph.