Ask Your Question
1

Symmetric matrix up to permutation of its columns

asked 2022-05-31 17:08:06 +0100

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
edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
1

answered 2022-05-31 18:45:37 +0100

Max Alekseyev gravatar image

updated 2022-06-01 17:56:32 +0100

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)
edit flag offensive delete link more

Comments

Do you have a copy of Bhat's paper? Or do you know if the (python) code for his algorithm is available somewhere?

Sébastien Palcoux gravatar imageSébastien Palcoux ( 2022-05-31 21:37:21 +0100 )edit

It's on Sci-Hub...

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2022-05-31 22:42:37 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2022-05-31 17:08:06 +0100

Seen: 680 times

Last updated: Jun 01 '22