# How can I get an invertible matrix X with integral entries and AX=XB, where A and B are matrices with integral entries.

Let M be the set of all n by n matrices with integral entries.

For A and B in M, how can I get an invertible matrix X in M with AX=XB in Sage.

I can partially solve that problem in GAP following method.

• V={ X in Mn(QQ) | AX=XB }

(V is a vector space over QQ)

• Basis(V)={B_1,B_2, ..., B_k}

(I wonder which number k it is according to the changes of A and B.)

• Make X=a_1 * B_1 + ... +a_k * B_k , a_i in some interval in ZZ.

• Check two things which are X in Mn(ZZ) and the existence of the inverse of X in Mn(ZZ).

I can find such X for some easy matrices A,B.

How can I solve this problem in Sage?

Thanks.

edit retag close merge delete

Sort by » oldest newest most voted

Hello,

It is sad that in Sage, it is not yet possible to play with the vector space of matrices. One workaround is to use tensorial product which does exactly what you want. Let us take the following example

sage: A = matrix([[0,0,1],[1,1,0],[1,0,-3]])
sage: B = matrix([[1,0,-1],[0,0,1],[0,2,2]])

sage: AA = A.tensor_product(identity_matrix(3))
sage: BB = identity_matrix(3).tensor_product(B.transpose())


The matrices AA and BB are 9x9 matrices that correspond to matrix multiplication seen on vectors:

sage: print AA
[ 0  0  0| 0  0  0| 1  0  0]
[ 0  0  0| 0  0  0| 0  1  0]
[ 0  0  0| 0  0  0| 0  0  1]
[--------+--------+--------]
[ 1  0  0| 1  0  0| 0  0  0]
[ 0  1  0| 0  1  0| 0  0  0]
[ 0  0  1| 0  0  1| 0  0  0]
[--------+--------+--------]
[ 1  0  0| 0  0  0|-3  0  0]
[ 0  1  0| 0  0  0| 0 -3  0]
[ 0  0  1| 0  0  0| 0  0 -3]


You can check

sage: X = matrix([[1,0,0],[1,1,1],[1,2,-1]])
sage: v = vector(X.list())
sage: (A*X).list() == (AA*v).list()
True
sage: (X*B).list() == (BB*v).list()
True


Then you can solve your problem with standard linear algebra

sage: C = AA - BB
sage: V = [matrix(3,3,v.list()) for v in C.right_kernel().basis()]
sage: m = V[0]
sage: print m
[0 0 0]
[3 2 1]
[0 0 0]
sage: A * m == m * B
True


Of course you still have to play with the basis to find an invertible solution... but it might not exists as in my example above.

Vincent

more

Oh, I see. Your method help me to obtain a basis for V. :) Using tensor_product is interesting. Thanks for giving good advice. :)

( 2014-10-16 02:38:10 -0500 )edit