ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 23 May 2022 18:17:44 +0200Solve equation of matrices over integershttps://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/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}$?Fri, 20 May 2022 13:01:58 +0200https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/Comment by Diego99 for <p>Hi,</p>
<p>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}$?</p>
https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62556#post-id-62556My 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, 11, 15]])
r = matrix(ZZ, [1, 21, 45, 45, 55, 99, 154, 210, 231, 280, 280, 385])
v1 = M.solve_left(r)
print(v)
The output is the following:
v1 = [-11/2 -14 1 1 11/2 12 35/2 0 0 21/2 21/2 0]Fri, 20 May 2022 16:17:45 +0200https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62556#post-id-62556Comment by Diego99 for <p>Hi,</p>
<p>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}$?</p>
https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62557#post-id-62557I can now define $v2=r - 44*v1$. This is an integer vector satisfying the equation.Fri, 20 May 2022 16:20:23 +0200https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62557#post-id-62557Comment by Max Alekseyev for <p>Hi,</p>
<p>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}$?</p>
https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62551#post-id-62551Have you defined your matrix over `ZZ`? Can you provide an example?Fri, 20 May 2022 13:41:27 +0200https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62551#post-id-62551Comment by Diego99 for <p>Hi,</p>
<p>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}$?</p>
https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62550#post-id-62550I 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.Fri, 20 May 2022 13:10:27 +0200https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62550#post-id-62550Answer by Max Alekseyev for <p>Hi,</p>
<p>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}$?</p>
https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?answer=62563#post-id-62563If 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)Fri, 20 May 2022 20:28:57 +0200https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?answer=62563#post-id-62563Comment by Max Alekseyev for <p>If you deal with integer vectors, you need to employ integer lattices rather than linear algebra. Here is our set up:</p>
<pre><code>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])
</code></pre>
<p>First, you need to find an integer basis <code>B</code> of <code>M</code> and a transformation <code>U</code> between them, using LLL.
As a result of LLL, <code>B</code> will have as many rows as <code>M</code> 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 <code>B</code> and the corresponding rows of <code>U</code>.</p>
<pre><code>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
</code></pre>
<p>Then we construct the lattice <code>L</code> spanned by <code>B</code> and represent vector <code>r</code> as a linear combination of the basis vectors of <code>L</code> (i.e. the rows of <code>B</code>). It then remains to multiply the coordinate vector by <code>U</code> from the right to get a solution:</p>
<pre><code>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)
</code></pre>
https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62601#post-id-62601`r` should be a `vector`, not a `matrix`:
M = matrix(ZZ, [[0,1],[0,0]])
r = vector(ZZ, [0,1])
r in IntegerLattice(M)Mon, 23 May 2022 18:17:44 +0200https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62601#post-id-62601Comment by Diego99 for <p>If you deal with integer vectors, you need to employ integer lattices rather than linear algebra. Here is our set up:</p>
<pre><code>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])
</code></pre>
<p>First, you need to find an integer basis <code>B</code> of <code>M</code> and a transformation <code>U</code> between them, using LLL.
As a result of LLL, <code>B</code> will have as many rows as <code>M</code> 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 <code>B</code> and the corresponding rows of <code>U</code>.</p>
<pre><code>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
</code></pre>
<p>Then we construct the lattice <code>L</code> spanned by <code>B</code> and represent vector <code>r</code> as a linear combination of the basis vectors of <code>L</code> (i.e. the rows of <code>B</code>). It then remains to multiply the coordinate vector by <code>U</code> from the right to get a solution:</p>
<pre><code>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)
</code></pre>
https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62600#post-id-62600I think that is not working. Consider for example the following easy example:
M = matrix(ZZ, [[0,1],[0,0]])
r = matrix(ZZ, [[0,1]])
r in IntegerLattice(M)
I get 'false' as an output.
I want to know if the row vector r is the integer span of the rows of M. Do I need to take a transpose or something?Mon, 23 May 2022 17:12:42 +0200https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62600#post-id-62600Comment by Diego99 for <p>If you deal with integer vectors, you need to employ integer lattices rather than linear algebra. Here is our set up:</p>
<pre><code>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])
</code></pre>
<p>First, you need to find an integer basis <code>B</code> of <code>M</code> and a transformation <code>U</code> between them, using LLL.
As a result of LLL, <code>B</code> will have as many rows as <code>M</code> 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 <code>B</code> and the corresponding rows of <code>U</code>.</p>
<pre><code>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
</code></pre>
<p>Then we construct the lattice <code>L</code> spanned by <code>B</code> and represent vector <code>r</code> as a linear combination of the basis vectors of <code>L</code> (i.e. the rows of <code>B</code>). It then remains to multiply the coordinate vector by <code>U</code> from the right to get a solution:</p>
<pre><code>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)
</code></pre>
https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62599#post-id-62599Sorry for not pointing that out before. Should then something like this give me what I desire?
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])
if r not in IntegerLattice(M):
print("No integer solution")
else:
print("Integer solution")Mon, 23 May 2022 16:59:33 +0200https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62599#post-id-62599Comment by Max Alekseyev for <p>If you deal with integer vectors, you need to employ integer lattices rather than linear algebra. Here is our set up:</p>
<pre><code>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])
</code></pre>
<p>First, you need to find an integer basis <code>B</code> of <code>M</code> and a transformation <code>U</code> between them, using LLL.
As a result of LLL, <code>B</code> will have as many rows as <code>M</code> 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 <code>B</code> and the corresponding rows of <code>U</code>.</p>
<pre><code>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
</code></pre>
<p>Then we construct the lattice <code>L</code> spanned by <code>B</code> and represent vector <code>r</code> as a linear combination of the basis vectors of <code>L</code> (i.e. the rows of <code>B</code>). It then remains to multiply the coordinate vector by <code>U</code> from the right to get a solution:</p>
<pre><code>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)
</code></pre>
https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62597#post-id-62597If you do not need an actual solution, then everything is simpler:
if r not in IntegerLattice(M):
print("No integer solution")Mon, 23 May 2022 15:10:43 +0200https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62597#post-id-62597Comment by Diego99 for <p>If you deal with integer vectors, you need to employ integer lattices rather than linear algebra. Here is our set up:</p>
<pre><code>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])
</code></pre>
<p>First, you need to find an integer basis <code>B</code> of <code>M</code> and a transformation <code>U</code> between them, using LLL.
As a result of LLL, <code>B</code> will have as many rows as <code>M</code> 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 <code>B</code> and the corresponding rows of <code>U</code>.</p>
<pre><code>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
</code></pre>
<p>Then we construct the lattice <code>L</code> spanned by <code>B</code> and represent vector <code>r</code> as a linear combination of the basis vectors of <code>L</code> (i.e. the rows of <code>B</code>). It then remains to multiply the coordinate vector by <code>U</code> from the right to get a solution:</p>
<pre><code>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)
</code></pre>
https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62595#post-id-62595Okey. 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?Mon, 23 May 2022 11:30:06 +0200https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62595#post-id-62595Comment by Max Alekseyev for <p>If you deal with integer vectors, you need to employ integer lattices rather than linear algebra. Here is our set up:</p>
<pre><code>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])
</code></pre>
<p>First, you need to find an integer basis <code>B</code> of <code>M</code> and a transformation <code>U</code> between them, using LLL.
As a result of LLL, <code>B</code> will have as many rows as <code>M</code> 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 <code>B</code> and the corresponding rows of <code>U</code>.</p>
<pre><code>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
</code></pre>
<p>Then we construct the lattice <code>L</code> spanned by <code>B</code> and represent vector <code>r</code> as a linear combination of the basis vectors of <code>L</code> (i.e. the rows of <code>B</code>). It then remains to multiply the coordinate vector by <code>U</code> from the right to get a solution:</p>
<pre><code>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)
</code></pre>
https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62586#post-id-62586Btw, I've created a ticket about unexpected behavior of `L.coordinate_vector(r)`: https://trac.sagemath.org/ticket/33882Sun, 22 May 2022 19:39:53 +0200https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62586#post-id-62586Comment by Max Alekseyev for <p>If you deal with integer vectors, you need to employ integer lattices rather than linear algebra. Here is our set up:</p>
<pre><code>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])
</code></pre>
<p>First, you need to find an integer basis <code>B</code> of <code>M</code> and a transformation <code>U</code> between them, using LLL.
As a result of LLL, <code>B</code> will have as many rows as <code>M</code> 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 <code>B</code> and the corresponding rows of <code>U</code>.</p>
<pre><code>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
</code></pre>
<p>Then we construct the lattice <code>L</code> spanned by <code>B</code> and represent vector <code>r</code> as a linear combination of the basis vectors of <code>L</code> (i.e. the rows of <code>B</code>). It then remains to multiply the coordinate vector by <code>U</code> from the right to get a solution:</p>
<pre><code>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)
</code></pre>
https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62583#post-id-62583i) 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_(group)Sun, 22 May 2022 18:13:53 +0200https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62583#post-id-62583Comment by Diego99 for <p>If you deal with integer vectors, you need to employ integer lattices rather than linear algebra. Here is our set up:</p>
<pre><code>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])
</code></pre>
<p>First, you need to find an integer basis <code>B</code> of <code>M</code> and a transformation <code>U</code> between them, using LLL.
As a result of LLL, <code>B</code> will have as many rows as <code>M</code> 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 <code>B</code> and the corresponding rows of <code>U</code>.</p>
<pre><code>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
</code></pre>
<p>Then we construct the lattice <code>L</code> spanned by <code>B</code> and represent vector <code>r</code> as a linear combination of the basis vectors of <code>L</code> (i.e. the rows of <code>B</code>). It then remains to multiply the coordinate vector by <code>U</code> from the right to get a solution:</p>
<pre><code>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)
</code></pre>
https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62579#post-id-62579Hi,
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?Sun, 22 May 2022 10:48:35 +0200https://ask.sagemath.org/question/62549/solve-equation-of-matrices-over-integers/?comment=62579#post-id-62579