Is Hankelability NP-hard?

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.

• Just a guess: maybe this problem is GI-complete? Apr 16 '15 at 19:43
• Do you mean that the same permutation is applied to rows and columns? (my got feeling says this is in P, if a matrix is Hankelable with different diagonal values there aren't that many possibilities for the permutation.) Apr 17 '15 at 7:37
• @Kaveh Thanks for the question. The permutation applied to the order of the columns can be different from the one applied to the order of the rows. Apr 17 '15 at 7:43
• Do you mean apply first some permutation on the rows and then some permutation on the columns? or do you allow more permutations? Apr 17 '15 at 21:33
• Cross-posted now to mathoverflow.net/questions/204294/is-hankelability-np-hard Apr 29 '15 at 17:03