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 16:59:49 +0200How to find the permutation matrix associated with the similarity transformation in the following codehttps://ask.sagemath.org/question/39515/how-to-find-the-permutation-matrix-associated-with-the-similarity-transformation-in-the-following-code/
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.
Mon, 13 Nov 2017 19:23:18 +0100https://ask.sagemath.org/question/39515/how-to-find-the-permutation-matrix-associated-with-the-similarity-transformation-in-the-following-code/Comment by B r u n o for <p>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])</p>
<p>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])</p>
<p>the matrices m,j are similar via a permutation matrix. How I can find that matrix.</p>
https://ask.sagemath.org/question/39515/how-to-find-the-permutation-matrix-associated-with-the-similarity-transformation-in-the-following-code/?comment=39516#post-id-39516Have you read the answers to [this question](https://ask.sagemath.org/question/39355/how-to-find-the-similarity-matrix-between-two-similar-matrices/), in particular [Dan's](https://ask.sagemath.org/question/39355/how-to-find-the-similarity-matrix-between-two-similar-matrices/?answer=39373#post-id-39373)?Mon, 13 Nov 2017 19:51:29 +0100https://ask.sagemath.org/question/39515/how-to-find-the-permutation-matrix-associated-with-the-similarity-transformation-in-the-following-code/?comment=39516#post-id-39516Comment by dan_fulea for <p>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])</p>
<p>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])</p>
<p>the matrices m,j are similar via a permutation matrix. How I can find that matrix.</p>
https://ask.sagemath.org/question/39515/how-to-find-the-permutation-matrix-associated-with-the-similarity-transformation-in-the-following-code/?comment=39522#post-id-39522The 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?**Tue, 14 Nov 2017 00:54:36 +0100https://ask.sagemath.org/question/39515/how-to-find-the-permutation-matrix-associated-with-the-similarity-transformation-in-the-following-code/?comment=39522#post-id-39522Comment by rewi for <p>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])</p>
<p>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])</p>
<p>the matrices m,j are similar via a permutation matrix. How I can find that matrix.</p>
https://ask.sagemath.org/question/39515/how-to-find-the-permutation-matrix-associated-with-the-similarity-transformation-in-the-following-code/?comment=39528#post-id-39528m = 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 collectionsTue, 14 Nov 2017 08:47:43 +0100https://ask.sagemath.org/question/39515/how-to-find-the-permutation-matrix-associated-with-the-similarity-transformation-in-the-following-code/?comment=39528#post-id-39528Comment by imy for <p>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])</p>
<p>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])</p>
<p>the matrices m,j are similar via a permutation matrix. How I can find that matrix.</p>
https://ask.sagemath.org/question/39515/how-to-find-the-permutation-matrix-associated-with-the-similarity-transformation-in-the-following-code/?comment=53792#post-id-53792The matrices A and B are seidel adjacency matrices, similar via a signed permutation matrix.
Please, how I can find that matrix.Fri, 09 Oct 2020 00:29:11 +0200https://ask.sagemath.org/question/39515/how-to-find-the-permutation-matrix-associated-with-the-similarity-transformation-in-the-following-code/?comment=53792#post-id-53792Answer by dan_fulea for <p>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])</p>
<p>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])</p>
<p>the matrices m,j are similar via a permutation matrix. How I can find that matrix.</p>
https://ask.sagemath.org/question/39515/how-to-find-the-permutation-matrix-associated-with-the-similarity-transformation-in-the-following-code/?answer=53873#post-id-53873Here 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_SD\Delta_S^{-1}$. So we can replace the above $S$ by $S\Delta_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
$$
(S\Delta_S)^{-1}M(S\Delta_S) = D = (T\Delta_T)^{-1}N(T\Delta_T)\ .
$$
We get rid of the expression $D$ "in the middle", and obtain the general form for an intertwiner:
$$
(T\Delta_T)(S\Delta_S)^{-1}\ M\ (S\Delta_S)(T\Delta_T)^{-1} = N\ .
$$
So we want to get a (**signed** - came in later) permutation matrix $P$ in:
$$
(T\Delta_T)(S\Delta_S)^{-1}= P\ .
$$
Equivalently:
$$
T\Delta_T= PS\Delta_S\ .
$$
We can arrange this (iff we can) with only one diagonal matrix $\Delta$,
$$
T\Delta = 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.)Mon, 12 Oct 2020 16:59:49 +0200https://ask.sagemath.org/question/39515/how-to-find-the-permutation-matrix-associated-with-the-similarity-transformation-in-the-following-code/?answer=53873#post-id-53873