Determine if some row permutation of a matrix is Toeplitz

Question

A Toeplitz matrix "is a matrix in which each descending diagonal from left to right is constant." Given a binary matrix M, is there an efficient algorithm to determine if there is a permutation of the rows which makes it Toeplitz?

For example, set

M= [0 1 1]
   [1 1 0]
   [1 0 1]

If you swap the first and second row you get

[1 1 0]
[0 1 1]
[1 0 1]

which is Toeplitz.

In python you can make a random binary matrix as follows.

n = 10
h = 10
M =  np.random.randint(2, size=(h,n))

I would like to apply the test to M.

(Note the matrix M does not need to be square.)

Answer 1

This problem can be solved in linear O(h*w) time, where h is number of rows and w is number of columns.

Construct a graph where each vertex corresponds to (w-1)-length substring which may be either prefix or suffix of some row in the matrix. One vertex may correspond to several duplicate substrings. Connect these vertexes with h edges. Each edge corresponds to row of the matrix. It is directed from the vertex corresponding to this row's prefix to the vertex corresponding to this row's suffix.

To determine if some row permutation is a Toeplitz matrix, it is enough to check if constructed graph is Eulerian graph. To find permutation itself, it is enough to find Eulerian path in this graph.

We need some efficient way to interconnect vertexes and edges. Straightforward approach assumes comparing each row-substring pair. This is not very interesting because of O(h²*w) time complexity.

Building Generalized suffix tree (or suffix array) for rows of the matrix needs only O(h*w) time. And this tree allows to interconnect vertexes and edges also in linear time: each internal node with depth w-1 represents some (w-1)-length substring (vertex); each leaf attached to this node represents some row's suffix (incoming edge); and each leaf attached to this node's children represents some row containing this substring as a prefix (outgoing edge).

Other alternative is to use hash map. With (w-1)-length substring of matrix row as a key and pair of lists of row indexes (for rows where this substring is prefix/suffix) as a value. Comparing to suffix tree/array approach, this allows simpler implementation, needs less memory (each key needs only space for hash value and pointer to beginning of the substring), should work faster (on average), but has inferior worst-case complexity: O(h²*w).