# Solve an non-homogeneous system of equations mod Z (integers)

**URL:** <https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309>\
**Category:** Questions\
**Tags:** algebra, equation-solving\
**Created:** [January 1, 2023, 3:25pm UTC](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309 "2023-01-01T15:25:52Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![hongyizhao](https://avatars.discourse-cdn.com/v4/letter/h/8491ac/32.png) [@hongyizhao](https://community.wolfram.com/u/hongyizhao)\
**Post date:** [January 1, 2023, 3:25pm UTC](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309/1 "2023-01-01T15:25:52Z")

</div>

Hi here,

I’ve a set of matrices and vectors as follows:

```
In[87]:= mats={{{-2, 0, 0}, {0, -2, 0}, {1, 1, 0}}, {{-2, 0, 0}, {0, 0, 
   0}, {0, -1, -2}}, {{0, 1, 2}, {1, -1, 0}, {-1, 0, -2}}, {{-1, 1, 
   0}, {1, -1, 0}, {-1, -1, -2}}, {{-2, 0, 0}, {0, -2, 0}, {0, 
   0, -2}}}
vecs={{-(23/8), 17/8, -(9/8)}, {17/8, 1, -3}, {0, 0, 
  0}, {1, -2, -(15/16)}, {1/8, -(23/8), 15/16}}

Out[87]= {{{-2, 0, 0}, {0, -2, 0}, {1, 1, 0}}, {{-2, 0, 0}, {0, 0, 
   0}, {0, -1, -2}}, {{0, 1, 2}, {1, -1, 0}, {-1, 0, -2}}, {{-1, 1, 
   0}, {1, -1, 0}, {-1, -1, -2}}, {{-2, 0, 0}, {0, -2, 0}, {0, 0, -2}}}

Out[88]= {{-(23/8), 17/8, -(9/8)}, {17/8, 1, -3}, {0, 0, 
  0}, {1, -2, -(15/16)}, {1/8, -(23/8), 15/16}}

```

I want to find a common set of solutions, a.k.a., x, for the above  
matrices and their corresponding vectors, which satisfy the following  
conditions:

```
Dot[mat, x] = vec (mod Z)
\forall mat \in mats

```

and

```
\forall vec \in vecs

```

in the corresponding order.

Any tips for tackling this problem?

Regards,  
Zhao

---

<div class="post-metadata">

**Author:** ![danl](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/danl/32/41267_2.png) [@danl](https://community.wolfram.com/u/danl)\
**Post date:** [January 1, 2023, 6:11pm UTC](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309/2 "2023-01-01T18:11:56Z")

</div>

Are you sure there is such an `x`? Maybe for a start work out what it could be if you use only the first two matrices and corresponding vectors.

---

<div class="post-metadata">

**Author:** ![hongyizhao](https://avatars.discourse-cdn.com/v4/letter/h/8491ac/32.png) [@hongyizhao](https://community.wolfram.com/u/hongyizhao)\
**Post date:** [January 2, 2023, 3:45am UTC](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309/3 "2023-01-02T03:45:48Z")

</div>

I really don’t know how to solve this problem in Wolfram. Here is a GAP-based solution to the first matrix and its corresponding vector given in the above example:

```
gap> mat:=[[ -2, 0, 0], [0, -2, 0], [1, 1, 0] ];
[[ -2, 0, 0], [0, -2, 0], [1, 1, 0] ]
gap> vec1:=[-23/8, 17/8, -9/8];
[-23/8, 17/8, -9/8]
gap> vec2:=List(vec1, x -> FractionModOne(x));
[1/8, 1/8, 7/8]
gap> # false means acting on left, a.k.a,
gap> # compute the set of solutions of the equation
gap> # M * x = b (mod Z).
gap> sol1:=SolveInhomEquationsModZ(mat, vec1, false);
[[ [ 15/16, 15/16, 0], [7/16, 7/16, 0] ], [[ 0, 0, 1] ] ]
gap> sol2:=SolveInhomEquationsModZ(mat, vec2, false);
[[ [ 15/16, 15/16, 0], [7/16, 7/16, 0] ], [[ 0, 0, 1] ] ]
gap> sol1=sol2;
true
gap> # These soloutions are all on the integer lattice spanned by vec2:
gap> List(Union(sol1), x -> VectorModL(mat * x, [vec2] ));
[[ 0, 0, 0], [0, 0, 7], [0, 0, 15] ]

```

---

<div class="post-metadata">

**Author:** ![danl](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/danl/32/41267_2.png) [@danl](https://community.wolfram.com/u/danl)\
**Post date:** [January 2, 2023, 3:25pm UTC](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309/4 "2023-01-02T15:25:10Z")

</div>

What is needed is an example closer to the actual one. So, two matrices and two right hand side vectors with one common solution. Not asking for a WL-based solution, just input and expected result.

---

<div class="post-metadata">

**Author:** ![hongyizhao](https://avatars.discourse-cdn.com/v4/letter/h/8491ac/32.png) [@hongyizhao](https://community.wolfram.com/u/hongyizhao)\
**Post date:** [January 3, 2023, 4:17am UTC](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309/5 "2023-01-03T04:17:40Z")

</div>

See the following example:

```
In[86]:= sol={-(1/4),-(7/8),-(5/16)};
mats={{{-1, -1, 0}, {-31, -32, -32}, {30, 31, 30}}, {{-121, -109, -120}, {-101, -91, -100}, {210, 189, 208}}};
vecs={{9/8, 183/4, -44}, {1305/8, 1089/8, -(2263/8)}};
# . sol&/@mats
%==vecs

Out[89]= {{9/8, 183/4, -44}, {1305/8, 1089/8, -(2263/8)}}

Out[90]= True

```

---

<div class="post-metadata">

**Author:** ![danl](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/danl/32/41267_2.png) [@danl](https://community.wolfram.com/u/danl)\
**Post date:** [January 3, 2023, 4:08pm UTC](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309/6 "2023-01-03T16:08:41Z")

</div>

This is closer. Since we only insist on equivalence modulo integers this example is in a sense too trivial-- one can solve it directly. I will propose the following modest alteration on the right hand sides.

```
sol = {-(1/4), -(7/8), -(5/16)};
mats = {{{-1, -1, 0}, {-31, -32, -32}, {30, 31, 
     30}}, {{-121, -109, -120}, {-101, -91, -100}, {210, 189, 208}}};
vecs = {{17/8, 143/4, -44}, {65/8, 1289/8, (137/8)}};
results = # . sol & /@ mats
results - vecs

(* Out[552]= {{9/8, 183/4, -44}, {1305/8, 1089/8, -(2263/8)}}

Out[553]= {{-1, 10, 0}, {155, -25, -300}} *)

```

So `sol` does what is required mod Z.

---

<div class="post-metadata">

**Author:** ![hongyizhao](https://avatars.discourse-cdn.com/v4/letter/h/8491ac/32.png) [@hongyizhao](https://community.wolfram.com/u/hongyizhao)\
**Post date:** [January 4, 2023, 12:40am UTC](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309/7 "2023-01-04T00:40:11Z")

</div>

You are right. This is the exact mathematical description of the problem, as shown below:

```
results - vecs == 0, (mod Z^n), where n is the dimension of these vectors.

```

But how to solve this problem in WL? I tried the following method, but WL does not support it at all:

```
In[51]:= m=Array[v,3]
Solve[ConstantArray[ConstantArray[0,Length[vecs[[1]]]], Length[mats]]==(# . m & /@ mats), m, Modulus->1]

Out[51]= {v[1], v[2], v[3]}

During evaluation of In[51]:= Solve::rmod: Modulus 1 must be a non-negative integer other than 1.

Out[52]= Solve[{{0, 0, 0}, {0, 0, 
    0}} == {{-v[1] - v[2], -31 v[1] - 32 v[2] - 32 v[3], 
    30 v[1] + 31 v[2] + 30 v[3]}, {-121 v[1] - 109 v[2] - 
     120 v[3], -101 v[1] - 91 v[2] - 100 v[3], 
    210 v[1] + 189 v[2] + 208 v[3]}}, {v[1], v[2], v[3]}, 
 Modulus -> 1]

```

---

<div class="post-metadata">

**Author:** ![danl](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/danl/32/41267_2.png) [@danl](https://community.wolfram.com/u/danl)\
**Post date:** [January 4, 2023, 12:55am UTC](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309/8 "2023-01-04T00:55:02Z")

</div>

Not sure yet how to go about this. Appears to be tricky.

---

<div class="post-metadata">

**Author:** ![hongyizhao](https://avatars.discourse-cdn.com/v4/letter/h/8491ac/32.png) [@hongyizhao](https://community.wolfram.com/u/hongyizhao)\
**Post date:** [January 4, 2023, 1:05am UTC](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309/9 "2023-01-04T01:05:32Z")

</div>

I used the following option for **Solve** in the previous post:

```
Modulus->Integers 

```

However, it should be changed to the following option, which has been corrected in the previous post:

```
Modulus->1

```

But, even so, WL still does not support related processing.

---

<div class="post-metadata">

**Author:** ![hongyizhao](https://avatars.discourse-cdn.com/v4/letter/h/8491ac/32.png) [@hongyizhao](https://community.wolfram.com/u/hongyizhao)\
**Post date:** [January 7, 2023, 3:38am UTC](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309/10 "2023-01-07T03:38:43Z")

</div>

Hi Daniel,

After I re-examine the problem, I find that the above description is  
still inappropriate. Therefore, I make the following revision.

For an inhomogeneous system of linear equations represented as the matrix form:

```
M . x = b

```

I would like to find the set of all such solutions, sol, in which any solutions can be added by an arbitrary integer vector with the same dimension, and the mod 1 remainder of the components of the  
result vector obtained from the original equation, remains the same.

In order to facilitate intuitive understanding, I show the following example which meets the requirements of the above:

```
In[130]:= mat2={{-132, -121, -132}, {-120, -110, -120}, {240, 220, 240}}
vec2={-(47/8), -(29/4), 25/2}
sol={{-1, 0, 1}, {5/8, 3/8, 0}, {11, -12, 0}}
rnd=RandomInteger[{-1000,1000},3]
Mod[mat2 . #&/@sol,1]==Mod[mat2 . (#+rnd)&/@sol,1]

Out[130]= {{-132, -121, -132}, {-120, -110, -120}, {240, 220, 240}}

Out[131]= {-(47/8), -(29/4), 25/2}

Out[132]= {{-1, 0, 1}, {5/8, 3/8, 0}, {11, -12, 0}}

Out[133]= {901, -781, -627}

Out[134]= True

```

Where, the corresponding relationship is as follows:

```
M . x = b
mat2 . sol = vec2

```

As you can see, any solution in sol can be added by an arbitrary integer vector with the same dimension and the mod 1 remainder of the components of the result vector obtained from the original equation, remains the same.

P.S.: The matrices here are all unimodular integer matrices, but the vectors and solutions belongs to the field of rationals.

Best,  
Zhao

---

<div class="post-metadata">

**Author:** ![danl](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/danl/32/41267_2.png) [@danl](https://community.wolfram.com/u/danl)\
**Post date:** [January 7, 2023, 4:30pm UTC](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309/11 "2023-01-07T16:30:34Z")

</div>

Hi Zhao,

I think I understand the problem. What has been elusive thus far is how to solve it. I’ll try some ,ore and post a response if I get anywhere.

—edit —

I posted a notebook that describes how to proceed. I did not elaborate too much but here is the outline.

First I show a not-quite-standard way to set up a linear system to solve using the reduced echelon form.

Then I show how it readily extends to find, when one exists, a common solution to two (or more) such systems.

The next step is to extend the idea to solving over integers modulo some given integer. Here we do not assume the given integer is prime.

The important last step is to adjust this technology to finding a rational solution that is correct modulo the integers. This solves the particular example I had posed, which in turn was a minor change to one you had provided.

— end edit —

---

<div class="post-metadata">

**Author:** ![bradklee](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/bradklee/32/16606_2.png) [@bradklee](https://community.wolfram.com/u/bradklee)\
**Post date:** [January 7, 2023, 8:44pm UTC](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309/12 "2023-01-07T20:44:35Z")

</div>

a \times b \mod d = a \times (b + c) \mod d \implies a \times c \mod d = 0 \implies c = k \times d, where k is an integer. This property entirely explains your identity that:

```
Mod[mat2 . #&/@sol,1]==Mod[mat2 . (#+rnd)&/@sol,1]
Out[] = True

```

Because all elements in _ **rnd** _ are integers of the form k \times 1. Is _ **vec2** _ meant to be distraction or did you want that in the identity somewhere? Possible dimension mismatch?

---

<div class="post-metadata">

**Author:** ![danl](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/danl/32/41267_2.png) [@danl](https://community.wolfram.com/u/danl)\
**Post date:** [January 7, 2023, 10:23pm UTC](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309/13 "2023-01-07T22:23:02Z")

</div>

[Open in Wolfram Cloud ↗](https://www.wolframcloud.com/obj/a91ba5c4-fb45-4cf6-8071-fe9a8ce2513d)

---

<div class="post-metadata">

**Author:** ![hongyizhao](https://avatars.discourse-cdn.com/v4/letter/h/8491ac/32.png) [@hongyizhao](https://community.wolfram.com/u/hongyizhao)\
**Post date:** [January 8, 2023, 1:23am UTC](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309/14 "2023-01-08T01:23:30Z")

</div>

Hi Daniel,

First, I appreciate your wonderful analysis and detailed solving process. I need some time to fully understand your method and specific details.

However, based on the general characteristics of the problem, I still have the following questions:

1. For a problem like this, if there are solutions, then there should be infinitely many solutions, how do I find and represent all of them in a reasonable form?
2. What are the characteristics and properties of the set of all solutions?
3. How to quickly determine if there is no solution?

---

<div class="post-metadata">

**Author:** ![hongyizhao](https://avatars.discourse-cdn.com/v4/letter/h/8491ac/32.png) [@hongyizhao](https://community.wolfram.com/u/hongyizhao)\
**Post date:** [January 8, 2023, 1:27am UTC](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309/15 "2023-01-08T01:27:59Z")

</div>

> Is vec2 meant to be distraction or did you want that in the identity  
> somewhere? Possible dimension mismatch?

I really don’t understand why you say that. Can you give more specific examples?

---

<div class="post-metadata">

**Author:** ![danl](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/danl/32/41267_2.png) [@danl](https://community.wolfram.com/u/danl)\
**Post date:** [January 8, 2023, 2:30am UTC](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309/16 "2023-01-08T02:30:16Z")

</div>

In order:

(1) Just like working over a field, solutions are comprised of a specific solution plus arbitrary combinations over Z of null solutions. Those latter are also found in the HNF.

```
nullsZ = 
 Cases[hhnew, {Repeated[0, {Length[bigvec] + 1}], 
    rest__} :> {rest}[[1 ;; Length[mats[[1, 1]]]]]]

(* Out[576]= {{16, 0, 0}, {0, 16, 0}, {0, 0, 8}} *)

nullvecs = nullsZ/(mult*lcm)

(* Out[577]= {{1, 0, 0}, {0, 1, 0}, {0, 0, 1/2}} *)

```

The first two are “obvious” insofar as we can add any integer to components of the specific solution found and still have a solution modulo 1. The third null vector shows we can add half integers to the third component. For example:

```
In[578]:= mats[[1]] . (mod1soln + nullvecs[[3]]) - vecs[[1]]

(* Out[578]= {-3, -85, 91} *)

```

(2) See (1).

(3) I do not know of a quick way offhand. I think you’d have to do the solve process as shown, and see if there are no rows in the HNF that have annihilated that `bigvec`. In the terminology I used, that would mean `keeprow` came back empty or in the form `Missing[...]`.

---

<div class="post-metadata">

**Author:** ![bradklee](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/bradklee/32/16606_2.png) [@bradklee](https://community.wolfram.com/u/bradklee)\
**Post date:** [January 8, 2023, 4:03am UTC](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309/17 "2023-01-08T04:03:46Z")

</div>

You say that :

```
mat2 . sol = vec2

```

but the dimensions of **mat2** , **sol** , and **vec2** are inconsistent:

(3\times3)\cdot(3\times 3) = (3 \times 3 )\neq1 \times 3.

I thought you may have made a mistake, meaning by **sol** in this equation, one row from the **sol** example you gave, but none of the three dot products equal to **vec2**.

---

<div class="post-metadata">

**Author:** ![hongyizhao](https://avatars.discourse-cdn.com/v4/letter/h/8491ac/32.png) [@hongyizhao](https://community.wolfram.com/u/hongyizhao)\
**Post date:** [January 8, 2023, 4:15am UTC](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309/18 "2023-01-08T04:15:22Z")

</div>

Sorry, my statement is unclear. I mean, in all the context mentioned here, it corresponds to the following meaning:

```
mat2 . #&/@sol

```

---

<div class="post-metadata">

**Author:** ![hongyizhao](https://avatars.discourse-cdn.com/v4/letter/h/8491ac/32.png) [@hongyizhao](https://community.wolfram.com/u/hongyizhao)\
**Post date:** [January 8, 2023, 9:25am UTC](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309/19 "2023-01-08T09:25:52Z")

</div>

Hi Daniel,

I notice that in the last step of your approach there are some difficulties and problems as follows:

- You said the following:

> The catch is that we might not obtain such a vector in the HNF.

This means that the method may miss solutions.

- In this step, there are a lot of empirical judgment and trial-and-error, which make this approach difficult to implement programmatically.

---

<div class="post-metadata">

**Author:** ![danl](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/danl/32/41267_2.png) [@danl](https://community.wolfram.com/u/danl)\
**Post date:** [January 8, 2023, 2:36pm UTC](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309/20 "2023-01-08T14:36:52Z")

</div>

There is no trial-and-error guessing. The part ’ mult=First[keeprow]’ determines whether we have a solution, and, if not, what new multiplier we require in the denominators. It’s actually a complete algorithm.

[Next page](https://community.wolfram.com/t/solve-an-non-homogeneous-system-of-equations-mod-z-integers/21309.md?page=2)
