solving integer linear equations

[tvn]

is there something in SAGE that solves integer linear equations ?   essentially like normal equation solving but the results must be integers.  Thanks  , 

[Volker Braun]

sage: m = random_matrix(ZZ, 3)

sage: m.smith_form()

[William Stein]

Hi,

I wrote some code (which was rather tricky to write!) that can find the kernel of a linear map over Z.  This will give all solutions S to Ax = 0, if A is an integer matrix.   This is useful since if you have any particular solution x to Ax=b, then all other solutions are of the form x + s for s in S.

sage: a = matrix(ZZ,2,2,[2,4, 4,8]); a

[2 4] [4 8]

sage: a.kernel()

Free module of degree 2 and rank 1 over Integer Ring Echelon basis matrix: [ 2 -1]

sage: a.kernel().basis()

[ (2, -1) ]

Regarding finding a particular solution, just find a solution over QQ (easy using Sage's solve_right()) and clear denominators. 

The above will make sense to somebody who knows linear algebra, but might not otherwise. 

William

On Thu, Apr 25, 2013 at 12:57 PM, tvn <nguyent...@gmail.com> wrote:

is there something in SAGE that solves integer linear equations ?   essentially like normal equation solving but the results must be integers.  Thanks  , 

--
You received this message because you are subscribed to the Google Groups "sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.
To post to this group, send email to sage-s...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org