<p>I asked this question on <a href="https://stackoverflow.com/questions/29484864/an-algorithm-to-detect-permutations-of-hankel-matrices">SO</a>  on April 7 and added a bounty which has now expired but no poly time solution has been found yet. </p>

<p>I am trying to write code to detect if a matrix is a permutation of a Hankel matrix.  Here is the spec.</p>

<p><strong>Input:</strong> An n by n matrix M whose entries are 1 or 0.</p>

<p><strong>Output:</strong> A permutation of the rows and columns of M so that M is a <a href="http://en.m.wikipedia.org/wiki/Hankel_matrix" rel="nofollow noreferrer">Hankel matrix</a> if that is possible. A Hankel matrix has constant skew-diagonals (positive sloping diagonals). </p>

<p>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.</p>

<p>A very nice $O(n^2)$ time algorithm <a href="https://stackoverflow.com/questions/20704900/determine-if-some-row-permutation-of-a-matrix-is-toeplitz">is known</a> for this problem if we only allow permutation of the order of rows.</p>

<p>Peter de Rivaz pointed out this <a href="http://www.mat.ucsb.edu/~g.legrady/academic/courses/15w259/d/re_orderableMatrix.pdf" rel="nofollow noreferrer">paper</a> as a possible route to proving NP-hardness but I haven't managed to get that to work.</p>

CC BY-SA 3.0
2015-04-16T19:43:37.657Z
Just a guess: maybe this problem is [GI-complete](http://en.wikipedia.org/wiki/Graph_isomorphism_problem#GI-complete_and_GI-hard_problems)?
Tom van der Zanden
CC BY-SA 3.0
2015-04-17T07:37:33.113Z
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
CC BY-SA 3.0
2015-04-17T07:43:30.677Z
@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
CC BY-SA 3.0
2015-04-17T21:33:31.323Z
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
CC BY-SA 3.0
2015-04-18T06:08:41.637Z
@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
CC BY-SA 3.0
2015-04-29T17:03:20.583Z
Cross-posted now to http://mathoverflow.net/questions/204294/is-hankelability-np-hard
Simd
<cc.complexity-theory>
Is Hankelability NP-hard?
Simd
# Is Hankelability NP-hard?

(Asked by: username_0 on 2015-04-16)

I asked this question on [SO](https://stackoverflow.com/questions/29484864/an-algorithm-to-detect-permutations-of-hankel-matrices) 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](http://en.m.wikipedia.org/wiki/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](https://stackoverflow.com/questions/20704900/determine-if-some-row-permutation-of-a-matrix-is-toeplitz) for this problem if we only allow permutation of the order of rows.

Peter de Rivaz pointed out this [paper](http://www.mat.ucsb.edu/~g.legrady/academic/courses/15w259/d/re_orderableMatrix.pdf) as a possible route to proving NP-hardness but I haven't managed to get that to work.

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: Just a guess: maybe this problem is [GI-complete](http://en.wikipedia.org/wiki/Graph_isomorphism_problem#GI-complete_and_GI-hard_problems)?  
> **username_2**: 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.)  
> **username_0**: @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.  
> **username_3**: Do you mean apply first some permutation on the rows and then some permutation on the columns? or do you allow more permutations?  
> **username_0**: @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.  
> **username_0**: Cross-posted now to http://mathoverflow.net/questions/204294/is-hankelability-np-hard  

---

## 0 answers

