ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 16 Oct 2014 02:38:10 -0500How can I get an invertible matrix X with integral entries and AX=XB, where A and B are matrices with integral entries.http://ask.sagemath.org/question/24467/how-can-i-get-an-invertible-matrix-x-with-integral-entries-and-axxb-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.Sun, 12 Oct 2014 01:09:43 -0500http://ask.sagemath.org/question/24467/how-can-i-get-an-invertible-matrix-x-with-integral-entries-and-axxb-where-a-and-b-are-matrices-with-integral-entries/Answer by vdelecroix for <p>Let M be the set of all n by n matrices with integral entries.</p>
<p>For A and B in M, how can I get an invertible matrix X in M with AX=XB in Sage.</p>
<p>I can partially solve that problem in GAP following method.</p>
<ul>
<li>V={ X in Mn(QQ) | AX=XB } </li>
</ul>
<p>(V is a vector space over QQ)</p>
<ul>
<li>Basis(V)={B_1,B_2, ..., B_k}</li>
</ul>
<p>(I wonder which number k it is according to the changes of A and B.)</p>
<ul>
<li><p>Make X=a_1 * B_1 + ... +a_k * B_k , a_i in some interval in ZZ.</p></li>
<li><p>Check two things which are X in Mn(ZZ) and the existence of the inverse of X in Mn(ZZ).</p></li>
</ul>
<p>I can find such X for some easy matrices A,B.</p>
<p>How can I solve this problem in Sage?</p>
<p>Thanks.</p>
http://ask.sagemath.org/question/24467/how-can-i-get-an-invertible-matrix-x-with-integral-entries-and-axxb-where-a-and-b-are-matrices-with-integral-entries/?answer=24470#post-id-24470Hello,
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.
VincentSun, 12 Oct 2014 17:11:52 -0500http://ask.sagemath.org/question/24467/how-can-i-get-an-invertible-matrix-x-with-integral-entries-and-axxb-where-a-and-b-are-matrices-with-integral-entries/?answer=24470#post-id-24470Comment by Semin for <p>Hello,</p>
<p>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</p>
<pre><code>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())
</code></pre>
<p>The matrices AA and BB are 9x9 matrices that correspond to matrix multiplication seen on vectors:</p>
<pre><code>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]
</code></pre>
<p>You can check</p>
<pre><code>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
</code></pre>
<p>Then you can solve your problem with standard linear algebra</p>
<pre><code>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
</code></pre>
<p>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.</p>
<p>Vincent</p>
http://ask.sagemath.org/question/24467/how-can-i-get-an-invertible-matrix-x-with-integral-entries-and-axxb-where-a-and-b-are-matrices-with-integral-entries/?comment=24492#post-id-24492Oh, I see. Your method help me to obtain a basis for V. :) Using tensor_product is interesting. Thanks for giving good advice. :)Thu, 16 Oct 2014 02:38:10 -0500http://ask.sagemath.org/question/24467/how-can-i-get-an-invertible-matrix-x-with-integral-entries-and-axxb-where-a-and-b-are-matrices-with-integral-entries/?comment=24492#post-id-24492