Find integer solutions to a set of equations with more unknowns than equations

Question

I am trying to build a system for which I need to find a solution to a set of linear equations with (much) more variables than equations.

The problem boils down to the following:

Imagine a set of equations:

A = A1*X1 + A2*X2 + ... + AnXn
B = B1*X1 + B2*X2 + ... + BnXn

How can I find one or multiple (positive) integer solutions to this system?

Note: I have been looking at the apache-commons-math library but I couldn't find any directions on how to solve/find a solution of a system with free variables.

Answer 1

Use the Lenstra–Lenstra–Lovász lattice basis reduction algorithm to find the Hermite normal form of your system.

It's straaightforward in matlab http://fr.mathworks.com/help/symbolic/mupad_ref/linalg-hermiteform.html

Check NTL for c++ http://www.shoup.net/ntl/index.html

Answer 2

Follow this example: suppose the equations are:

7 = x + 3y + 4z + 9w
12 = 4x + 2y + 3z + 7w

There are 2 equations and 4 unknowns. You can set 2 of the unknowns to be parameters, so the system will have as many equations as unknowns:

7 - (4z + 9w) = x + 3y
12 - (3z + 7w) = 4x + 2y

We will be using x and y as the unknowns. It is possible to solve it and leave w and z as parameters in the linear solution:

x = (22 - 3w - z)/10
y = (16 - 29w - 13z)/10

Now, you need to make the numerators divisible by 10, the denominator. If there is a solution, you can test all the parameters from 1 to 10.

In general, you do this:

• Choose parameters so that there are as many unknowns as equations. Try to leave the unknowns that generates the smallest absolute value for the determinant (in the example, it was 10, but choosing y and z would be better, as it would be |det|=3)
• Solve the linear system and generate the answer depending on the parameters
• Test the values of the parameters from 1 to the absolute value of the det (if there is a solution, you will find it at this point), until there is a integer solution for all the unknowns (that is why you choose the smallest determinant absolute value before) and check if it is positive (this was not illustrated in the example).

Sorry if it is brute force in the final step, but at least there is a possibility of minimizing the range of the test. Maybe, there could be a better way to solve the final system of diophantine equations, but I don't know any method.

EDIT1

There is a method to avoid brute forcing the last part. Again, in the example, you have to make:

22 = 3w + z (congruent, mod 10)
16 = 29w + 13z (congruent, mod 10)

Applying the modulus:

2 = 3w + z (congruent, mod 10)
6 = 9w + 3z (congruent, mod 10)

You can make the system of congruences triangular (Gaussian elimination), multiplying a congruence by inverses in the modulus 10 and summing up to the other ones. The inverse of 9 in the modulus 10 is -1, so we multiply the last congruence:

2 = 3w + z (congruent, mod 10)
-6 = -9w + -3z (congruent, mod 10)

Equivalent to:

2 = 3w + z (congruent, mod 10)
4 = w + 7z (congruent, mod 10)

Then, multiply by -3 and add to the first:

2 - 3*4 = 3w + z -3w - 21z (congruent, mod 10)
4 = w + 7z (congruent, mod 10)

Equivalent to:

-10 = -20z (congruent, mod 10)
4 = w + 7z (congruent, mod 10)

Then, you solve from top to bottom (this example seems to be true for any z value). There can be some degree of freedom if you have more parameters than congruences, but they are equivalent and you can set the excess parameters at any value, preferably the least which is 1.

Let me know if there is something not clear yet!

Answer 3

I would try the following approach (note that I never had to deal with that problem, so take this answer as an attempt to solve with you the problem instead of a real analytical answer).

You just find solutions just like if it is a regular system, so you may possibly find infinetly many solutions:

Example:

y = x + 3

then the real numbers pair (2,5) is a possible real solution for that system, once you have the infinitely many solutions you just restrict a subset of solutions that are made by whole numbers.

Of course you have constraints, in our case the solution has just 1 free variable, so we can write all solutions like that:

(x, x+3)

Surprise:

If there's a irrational number somewhere, there are no integer solutions:

(x, x+pi)  => neither 1st or 2nd number here can be whole at same time

So you can probably find integer solutions if and only if your "infinitely many solutions" are constrained by whole or by rational numbers.

Assume you have the following vector:

 ( 3x, (2/5)y, y, x, x+y)

Then a whole solution can be:

 x=3
 y=10/2

If you feel the answer is not satisfying for you, Just tell: I'll delete it to not gain the bounty points