[Haskell-cafe] Solving integer equations in Haskell
ariep at xs4all.nl
Mon Oct 15 17:29:20 CEST 2012
> Can anyone suggest a library written in Haskell which can solve equations of
> the form xM(transpose(x)) = y, where x should be an integer vector, M is an
> integer matrix and y is an integer? I'm aware that Mathematica can do this,
> but I would like something written in Haskell. I haven't been sure of what
> exact keywords I should be searching for, hence my asking here.
You may interpret the function x ↦ x M transpose(x) as a quadratic form on the
additive group of vectors. The group of integer vectors, together with such a
quadratic form, is usually called a /lattice/ (not to be confused with its
other meaning, of a set with a partial order and some meet/join operators).
A vector x satisfying your equation is sometimes said to /represent/ the
number y, with respect to the quadratic form.
On hackage, a quick search gives the "Lattices" package, which seems related.
(There is also the "lattices" package, but this is about the other lattices.)
Incidentally, I also have use for this functionality, but specifically for
vectors with 2 components (so the quadratic form is then binary). The equation
is then a generalised Pell equation, and I think I have read somewhere how to
solve it. If such code does not exist yet, I will probably write it, but this
might not be very soon.
More information about the Haskell-Cafe