An algorithm to detect permutations of Hankel matrices

Question

I am trying to write code to detect if a matrix is permutation of a Hankel matrix but I can't think of an efficient solution other than very slow brute force. Here is the spec.

Input: An n by n matrix M whose entries are 1 or 0.

Input format: Space separated rows. One row per line. For example

0 1 1 1
0 1 0 1
0 1 0 0
1 0 1 1

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.

I would be very grateful for any ideas.

Answer 1

Without Loss of Generality, we will assume that there are fewer 0's than 1's. We can then find the possible diagonals in a Hankel Matrix that could be 0's to give us the appropriate number of 0's in the entire matrix. And, this will give us the possible Hankel matrices. From there, you can count the number of 0's in each column, and compare it to the number of 0's in the columns of the original matrix. Once you have done this, you have a much smaller space in which to perform a brute force search: permuting on columns and rows that have the right number of 0's.

Example: OP's suggested a 4x4 matrix with 7 0's. We need to partition this using the set {4,3,3,2,2,1,1}. So, or partitions would be:

• {4,3}
• {4,2,1} (2 of these matrices)
• {3,3,1}
• {3,2,2}
• {3,2,1,1} (2 of these matrices)

And this gives us the Hankel Matrices (excluding symmetries)

1 1 0 0    1 1 1 0    0 1 1 0    1 1 0 1
1 0 0 1    1 1 0 1    1 1 0 1    1 0 1 0
0 0 1 1    1 0 1 0    1 0 1 0    0 1 0 1
0 1 1 1    0 1 0 0    0 1 0 1    1 0 1 0

1 0 0 1    0 1 1 1    0 1 0 1
0 0 1 1    1 1 1 0    1 0 1 1
0 1 1 0    1 1 0 0    0 1 1 0
1 1 0 1    1 0 0 0    1 1 0 0

The original matrix had columns with 3, 1, 2, and 1 0's in its four columns. Comparing this to the 7 possible Hankel matrices gives us 2 possibilities

1 1 1 0    0 1 1 1    
1 1 0 1    1 1 1 0    
1 0 1 0    1 1 0 0    
0 1 0 0    1 0 0 0    

Now, there are only 4 possible permutations that could map the original matrix to each of these: we have only 1 choice based on the columns with 2 and 3 0's, but 2 choices for the columns with 1 0's, and also 2 choices for the rows with 1 0's. Checking those permutations, we see that the following Hankel matrix is a permutation of the original

0 1 1 1    
1 1 1 0    
1 1 0 0    
1 0 0 0