Minimal integer solution to homogeneous system of linear equations

As the title says, I’m looking for a way to find a minimal integer solution of the homogeneous system of linear equations.

Such systems have infinitely many solutions (since you can multiply by constant or linearly combine the solutions you obtain). Let’s say I obtained a real solution in the form of vector v. I’m looking for a method to transform v such that all of its elements are integers, and ideally, that such solution is minimal required (e.g. (1, 2, 2) and not (2, 4, 4)).

This is somewhat similar to https://stackoverflow.com/questions/13898233/solving-linear-system-over-integers-with-numpy.

Is there a package or a convenient method which does this, or I will have to implement a method myself? Ideally, it should be able to compute the solutions exactly.

What do you mean by “minimal”? Smallest 2-norm?

It’s possible that “A Modification of the LLL Reduction Algorithm” by Pohst solves the problem you’re looking at.

3 Likes

Yes, that’s a good description. Although that’s not the most important part, since transforming a non-minimal solution into the minimal one is not complicated.

I’ll check it. I was just wondering if something similar is available in one of mathematical Julia packages, or I have to make it myself.

The LLLplus.jl package has a couple of LLL functions that may be useful. I haven’t looked recently at how much you’d have to modify them to get the “Modified LLL” of Phost, assuming it solves the problem you’re looking at

1 Like

It turns out that what I was looking for is reduced row-echelon form over Z, which is already implemented in AbstractAlgebra, Nemo and Hecke packages (this discussion helped me find it: Rank is wrong for Rational matrices).

I ended up using AbstractAlgebra, since it’s pure Julia and the most convenient to use.

3 Likes