Ask Your Question

Is there a routine to find a integer base?

asked 2011-11-26 05:59:56 -0500

roland gravatar image

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):



How to find (x,y) such that [(xaa[i]+ybb[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

edit retag flag offensive close merge delete

2 answers

Sort by » oldest newest most voted

answered 2011-11-26 17:38:52 -0500

Jason Grout gravatar image

updated 2011-11-26 17:43:43 -0500

To 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
sage: M7.coordinates(cc)
[3, 3]
edit flag offensive delete link more

answered 2011-11-26 13:45:54 -0500

You 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
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 (see also this) 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.

edit flag offensive delete link more


Jason 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.

roland gravatar imageroland ( 2011-11-27 07:13:26 -0500 )edit

What 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.

John Palmieri gravatar imageJohn Palmieri ( 2011-11-27 08:44:28 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2011-11-26 05:59:56 -0500

Seen: 229 times

Last updated: Nov 26 '11