# 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

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

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.