Ask Your Question
0

Solve equation of matrices over integers

asked 2022-05-20 13:02:27 +0100

Diego99 gravatar image

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}$?

edit retag flag offensive close merge delete

Comments

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.

Diego99 gravatar imageDiego99 ( 2022-05-20 13:10:27 +0100 )edit

Have you defined your matrix over ZZ? Can you provide an example?

Max Alekseyev gravatar imageMax Alekseyev ( 2022-05-20 13:41:27 +0100 )edit

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)

Diego99 gravatar imageDiego99 ( 2022-05-20 16:17:45 +0100 )edit

I can now define $v2=r - 44*v1$. This is an integer vector satisfying the equation.

Diego99 gravatar imageDiego99 ( 2022-05-20 16:20:23 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted
0

answered 2022-05-20 20:28:57 +0100

Max Alekseyev gravatar image

updated 2022-05-20 20:43:09 +0100

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)
edit flag offensive delete link more

Comments

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?

Diego99 gravatar imageDiego99 ( 2022-05-22 10:48:35 +0100 )edit

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...

Max Alekseyev gravatar imageMax Alekseyev ( 2022-05-22 18:13:53 +0100 )edit

Btw, I've created a ticket about unexpected behavior of L.coordinate_vector(r): https://trac.sagemath.org/ticket/33882

Max Alekseyev gravatar imageMax Alekseyev ( 2022-05-22 19:39:53 +0100 )edit

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?

Diego99 gravatar imageDiego99 ( 2022-05-23 11:30:06 +0100 )edit

If you do not need an actual solution, then everything is simpler:

if r not in IntegerLattice(M):
    print("No integer solution")
Max Alekseyev gravatar imageMax Alekseyev ( 2022-05-23 15:10:43 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

2 followers

Stats

Asked: 2022-05-20 13:01:58 +0100

Seen: 956 times

Last updated: May 20 '22