I asked this question on SO on April 7 and added a bounty which has now expired but no poly time solution has been found yet.
I am trying to write code to detect if a matrix is a permutation of a Hankel matrix. Here is the spec.
Input: An n by n matrix M whose entries are 1 or 0.
Output: A permutation of the rows and columns of M so that M is a Hankel matrix if that is possible. A Hankel matrix has constant skew-diagonals (positive sloping diagonals).
When I say a permutation, I mean we can apply one permutation to the order of the rows and a possibly different one to the columns.
A very nice $O(n^2)$ time algorithm is known for this problem if we only allow permutation of the order of rows.
Peter de Rivaz pointed out this paper as a possible route to proving NP-hardness but I haven't managed to get that to work.