getLinearDiophantineSolution -- find a solution of the linear Diophantine equation Ax = b

Synopsis

Usage:

getLinearDiophantineSolution(l, L)

getLinearDiophantineSolution(l, A)
Inputs:
- L, a basic list,
- l, a basic list,
- A, a matrix,
Optional inputs:
- Safe => a Boolean value, default value true, turns on or off routine checks in the function
Outputs:
- a list,

Description

Given a linear Diophantine equation $Ax = b$ (i.e. an integer matrix with target vector also integer), we want to find a solution of this equation.

i1 : colList = {{1,3,7}, {2,4,-31}, {1,6,101}, {3,-2,47}, {8,9,1}};

i2 : A = transpose matrix colList;

              3       5
o2 : Matrix ZZ  <-- ZZ

i3 : b = {1, 2, 3}

o3 = {1, 2, 3}

o3 : List

i4 : getLinearDiophantineSolution(b, A)

o4 = {-9268, 3946, 1941, -188, 0}

o4 : List

i5 : sol = getLinearDiophantineSolution(b, colList )

o5 = {-9268, 3946, 1941, -188, 0}

o5 : List

i6 : sum apply(#sol, i->(sol#i)*(colList#i) )

o6 = {1, 2, 3}

o6 : List

When the context is clear, set the Safe option to false in order to avoid routine checks.

i7 : A = matrix{ {1, 0, 0, 0, 0}, {0, 2, 0, 0, 0}, {3, 4, 5, 6, 8} }

o7 = | 1 0 0 0 0 |
     | 0 2 0 0 0 |
     | 3 4 5 6 8 |

              3       5
o7 : Matrix ZZ  <-- ZZ

i8 : b = {1, 2, 3}

o8 = {1, 2, 3}

o8 : List

i9 : getLinearDiophantineSolution(b, A, Safe => false)

o9 = {1, 1, 16, -14, 0}

o9 : List

Ways to use getLinearDiophantineSolution :

getLinearDiophantineSolution(BasicList,BasicList)
getLinearDiophantineSolution(BasicList,Matrix)

For the programmer

The object getLinearDiophantineSolution is a method function with options.

getLinearDiophantineSolution -- find a solution of the linear Diophantine equation Ax = b

Synopsis

Description

See also

Ways to use getLinearDiophantineSolution :

For the programmer