       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 0 0 1 1 ][B]   
> [ 1 0 0 1 0 ][C] =   (mod 5)
> [ 1 1 1 0 1 ][D]   
> [ 0 1 0 1 0 ][E]   
>
> The solution to this is
>
> [A]   
> [B]   
> [C] = 
> [D]   
> [E]   
>
> 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:= 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:= rhs = {1,2,3,0,1};

In:= LinearSolve[mat, rhs, Modulus->5]
Out= {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:= LinearSolve[mat, Transpose[{rhs}], Modulus->5]
Out= {{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