27

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.

Community
  • 1
Simd
  • 3,902
  • 20
  • 49
  • 5
    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 07: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. – Simd Apr 17 '15 at 07: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
  • @IgorShinkar I mean first some permutation on the order of the rows and then a possibly different permutation on the order of the columns, then stop. – Simd Apr 18 '15 at 06:08
  • 2
    Cross-posted now to http://mathoverflow.net/questions/204294/is-hankelability-np-hard – Simd Apr 29 '15 at 17:03

0 Answers0