0
|
4348 Views
|
29 Replies
|
11 Total Likes
View groups...
Share
GROUPS:

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

Posted 1 year ago
 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
29 Replies
Sort By:
Posted 26 days ago
 We now have LinearSolveModIntegers in the Wolfram Function Repository. Here I run it on your example. We join the matrices and the vectors to get on large matrix and one corresponding right-hand-side vector. 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}}; ResourceFunction["LinearSolveModIntegers"][Apply[Join, mats], Apply[Join, vecs], True](* Out[146]= {{15/16, 15/16, 1/32}, {}} *)The first part is a specific solution. The empty list in the second part indicates the null space is empty. So the solution is unique.
Posted 1 year ago
 Now, I try to obtain the nullvecs computed by you, which can be generated in GAP as follows: gap> mat1:= [ [-210, -210, -220], [ -221, -222, -232], [410, 411, 430 ] ]; [ [ -210, -210, -220 ], [ -221, -222, -232 ], [ 410, 411, 430 ] ] gap> mat2:= [ [-132, -121, -132], [ -120, -110, -120], [240, 220, 240] ]; [ [ -132, -121, -132 ], [ -120, -110, -120 ], [ 240, 220, 240 ] ] gap> mats:=[mat1, mat2]; [ [ [ -210, -210, -220 ], [ -221, -222, -232 ], [ 410, 411, 430 ] ], [ [ -132, -121, -132 ], [ -120, -110, -120 ], [ 240, 220, 240 ] ] ] gap> LoadPackage("fr"); true gap> # M * x = b gap> d:=DimensionsMat(M)[1]; 6 gap> nullvecs:=SolveInhomEquationsModZ(M, 0*[1..d], false )[1]; [ [ 0, 0, 0 ], [ 0, 0, 1/2 ] ] gap> # TransposedMat(M)* x = b gap> # M_mn * x_n1 = b_m1 gap> d:=DimensionsMat(TransposedMat(M))[1]; 3 gap> nullvecs:=SolveHomEquationsModZ(TransposedMat(M))[1]; [ [ 0, 0, 0 ], [ 0, 0, 1/2 ] ] gap> # or gap> nullvecs:=SolutionMatMod1(TransposedMat(M), 0*[1..d]); [ [ 0, 0, 0 ], [ 0, 0, 1/2 ] ] Then I try to compute with your WL based method as follows, but failed: In[88]:= mat1 = {{-210, -210, -220}, {-221, -222, -232}, {410, 411, 430}}; mat2 = {{-132, -121, -132}, {-120, -110, -120}, {240, 220, 240}}; mats = {mat1, mat2}; bigmat = Apply[Join[##, 2] &, Map[Transpose, mats]]; In[92]:= vec1 = {-27, -28, 105/2}; vec2 = {-47/8, -29/4, 25/2}; vecs = {vec1, vec2}; bigvec = vecs // Flatten; In[102]:= lcm = LCM @@ Denominator[bigvec]; {uu, hh} = HermiteDecomposition[bigmat]; keeprow = FirstCase[ hh, {Repeated[0, {Length[bigvec]}], nz : Except[0], rest__} :> {nz, rest}]; mult = keeprow // First nullsZ = Cases[hh, {Repeated[0, {Length[bigvec] + 1}], rest__} :> {rest}[[1 ;; Length[mats[[1, 1]]]]]] nullvecs = nullsZ/(mult*lcm) Out[105]= "NotFound" Out[106]= {} Out[107]= {} Any further tips/comments/remarks will be appreciated.Regards, Zhao
Posted 1 year ago
 You skipped some of the code I used. Check part 4 of the notebook I put in this thread. Below is a variant suitable for finding the null vectors, skipping the parts needed to find a single solution to the inhomogeneous system. mat1 = {{-210, -210, -220}, {-221, -222, -232}, {410, 411, 430}}; mat2 = {{-132, -121, -132}, {-120, -110, -120}, {240, 220, 240}}; mats = {mat1, mat2}; vec1 = {-27, -28, 105/2}; vec2 = {-47/8, -29/4, 25/2}; vecs = {vec1, vec2}; bigmat0 = Apply[Join[##, 2] &, Map[Transpose, mats]]; bigvec = -Flatten[vecs]; lcm = LCM @@ Denominator[bigvec]; bigmat1 = Join[lcm*{bigvec}, bigmat0]; bigmat2 = Join[bigmat1, lcm*IdentityMatrix[Length[bigmat1[[1]]]]]; bigmat = Join[bigmat2, IdentityMatrix[Length[bigmat2]], 2]; {uu, hh} = HermiteDecomposition[bigmat]; Cases[hh, {Repeated[0, {Length[bigvec] + 1}], rest__} :> {rest}[[1 ;; Length[mats[[1, 1]]]]]]/lcm (* Out[87]= {{1, 0, 0}, {0, 1, 0}, {0, 0, 1/2}} *) 
Posted 1 year ago
Posted 1 year ago
 Since it is a complete algorithm, why do you still say the following? The catch is that we might not obtain such a vector in the HNF.
Posted 1 year ago
 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.
Posted 1 year ago
 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.
Posted 1 year ago
 I meant to ask: Do you have references for this type of solving? Or applications? I tried to look up this type of solving and got nowhere.
Posted 1 year ago
Posted 1 year ago
 Dear Zhao,I found in another thread (Pari/GP bulletin board it seems) that you also asked about a different matrix and vector pair. mat1 = {{-210, -210, -220}, {-221, -222, -232}, {410, 411, 430}}; mat2 = {{-132, -121, -132}, {-120, -110, -120}, {240, 220, 240}}; vec1 = {-27, -28, 105/2}; vec2 = {-47/8, -29/4, 25/2}; Using the same code as I showed in this thread I get (again) a common solution modulo Z of {3/4, 1/8, 3/16}. Also the null vectors are the same as with the prior example. Perhaps the two examples are related in your work. I am really not familiar with crystallographic groups so I'm a bit lost there.Anyway I thought this might be useful to you. From what I could tell, the result in that other thread excluded the second matrix and vector. Possibly readers failed to understand that you are seeking a common solution to both pairs. Or maybe I misunderstand what is wanted.
Posted 1 year ago
 Yes. I discussed the similar question here.Below is the complete solution set obtained in GAP with cryst and fr packages, respectively: gap> mat1:= [ [-210, -210, -220], [ -221, -222, -232], [410, 411, 430 ] ]; [ [ -210, -210, -220 ], [ -221, -222, -232 ], [ 410, 411, 430 ] ] gap> mat2:= [ [-132, -121, -132], [ -120, -110, -120], [240, 220, 240] ]; [ [ -132, -121, -132 ], [ -120, -110, -120 ], [ 240, 220, 240 ] ] gap> vec1 := [ -27, -28, 105/2 ]; [ -27, -28, 105/2 ] gap> vec2 := [ -47/8, -29/4, 25/2 ]; [ -47/8, -29/4, 25/2 ] gap> mats:=[mat1, mat2]; [ [ [ -210, -210, -220 ], [ -221, -222, -232 ], [ 410, 411, 430 ] ], [ [ -132, -121, -132 ], [ -120, -110, -120 ], [ 240, 220, 240 ] ] ] gap> vecs:=[vec1, vec2]; [ [ -27, -28, 105/2 ], [ -47/8, -29/4, 25/2 ] ] gap> M:= Concatenation( mats ); [ [ -210, -210, -220 ], [ -221, -222, -232 ], [ 410, 411, 430 ], [ -132, -121, -132 ], [ -120, -110, -120 ], [ 240, 220, 240 ] ] gap> b := Concatenation( vecs ); [ -27, -28, 105/2, -47/8, -29/4, 25/2 ] gap> sol:=SolveInhomEquationsModZ(M, b, false)[1]; [ [ 3/4, 1/8, 3/16 ], [ 3/4, 1/8, 11/16 ] ] gap> # Confirm solution set is correct: gap> Concatenation(List( mats, x -> List(sol, y -> x * y - vecs[Position(mats, x)] ) )); [ [ -198, -209, 387 ], [ -308, -325, 602 ], [ -133, -119, 240 ], [ -199, -179, 360 ] ] gap> # An alternative would be gap> LoadPackage("fr"); true gap> sol=SolutionMatMod1(TransposedMat(M), b); true As you can, see, there are two sets of solutions. I don't know whether your algorithm can also get exactly the same results.
Posted 1 year ago
 Yes, it is easy to get the same results as you obtained with GAP. They are (in WL notation) {{3/4, 1/8, 3/16}, {3/4, 1/8, 11/16 ]}}. Recall that I showed that first one. Also I mentioned the null vectors are the same as in a prior example. They were/are {1,0,0}, {0,1,0}, and {0,0,1/2}.As with linear systems in general, any solution can be cast as a specific solution plus a null vector. You are interested in solutions modulo Z and, since the matrices had all integer entries, any solution can trivially be modified by an integer. This means it makes sense to restrict to solutions lying in the unit cube. One such, as noted, is {3/4, 1/8, 3/16}. All others in this restricted range will of necessity be found by adding multiples of the third null vector, {0,0,1/2}. Quite obviously the only other restricted solution will be {3/4, 1/8, 3/16} + {0,0,1/2}, or {3/4, 1/8, 11/16}. So that's how we get the second GAP solution.One can of course put this reasoning into code, using the specific solution and null vectors. I'll show for the example at hand. sol = {3/4, 1/8, 3/16}; nulls = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1/2}}; vars = Array[c, Length[nulls]]; vals = Array[d, Length[sol]]; vals /. Solve[ Flatten[{Thread[sol + vars . nulls == vals], Map[0 <= # <= 1 &, vals], Element[vars, Integers]}], Join[vars, vals]] (* Out[193]= {{3/4, 1/8, 3/16}, {3/4, 1/8, 11/16}} *) 
Posted 1 year ago
 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[...].
Posted 1 year ago
 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: 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? What are the characteristics and properties of the set of all solutions? How to quickly determine if there is no solution?
Posted 1 year ago
Posted 1 year ago
 $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?
Posted 1 year ago
 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?
Posted 1 year ago
 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.
Posted 1 year ago
 Sorry, my statement is unclear. I mean, in all the context mentioned here, it corresponds to the following meaning: mat2 . #&/@sol 
Posted 1 year ago
Posted 1 year ago
 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
Posted 1 year ago
Posted 1 year ago
Posted 1 year ago
 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] 
Posted 1 year ago
 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.
Posted 1 year ago
 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 
Posted 1 year ago
 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.
Posted 1 year ago
 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 ] ] 
Posted 1 year ago
 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.