Revision history [back]
 | 1 | initial version |
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, but we will need to trim all rows of U corresponding to zero rows of B.
B, U = M.LLL(transformation=True)
assert U*M == B
nz = sum(1 for r in B.rows() if r==0) # number of zero rows in B
U = U[nz:,:] # trimming first nz rows of U
Then we construct a lattice spanned by B and represent vector r as a linear combination of the basis vectors. It then remains to prepend the zeros to beginning multiply by U:
L = IntegerLattice(B)
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)
| | 2 | No.2 Revision |
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, but basis. Thus we will need to trim all rows of U corresponding that correspond to zero rows of B.
B, U = M.LLL(transformation=True)
assert U*M == B
nz = sum(1 for r in B.rows() if r==0) # number of zero rows in B
U = U[nz:,:] # trimming first nz rows of U
Then we construct a the lattice L spanned by B and represent vector r as a linear combination of the basis vectors. vectors of L (which are the nonzero rows of B). It then remains to prepend the zeros to beginning multiply the coordinate vector by U: from the right:
L = IntegerLattice(B)
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)
| | 3 | No.3 Revision |
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 that correspond to zero rows of B.
B, U = M.LLL(transformation=True)
assert U*M == B
nz = sum(1 for r in B.rows() if r==0) # number of zero rows in B
B = B[nz:,:] # trimming first nz rows of B
U = U[nz:,:] # trimming first nz rows 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 (which are the nonzero (i.e. the rows of B). It then remains to multiply the coordinate vector by U from the right:right to get a solution:
L = IntegerLattice(B)
IntegerLattice(B, lll_reduce=False) # our basis is already reduced, and we don't want it to 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)
| | 4 | No.4 Revision |
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)
assert U*M == B
nz = sum(1 for r in B.rows() if r==0) # number of zero rows in B
B = B[nz:,:] # trimming first nz rows of B
U = U[nz:,:] # trimming first nz rows 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, reduced and we don't want it to 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)
| | 5 | No.5 Revision |
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)
assert U*M == B
nz = sum(1 for r in B.rows() if r==0) # number of zero rows in B
B = B[nz:,:] # trimming first nz rows of B
U = U[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)
| | 6 | No.6 Revision |
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[nz:,:] B.delete_rows(range(nz)) # trimming first nz rows of B
U = U[nz:,:] 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)
