This question was previously asked on cstheory but with no answers or substantive comments.

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: Yes if there is a permutation of the rows and columns of M so that M is a Hankel matrix and No otherwise. A Hankel matrix has constant skew-diagonals (positive sloping diagonals).

When I say a permutation, I mean we can apply exactly one permutation to the order of the rows and a possibly different one to the order of 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.

Is detecting Hankelability NP-hard?