On 9/14/12 10:18 AM, Victor Miller wrote:
Since the OP's problem has no inequalities (such as requiring that all
integers in question are non-negative), it is solved by using Hermite
normal form.
If A is an m by n integer matrix, the Hermite normal form of A is an
upper triangular integer matrix H (also m by n), along with an m by m
integer matrix of determinant 1 (i.e. it's invertible) so that H = U A.
So the original equation A x = b becomes (after multiplying by U): H x =
U b, for which it's easy to get the general solution (just back solve.
If you ever get a non-integer by dividing there are no solutions).
Since U is invertible, multiplying the equation by U doesn't introduce
spurious solutions.
And for completeness, you can get hermite form by using the
.hermite_form method:
sage: a=random_matrix(ZZ,5)
sage: a.hermite_form()
[ 1 0 0 0 35]
[ 0 1 0 0 73]
[ 0 0 1 0 40]
[ 0 0 0 1 51]
[ 0 0 0 0 103]
sage: a.hermite_form(transformation=True)
(
[ 1 0 0 0 35] [ -37 -108 28 -10 97]
[ 0 1 0 0 73] [ -77 -224 58 -21 201]
[ 0 0 1 0 40] [ -44 -128 33 -12 115]
[ 0 0 0 1 51] [ -59 -172 44 -16 154]
[ 0 0 0 0 103], [-110 -321 83 -30 288]
)
Thanks,
Jason
--
You received this message because you are subscribed to the Google Groups
"sage-support" group.
To post to this group, send email to sage-support@googlegroups.com.
To unsubscribe from this group, send email to
sage-support+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support?hl=en.
