Re: Newbie solving mod M linear equations

*To*: mathgroup at smc.vnet.net*Subject*: [mg29081] Re: [mg29045] Newbie solving mod M linear equations*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Sun, 27 May 2001 18:04:46 -0400 (EDT)*References*: <200105270153.VAA01598@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Bob Harris wrote: > > Howdy, > > I can't figure out how to use mathematica to solve systems of linear > equations in which all the arithemetic should be performed modulo m. Can > anyone give me a few pointers? > > For example, I might want to solve this system, modulo 5 (this is matrix > times vector = vector): > > [ 0 1 1 1 0 ][A] [1] > [ 1 0 0 1 1 ][B] [2] > [ 1 0 0 1 0 ][C] = [3] (mod 5) > [ 1 1 1 0 1 ][D] [0] > [ 0 1 0 1 0 ][E] [1] > > The solution to this is > > [A] [4] > [B] [2] > [C] = [0] > [D] [4] > [E] [4] > > I know how to solve these things manually, but it gets rather difficult on > the larger systems that I actually use. > > Any help would be appreciated. > > Thanks, > Bob Harris I realize you already found an answer in a related thread, but thought I'd indicate a few details related to efficient usage. The basic method uses LinearSolve. In[170]:= mat = {{0,1,1,1,0}, {1,0,0,1,1}, {1,0,0,1,0}, {1,1,1,0,1}, {0,1,0,1,0}}; In[171]:= rhs = {1,2,3,0,1}; In[172]:= LinearSolve[mat, rhs, Modulus->5] Out[172]= {4, 2, 0, 4, 4} If you want to solve for multiple vectors (e.g, as one might do to invert a matrix), give the second argument as a matrix of column vectors. This will necessitate taking a transpose if what you have is a bunch of individual vectors. For example: In[184]:= LinearSolve[mat, Transpose[{rhs}], Modulus->5] Out[184]= {{4}, {2}, {0}, {4}, {4}} If m is not prime it is possible that LinearSolve will mess up (I'm not certain about this). In that case you may need to write it as a product of prime powers, solve modulo primes, and do a bit of work to lift and combine solutions. An alternative approach, alot easier to code, would involve using Developer`HermiteNormalForm, but this may run into problems sooner with respect to large dimensions of your matrix. If m is prime, mat is square, and you wish to reuse it for different right-hand-side vectors in sequential fashion, you can improve on the basic LinearSolve approach by using LUDecomposition on mat followed by LUBackSubstitution. I once found this tactic handy for coding a fast p-adic solver. Actually it is not of maximal asymptotic efficiency for a subtle reason I'll leave as an exercise for the experts to find, but does quite well in practice. A copy can be found at: http://library.wolfram.com/conferences/conference98/abstracts/various_ways_to_tackle_algebraic_equations.html Daniel Lichtblau Wolfram Research

**References**:**Newbie solving mod M linear equations***From:*Bob Harris <nitlion@mindspring.com>