Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 LinearSolveModIntegers

Source Notebook

Solve rational linear system modulo the integers

Contributed by: Daniel Lichtblau

ResourceFunction["LinearSolveModIntegers"][mat,rhs]

solves the rational linear system mat.x=rhs modulo the integers for the unknown vector x.

ResourceFunction["LinearSolveModIntegers"][mat,rhs,True]

solves the linear system modulo the integers and returns a list containing the solution vector and a set of rational vectors that span the null space.

Details

In typical use the system will be overdetermined e.g. have more equations than variables (so mat will have more rows than columns).
When there is no solution, ResourceFunction["LinearSolveModIntegers"] will return an empty list regardless of whether the null vectors were requested.

Examples

Basic Examples (2) 

Find rational solutions modulo the integers to an overdetermined system:

In[1]:=
mat = {{-210, -210, -220}, {-221, -222, -232}, {410, 411, 430}, {-132, -121, -132}, {-120, -110, -120}, {240, 220, 240}}; vec = {-27, -28, 105/2, -47/8, -29/4, 25/2}; sol = ResourceFunction["LinearSolveModIntegers"][mat, vec]
Out[3]=

Check that the result is correct modulo the integers:

In[4]:=
Mod[mat . sol - vec, 1]
Out[4]=

Scope (2) 

Find a solution and generating set for the null vectors of an overdetermined system:

In[5]:=
mat = {{-210, -210, -220}, {-221, -222, -232}, {410, 411, 430}, {-132, -121, -132}, {-120, -110, -120}, {240, 220, 240}}; vec = {-27, -28, 105/2, -47/8, -29/4, 25/2}; {sol, nulls} = ResourceFunction["LinearSolveModIntegers"][mat, vec, True]
Out[6]=

Use the null vector to obtain the other solution mod ℤ:

In[7]:=
sol2 = sol + nulls[[1]]
Out[7]=

Check this:

In[8]:=
Mod[mat . sol2 - vec, 1]
Out[8]=

Create a linear system over the rationals with a known solution:

In[9]:=
SeedRandom[1234]; dims = {4, 3}; max = 5; ratmat = RandomInteger[{-max, max}, dims]/RandomInteger[{1, max}, dims]; svec = {3/2, -3/5, 7/3}; rhs = ratmat . svec; {ratmat, rhs}
Out[10]=

Recover the solution from the matrix and right hand side:

In[11]:=
soln = ResourceFunction["LinearSolveModIntegers"][ratmat, rhs]
Out[11]=

Note that the found solution agrees with the known one modulo ℤ:

In[12]:=
Mod[soln - svec, 1]
Out[12]=

Requirements

Wolfram Language 13.0 (December 2021) or above

Version History

  • 1.0.0 – 24 June 2024

Related Resources

Author Notes

The GAP package Cryst apparently has a similar function SolveInhomEquationsModZ. I was unable to find actual documentation however.

License Information