  We study a semidefinite programming relaxation of the traveling salesman
problem introduced by de Klerk, Pasechnik, and Sotirov [8] and show that their
relaxation has an unbounded integrality gap. In particular, we give a family of
instances such that the gap increases linearly with $n$. To obtain this result,
we search for feasible solutions within a highly structured class of matrices;
the problem of finding such solutions reduces to finding feasible solutions for
a related linear program, which we do analytically. The solutions we find imply
the unbounded integrality gap. Further, they imply several corollaries that
help us better understand the semidefinite program and its relationship to
other TSP relaxations. Using the same technique, we show that a more general
semidefinite program introduced by de Klerk, de Oliveira Filho, and Pasechnik
[7] for the $k$-cycle cover problem also has an unbounded integrality gap.
