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.Sun, 27 Nov 2011 08:44:28 -0600Is there a routine to find a integer base?http://ask.sagemath.org/question/8511/is-there-a-routine-to-find-a-integer-base/Hi, Sage fans. Probably a simple Sage routine does the job, but I tried hard to find it but yet without successÂ…
My problem. Consider two rows (in QQ):
aa=[0,-1,1/5,-1/19,1/15,-35/57,7/5]
bb=[1,0,-6/5,20/19,-7/5,56/19,-12/5]
How to find (x,y) such that [(x*aa[i]+y*bb[i]) for i in xrange(7)] yields the row [3, -3, -3, 3, -4, 7, -3] with the smallest set integers?
For the above example (x,y)=(3,3) does the job, but is there a general routine to find the optimal (x,y)?
Many thanks in advance for your suggestions!
Roland
Sat, 26 Nov 2011 05:59:56 -0600http://ask.sagemath.org/question/8511/is-there-a-routine-to-find-a-integer-base/Answer by Jason Grout for <p>Hi, Sage fans. Probably a simple Sage routine does the job, but I tried hard to find it but yet without successÂ… </p>
<p>My problem. Consider two rows (in QQ):</p>
<p>aa=[0,-1,1/5,-1/19,1/15,-35/57,7/5]</p>
<p>bb=[1,0,-6/5,20/19,-7/5,56/19,-12/5]</p>
<p>How to find (x,y) such that [(x<em>aa[i]+y</em>bb[i]) for i in xrange(7)] yields the row [3, -3, -3, 3, -4, 7, -3] with the smallest set integers?</p>
<p>For the above example (x,y)=(3,3) does the job, but is there a general routine to find the optimal (x,y)?</p>
<p>Many thanks in advance for your suggestions!
Roland</p>
http://ask.sagemath.org/question/8511/is-there-a-routine-to-find-a-integer-base/?answer=12943#post-id-12943To answer John, you can use span_of_basis to preserve the basis:
sage: aa = [0,-1,1/5,-1/19,1/15,-35/57,7/5]
sage: bb = [1,0,-6/5,20/19,-7/5,56/19,-12/5]
sage: cc = [3, -3, -3, 3, -4, 7, -3]
sage: M7=(ZZ^7).span_of_basis([vector(aa),vector(bb)])
sage: M7
Free module of degree 7 and rank 2 over Integer Ring
User basis matrix:
[ 0 -1 1/5 -1/19 1/15 -35/57 7/5]
[ 1 0 -6/5 20/19 -7/5 56/19 -12/5]
sage: vector(cc) in M7
True
sage: M7.coordinates(cc)
[3, 3]
Sat, 26 Nov 2011 17:38:52 -0600http://ask.sagemath.org/question/8511/is-there-a-routine-to-find-a-integer-base/?answer=12943#post-id-12943Answer by John Palmieri for <p>Hi, Sage fans. Probably a simple Sage routine does the job, but I tried hard to find it but yet without successÂ… </p>
<p>My problem. Consider two rows (in QQ):</p>
<p>aa=[0,-1,1/5,-1/19,1/15,-35/57,7/5]</p>
<p>bb=[1,0,-6/5,20/19,-7/5,56/19,-12/5]</p>
<p>How to find (x,y) such that [(x<em>aa[i]+y</em>bb[i]) for i in xrange(7)] yields the row [3, -3, -3, 3, -4, 7, -3] with the smallest set integers?</p>
<p>For the above example (x,y)=(3,3) does the job, but is there a general routine to find the optimal (x,y)?</p>
<p>Many thanks in advance for your suggestions!
Roland</p>
http://ask.sagemath.org/question/8511/is-there-a-routine-to-find-a-integer-base/?answer=12942#post-id-12942You might need to modify your question: the two vectors `aa` and `bb` are linearly independent, so if there is a solution $(x,y)$ to $xa + yb = c$, then it is unique. So asking for an "optimal" solution is not meaningful.
To solve the question as asked:
sage: aa = [0,-1,1/5,-1/19,1/15,-35/57,7/5]
sage: bb = [1,0,-6/5,20/19,-7/5,56/19,-12/5]
sage: cc = [3, -3, -3, 3, -4, 7, -3]
sage: M = matrix([aa, bb])
sage: M.solve_left(cc) # turns out cc has integer coordinates w.r.t. aa, bb
(3, 3)
Maybe something closer to the question you're really asking: if `aa` and `bb` are vectors with rational entries, how do you tell if another vector `cc` is an integer linear combination of them?
First create a free module over the integers with the desired basis:
sage: M7 = (ZZ^7).span([vector(aa), vector(bb)])
sage: M7
Free module of degree 7 and rank 2 over Integer Ring
Echelon basis matrix:
[ 1 0 -6/5 20/19 -7/5 56/19 -12/5]
[ 0 1 -1/5 1/19 -1/15 35/57 -7/5]
sage: M7.basis()
[
(1, 0, -6/5, 20/19, -7/5, 56/19, -12/5),
(0, 1, -1/5, 1/19, -1/15, 35/57, -7/5)
]
Note that M7 is using `bb` and `-aa` for a basis, not `aa` and `bb`, so when we ask for coordinates, they won't be quite right.
sage: cc in M7 # cc is an integer linear combination of aa and bb
True
sage: M7.coordinates(cc) # coords with respect to the basis (bb, -aa)
[3, -3]
I don't know how to force it to use `aa` and `bb` for the basis, but there might be something in the [free_module code](http://sagemath.org/doc/reference/sage/modules/free_module.html) (see also [this](http://sagemath.org/doc/reference/sage/modules/free_module_element.html)) to do this. Short of that, you can just ask for coordinates for `aa` and `bb`, form a change-of-basis matrix, and then multiply that matrix by the coordinates with respect to the basis that Sage chose.
Sat, 26 Nov 2011 13:45:54 -0600http://ask.sagemath.org/question/8511/is-there-a-routine-to-find-a-integer-base/?answer=12942#post-id-12942Comment by roland for <p>You might need to modify your question: the two vectors <code>aa</code> and <code>bb</code> are linearly independent, so if there is a solution $(x,y)$ to $xa + yb = c$, then it is unique. So asking for an "optimal" solution is not meaningful.</p>
<p>To solve the question as asked:</p>
<pre><code>sage: aa = [0,-1,1/5,-1/19,1/15,-35/57,7/5]
sage: bb = [1,0,-6/5,20/19,-7/5,56/19,-12/5]
sage: cc = [3, -3, -3, 3, -4, 7, -3]
sage: M = matrix([aa, bb])
sage: M.solve_left(cc) # turns out cc has integer coordinates w.r.t. aa, bb
(3, 3)
</code></pre>
<p>Maybe something closer to the question you're really asking: if <code>aa</code> and <code>bb</code> are vectors with rational entries, how do you tell if another vector <code>cc</code> is an integer linear combination of them?</p>
<p>First create a free module over the integers with the desired basis:</p>
<pre><code>sage: M7 = (ZZ^7).span([vector(aa), vector(bb)])
sage: M7
Free module of degree 7 and rank 2 over Integer Ring
Echelon basis matrix:
[ 1 0 -6/5 20/19 -7/5 56/19 -12/5]
[ 0 1 -1/5 1/19 -1/15 35/57 -7/5]
sage: M7.basis()
[
(1, 0, -6/5, 20/19, -7/5, 56/19, -12/5),
(0, 1, -1/5, 1/19, -1/15, 35/57, -7/5)
]
</code></pre>
<p>Note that M7 is using <code>bb</code> and <code>-aa</code> for a basis, not <code>aa</code> and <code>bb</code>, so when we ask for coordinates, they won't be quite right.</p>
<pre><code>sage: cc in M7 # cc is an integer linear combination of aa and bb
True
sage: M7.coordinates(cc) # coords with respect to the basis (bb, -aa)
[3, -3]
</code></pre>
<p>I don't know how to force it to use <code>aa</code> and <code>bb</code> for the basis, but there might be something in the <a href="http://sagemath.org/doc/reference/sage/modules/free_module.html">free_module code</a> (see also <a href="http://sagemath.org/doc/reference/sage/modules/free_module_element.html">this</a>) to do this. Short of that, you can just ask for coordinates for <code>aa</code> and <code>bb</code>, form a change-of-basis matrix, and then multiply that matrix by the coordinates with respect to the basis that Sage chose.</p>
http://ask.sagemath.org/question/8511/is-there-a-routine-to-find-a-integer-base/?comment=20812#post-id-20812Jason and John, thanks for your reply. However, I probably was not quite clear regarding my question. You both assumed that I would know cc, but what is the answer to my question if you don't now cc?
More general: I have to rows (in QQ), what is the smallest row of integers I can get?
It is always possible to generate a row with integers, but the hard part is that I'm looking for the smallest.
Sun, 27 Nov 2011 07:13:26 -0600http://ask.sagemath.org/question/8511/is-there-a-routine-to-find-a-integer-base/?comment=20812#post-id-20812Comment by John Palmieri for <p>You might need to modify your question: the two vectors <code>aa</code> and <code>bb</code> are linearly independent, so if there is a solution $(x,y)$ to $xa + yb = c$, then it is unique. So asking for an "optimal" solution is not meaningful.</p>
<p>To solve the question as asked:</p>
<pre><code>sage: aa = [0,-1,1/5,-1/19,1/15,-35/57,7/5]
sage: bb = [1,0,-6/5,20/19,-7/5,56/19,-12/5]
sage: cc = [3, -3, -3, 3, -4, 7, -3]
sage: M = matrix([aa, bb])
sage: M.solve_left(cc) # turns out cc has integer coordinates w.r.t. aa, bb
(3, 3)
</code></pre>
<p>Maybe something closer to the question you're really asking: if <code>aa</code> and <code>bb</code> are vectors with rational entries, how do you tell if another vector <code>cc</code> is an integer linear combination of them?</p>
<p>First create a free module over the integers with the desired basis:</p>
<pre><code>sage: M7 = (ZZ^7).span([vector(aa), vector(bb)])
sage: M7
Free module of degree 7 and rank 2 over Integer Ring
Echelon basis matrix:
[ 1 0 -6/5 20/19 -7/5 56/19 -12/5]
[ 0 1 -1/5 1/19 -1/15 35/57 -7/5]
sage: M7.basis()
[
(1, 0, -6/5, 20/19, -7/5, 56/19, -12/5),
(0, 1, -1/5, 1/19, -1/15, 35/57, -7/5)
]
</code></pre>
<p>Note that M7 is using <code>bb</code> and <code>-aa</code> for a basis, not <code>aa</code> and <code>bb</code>, so when we ask for coordinates, they won't be quite right.</p>
<pre><code>sage: cc in M7 # cc is an integer linear combination of aa and bb
True
sage: M7.coordinates(cc) # coords with respect to the basis (bb, -aa)
[3, -3]
</code></pre>
<p>I don't know how to force it to use <code>aa</code> and <code>bb</code> for the basis, but there might be something in the <a href="http://sagemath.org/doc/reference/sage/modules/free_module.html">free_module code</a> (see also <a href="http://sagemath.org/doc/reference/sage/modules/free_module_element.html">this</a>) to do this. Short of that, you can just ask for coordinates for <code>aa</code> and <code>bb</code>, form a change-of-basis matrix, and then multiply that matrix by the coordinates with respect to the basis that Sage chose.</p>
http://ask.sagemath.org/question/8511/is-there-a-routine-to-find-a-integer-base/?comment=20811#post-id-20811What do you mean by "smallest row" of integers? You can define M7 as either Jason or I suggested, and then do 'M7.intersection(ZZ^7)' to find the collection of all integer vectors which are integer linear combinations of aa and bb. A basis for that intersection consists of two vectors which are "small" in some sense, and indeed the smallest possible in some sense.Sun, 27 Nov 2011 08:44:28 -0600http://ask.sagemath.org/question/8511/is-there-a-routine-to-find-a-integer-base/?comment=20811#post-id-20811