What is a quick way (if any) to decide whether a matrix is symmetric up to permutation of its columns?
Below is the slow way:
def SymPerm(L):
n=len(L)
for g in SymmetricGroup(n):
N=[[L[i][g(j+1)-1] for j in range(n)] for i in range(n)]
M=matrix(N)
if M==M.transpose():
return True
return False
This is an NP-complete problem - see https://mathoverflow.net/q/155468 for a reference. So, it's unlikely for a truly quick (ie. polynomial-time) way to exist. But there is also a reference to Bhat (1981) paper, which proposes some optimized algorithm for this problem.
ADDED.
Here is an ILP solution to this problem that for a given matrix M tries to find a permutation matrix Q (if one exists) such that M*Q is symmetric:
# matrix size
n = 10
# generate a random symmetric n X n 01-matrix
M = Matrix(ZZ,n,n)
for i in range(n):
for j in range(i+1):
M[i,j] = M[j,i] = randint(0,1)
# randomly permute columns of M
p = SymmetricGroup(n).random_element()
M = M[:,list(p(i)-1 for i in (1..n))]
# problem instance is created, let's now try to solve it
# define an ILP problem
milp = MixedIntegerLinearProgram()
milp.set_objective( None )
# permutation matrix to be found
Q = milp.new_variable(binary=True)
for i in range(n):
milp.add_constraint( sum( Q[(i,j)] for j in range(n) ) == 1 )
milp.add_constraint( sum( Q[(j,i)] for j in range(n) ) == 1 )
# constraints imposing that M*Q is symmetric
for i in range(n):
for j in range(i):
milp.add_constraint( sum( M[i,k] * Q[(k,j)] for k in range(n) ) == sum( M[j,k] * Q[(k,i)] for k in range(n) ) )
milp.solve()
R = Matrix( milp.get_values(Q) )
# print the permuted matrix, which should be symmetric
print(M*R)
Do you have a copy of Bhat's paper? Or do you know if the (python) code for his algorithm is available somewhere?
Asked: 2022-05-31 17:08:06 +0100
Seen: 698 times
Last updated: Jun 01 '22
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
