ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 12 Oct 2020 17:07:44 +0200"how to test if two matrices are similar by a signed permutation matrix" code sagehttps://ask.sagemath.org/question/50025/how-to-test-if-two-matrices-are-similar-by-a-signed-permutation-matrix-code-sage/"how to test if two matrices are similar by a signed permutation matrix" code sageSat, 22 Feb 2020 20:44:59 +0100https://ask.sagemath.org/question/50025/how-to-test-if-two-matrices-are-similar-by-a-signed-permutation-matrix-code-sage/Comment by rburing for <p>"how to test if two matrices are similar by a signed permutation matrix" code sage</p>
https://ask.sagemath.org/question/50025/how-to-test-if-two-matrices-are-similar-by-a-signed-permutation-matrix-code-sage/?comment=50028#post-id-50028What are the entries of the matrices? Real numbers or integers or?Sun, 23 Feb 2020 00:10:38 +0100https://ask.sagemath.org/question/50025/how-to-test-if-two-matrices-are-similar-by-a-signed-permutation-matrix-code-sage/?comment=50028#post-id-50028Comment by imy for <p>"how to test if two matrices are similar by a signed permutation matrix" code sage</p>
https://ask.sagemath.org/question/50025/how-to-test-if-two-matrices-are-similar-by-a-signed-permutation-matrix-code-sage/?comment=53771#post-id-53771the matrices are symmetric seidl matrices of simple graphs. zero on the diagonal , 1 and -1 off the diagonalThu, 08 Oct 2020 00:53:27 +0200https://ask.sagemath.org/question/50025/how-to-test-if-two-matrices-are-similar-by-a-signed-permutation-matrix-code-sage/?comment=53771#post-id-53771Comment by vdelecroix for <p>"how to test if two matrices are similar by a signed permutation matrix" code sage</p>
https://ask.sagemath.org/question/50025/how-to-test-if-two-matrices-are-similar-by-a-signed-permutation-matrix-code-sage/?comment=50040#post-id-50040The 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.Sun, 23 Feb 2020 10:27:57 +0100https://ask.sagemath.org/question/50025/how-to-test-if-two-matrices-are-similar-by-a-signed-permutation-matrix-code-sage/?comment=50040#post-id-50040Comment by imy for <p>"how to test if two matrices are similar by a signed permutation matrix" code sage</p>
https://ask.sagemath.org/question/50025/how-to-test-if-two-matrices-are-similar-by-a-signed-permutation-matrix-code-sage/?comment=53772#post-id-53772let A and B the seidel adjacency matrices of two simple graphs. How to write a code in sageMath for find a signed permutation matrix which gives A and B are similarThu, 08 Oct 2020 01:01:00 +0200https://ask.sagemath.org/question/50025/how-to-test-if-two-matrices-are-similar-by-a-signed-permutation-matrix-code-sage/?comment=53772#post-id-53772Answer by dan_fulea for <p>"how to test if two matrices are similar by a signed permutation matrix" code sage</p>
https://ask.sagemath.org/question/50025/how-to-test-if-two-matrices-are-similar-by-a-signed-permutation-matrix-code-sage/?answer=53874#post-id-53874I gave a detailed answer to a fuzzy question by Anonymous in the link below:
[https://ask.sagemath.org/question/39515/how-to-find-the-permutation-matrix-associated-with-the-similarity-transformation-in-the-following-code/](https://ask.sagemath.org/question/39515/how-to-find-the-permutation-matrix-associated-with-the-similarity-transformation-in-the-following-code/)
(But compared to this question, the 39515 question qualifies as a detailed exposition.)
The steps would be:
- check the characteristic polynoials, if there is no match, we can stop here.
- build the eigenvalues, sort them somehow, if there is no match, stop here.
- build the jordan decomposition and match the eigenvectors, allowing rescaling on the one side, and permutations of rows on the other side. A rough match can be done by first rescaling in the two Jordan base change matrices, so that the maximal absolute value occurs for the entry $1$ in each column.Mon, 12 Oct 2020 17:07:44 +0200https://ask.sagemath.org/question/50025/how-to-test-if-two-matrices-are-similar-by-a-signed-permutation-matrix-code-sage/?answer=53874#post-id-53874Answer by vdelecroix for <p>"how to test if two matrices are similar by a signed permutation matrix" code sage</p>
https://ask.sagemath.org/question/50025/how-to-test-if-two-matrices-are-similar-by-a-signed-permutation-matrix-code-sage/?answer=50042#post-id-50042If 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`.Sun, 23 Feb 2020 10:48:10 +0100https://ask.sagemath.org/question/50025/how-to-test-if-two-matrices-are-similar-by-a-signed-permutation-matrix-code-sage/?answer=50042#post-id-50042Comment by imy for <p>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</p>
<pre><code>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
</code></pre>
<p>Now, (assuming that I care about matrix with 0 on the diagonal)</p>
<pre><code>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})
</code></pre>
<p>The dictionary <code>{0: 2, 1: 3, 2: 0, 3: 1}</code> gives you the permutation to be performed namely <code>0↦2, 1↦3, 2↦0, 3↦1</code>.</p>
<p>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. </p>
<pre><code>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
</code></pre>
<p>Then</p>
<pre><code>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})
</code></pre>
<p>The dictionary now corresponds to a signed permutation where <code>i+4</code> should be thought as <code>-i</code>. So it should be interpreted as the signed permutation <code>+0↦-2, +1↦+3, +2↦+0, +3↦-1, -0↦+2, -1↦-3, -2↦-0, -3->+1</code>.</p>
https://ask.sagemath.org/question/50025/how-to-test-if-two-matrices-are-similar-by-a-signed-permutation-matrix-code-sage/?comment=53793#post-id-53793Let A and B be two seidel adjacency matrices of simple graphs without loops. The matrices A and B are similar via a signed permutation matrix.
Please, how I can find that matrix.??Fri, 09 Oct 2020 00:36:17 +0200https://ask.sagemath.org/question/50025/how-to-test-if-two-matrices-are-similar-by-a-signed-permutation-matrix-code-sage/?comment=53793#post-id-53793