The problem of determining if a given n×n binary matrix can be permuted (via row and column permutations) into a Hankel matrix is NP-hard.

This conclusion is supported by the referenced paper "Re-orderable Matrix: Recognition and Uniqueness" which states that recognizing whether a matrix can be reordered into a Hankel matrix (or Toeplitz matrix) via row and column permutations is NP-hard.

Key ...

Short answer: Yes. The decision version of Hankelability is NP-complete (already for 0–1 matrices).

Why the problem is in NP Given a certificate consisting of two permutations of {1,…,n} (for the rows and the columns) and a 0–1 pattern on anti-diagonals (a bit for each sum k=2,…,2n), you can verify in O(n^2) time that, after permuting rows and columns accordingly, every anti-diagonal is constant ...

Yes – deciding whether a 0/1-matrix can be permuted independently in its rows and its columns so as to become Hankel is NP-complete (“Hankelability” is NP-hard and lies in NP).

---

1. The decision problem

---

HANKELABILITY

Input : an n × n 0...

Here is a clean summary of what is known:

1. The decision problem “HANKELABILITY”
   Input: an n×n 0–1‐matrix M.
   Question: Do there exist two permutations P (of the rows) and Q (of the columns) and a vector f:[2…2n]→{0,1} so that for all i,j
   (P M Q)[i,j] = f(i+j)?

2. HANKELABILITY is in NP.
   A certificate is just the two permutations P,Q (and the f-vector can be read...

This is an interesting computational problem about determining whether a binary matrix can be transformed into a Hankel matrix through row and column permutations.

Let me analyze the complexity of this problem:

The Problem (Hankelability)

• Input: An n×n binary matrix M
• Question: Do there exist permutations π (for rows) and σ (for columns) such that M'[i,j] = M[π(i),σ(j)] is a Hank...

Excellent question. This is a classic example of a problem that seems simple on the surface but is computationally very hard.

Summary

Yes, the problem of determining if a matrix is a permutation of a Hankel matrix (which I'll call Hankelability) is NP-hard.

Intuition

The difficulty arises from the need to find two permutations simultaneously: one for the rows (p) and one fo...

Yes – deciding whether a 0/1 matrix can be turned into a Hankel matrix by independently permuting its rows and its columns is an NP-complete problem (so, unless P = NP, no polynomial-time algorithm exists).

Why the problem is in NP
If two permutations σ (of the rows) and τ (of the columns) are given it takes Θ(n²) time to build the rearranged matrix σ M τ and to verify that every north-east / s...

<think> We are given an n by n matrix M with entries 1 or 0. We wish to know if there is a permutation of the rows and a permutation of the columns such that the resulting matrix is Hankel. A Hankel matrix has constant skew-diagonals (i.e., the entries on each diagonal from top-left to bottom-right are constant).

Note: In a Hankel matrix, the (i,j) entry depends only on i+j. Specifically, for a f...

Is Hankelability NP-hard?

The question asks whether it's NP-hard to determine if a binary matrix can be transformed into a Hankel matrix through independent permutations of its rows and columns.

Problem Analysis

A Hankel matrix is one where each skew-diagonal (running from bottom-left to top-right) contains identical values. Formally, a matrix H is Hankel if H(i,j) = H(k,l) whenever i+...