Ask Your Question
2

Solving system of linear Diophantine equations

asked 2014-08-02 12:17:47 +0200

arunayyar gravatar image

updated 2014-08-03 02:27:08 +0200

slelievre gravatar image

I have an $m \times n$ integer matrix $A$ with $m>n$, and a set $S \subset \mathbb{Z}$, for example $S=\{-1,0,1\}$.

I want to enumerate all possible $X \in S^n$ such that $AX=0$.

I tried using smith_form(), but then i could not figure out how to force the solution to belong to elements of $S$.


EDIT. Thank you Dima for the solution. It works well. I am adding an example here to illustrate your solution.

lb = -1
ub = 1
A = matrix(ZZ, [(8,2,10,0,12,2,0), (4,6,9,1,14,5,2), (2,0,1,1,0,1,0), (2,1,3,0,4,0,1)])
eq1 = [(0,8,2,10,0,12,2,0), (0,4,6,9,1,14,5,2), (0,2,0,1,1,0,1,0), (0,2,1,3,0,4,0,1)]
ieq1 = [(-lb,1,0,0,0,0,0,0), (ub,-1,0,0,0,0,0,0),
         (-lb,0,1,0,0,0,0,0), (ub,0,-1,0,0,0,0,0),
         (-lb,0,0,1,0,0,0,0), (ub,0,0,-1,0,0,0,0),
         (-lb,0,0,0,1,0,0,0), (ub,0,0,0,-1,0,0,0),
         (-lb,0,0,0,0,1,0,0), (ub,0,0,0,0,-1,0,0),
         (-lb,0,0,0,0,0,1,0), (ub,0,0,0,0,0,-1,0),
         (-lb,0,0,0,0,0,0,1), (ub,0,0,0,0,0,0,-1)]
p = Polyhedron(eqns=eq1, ieqs=ieq1, base_ring=QQ)
p.integral_points()

returns the answer

((-1, -1, 1, 1, 0, 0, 0),
 (0, -1, -1, 1, 1, 0, 0),
 (0, -1, 0, -1, 0, 1,1), 
 (0, 0, 0, 0, 0, 0, 0),
 (0, 1, 0, 1, 0, -1, -1),
 (0, 1, 1, -1, -1, 0,0),
 (1, 1, -1, -1, 0, 0, 0))

which is exactly what i needed. Thanks again.

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
3

answered 2014-08-02 12:31:20 +0200

You can enumerate integer points in a polytope using Sage. Create the polytope $P$ using $A$ and inequalities specifying $S$, i.e. $-1\leq x_i\leq 1$ for all $i$. (look up docs on Polyhedron). Then call P.integral_points()

edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

Asked: 2014-08-02 12:17:47 +0200

Seen: 2,329 times

Last updated: Aug 03 '14