Mixing
Find out if two symmetric matrices are the same up to a permutation of the rows/columns
Clash Royale CLAN TAG#URR8PPP
up vote
6
down vote
favorite
I have two symmetric (item co-occurrence) matrices A and B and want to find out if they describe the same co-occurrence, only with the row/column labels permuted. (The same permutation has to be applied to rows and columns to keep the symmetry/co-occurrence property)
For example these two matrices should be equal in my test:
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
])
I currently test if the eigenvalues are the same using numpy.linalg.eigvals (I am not even sure this is a sufficient condition), but I would like to find a test which doesn't involve numerical accuracy, since I am dealing with integers here.
python numpy matrix linear-algebra
asked 2 hours ago
C. Yduqoli
38639
add a comment |Â
up vote
6
down vote
favorite
I have two symmetric (item co-occurrence) matrices A and B and want to find out if they describe the same co-occurrence, only with the row/column labels permuted. (The same permutation has to be applied to rows and columns to keep the symmetry/co-occurrence property)
For example these two matrices should be equal in my test:
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
])
I currently test if the eigenvalues are the same using numpy.linalg.eigvals (I am not even sure this is a sufficient condition), but I would like to find a test which doesn't involve numerical accuracy, since I am dealing with integers here.
python numpy matrix linear-algebra
asked 2 hours ago
C. Yduqoli
38639
1
This problem is equivalent to graph isomorphism: exact solutions are likely to be slow. See e.g. this question
– Maxim
1 hour ago
add a comment |Â
up vote
6
down vote
favorite
up vote
6
down vote
favorite
I have two symmetric (item co-occurrence) matrices A and B and want to find out if they describe the same co-occurrence, only with the row/column labels permuted. (The same permutation has to be applied to rows and columns to keep the symmetry/co-occurrence property)
For example these two matrices should be equal in my test:
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
])
I currently test if the eigenvalues are the same using numpy.linalg.eigvals (I am not even sure this is a sufficient condition), but I would like to find a test which doesn't involve numerical accuracy, since I am dealing with integers here.
python numpy matrix linear-algebra
asked 2 hours ago
C. Yduqoli
38639
I have two symmetric (item co-occurrence) matrices A and B and want to find out if they describe the same co-occurrence, only with the row/column labels permuted. (The same permutation has to be applied to rows and columns to keep the symmetry/co-occurrence property)
For example these two matrices should be equal in my test:
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
])
I currently test if the eigenvalues are the same using numpy.linalg.eigvals (I am not even sure this is a sufficient condition), but I would like to find a test which doesn't involve numerical accuracy, since I am dealing with integers here.
python numpy matrix linear-algebra
python numpy matrix linear-algebra
asked 2 hours ago
C. Yduqoli
38639
asked 2 hours ago
C. Yduqoli
38639
edited 1 hour ago
asked 2 hours ago
C. Yduqoli
38639
asked 2 hours ago
C. Yduqoli
38639
asked 2 hours ago
C. Yduqoli
38639
38639
1
This problem is equivalent to graph isomorphism: exact solutions are likely to be slow. See e.g. this question
– Maxim
1 hour ago
add a comment |Â
1
This problem is equivalent to graph isomorphism: exact solutions are likely to be slow. See e.g. this question
– Maxim
1 hour ago
1
1
This problem is equivalent to graph isomorphism: exact solutions are likely to be slow. See e.g. this question
– Maxim
1 hour ago
This problem is equivalent to graph isomorphism: exact solutions are likely to be slow. See e.g. this question
– Maxim
1 hour ago
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
1
down vote
You could always sort the matrix by row-norm and see if they are different. If two rows have the same norm, you'd have to check permutations of the rows that have the same norm though. But this reduces the problem to only rows with the same norm. In many cases you can first sort by 2-norm, then 1-norm and finally brute force the remaining permutations.
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):
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())
Note that if they are not equal, you still have to check permutation of the fifth and sixth row, since their norms are equal.
answered 1 hour ago
user2653663
917813
Here's a counter-example:a = np.array([[2, 2], [0, 1]]),b = np.array([[1, 0], [2, 2]]), wherebisawith swapped rows and columns.
– AndyK
1 hour ago
@AndyK But that is a different matrix altogether?
– user2653663
53 mins ago
I meantbisawith swapped rows 0 <-> 1 and columns 0 <-> 1.
– AndyK
47 mins ago
add a comment |Â
up vote
1
down vote
Here's a vectorized solution based on sorting and leveraging 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)
answered 49 mins ago
Divakar
151k1475164
Nice one, but a lot slower than the solution with eigenvalues.
– AndyK
29 mins ago
@AndyK What size are you testing it on?
– Divakar
28 mins ago
You are right, for large sizes (e.g. n = 100) your solution is much faster. +1
– AndyK
19 mins ago
That doesn't seem to be correct. I trieda = scipy.linalg.toeplitz(np.arange(8))andbsome shuffled version of that, and am gettingFalseall the time.
– Paul Panzer
18 mins ago
@AndyK I'm pretty sure eigenvalues are not sufficient. for example[[4 0] [0 0]]and[[2 2] [2 2]]have the same eigenvalues but obviously cannot be shuffled into each other.
– Paul Panzer
14 mins ago
 |Â
show 1 more comment
up vote
1
down vote
I will assume that you have the list of permutation of the rows/columns of a which gives the b, e.g. something like this
p = np.array([5, 7, 1, 3, 2, 4, 6]) - 1
Then you can simply do the following on a
a_p = a[p]
a_p = a_p[:, p]
and check if b and the permuted a_p are equal:
(a_p == b).all()
Edit: since you don't have a list like the p above, you could (at least for small arrays a and b) generate the permutations of the indices and check for each on:
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(p)
print('True')
break
else:
print('False')
But I think your solution with computing eigenvalues is much better, since the number of permutations becomes huge for large arrays a and b.
Here's a benchmark:
def Yduqoli(a, b):
''' I suppose your solution is similar'''
a_eigs = np.sort(np.linalg.eigvals(a))
b_eigs = np.sort(np.linalg.eigvals(b))
return np.allclose(a_eigs, b_eigs)
def AndyK(a, b):
for p in permutations(range(a.shape[0])):
if (a_p(a, b, p) == b).all():
return True
else:
return False
n = 5
perms = np.array(list(permutations(range(n))))
p0 = np.array(perms[-1]) # let's take the last permutation for the worst case scenario
a = np.random.randint(10, size=(n, n)) # some random array
b = a[p0]
b = b[:, p0]
Times:
%timeit AndyK(a,b)
3.12 ms ± 755 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit Yduqoli(a,b)
249 µs ± 47.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
Update: as mentioned by Divakar, the solution using eigenvalues can fail in some cases like a = np.array([[4, 0], [0, 0]]), b = np.array([[2, 2], [2, 2]]) which have the same eigenvalues, but cannot be shuffled one into the other.
answered 2 hours ago
AndyK
511314
Sorry, I don't have that list.
– C. Yduqoli
1 hour ago
Ok, I edited it.
– AndyK
1 hour ago
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
You could always sort the matrix by row-norm and see if they are different. If two rows have the same norm, you'd have to check permutations of the rows that have the same norm though. But this reduces the problem to only rows with the same norm. In many cases you can first sort by 2-norm, then 1-norm and finally brute force the remaining permutations.
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):
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())
Note that if they are not equal, you still have to check permutation of the fifth and sixth row, since their norms are equal.
answered 1 hour ago
user2653663
917813
Here's a counter-example:a = np.array([[2, 2], [0, 1]]),b = np.array([[1, 0], [2, 2]]), wherebisawith swapped rows and columns.
– AndyK
1 hour ago
@AndyK But that is a different matrix altogether?
– user2653663
53 mins ago
I meantbisawith swapped rows 0 <-> 1 and columns 0 <-> 1.
– AndyK
47 mins ago
add a comment |Â
up vote
1
down vote
You could always sort the matrix by row-norm and see if they are different. If two rows have the same norm, you'd have to check permutations of the rows that have the same norm though. But this reduces the problem to only rows with the same norm. In many cases you can first sort by 2-norm, then 1-norm and finally brute force the remaining permutations.
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):
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())
Note that if they are not equal, you still have to check permutation of the fifth and sixth row, since their norms are equal.
answered 1 hour ago
user2653663
917813
Here's a counter-example:a = np.array([[2, 2], [0, 1]]),b = np.array([[1, 0], [2, 2]]), wherebisawith swapped rows and columns.
– AndyK
1 hour ago
@AndyK But that is a different matrix altogether?
– user2653663
53 mins ago
I meantbisawith swapped rows 0 <-> 1 and columns 0 <-> 1.
– AndyK
47 mins ago
add a comment |Â
up vote
1
down vote
up vote
1
down vote
You could always sort the matrix by row-norm and see if they are different. If two rows have the same norm, you'd have to check permutations of the rows that have the same norm though. But this reduces the problem to only rows with the same norm. In many cases you can first sort by 2-norm, then 1-norm and finally brute force the remaining permutations.
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):
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())
Note that if they are not equal, you still have to check permutation of the fifth and sixth row, since their norms are equal.
answered 1 hour ago
user2653663
917813
You could always sort the matrix by row-norm and see if they are different. If two rows have the same norm, you'd have to check permutations of the rows that have the same norm though. But this reduces the problem to only rows with the same norm. In many cases you can first sort by 2-norm, then 1-norm and finally brute force the remaining permutations.
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):
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())
Note that if they are not equal, you still have to check permutation of the fifth and sixth row, since their norms are equal.
answered 1 hour ago
user2653663
917813
answered 1 hour ago
user2653663
917813
answered 1 hour ago
user2653663
917813
answered 1 hour ago
user2653663
917813
917813
Here's a counter-example:a = np.array([[2, 2], [0, 1]]),b = np.array([[1, 0], [2, 2]]), wherebisawith swapped rows and columns.
– AndyK
1 hour ago
@AndyK But that is a different matrix altogether?
– user2653663
53 mins ago
I meantbisawith swapped rows 0 <-> 1 and columns 0 <-> 1.
– AndyK
47 mins ago
add a comment |Â
Here's a counter-example:a = np.array([[2, 2], [0, 1]]),b = np.array([[1, 0], [2, 2]]), wherebisawith swapped rows and columns.
– AndyK
1 hour ago
@AndyK But that is a different matrix altogether?
– user2653663
53 mins ago
I meantbisawith swapped rows 0 <-> 1 and columns 0 <-> 1.
– AndyK
47 mins ago
Here's a counter-example:
a = np.array([[2, 2], [0, 1]]), b = np.array([[1, 0], [2, 2]]), where b is a with swapped rows and columns.– AndyK
1 hour ago
Here's a counter-example:
a = np.array([[2, 2], [0, 1]]), b = np.array([[1, 0], [2, 2]]), where b is a with swapped rows and columns.– AndyK
1 hour ago
@AndyK But that is a different matrix altogether?
– user2653663
53 mins ago
@AndyK But that is a different matrix altogether?
– user2653663
53 mins ago
I meant
b is a with swapped rows 0 <-> 1 and columns 0 <-> 1.– AndyK
47 mins ago
I meant
b is a with swapped rows 0 <-> 1 and columns 0 <-> 1.– AndyK
47 mins ago
add a comment |Â
up vote
1
down vote
Here's a vectorized solution based on sorting and leveraging 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)
answered 49 mins ago
Divakar
151k1475164
Nice one, but a lot slower than the solution with eigenvalues.
– AndyK
29 mins ago
@AndyK What size are you testing it on?
– Divakar
28 mins ago
You are right, for large sizes (e.g. n = 100) your solution is much faster. +1
– AndyK
19 mins ago
That doesn't seem to be correct. I trieda = scipy.linalg.toeplitz(np.arange(8))andbsome shuffled version of that, and am gettingFalseall the time.
– Paul Panzer
18 mins ago
@AndyK I'm pretty sure eigenvalues are not sufficient. for example[[4 0] [0 0]]and[[2 2] [2 2]]have the same eigenvalues but obviously cannot be shuffled into each other.
– Paul Panzer
14 mins ago
 |Â
show 1 more comment
up vote
1
down vote
Here's a vectorized solution based on sorting and leveraging 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)
answered 49 mins ago
Divakar
151k1475164
Nice one, but a lot slower than the solution with eigenvalues.
– AndyK
29 mins ago
@AndyK What size are you testing it on?
– Divakar
28 mins ago
You are right, for large sizes (e.g. n = 100) your solution is much faster. +1
– AndyK
19 mins ago
That doesn't seem to be correct. I trieda = scipy.linalg.toeplitz(np.arange(8))andbsome shuffled version of that, and am gettingFalseall the time.
– Paul Panzer
18 mins ago
@AndyK I'm pretty sure eigenvalues are not sufficient. for example[[4 0] [0 0]]and[[2 2] [2 2]]have the same eigenvalues but obviously cannot be shuffled into each other.
– Paul Panzer
14 mins ago
 |Â
show 1 more comment
up vote
1
down vote
up vote
1
down vote
Here's a vectorized solution based on sorting and leveraging 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)
answered 49 mins ago
Divakar
151k1475164
Here's a vectorized solution based on sorting and leveraging 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)
answered 49 mins ago
Divakar
151k1475164
edited 33 mins ago
answered 49 mins ago
Divakar
151k1475164
answered 49 mins ago
Divakar
151k1475164
answered 49 mins ago
Divakar
151k1475164
151k1475164
Nice one, but a lot slower than the solution with eigenvalues.
– AndyK
29 mins ago
@AndyK What size are you testing it on?
– Divakar
28 mins ago
You are right, for large sizes (e.g. n = 100) your solution is much faster. +1
– AndyK
19 mins ago
That doesn't seem to be correct. I trieda = scipy.linalg.toeplitz(np.arange(8))andbsome shuffled version of that, and am gettingFalseall the time.
– Paul Panzer
18 mins ago
@AndyK I'm pretty sure eigenvalues are not sufficient. for example[[4 0] [0 0]]and[[2 2] [2 2]]have the same eigenvalues but obviously cannot be shuffled into each other.
– Paul Panzer
14 mins ago
 |Â
show 1 more comment
Nice one, but a lot slower than the solution with eigenvalues.
– AndyK
29 mins ago
@AndyK What size are you testing it on?
– Divakar
28 mins ago
You are right, for large sizes (e.g. n = 100) your solution is much faster. +1
– AndyK
19 mins ago
That doesn't seem to be correct. I trieda = scipy.linalg.toeplitz(np.arange(8))andbsome shuffled version of that, and am gettingFalseall the time.
– Paul Panzer
18 mins ago
@AndyK I'm pretty sure eigenvalues are not sufficient. for example[[4 0] [0 0]]and[[2 2] [2 2]]have the same eigenvalues but obviously cannot be shuffled into each other.
– Paul Panzer
14 mins ago
Nice one, but a lot slower than the solution with eigenvalues.
– AndyK
29 mins ago
Nice one, but a lot slower than the solution with eigenvalues.
– AndyK
29 mins ago
@AndyK What size are you testing it on?
– Divakar
28 mins ago
@AndyK What size are you testing it on?
– Divakar
28 mins ago
You are right, for large sizes (e.g. n = 100) your solution is much faster. +1
– AndyK
19 mins ago
You are right, for large sizes (e.g. n = 100) your solution is much faster. +1
– AndyK
19 mins ago
That doesn't seem to be correct. I tried
a = scipy.linalg.toeplitz(np.arange(8)) and b some shuffled version of that, and am getting False all the time.– Paul Panzer
18 mins ago
That doesn't seem to be correct. I tried
a = scipy.linalg.toeplitz(np.arange(8)) and b some shuffled version of that, and am getting False all the time.– Paul Panzer
18 mins ago
@AndyK I'm pretty sure eigenvalues are not sufficient. for example
[[4 0] [0 0]] and [[2 2] [2 2]] have the same eigenvalues but obviously cannot be shuffled into each other.– Paul Panzer
14 mins ago
@AndyK I'm pretty sure eigenvalues are not sufficient. for example
[[4 0] [0 0]] and [[2 2] [2 2]] have the same eigenvalues but obviously cannot be shuffled into each other.– Paul Panzer
14 mins ago
 |Â
show 1 more comment
up vote
1
down vote
I will assume that you have the list of permutation of the rows/columns of a which gives the b, e.g. something like this
p = np.array([5, 7, 1, 3, 2, 4, 6]) - 1
Then you can simply do the following on a
a_p = a[p]
a_p = a_p[:, p]
and check if b and the permuted a_p are equal:
(a_p == b).all()
Edit: since you don't have a list like the p above, you could (at least for small arrays a and b) generate the permutations of the indices and check for each on:
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(p)
print('True')
break
else:
print('False')
But I think your solution with computing eigenvalues is much better, since the number of permutations becomes huge for large arrays a and b.
Here's a benchmark:
def Yduqoli(a, b):
''' I suppose your solution is similar'''
a_eigs = np.sort(np.linalg.eigvals(a))
b_eigs = np.sort(np.linalg.eigvals(b))
return np.allclose(a_eigs, b_eigs)
def AndyK(a, b):
for p in permutations(range(a.shape[0])):
if (a_p(a, b, p) == b).all():
return True
else:
return False
n = 5
perms = np.array(list(permutations(range(n))))
p0 = np.array(perms[-1]) # let's take the last permutation for the worst case scenario
a = np.random.randint(10, size=(n, n)) # some random array
b = a[p0]
b = b[:, p0]
Times:
%timeit AndyK(a,b)
3.12 ms ± 755 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit Yduqoli(a,b)
249 µs ± 47.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
Update: as mentioned by Divakar, the solution using eigenvalues can fail in some cases like a = np.array([[4, 0], [0, 0]]), b = np.array([[2, 2], [2, 2]]) which have the same eigenvalues, but cannot be shuffled one into the other.
answered 2 hours ago
AndyK
511314
Sorry, I don't have that list.
– C. Yduqoli
1 hour ago
Ok, I edited it.
– AndyK
1 hour ago
add a comment |Â
up vote
1
down vote
I will assume that you have the list of permutation of the rows/columns of a which gives the b, e.g. something like this
p = np.array([5, 7, 1, 3, 2, 4, 6]) - 1
Then you can simply do the following on a
a_p = a[p]
a_p = a_p[:, p]
and check if b and the permuted a_p are equal:
(a_p == b).all()
Edit: since you don't have a list like the p above, you could (at least for small arrays a and b) generate the permutations of the indices and check for each on:
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(p)
print('True')
break
else:
print('False')
But I think your solution with computing eigenvalues is much better, since the number of permutations becomes huge for large arrays a and b.
Here's a benchmark:
def Yduqoli(a, b):
''' I suppose your solution is similar'''
a_eigs = np.sort(np.linalg.eigvals(a))
b_eigs = np.sort(np.linalg.eigvals(b))
return np.allclose(a_eigs, b_eigs)
def AndyK(a, b):
for p in permutations(range(a.shape[0])):
if (a_p(a, b, p) == b).all():
return True
else:
return False
n = 5
perms = np.array(list(permutations(range(n))))
p0 = np.array(perms[-1]) # let's take the last permutation for the worst case scenario
a = np.random.randint(10, size=(n, n)) # some random array
b = a[p0]
b = b[:, p0]
Times:
%timeit AndyK(a,b)
3.12 ms ± 755 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit Yduqoli(a,b)
249 µs ± 47.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
Update: as mentioned by Divakar, the solution using eigenvalues can fail in some cases like a = np.array([[4, 0], [0, 0]]), b = np.array([[2, 2], [2, 2]]) which have the same eigenvalues, but cannot be shuffled one into the other.
answered 2 hours ago
AndyK
511314
Sorry, I don't have that list.
– C. Yduqoli
1 hour ago
Ok, I edited it.
– AndyK
1 hour ago
add a comment |Â
up vote
1
down vote
up vote
1
down vote
I will assume that you have the list of permutation of the rows/columns of a which gives the b, e.g. something like this
p = np.array([5, 7, 1, 3, 2, 4, 6]) - 1
Then you can simply do the following on a
a_p = a[p]
a_p = a_p[:, p]
and check if b and the permuted a_p are equal:
(a_p == b).all()
Edit: since you don't have a list like the p above, you could (at least for small arrays a and b) generate the permutations of the indices and check for each on:
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(p)
print('True')
break
else:
print('False')
But I think your solution with computing eigenvalues is much better, since the number of permutations becomes huge for large arrays a and b.
Here's a benchmark:
def Yduqoli(a, b):
''' I suppose your solution is similar'''
a_eigs = np.sort(np.linalg.eigvals(a))
b_eigs = np.sort(np.linalg.eigvals(b))
return np.allclose(a_eigs, b_eigs)
def AndyK(a, b):
for p in permutations(range(a.shape[0])):
if (a_p(a, b, p) == b).all():
return True
else:
return False
n = 5
perms = np.array(list(permutations(range(n))))
p0 = np.array(perms[-1]) # let's take the last permutation for the worst case scenario
a = np.random.randint(10, size=(n, n)) # some random array
b = a[p0]
b = b[:, p0]
Times:
%timeit AndyK(a,b)
3.12 ms ± 755 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit Yduqoli(a,b)
249 µs ± 47.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
Update: as mentioned by Divakar, the solution using eigenvalues can fail in some cases like a = np.array([[4, 0], [0, 0]]), b = np.array([[2, 2], [2, 2]]) which have the same eigenvalues, but cannot be shuffled one into the other.
answered 2 hours ago
AndyK
511314
I will assume that you have the list of permutation of the rows/columns of a which gives the b, e.g. something like this
p = np.array([5, 7, 1, 3, 2, 4, 6]) - 1
Then you can simply do the following on a
a_p = a[p]
a_p = a_p[:, p]
and check if b and the permuted a_p are equal:
(a_p == b).all()
Edit: since you don't have a list like the p above, you could (at least for small arrays a and b) generate the permutations of the indices and check for each on:
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(p)
print('True')
break
else:
print('False')
But I think your solution with computing eigenvalues is much better, since the number of permutations becomes huge for large arrays a and b.
Here's a benchmark:
def Yduqoli(a, b):
''' I suppose your solution is similar'''
a_eigs = np.sort(np.linalg.eigvals(a))
b_eigs = np.sort(np.linalg.eigvals(b))
return np.allclose(a_eigs, b_eigs)
def AndyK(a, b):
for p in permutations(range(a.shape[0])):
if (a_p(a, b, p) == b).all():
return True
else:
return False
n = 5
perms = np.array(list(permutations(range(n))))
p0 = np.array(perms[-1]) # let's take the last permutation for the worst case scenario
a = np.random.randint(10, size=(n, n)) # some random array
b = a[p0]
b = b[:, p0]
Times:
%timeit AndyK(a,b)
3.12 ms ± 755 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit Yduqoli(a,b)
249 µs ± 47.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
Update: as mentioned by Divakar, the solution using eigenvalues can fail in some cases like a = np.array([[4, 0], [0, 0]]), b = np.array([[2, 2], [2, 2]]) which have the same eigenvalues, but cannot be shuffled one into the other.
answered 2 hours ago
AndyK
511314
edited 1 min ago
answered 2 hours ago
AndyK
511314
answered 2 hours ago
AndyK
511314
answered 2 hours ago
AndyK
511314
511314
Sorry, I don't have that list.
– C. Yduqoli
1 hour ago
Ok, I edited it.
– AndyK
1 hour ago
add a comment |Â
Sorry, I don't have that list.
– C. Yduqoli
1 hour ago
Ok, I edited it.
– AndyK
1 hour ago
Sorry, I don't have that list.
– C. Yduqoli
1 hour ago
Sorry, I don't have that list.
– C. Yduqoli
1 hour ago
Ok, I edited it.
– AndyK
1 hour ago
Ok, I edited it.
– AndyK
1 hour ago
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53042859%2ffind-out-if-two-symmetric-matrices-are-the-same-up-to-a-permutation-of-the-rows%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
This problem is equivalent to graph isomorphism: exact solutions are likely to be slow. See e.g. this question
– Maxim
1 hour ago