# How to find the permutation matrix associated with the similarity transformation in the following code

Anonymous

m = matrix(QQbar,6,[2,-1,-I,0,0,0, -1,2,-1,0,0,0,i,-1,3,-1,0,0, 0,0,-1,2,-1,0, 0,0,0,-1,2,-1, 0,0,0,0,-1,1])

j=matrix(QQbar,6,[2,-1,0,-I,0,0, -1,2,-1,0,0,0,0,-1,2,-1,0,0, I,0,-1,3,0,-1, 0,0,0,0,1,-1, 0,0,0,-1,-1,2])

the matrices m,j are similar via a permutation matrix. How I can find that matrix.

edit retag close merge delete

( 2017-11-13 19:51:29 +0200 )edit

The following code searches for permutation matrices $S$ that satisfy $MS=SJ$.

F.<v> = QuadraticField( -1 )
M = matrix( F, 6,
[  2,-1,-v, 0, 0, 0,
-1, 2,-1, 0, 0, 0,
v,-1, 3,-1, 0, 0,
0, 0,-1, 2,-1, 0,
0, 0, 0,-1, 2,-1,
0, 0, 0, 0,-1, 1, ] )

J = matrix( F, 6,
[   2,-1, 0,-v, 0, 0,
-1, 2,-1, 0, 0, 0,
0,-1, 2,-1, 0, 0,
v, 0,-1, 3, 0,-1,
0, 0, 0, 0, 1,-1,
0, 0, 0,-1,-1, 2, ] )

for s in SymmetricGroup(6):
S = s.matrix()
if M*S == S*J:
print S


Nothing found.

Which is the source of the problem?

( 2017-11-14 00:54:36 +0200 )edit

m = matrix(QQbar,6,[2,-1,-I,0,0,0, -1,2,-1,0,0,0,i,-1,3,-1,0,0, 0,0,-1,2,-1,0, 0,0,0,-1,2,-1, 0,0,0,0,-1,1]) n = matrix(QQbar,6,[2,-1,0,-I,0,0,-1,2,-1,0,0,0,0,-1,2,-1,0,0,i,0,-1,3,-1,0,0,0,0,-1,2,-1, 0,0,0,0,-1,1]) Actually the problem was as follows: Suppose we find out the all possible permutation similar matrices for both the matrices m,n. Now I want to take the intersection of these two set of collections

( 2017-11-14 08:47:43 +0200 )edit

The matrices A and B are seidel adjacency matrices, similar via a signed permutation matrix. Please, how I can find that matrix.

( 2020-10-09 00:29:11 +0200 )edit

Sort by » oldest newest most voted

Here is one more try to understand the situation. First of all, we will work over $\bar{\Bbb Q}$, and introduce the two matrices, $M,N$ to fix a notation with two similar letters:

v = i
F = QQbar
M = matrix( F, 6, 6,
[  2,-1,-v, 0, 0, 0,
-1, 2,-1, 0, 0, 0,
v,-1, 3,-1, 0, 0,
0, 0,-1, 2,-1, 0,
0, 0, 0,-1, 2,-1,
0, 0, 0, 0,-1, 1, ] )

N = matrix( F, 6, 6,
[   2,-1, 0,-v, 0, 0,
-1, 2,-1, 0, 0, 0,
0,-1, 2,-1, 0, 0,
v, 0,-1, 3, 0,-1,
0, 0, 0, 0, 1,-1,
0, 0, 0,-1,-1, 2, ] )


Then indeed, their characteristic polynomials coincide.

sage: M.charpoly()
x^6 - 12*x^5 + 53*x^4 - 106*x^3 + 94*x^2 - 30*x + 2
sage: N.charpoly()
x^6 - 12*x^5 + 53*x^4 - 106*x^3 + 94*x^2 - 30*x + 2
sage: N.charpoly() == N.charpoly()
True


We can ask for the Jordan normal form of each of the two matrices.

D, S = M.jordan_form(transformation=True)
E, T = N.jordan_form(transformation=True)


And note that the two diagonal matrices D and E coincide:

sage: D == E
True


We can print D, but to fit the result on this page, i will take the numerical approximation of D:

sage: D.n(30)
[0.089198758| 0.00000000| 0.00000000| 0.00000000| 0.00000000| 0.00000000]
[-----------+-----------+-----------+-----------+-----------+-----------]
[ 0.00000000| 0.47256641| 0.00000000| 0.00000000| 0.00000000| 0.00000000]
[-----------+-----------+-----------+-----------+-----------+-----------]
[ 0.00000000| 0.00000000|  1.3956621| 0.00000000| 0.00000000| 0.00000000]
[-----------+-----------+-----------+-----------+-----------+-----------]
[ 0.00000000| 0.00000000| 0.00000000|  2.3867094| 0.00000000| 0.00000000]
[-----------+-----------+-----------+-----------+-----------+-----------]
[ 0.00000000| 0.00000000| 0.00000000| 0.00000000|  3.1882644| 0.00000000]
[-----------+-----------+-----------+-----------+-----------+-----------]
[ 0.00000000| 0.00000000| 0.00000000| 0.00000000| 0.00000000|  4.4675990]


So the roots of the characteristic polynomials of M and N coincide, are real, and are placed on the diagonal above in increasing order. Note also: $$MS=SD\ ,\qquad NT=TD\ .$$ A check:

sage: bool(M*S == S*D)
True
sage: bool(N*T == T*D)
True


So far we have the equalities: $$S^{-1}MS = D = T^{-1}NT\ .$$ The intertwiner $S$ between $M$ and $D$ is not unique, but it is unique up to multiplication with a diagonal matrix $Delta_S$. This is because of different eigenvalues on the diagonal. And of course, $D=Delta_SDDelta_S^{-1}$. So we can replace the above $S$ by $SDelta_S$, and this is the only freedom we have. The same holds "on the other side" with a diagonal matrix $Delta_T$. So, the "maximal freedom" we have is by writing $$(SDelta_S)^{-1}M(SDelta_S) = D = (TDelta_T)^{-1}N(TDelta_T)\ .$$ We get rid of the expression $D$ "in the middle", and obtain the general form for an intertwiner: $$(TDelta_T)(SDelta_S)^{-1}\ M\ (SDelta_S)(TDelta_T)^{-1} = N\ .$$ So we want to get a (signed - came in later) permutation matrix $P$ in: $$(TDelta_T)(SDelta_S)^{-1}= P\ .$$ Equivalently: $$TDelta_T= PSDelta_S\ .$$ We can arrange this (iff we can) with only one diagonal matrix $Delta$, $$TDelta = PS\ .$$ The action of $Delta$ on $T$ is a renormalization of the column vectors.

The action of $P$ on $S$ is given by a row permutation. Such a row permutation also invariates the columns as a list. So we may want to compare the columns of $S$ and $T$. Numerically, the first column of $T$ and $S$ are:

T.columns()[0].n()
S.columns()[0].n()


Well, it is not so easy to keep order, so let us consider absolute values:

[ abs(entry) for entry in T.columns()[0].n() ]
[ abs(entry) for entry in S.columns()[0].n() ]


We obtain:

[1.00000000000000,
0.953694040309665,
1.00000000000000,
1.11348300986965,
1.50397481281530,
1.36982212753272]

[1.00000000000000,
1.00000000000000,
1.22929314902987,
1.80622358363301,
2.22204111800645,
2.43965534455263]


Again, we need a better strategy to match, so we divide by the maximal entry in the column in both cases.

sage: AS = [ max([ abs(e) for e in S.columns()[k] ]) for k in range(6) ]
sage: AT = [ max([ abs(e) for e in T.columns()[k] ]) for k in range(6) ]
sage:
....:     [ abs(entry) / AT[0] for entry in T.columns()[0].n() ]
....:     [ abs(entry) / AS[0] for entry in S.columns()[0].n() ]
....:

[0.664904752047072,
0.634115699400868,
0.664904752047072,
0.740360144586006,
1.00000000000000,
0.910801242055735]

[0.409893964011287,
0.409893964011287,
0.503879841787769,
0.740360144586006,
0.910801242055736,
1.00000000000000]


We expect a permutation of the values, but this is not the case. In this first column there are three entries that match each other, but the other three...

So we have a negative answer.

Note: Also the less structural brute force search leads to nothing.

sage: for p in SymmetricGroup(6):
....:     for d in cartesian_product([[+1, -1] for _ in range(6)]):
....:         D = diagonal_matrix(d)
....:         P = p.matrix()
....:         SP = S*P    # signed permutation
....:         if M*SP == SP*N:
....:             print(SD)


No result.

This note is here just to make clear which is the difference between an answer and an answer. The first answer is a good piece of work. (A lot to type and explain.) The second answer is close to run+copy+paste. It transposes also to questions, there is a big difference between a question and a question. In this case, more details would have been more than typing them. (Some people consider that giving details to the whole world would put every single individual researcher in the position to solve the problem on her or his own, then publish this the next day, than claim ownership of the result. This is never the case, we are in an other century, fluent information works best with pointed, complete information.)

more