This question was previously [asked on cstheory][1] but with no answers or substantive comments.


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:** Yes if there is a permutation of the rows and columns of M so that M is a [Hankel matrix][2] and No otherwise. A Hankel matrix has constant skew-diagonals (positive sloping diagonals). 

When I say a permutation, I mean we can apply exactly one permutation to the order of the rows and a possibly different one to the order of the columns.

A very nice $O(n^2)$ time algorithm [is known][3] for this problem if we only allow permutation of the order of rows.

Peter de Rivaz pointed out this [paper][4] as a possible route to proving NP-hardness but I haven't managed to get that to work.

> Is detecting Hankelability NP-hard?

  [1]: http://stackoverflow.com/questions/29484864/an-algorithm-to-detect-permutations-of-hankel-matrices
  [2]: http://en.m.wikipedia.org/wiki/Hankel_matrix
  [3]: http://stackoverflow.com/questions/20704900/determine-if-some-row-permutation-of-a-matrix-is-toeplitz
  [4]: http://www.mat.ucsb.edu/~g.legrady/academic/courses/15w259/d/re_orderableMatrix.pdf


  [1]: https://cstheory.stackexchange.com/questions/31174/is-hankelability-np-hard