26
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Just a guess: maybe this problem is GI-complete? $\endgroup$ – Tom van der Zanden Apr 16 '15 at 19:43
  • $\begingroup$ 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.) $\endgroup$ – Kaveh Apr 17 '15 at 7:37
  • $\begingroup$ @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. $\endgroup$ – Lembik Apr 17 '15 at 7:43
  • $\begingroup$ Do you mean apply first some permutation on the rows and then some permutation on the columns? or do you allow more permutations? $\endgroup$ – Igor Shinkar Apr 17 '15 at 21:33
  • 2
    $\begingroup$ Cross-posted now to mathoverflow.net/questions/204294/is-hankelability-np-hard $\endgroup$ – Lembik Apr 29 '15 at 17:03

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.