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.)