Узнайте, совпадают ли две симметричные матрицы с точностью до перестановки строк / столбцов

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

Вы всегда можете отсортировать матрицу по норме строки и посмотреть, отличаются ли они. Если две строки имеют одинаковую норму, вам придется проверить перестановки строк, которые имеют одинаковую норму. Но это сводит проблему только к строкам с одинаковой нормой. Во многих случаях вы можете сначала отсортировать по 2-норме, затем по 1-норме и, наконец, перебрать оставшиеся перестановки грубой силой.

import numpy as np

def get_row_norm(a):
    """
    Sort by 2-norm
    """
    row_norms = np.sum(a**2, axis=1)
    return row_norms

def sort(a):
    """
    Return the matrix a sorted by 2-norm
    """
    n = a.shape[0]
    # Get the norms
    row_norms = get_row_norm(a)
    # Get the order
    order = np.argsort(row_norms)[::-1]

    sorted_a = a.copy()

    for m in range(n):
        i = order[m]
        for k in range(m+1): 
            j = order[k]
            sorted_a[m, k] = a[i, j]
            sorted_a[k, m] = a[i, j]

    return sorted_a


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

# Sort a and b
A = sort(a)
B = sort(b)
# Print the norms
print(get_row_norm(a)) # [ 3. 12.  3. 36. 22.  2. 26.]
print(get_row_norm(A)) # [36. 26. 22. 12.  3.  3.  2.]
print(get_row_norm(B)) # [36. 26. 22. 12.  3.  3.  2.]
# Assert that they are equal
print( (A == B).all())

Обратите внимание, что если они не равны, вам все равно нужно проверить перестановку пятого и шестого ряда, поскольку их нормы равны.

Answer 2

Вот векторизованное решение, основанное на sorting и использующее searchsorted -

import pandas as pd

# Sort rows for a and b
aS = np.sort(a,axis=1)
bS = np.sort(b,axis=1)

# Scale down each row to a scalar each
scale = np.r_[(np.maximum(aS.max(0),bS.max(0))+1)[::-1].cumprod()[::-1][1:],1]
aS1D = aS.dot(scale)
bS1D = bS.dot(scale)

# Use searchsorted to get the correspondence on indexing
sidx = aS1D.argsort()
searchsorted_idx = np.searchsorted(aS1D,bS1D,sorter=sidx)
searchsorted_idx[searchsorted_idx==len(aS1D)] = len(aS1D)-1
df = pd.DataFrame({'A':searchsorted_idx})
new_order = sidx[df.groupby('A').cumcount().values+searchsorted_idx]
# new_order is the permuted order, i.e. [5, 7, 1, 3, 2, 4, 6]

# Finally index into a with the new_order and compare against b
out = np.array_equal(a[new_order[:,None], new_order],b)

Answer 3

Я предполагаю, что у вас есть список перестановок строк / столбцов a, который дает b, например, как то так

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

Тогда вы можете просто сделать следующее на a

a_p = a[p]
a_p = a_p[:, p]

и проверьте, равны ли b и переставленные a_p:

(a_p == b).all()

Редактировать : поскольку у вас нет списка, подобного приведенному выше p, вы можете (по крайней мере для небольших массивов a и b) сгенерировать перестановки индексов и проверить для каждого:

from itertools import permutations

def a_p(a, b, p):
    p = np.array(p)
    a_p = a[p]
    a_p = a_p[:, p]
    return a_p

for p in permutations(range(a.shape[0])):
    if (a_p(a, b, p) == b).all():
        print('True')
        break
else:
    print('False')

Обратите внимание, что этот метод грубой силы работает и для несимметричных матриц. Но так как число перестановок огромно для больших массивов a и b, этот метод может быть очень медленным. Так что ваше решение с вычислением собственных значений намного лучше.

Вот эталонный тест:

def Yduqoli(a, b):
    ''' I suppose your solution is similar'''
    if (np.array(np.unique(a, return_counts=True)) == np.array(np.unique(b, return_counts=True))).all():
        a_eigs = np.sort(np.linalg.eigvals(a))
        b_eigs = np.sort(np.linalg.eigvals(b))
        return np.allclose(a_eigs, b_eigs)
    else:
        return False

def AndyK(a, b):
    for p in permutations(range(a.shape[0])):
        if (a_p(a, b, p) == b).all():
            return True
    return False  

%timeit AndyK(a,b)
103 ms ± 4.54 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit Yduqoli(a,b)
408 µs ± 65.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

, где я использовал симметричные матрицы a и b, предоставленные ОП.

Обновление : Как упоминал Пол Панцер, простая проверка собственных значений в некоторых случаях может дать неверный результат, например, a = np.array([[4, 0], [0, 0]]), b = np.array([[2, 2], [2, 2]]) имеют те же собственные значения, но не могут быть перетасованы одно в другое. Поэтому сначала нужно проверить, имеют ли массивы a и b одинаковые элементы (независимо от их положения).