判断矩阵的行排列是否为Toeplitz

Question

“托普利茨矩阵”是一个矩阵，其中每个从左到右下降的对角线都是常数。给定一个二元矩阵M，是否有一个有效的算法来确定是否存在行的排列，从而使之成为Toeplitz？

例如，设置

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

如果您交换第一行和第二行，您将得到

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

那就是Toeplitz。

在python中，您可以生成一个随机二进制矩阵，如下所示。

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

我想把这个测试应用于M。

(注意矩阵M不需要是正方形的。)

Answer 1

一种对小矩阵有效的简单方法是：

Sort the rows of M
For each choice of start row
    For each choice of end row
         construct a Toeplitz matrix T from the given start and end row
         Sort the rows of T and compare to M
         If you find a match then T is a permutation of M that is Toeplitz

这是基于这样一个事实:一旦知道起始行和结束行，Toeplitz矩阵就是唯一定义的。

然而，这种做法并不特别有效。

Python代码示例

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

n=len(M)
M2 = sorted(M)
for start in M2:
    for end in M2:
        v = end+start[1:]
        T = [v[s:s+n] for s in range(n-1,-1,-1)]
        if sorted(T)==M2:
            print 'Found Toeplitz representation'
            print T

版画

Found Toeplitz representation
[[0, 1, 1], 
 [1, 0, 1], 
 [1, 1, 0]]
Found Toeplitz representation
[[1, 0, 1],
 [1, 1, 0],
 [0, 1, 1]]
Found Toeplitz representation
[[1, 1, 0], 
 [0, 1, 1], 
 [1, 0, 1]]

Answer 2

您可以对排除条件进行初步检查：

1. 求出矩阵中所有列的按列和。
2. 现在，在行的任何排列中，列中的值应保留在同一列中。
3. 因此，任意两个相邻列之和之间的差额应该是最大的1。

另外，如果我和i+1是两个相邻的列，那么：

1. 如果是sum(i+1) = sum(i) + 1，那么我们知道列I中最底层的元素应该是0，而列中的最顶层元素(i+1)应该是1。
2. 如果是sum(i+1) = sum(i) - 1，那么我们知道列I中最底层的元素应该是1，而列中的最顶层元素(i+1)应该是0。
3. 如果是sum(i+1) = sum(i)，那么我们知道第一列中最底层的元素应该等于列中的最顶层元素(i+1)。

您还可以通过对行的求和来进行类似的检查，并查看是否存在任何排列，其中任意两个相邻行的之和最多只有一个。

当然，您仍然需要进行一些组合搜索，但是上面的过滤器可能会减少搜索场景。

这是因为您现在必须为每对相邻列搜索一对(候选的顶部和底部)行，这些行满足上述3项条件。

此外，如果行数远远大于列数，则此优化将不会有多大帮助。