MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: RE: Re: ColorFunction for ListPlot3D, ListContourPlot or ListDensityPlot ?
  • Next by Date: Re: Trouble modif. Matrix in function
  • Previous by thread: Newbie solving mod M linear equations
  • Next by thread: Re: Newbie solving mod M linear equations