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'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
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