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.
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