8
$\begingroup$

This question was previously asked on cstheory 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 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 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.

Is detecting Hankelability NP-hard?

Improve this question
$\endgroup$
6
  • $\begingroup$ Does Hankem matrices correspond to distance matrices for some nice family of graphs? If so, you are looking at a graph isomorphism problem, that is, to detect if a weighted graph is isomorphic to some graph in the "Hankel family"... $\endgroup$
    – Per Alexandersson
    Commented Apr 29, 2015 at 17:07
  • $\begingroup$ @PerAlexandersson It's an excellent question but the answer is, I don't know. That is I don't know what family of graphs this would correspond to. $\endgroup$
    – Simd
    Commented Apr 29, 2015 at 17:34
  • $\begingroup$ If you allow both rows and columns to be permuted, then Hankelability would be the same as Toeplitzability, yes? (en.wikipedia.org/wiki/Toeplitz_matrix) $\endgroup$
    – Yoav Kallus
    Commented Apr 29, 2015 at 20:56
  • $\begingroup$ @YoavKallus Yes that is right. $\endgroup$
    – Simd
    Commented Apr 29, 2015 at 20:57
  • 1
    $\begingroup$ I realize what I wrote above is slightly wrong, but I think it works if you replace "cyclic graph" (by which I actually meant circulant) with "bipartite graph on 2n vertices with automorphism of order n that preserves the parts" $\endgroup$
    – Yoav Kallus
    Commented Apr 29, 2015 at 22:53

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .