Eliminating torsion

I've been trying out by hand a method which looks promising.

Let M be a kxn integral matrix with linearly independent rows representing a list of vals or monzos. Stepping through the kxk minors in some order, find the first one which is nonsingular and not a multiple of the identity, and take the adjoint matrix. Multiply M on the left by this, and divide out the GCD of all the rows. Rinse, lather, repeat. Seems to be working so far.

--- In tuning-math@yahoogroups.com, "genewardsmith" <genewardsmith@...> wrote:

>Multiply M on the left by this, and divide out the GCD of all the rows. Rinse, lather, repeat. Seems to be working so far.

In order for this to work, evidently you need a more elaborate reduction step. Iterating Hermite reduction, GCD rediuction, Hermite again etc until it stabizizes may work, at least it has been. Maybe I need to find some good unimodular matricies instead of these adjoints.

On 12 July 2010 09:07, genewardsmith <genewardsmith@sbcglobal.net> wrote:

> In order for this to work, evidently you need a more elaborate reduction step. Iterating Hermite reduction, GCD rediuction, Hermite again etc until it stabizizes may work, at least it has been. Maybe I need to find some good unimodular matricies instead of these adjoints.

Removing torsion from a pair of vectors is fairly easy. Perhaps the
solution is to start with a pair, and add one vector at a time,
removing the torsion as you go.

I found an algorithm using the extended Euclidean algorithm, but I
didn't understand it. You might find a post about it in the archives.

Graham

--- In tuning-math@yahoogroups.com, Graham Breed <gbreed@...> wrote:

> I found an algorithm using the extended Euclidean algorithm, but I
> didn't understand it. You might find a post about it in the archives.

I didn't. I've quit with the adjoints, since I've found that in all cases I've tried I can reduce by interating Hermite, GCD, LLL, GCD.
Do you have any nasty examples to test this with?

On 13 July 2010 07:49, genewardsmith <genewardsmith@sbcglobal.net> wrote:
>
>
> --- In tuning-math@yahoogroups.com, Graham Breed <gbreed@...> wrote:
>
>> I found an algorithm using the extended Euclidean algorithm, but I
>> didn't understand it.  You might find a post about it in the archives.
>
> I didn't. I've quit with the adjoints, since I've found that in all cases I've tried I can reduce by interating Hermite, GCD, LLL, GCD.

This is the link I should have given, then:

http://www.math.niu.edu/~rusin/known-math/95/null

> Do you have any nasty examples to test this with?

Not really, no. What I did was generate a huge load of mappings from
my usual temperament search, and try to find their unison vectors. If
they ended up with torsion, the program would report it. I don't
remember the details. It's likely that a different algorithm will
fail for different cases anyway.

Graham