# Minimal integer solution to homogeneous system of linear equations
**URL:** https://discourse.julialang.org/t/minimal-integer-solution-to-homogeneous-system-of-linear-equations/43848
**Category:** Numerics
**Created:** [July 29, 2020, 12:22am UTC](https://discourse.julialang.org/t/minimal-integer-solution-to-homogeneous-system-of-linear-equations/43848 "2020-07-29T00:22:08Z")
**Posts on this page:** 5
**Page:** 1
### Author:  [@anon37204545](https://discourse.julialang.org/u/anon37204545)
#### Post date: [July 29, 2020, 12:22am UTC](https://discourse.julialang.org/t/minimal-integer-solution-to-homogeneous-system-of-linear-equations/43848/1 "2020-07-29T00:22:08Z")
As the title says, I’m looking for a way to find a minimal integer solution of the [homogeneous system of linear equations](https://en.wikipedia.org/wiki/System_of_linear_equations#Homogeneous_systems).
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 [python - Solving linear system over integers with numpy - Stack Overflow](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.
---
### Author:  [@chrisvwx](https://discourse.julialang.org/u/chrisvwx)
#### Post date: [July 29, 2020, 4:25am UTC](https://discourse.julialang.org/t/minimal-integer-solution-to-homogeneous-system-of-linear-equations/43848/2 "2020-07-29T04:25:59Z")
What do you mean by “minimal”? Smallest 2-norm?
It’s possible that “[A Modification of the LLL Reduction Algorithm](https://www.researchgate.net/publication/222439306_A_Modification_of_the_LLL_Reduction_Algorithm)” by Pohst solves the problem you’re looking at.
---
### Author:  [@anon37204545](https://discourse.julialang.org/u/anon37204545)
#### Post date: [July 29, 2020, 10:36am UTC](https://discourse.julialang.org/t/minimal-integer-solution-to-homogeneous-system-of-linear-equations/43848/3 "2020-07-29T10:36:39Z")
> [@chrisvwx](#):
>
> Smallest 2-norm?
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.
> [@chrisvwx](#):
>
> It’s possible that “[A Modification of the LLL Reduction Algorithm](https://www.researchgate.net/publication/222439306_A_Modification_of_the_LLL_Reduction_Algorithm)” by Pohst solves the problem you’re looking at.
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.
---
### Author:  [@chrisvwx](https://discourse.julialang.org/u/chrisvwx)
#### Post date: [July 29, 2020, 1:39pm UTC](https://discourse.julialang.org/t/minimal-integer-solution-to-homogeneous-system-of-linear-equations/43848/4 "2020-07-29T13:39:06Z")
The [LLLplus.jl](https://github.com/christianpeel/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
---
### Author:  [@anon37204545](https://discourse.julialang.org/u/anon37204545)
#### Post date: [July 29, 2020, 2:44pm UTC](https://discourse.julialang.org/t/minimal-integer-solution-to-homogeneous-system-of-linear-equations/43848/5 "2020-07-29T14:44:54Z")
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 - #19 by chakravala](https://discourse.julialang.org/t/rank-is-wrong-for-rational-matrices/19380/19)).
I ended up using AbstractAlgebra, since it’s pure Julia and the most convenient to use.