Ask Your Question
0

"how to test if two matrices are similar by a signed permutation matrix" code sage

asked 2020-02-22 13:44:59 -0500

imy gravatar image

"how to test if two matrices are similar by a signed permutation matrix" code sage

edit retag flag offensive close merge delete

Comments

What are the entries of the matrices? Real numbers or integers or?

rburing gravatar imagerburing ( 2020-02-22 17:10:38 -0500 )edit

The nature of the entries should not matter. For the problem to make sense you only need to be able to test for equality of entries and negates an entry.

vdelecroix gravatar imagevdelecroix ( 2020-02-23 03:27:57 -0500 )edit

1 answer

Sort by » oldest newest most voted
0

answered 2020-02-23 03:48:10 -0500

vdelecroix gravatar image

updated 2020-02-23 03:58:14 -0500

If you remove "signed" from your question this is equivalent to the isomorphism problem of vertex and edge labeled directed graphs. To do that in Sage let us define the following auxilliary function that turns a matrix into a (edge labeled) directed graph

def mat_to_dig(A):
    n = A.nrows()
    G = DiGraph(loops=False, multiedges=False)
    for i in range(n):
        for j in range(n):
            if A[i,j]:
                G.add_edge(i, j, A[i,j])
    return G

Now, (assuming that I care about matrix with 0 on the diagonal)

sage: A = matrix(4, [0,1,2,3,4,0,5,6,7,8,0,9,10,11,12,0])
sage: A
[ 0   1   2  3]
[ 4   0   5  6]
[ 7   8   0  9]
[10 11 12  0]
sage: p = Permutation('(1,3)(2,4)')
sage: B = copy(A)
sage: B.permute_rows_and_columns(p,p)
sage: B
[ 0   9   7  8]
[12  0 10 11]
[ 2   3   0  1]
[ 5   6   4  0]
sage: G = mat_to_dig(A)
sage: H = mat_to_dig(B)
sage: G.is_isomorphic(H, edge_labels=True, certificate=True)
(True, {0: 2, 1: 3, 2: 0, 3: 1})

The dictionary {0: 2, 1: 3, 2: 0, 3: 1} gives you the permutation to be performed namely 0↦2, 1↦3, 2↦0, 3↦1.

Now, if you want to consider the signed version what you can do is to replace your graph by a "signed graph" in which the vertices are doubled.

def mat_to_signed_dig(A):
    n = A.nrows()
    G = DiGraph(loops=False, multiedges=False)
    for i in range(n):
        for j in range(n):
            if A[i,j]:
                G.add_edge(i, j, A[i,j])
                G.add_edge(n+i, n+j, A[i,j])
                G.add_edge(i, n+j, -A[i,j])
                G.add_edge(n+i, j, -A[i,j])
    return G

Then

sage: A = matrix(4, [0,1,2,3,4,0,5,6,7,8,0,9,10,11,12,0])
sage: p = matrix(Permutation('(1,3)(2,4)')) * diagonal_matrix([1,-1,-1,1])
sage: B = p * A * ~p
sage: B
[  0  -9  -7   8]
[-12   0  10 -11]
[ -2   3   0  -1]
[  5  -6  -4   0]
sage: G = mat_to_signed_dig(A)
sage: H = mat_to_signed_dig(B)
sage: G.is_isomorphic(H, edge_labels=True, certificate=True)
(True, {0: 6, 1: 3, 2: 0, 3: 5, 4: 2, 5: 7, 6: 4, 7: 1})

The dictionary now corresponds to a signed permutation where i+4 should be thought as -i. So it should be interpreted as the signed permutation +0↦-2, +1↦+3, +2↦+0, +3↦-1, -0↦+2, -1↦-3, -2↦-0, -3->+1.

edit flag offensive delete link more

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: 2020-02-22 13:44:59 -0500

Seen: 80 times

Last updated: Feb 23