Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

solving a matrix equation in the integers.

I'm trying to use sage to solve an expression of the form $xS = y$ for a fixed integer matrix $S$ and a fixed integer vector $y$. I need my solution vector $x$ to also have integer coefficients.

How I'm currently doing this is by using the mixed integer linear programming tool and my code looks something like this.

p = MixedIntegerLinearProgram(maximization = True, solver = "GLPK")
x = p.new_variable(integer = True, nonnegative = True)
p.add_constraint( x*S == y) #here the vector can be anything
p.add_constraint( x[25] <= 2020 )
p.set_objective( x[25] )

The issue I have here is that the objective and the constraint are arbitrary and were just picked so that the space that the MixedIntegerLinearProgram function is trying to optimize over has a "feasable solution" (sage's words not mine). Is there a better way to find a solution to $xS = y$ in the integers (i.e a different function or package supported by sage) and if not, is there a way to have my constarint be to make the norm of the vector as small as possible (so that I'm not just artificially picking an entry to optimize my search over)?