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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.