Determine se alguma permutação de linha de uma matriz é Toeplitz
A Toeplitz matrix "é uma matriz na qual cada diagonal descendente da esquerda para a direita é constante". Dada uma matriz binária M, existe um algoritmo eficiente para determinar se existe uma permutação das linhas que o torna Toeplitz?
Por exemplo, defina
M= [0 1 1]
[1 1 0]
[1 0 1]
Se você trocar a primeira e segunda linha, você terá
[1 1 0]
[0 1 1]
[1 0 1]
que é Toeplitz.
Em python você pode fazer uma matriz binária aleatória da seguinte maneira.
n = 10
h = 10
M = np.random.randint(2, size=(h,n))
Eu gostaria de aplicar o teste para M.
(Observe que a matriz M não precisa ser quadrada.)