# 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? – Tom van der Zanden 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.) – Kaveh 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. – Lembik 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? – Igor Shinkar Apr 17 '15 at 21:33
• Cross-posted now to mathoverflow.net/questions/204294/is-hankelability-np-hard – Lembik Apr 29 '15 at 17:03