Hi,
I have a matrix M and a vector r both over the integers and I want to solve the equation $ v*M = r $ over the integers. I know that there is the command v = M.solve_left(r) to a vector $v$ satisfying the equation. But how can I force it to be a vector over $\mathbb{Z}$?
If you deal with integer vectors, you need to employ integer lattices rather than linear algebra. Here is our set up:
from sage.modules.free_module_integer import IntegerLattice
M = matrix(ZZ, [[0,0,1,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,1,1,1], [0,0,0,1,1,0,1,1,1,1,1,2],[1,0,0,0,0,1,1,1,1,1,1,2], [0, 0, 0, 1, 0, 1, 0, 1, 1, 2, 2, 2], [ 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 3, 4], [ 0, 0, 1, 1, 0, 1, 2, 3, 3, 5, 5, 6], [ 0, 0, 1, 1, 1, 2, 3, 5, 5, 6, 6, 8], [ 0, 0, 1, 1, 1, 2, 3, 5, 5, 7, 7, 9], [ 0, 1, 1, 1, 2, 3, 5, 6, 7, 8, 7, 11], [ 0, 1, 1, 1, 2, 3, 5, 6, 7, 7, 8, 11], [0, 1, 2, 2, 2, 4, 6, 8, 9, 11, 11, 15]])
r = vector(ZZ, [1, 21, 45, 45, 55, 99, 154, 210, 231, 280, 280, 385])
First, you need to find an integer basis B of M and a transformation U between them, using LLL.
As a result of LLL, B will have as many rows as M but first few of them can be zero and will not be used in the lattice basis. Thus we will need to trim all zero rows of B and the corresponding rows of U.
B, U = M.LLL(transformation=True)
nz = sum(1 for r in B.rows() if r==0) # number of zero rows in B
B = B.delete_rows(range(nz)) # trimming first nz rows of B
U = U.delete_rows(range(nz)) # trimming first nz rows of U
assert U*M == B # the key property of U
Then we construct the lattice L spanned by B and represent vector r as a linear combination of the basis vectors of L (i.e. the rows of B). It then remains to multiply the coordinate vector by U from the right to get a solution:
L = IntegerLattice(B, lll_reduce=False) # our basis is already reduced and should not be altered
assert r in L # just in case checking that r belongs to L
v = L.coordinate_vector(r) * U
assert v*M == r # have we got correct result?
print(v)
Hi, Thanks a lot for this. I implemented this in my code and now everything works as I wanted. I just have some small questions regarding your code.
i) If the solution over the integers is not unique will it just give me one? Which one?
ii) If there is no solution over the integers what will the code give me?
iii) Why do include the line: assert r in L? What does it mean for r to belong to L?
i) you get some arbitrary solution, but you can get all solutions by adding to it an integer linear combinations of the integer kernel of M;
ii) if there are no solutions, then assert r in L will fail.
iii) r in L means that r belongs to the integer span of the basis of L. It's important to check this as L.coordinate_vector(r) may produce a vector with fractional components when r not in L.
You may learn some background about lattices at https://en.wikipedia.org/wiki/Lattice...
Btw, I've created a ticket about unexpected behavior of L.coordinate_vector(r): https://trac.sagemath.org/ticket/33882
Okey. Thanks a lot. This part of the code of a small bit of a larger code that produces lots of integer matrices with a for loop. My goal is to know for which matrices there are integer solutions and for which ones no. I have been trying to edit the code so that when there is no solutions, it returns me something like "no integer solution" rather than an error because it then stops computing it for the rest of the matrices. How can this be done?
If you do not need an actual solution, then everything is simpler:
if r not in IntegerLattice(M):
print("No integer solution")
Asked: 2022-05-20 13:01:58 +0100
Seen: 913 times
Last updated: May 20 '22
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
I have a particular case with a matrix M and a vector r defined both over the integers and an integer vector v solving this equation, but solve_left returns a vector with fractions.
Have you defined your matrix over
ZZ? Can you provide an example?My input is the following:
M = matrix(ZZ, [[0,0,1,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,1,1,1], [0,0,0,1,1,0,1,1,1,1,1,2],[1,0,0,0,0,1,1,1,1,1,1,2], [0, 0, 0, 1, 0, 1, 0, 1, 1, 2, 2, 2], [ 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 3, 4], [ 0, 0, 1, 1, 0, 1, 2, 3, 3, 5, 5, 6], [ 0, 0, 1, 1, 1, 2, 3, 5, 5, 6, 6, 8], [ 0, 0, 1, 1, 1, 2, 3, 5, 5, 7, 7, 9], [ 0, 1, 1, 1, 2, 3, 5, 6, 7, 8, 7, 11], [ 0, 1, 1, 1, 2, 3, 5, 6, 7, 7, 8, 11], [0, 1, 2, 2, 2, 4, 6, 8, 9, 11 ...(more)
I can now define $v2=r - 44*v1$. This is an integer vector satisfying the equation.