On the Euclidean travelling salesman problem with a permuted Van der Veen matrix

We discuss the problem of recognizing permuted Van der Veen (VdV) matrices. It is well known that the TSP with a VdV matrix as distance matrix is pyramidally solvable. In this note we solve the problem of recognizing permuted strong VdV matrices. This yields an O(n⁴) time algorithm for the TSP with a permuted Euclidean VdV matrix. The problem, however, of recognizing permuted VdV matrices in general remains open.