找出两个对称矩阵是否相同,直到行/列的排列

Question

我有两个对称(项目共现)矩阵A和B,并想知道它们是否描述相同的共现,只有排列的行/列标签.(必须对行和列应用相同的排列以保持对称/共现属性)

例如,我的测试中这两个矩阵应该相等:

a = np.array([
    #1 #2 #3 #4 #5 #6 #7
    [0, 1, 1, 0, 0, 0, 1], #1
    [1, 0, 1, 2, 1, 1, 2], #2
    [1, 1, 0, 0, 0, 0, 1], #3
    [0, 2, 0, 0, 4, 0, 4], #4
    [0, 1, 0, 4, 0, 1, 2], #5
    [0, 1, 0, 0, 1, 0, 0], #6
    [1, 2, 1, 4, 2, 0, 0]  #7
])
b = np.array([
    #5 #7 #1,3#3,1#2 #4 #6
    [0, 2, 0, 0, 1, 4, 1], #5
    [2, 0, 1, 1, 2, 4, 0], #7
    [0, 1, 0, 1, 1, 0, 0], #1,3 could be either
    [0, 1, 1, 0, 1, 0, 0], #1,3 could be either
    [1, 2, 1, 1, 0, 2, 1], #2
    [4, 4, 0, 0, 2, 0, 0], #4
    [1, 0, 0, 0, 1, 0, 0]  #6
])

我目前测试特征值是否相同使用numpy.linalg.eigvals(我甚至不确定这是一个充分的条件),但我想找到一个不涉及数值精度的测试,因为我在这里处理整数.

Answer 1

我假设您有行/列的排列列表，其中a给出了b，例如类似这样的内容

\n\n

p = np.array([5, 7, 1, 3, 2, 4, 6]) - 1\n

\n\n

然后你可以简单地执行以下操作a

\n\n

a_p = a[p]\na_p = a_p[:, p]\n

\n\n

并检查b和 排列是否a_p相等：

\n\n

(a_p == b).all()\n

\n\n

编辑：由于您没有像上面这样的列表p，因此您可以（至少对于小数组a和b）生成索引的排列并检查每个索引：

\n\n

from itertools import permutations\n\ndef a_p(a, b, p):\n    p = np.array(p)\n    a_p = a[p]\n    a_p = a_p[:, p]\n    return a_p\n\nfor p in permutations(range(a.shape[0])):\n    if (a_p(a, b, p) == b).all():\n        print('True')\n        break\nelse:\n    print('False')\n

\n\n

请注意，这种强力方法也适用于非对称矩阵。a但由于大型数组和的排列数量很大b，因此该方法可能非常慢。所以你的计算特征值的解决方案要好得多。

\n\n

这是一个基准：

\n\n

def Yduqoli(a, b):\n    ''' I suppose your solution is similar'''\n    if (np.array(np.unique(a, return_counts=True)) == np.array(np.unique(b, return_counts=True))).all():\n        a_eigs = np.sort(np.linalg.eigvals(a))\n        b_eigs = np.sort(np.linalg.eigvals(b))\n        return np.allclose(a_eigs, b_eigs)\n    else:\n        return False\n\ndef AndyK(a, b):\n    for p in permutations(range(a.shape[0])):\n        if (a_p(a, b, p) == b).all():\n            return True\n    return False  \n\n%timeit AndyK(a,b)\n103 ms \xc2\xb1 4.54 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 10 loops each)\n\n%timeit Yduqoli(a,b)\n408 \xc2\xb5s \xc2\xb1 65.4 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 1000 loops each)\n

\n\n

我使用了OP提供的a对称矩阵。b

\n\n

更新：正如 Paul Panzer 所提到的，在某些情况下，简单地检查特征值可能会给出不正确的结果，例如a = np.array([[4, 0], [0, 0]])，b = np.array([[2, 2], [2, 2]])具有相同的特征值，但不能将一个特征值混入另一个特征值。因此，我们首先需要检查数组a和是否b具有相同的元素（无论它们的位置如何）。

\n