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>
- Newbie solving mod M linear equations