Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

We can use RowReduce with a field. For example, we state

RowReduce[{{1,3,5},{0,1,2}},Modulous->23]

...which then returns:

{{1,0,22},{0,1,2}}

...So we will have effectively solved a linear system in a field.

THE QUESTION

Can we somehow use this to solve a system with variables, i.e. solve a symbolic system? As an example, I would like to somehow solve:

RowReduce[{{1,3,a},{0,1,b}},Modulous->23]

The idea is that we should get a result essentially stating something like:

{{1,0,a - 3b},{0,1,b}}

or possibly even better:

{{1,0,a + 20b},{0,1,b}}

The first result is just the solution without the modulous included. I'm wondering if there is some way to get the second result.

share|improve this question
    
RowReduce[{{1, 3, a}, {0, 1, b}}] gives {{1, 0, a - 3 b}, {0, 1, b}}. All you seem to want is for each element of this to be reduced by the modulus? –  bill s Aug 26 '13 at 0:54
    
@bills: Sort of. The problem that I have is that if I don't use a field, the values/coefficients are astronomically large. So I'd like to find a way to work with smaller coefficients, if possible. In the end, the results I get from this particular piece of linear algebra will be used in a field anyways. –  Matt Groff Aug 26 '13 at 3:19
1  
Check the nb here. See section "Linear Algebra in a Galois field" –  Daniel Lichtblau Aug 26 '13 at 18:57
    
@DanielLichtblau: It seems to have the solution I'm looking for. Unfortunately, I don't have the mathematical background to understand a Groebner Basis. I would be grateful if someone could essentially convert this code into something that works with integers modulo $p$. –  Matt Groff Aug 26 '13 at 19:08
    
Essentially converted. –  Daniel Lichtblau Aug 26 '13 at 19:24

1 Answer 1

up vote 3 down vote accepted

Per comment, this is based on "Linear Algebra in a Galois field" from the notebook avaliable here. (Given its age, one might be surprised at how often I seem to need it).

Packaged code:

rowReduceModP[mat_?MatrixQ, p_] /; PrimeQ[p] := Module[
  {n = Length[mat[[1]]], z, newvars, gb},
  newvars = Array[z, n];
  gb = GroebnerBasis[mat.newvars, newvars, 
    CoefficientDomain -> RationalFunctions, Modulus -> p];
  Reverse[Outer[D, gb, newvars]]
  ]

Example:

mat = {{1, 3, a}, {0, 1, b}};
rowReduceModP[mat, 23]

(* Out[42]= {{1, 0, a + 20 b}, {0, 1, b}} *)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.