# 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 [(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)?

edit retag close merge delete

Sort by Â» oldest newest most voted

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

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.

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

( 2011-11-27 08:44:28 -0500 )edit

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
True
sage: M7.coordinates(cc)
[3, 3]

more