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

The one thing which the first answer to this question got right is that permuting the rows and columns doesn't change the row sums or column sums.

Another easy observation is that in a Hankel matrix, the difference in row sum between two consecutive rows is -1, 0, or 1, and each case gives us a constraint on the rows. If the difference is 0 then the entering variable is equal to the exiting variable; otherwise we know which is 0 and which is 1.

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

has row sums 3, 2, 1, 3. The orders which respect the difference requirement are 1 2 3 3 and 3 3 2 1, and wlog we can discard reversals because reversing the row and column permutations just rotates the matrix by 180 degrees. Therefore we reduce to considering four permuted matrices (two possible orderings of the 3s in the row sums, and two in the column sums):

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

We could actually have taken the analysis further by observing that by forcing the initial rows to have sums 1 and 2 we constrain the order of the columns with sum 3, since

0 0 1 0
0 0 1 1

is not a valid initial two rows of a Hankel matrix. Whether or not this kind of reasoning is easy to implement depends on your programming paradigm.

Note that in the worst case this kind of reasoning still doesn't leave a polynomial number of cases to brute force through.

Answer 2

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    

Answer 3

Here are some ideas.

1)

Row and Column permutations preserve the row and column sums:

1 0 1 0 - 2
0 0 0 1 - 1  row sums
1 0 0 0 - 1
1 1 1 0 - 3
| | | |
3 1 2 1
column sums

Whichever way you permute the rows, the row sums will still be {2, 1, 1, 3} in some permutation; the column sums will be unchanged. And vice versa. Hankel matrices and their permutations will always have the same set of row sums as column sums. This gives you a quick test to rule out a set of non-viable matrices.

2)

I posit that Hankel matrices can always be permuted in such a way that their row and column sums are in ascending order, and the result is still a Hankel matrix:

0 1 1 0 - 2         0 0 0 1 - 1
1 1 0 0 - 2         0 0 1 1 - 2
1 0 1 1 - 3   -->   0 1 1 0 - 2
0 0 1 0 - 1         1 1 0 1 - 3
| | | |             | | | |
2 2 3 1             1 2 2 3

Therefore if a matrix can be permuted into a Hankel matrix, then it can also be permuted into a Hankel matrix of ascending row and column sum. That is, we can reduce the number of permutations needed to test by only testing permutations where the row and column sums are in ascending order.

3)

I posit further that for any Hankel matrix where two or more rows have the same sum, every permutation of columns has a matching permutation of rows that also produces a Hankel matrix. That is, if a Hankel matrix exists for one permutation of columns, then it exists for every permutation of columns - since we can simply apply that same permutation to the corresponding rows and achieve a symmetrical result.

The upshot is that we only need to test permutations of rows or columns, not rows and columns.

---

Applied to the original example:

1 0 1 0 - 2       0 0 0 1       0 1 0 0 - 1     0 0 0 1
0 0 0 1 - 1       1 0 0 0       0 0 0 1 - 1     0 1 0 0
1 0 0 0 - 1  -->  1 0 1 0  -->  0 0 1 1 - 2 --> 0 0 1 1 = Hankel!
1 1 1 0 - 3       1 1 1 0       1 0 1 1 - 3     1 0 1 1
| | | |
3 1 2 1      permute rows into|   ditto     | try swapping    
              ascending order | for columns |  top 2 rows

---

4)

I posit, finally, that every Hankel matrix where there are multiple rows and columns with the same sum can be permuted into another Hankel matrix with the property that those rows and columns are in increasing order when read as binary numbers - reading left-to-right for rows and top-to-bottom for columns. That is:

0 1 1 0       0 1 0 1       0 0 1 1
1 0 0 1       0 1 1 0       0 1 0 1  New
1 0 1 0  -->  1 0 0 1  -->  1 0 1 0 Hankel
0 1 0 1       1 0 1 0       1 1 0 0
Original       rows         columns
 Hankel      ascending     ascending

If this is true (and I'm still undecided), then we only ever need to create and test one permutation of any given input matrix. That permutation puts both the rows and columns in order of ascending sum, and in the case of equal sums, orders them by their binary number interpretations. If this resultant matrix is not Hankel, then there is no permutation that will make it Hankel.

Hope that gets you on the way to an algorithm!

---

Addendum: Counterexamples?

Trying @orlp's example:

0 0 1 0     0 0 1 0     0 0 0 1
0 1 0 1     0 1 0 1     0 1 1 0
1 0 1 1 --> 0 1 1 1 --> 0 1 1 1
0 1 1 1     1 0 1 1     1 0 1 1
  (A)         (B)         (C)

• A: Original Hankel. Row sums are 1, 2, 3, 3; Rows 3 and 4 are not in binary order.
• B: Swap rows 3 and 4. Columns 3 and 4 are not in binary order.
• C: Swap columns 3 and 4. Result is Hankel and satisfies all the properties.

Trying @Degustaf's example:

1 1 0 1     0 1 0 0     0 0 1 0
1 0 1 0     1 0 0 1     0 1 0 1
0 1 0 0 --> 1 0 1 0 --> 1 0 0 1
1 0 0 1     1 1 0 1     0 1 1 1
  (A)         (B)         (C)

• A: Original Hankel matrix. Row sums are 3, 2, 1, 2.
• B: Rearrange so that the row sums are 1, 2, 2, 3, and the rows of sum 2 are in ascending binary order (i.e. 1001, 1010)
• C: Rearrange column sums to 1, 2, 2, 3, with the two columns of sum 2 in order (0101, 1001). Result is Hankel and satisfies all the properties. Note also that the permutation on the columns matches the permutation on the rows: the new column order from the old one is {3, 4, 2, 1}, the same operation to get from A to B.

Note: I suggest the binary order (#4) only for tiebreak situations on the row or column sum, not as a replacement for the sort in (#2).