Ask Your Question

Revision history [back]

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.