Yahoo Tuning Groups Ultimate Backup tuning-math Finding the preimage of a tempered interval

In my last posts on this subject I introduced some ideas on how to
embed the affine space A^n_R in R^(n+1). I also talked about some ways
to represent affine spans by using matrices in normal form.

Although I wrote originally about affine spaces over R^n, these same
principles trivially apply to Z^n-torsors, which you can embed in
Z^(n+1) if you'd prefer to work in modules over rings instead of
vector spaces. A nice middle ground is to define everything over Q, so
you get fractional monzos and vals. I'll keep using R for simplicity.

For now I'm going to go with these conventions:

1) Notation - affine vals will be represented as (a b c ...|, and
affine monzos as |a b c ...).

2) "Augmented coordinates" - the "copoint" (a b c ...| maps to the
augmented covector <a b c ... ; 1|, and likewise the point |a b c ...
) maps to the augmented vector |a b c ... ; 1>. Note that this
convention affixes "1" to the end of both affine vals and affine
monzos, though there's other ways you could do it.

3) Normal form for monzos - a matrix of monzos will be written with
the columns as monzos, and it will be in normal form if its transpose
is in column-reversed Hermite form, defined as
fliplr(hermiteForm(fliplr(matrix))).

4) Normal form for vals - a matrix of vals will be written with the
rows as vals, and it will be in normal form if the matrix obtained by
removing the rightmost column and appending it to the left of the
matrix is in Hermite form.

A useful application of all this is to find the JI preimage of some
tempered interval, where the tempered interval could be the period,
the generator, or something else. To do this, we'll first take
advantage of the fact that matrices containing augmented vectors are
also just augmented matrices in the usual linear algebra sense.

First, assume you have a mapping matrix:

[1 1 0 -3]
[0 1 4 10]

And say you want to find the preimage of the tempered interval |x y>,
which is an element in the column space of the above matrix. Then
affix the column [-x -y]' to the above matrix, noting the coordinates
are negated

[1 1 0 -3 ; -x]
[0 1 4 10 ; -y]

So for instance, if we want the generator for the above matrix, which
is |0 1>, we affix [0 -1]' to the mapping

[1 1 0 -3 ; 0]
[0 1 4 10 ; -1]

Now, we simply take the null space of this matrix, and we get (in normal form)

[-1 13 4]
[1 -10 -4]
[0 0 1]
[0 1 0]
[1 0 0]

The column space of this matrix is the null space of the augmented
mapping matrix; note the bottom row is the augmented coordinate. To
interpret this as an affine subspace and get our preimage, first take
the intersection of this column space and the affine subspace of
R^(n+1) in which A^n is embedded (e.g. the subspace in which the
augmented coordinate is 1).

The above matrix makes it easy to see that this intersection will
consist of the affine span |-1 1 0 0) + k*|13 -10 0 1> + l*|4 -4 1>,
which is indeed the preimage of |0 1> given the interval we started
with.

I can go deeper into why the paradigm shift from affine space
embedding to ordinary augmented matrix and back produces such a nice
consistent result if anyone wants more detail on that.

Additionally, it's useful to do the same process in reverse and get
the left null space of a matrix in which the column vectors are
monzos, which I'll talk about next. There are some random useful
applications for this too, like finding the generator for a
temperament which has the lowest-complexity interval in its preimage.

-Mike on a bus

🔗genewardsmith <genewardsmith@sbcglobal.net>

🔗Mike Battaglia <battaglia01@gmail.com>

You only get fractional monzos if you consider the domain of the mapping to
be R^n or Q^n instead of Z^n. If the nullspace matrix is in hermite form,
it'll be an integer matrix by definition, you can always just consider all
integral combinations of the column vectors instead of all linear
combinations, and consider the lattice coset formed by the columns instead
of the affine subspace spanned by them.

I'm aware that fractional monzos are indeed trivially in the null space of
the matrix, as would be things like irrational and even uncomputable monzos
if you're working in R^n, but you can just consider integral monzos if
that's all you care about. The only time I can think of when fractional
monzos are truly necessary in this process is if you're trying to find the
preimage of some unmapped interval in a contorted temperament.

I also think that they can be more of a feature than a bug, but that's just
me.

-Mike

On May 26, 2012, at 10:59 PM, genewardsmith <genewardsmith@sbcglobal.net>
wrote:

--- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...> wrote:

> A useful application of all this is to find the JI preimage of some
> tempered interval, where the tempered interval could be the period,
> the generator, or something else.

This seems to have the same problem as the methods I already know about,
namely that you can get fractional monzos for your answer.

🔗genewardsmith <genewardsmith@sbcglobal.net>

🔗Mike Battaglia <battaglia01@gmail.com>

We can represent affine lattices in the same way that we represented affine
subspaces: treat lattices in A^n as lattices in A^(n+1), and then take the
resulting intersection with the subspace with augmented coordinate of 1.

In our embedded representation, what this means is that you really want is
the intersection of the null space with the lattice coset generated by all
Z-affine combinations of |1 0 0 0 ... ;1>, |0 1 0 0 ... ; 1>, |0 0 1 0 ...
; 1>, etc. Since we're going to take the intersection afterwards, this
means we can simply look at the intersection of the null space and the set
all Z-linear combinations of |1 0 0 0 ... ; 0>, |0 1 0 0 ... ; 0>, ... , |0
0 0 0 ... ; 1>, of which our lattice coset will be a coset.

We can accomplish this task in two parts:
1) Find any lattice with augmented vectors of integral coordinates whose
spanning subspace is the null space of our matrix
2) Find the saturation of the lattice.

The first step can be done by taking your null space matrix and multiplying
every entry by the lowest common denominator of the entries in the matrix.

If the resulting matrix is M, then it can be written M=USV, where S is in
Smith normal form. If S is nxm, then you can replace S with the first n
rows of the mxm identity matrix. If this matrix is called I, then the matrix
L representing the associated saturated lattice for your null space will be
L=UIV.

Using your example and putting back into hermite form, we get

|-21 6 5 0 0), |-12 1 3 0 1>, |-20 5 4 1 0>, |-25 7 6 0 0>

This is indeed the correct lattice coset representing the miracle generator.

-Mike

On May 27, 2012, at 3:16 AM, genewardsmith <genewardsmith@sbcglobal.net>
wrote:

--- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...> wrote:
>
> You only get fractional monzos if you consider the domain of the mapping
to
> be R^n or Q^n instead of Z^n. If the nullspace matrix is in hermite form,
> it'll be an integer matrix by definition

The question is, how do I get the nullspace matrix to be in HNF? For
example, the nullspace of

[<1 1 3 3 2; 0|, <0 6 -7 -2 15; -1]]

[[-1/6 1/6 0 0 0 1] [1/2 -5/2 0 0 1 0] [-10/3 1/3 0 1 0 0] [-25/6 7/6 1 0 0
0]]

Now what?

🔗genewardsmith <genewardsmith@sbcglobal.net>

🔗Mike Battaglia <battaglia01@gmail.com>

On May 28, 2012, at 12:53 PM, genewardsmith <genewardsmith@sbcglobal.net>
wrote:

--- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...> wrote:

> Using your example and putting back into hermite form, we get
>
> |-21 6 5 0 0), |-12 1 3 0 1>, |-20 5 4 1 0>, |-25 7 6 0 0>

From my example, your saturation procedure gave me

[[-1 0 0 0 1 6], [-2 0 1 1 2 13], [1 1 -2 -4 -2 -6], [-3 0 2 2 4 20]]

HNF of that is

[[1 0 0 0 0 -6], [0 1 0 -2 0 2], [0 0 1 1 0 1], [0 0 0 0 1 0]]

I'm not getting that at all. Are you sure there's not a bug in your code?
Did you multiply the matrix by 6, take the Smith form, then multiply
inv(U)*I*inv(V)?

Could I see your Maple code?

-Mike

🔗genewardsmith <genewardsmith@sbcglobal.net>

🔗battaglia01 <battaglia01@gmail.com>

On Tue, May 29, 2012 at 1:09 AM, genewardsmith <genewardsmith@sbcglobal.net>
wrote:
>
> --- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...>
> wrote:
>
> > I'm not getting that at all. Are you sure there's not a bug in your
> > code?
> > Did you multiply the matrix by 6, take the Smith form, then multiply
> > inv(U)*I*inv(V)?
>
> Before you said U*I*V, not inv(U)*I*inv(V). But it still doesn't check
> your result.

I said

> If the resulting matrix is M, then it can be written M=USV, where S is in
> Smith normal form.

Maple's Smith Form routine also can output variables called U and V, but they instead satisfy the equation S = UMV. So if you do LinearAlgebra[SmithForm](M, output=['U','S','V']), you need to take the inverse of U and V to do what I said. But I knew this wasn't the problem by itself because I tested this out in Maple, among other things, and I saw it didn't produce the matrix you wrote.

> > Could I see your Maple code?
>
> I'm just calling LinearAlgebra[SmithForm].

It works for me and I can't figure out why you're getting a different result. I can't find the magic bullet to reproduce the matrix you're getting; it keeps spitting out the right answer for me. Here's what I'm doing (view fixed width)

> M := Matrix([[-1/6, 1/6, 0, 0, 0, 1], [1/2, -5/2, 0, 0, 1, 0], [-10/3, 1/3, 0, 1, 0, 0], [-25/6, 7/6, 1, 0, 0, 0]]);
%;
[ -1 1 ]
[ -- - 0 0 0 1]
[ 6 6 ]
[ ]
[ 1 -5 ]
[ - -- 0 0 1 0]
[ 2 2 ]
M := [ ]
[-10 1 ]
[--- - 0 1 0 0]
[ 3 3 ]
[ ]
[-25 7 ]
[--- - 1 0 0 0]
[ 6 6 ]

print(??); # input placeholder
> M := 6*M;
%;
[ -1 1 0 0 0 6]
[ ]
[ 3 -15 0 0 6 0]
M := [ ]
[-20 2 0 6 0 0]
[ ]
[-25 7 6 0 0 0]

> out := LinearAlgebra[SmithForm](M, output = ['U', 'S', 'V']);
%;
[-1 0 0 0 1 6]
[ ]
[ 1 0 0 0] [1 0 0 0 0 0] [ 0 0 0 0 1 0]
[ ] [ ] [ ]
[-6 1 1 1] [0 6 0 0 0 0] [-4 1 1 1 3 25]
out := [ ], [ ], [ ]
[ 8 -2 -1 0] [0 0 6 0 0 0] [-3 0 -1 -2 3 20]
[ ] [ ] [ ]
[-3 1 0 0] [0 0 0 6 0 0] [ 1 0 0 1 2 -3]
[ ]
[ 0 0 0 0 0 1]

> U := out[1];
%;
[ 1 0 0 0]
[ ]
[-6 1 1 1]
U := [ ]
[ 8 -2 -1 0]
[ ]
[-3 1 0 0]

> S := out[2];
%;
[1 0 0 0 0 0]
[ ]
[0 6 0 0 0 0]
S := [ ]
[0 0 6 0 0 0]
[ ]
[0 0 0 6 0 0]

> V := out[3];
%;
[-1 0 0 0 1 6]
[ ]
[ 0 0 0 0 1 0]
[ ]
[-4 1 1 1 3 25]
V := [ ]
[-3 0 -1 -2 3 20]
[ ]
[ 1 0 0 1 2 -3]
[ ]
[ 0 0 0 0 0 1]

> Iden := LinearAlgebra[IdentityMatrix](ArrayTools[Size](S)[1], ArrayTools[Size](S)[2]);
%;
[1 0 0 0 0 0]
[ ]
[0 1 0 0 0 0]
Iden := [ ]
[0 0 1 0 0 0]
[ ]
[0 0 0 1 0 0]

> result := LinearAlgebra[MatrixInverse](U).Iden.LinearAlgebra[MatrixInverse](V);
%;
[-1 1 0 0 0 6]
[ ]
[-2 0 0 0 1 15]
result := [ ]
[-5 2 0 1 0 10]
[ ]
[-5 2 1 0 0 5]

> result := ArrayTools[FlipDimension](LinearAlgebra[HermiteForm](ArrayTools[FlipDimension](result, 2)), 2);
%;
[-21 6 5 0 0 1]
[ ]
[-12 1 3 0 1 0]
result := [ ]
[-20 5 4 1 0 0]
[ ]
[-25 7 6 0 0 0]

-Mike

🔗battaglia01 <battaglia01@gmail.com>

--- In tuning-math@yahoogroups.com, "battaglia01" <battaglia01@...> wrote:
>
> print(??); # input placeholder

I dunno wtf this is, Maple just added a bunch of random crap for no reason. If I remove the outputs I get this (comments added)

> M := Matrix([[-1/6, 1/6, 0, 0, 0, 1], [1/2, -5/2, 0, 0, 1, 0], [-10/3, 1/3, 0, 1, 0, 0], [-25/6, 7/6, 1, 0, 0, 0]]); #Gene's test null space matrix
> M := 6*M; #We're manually multiplying by the GCD here, but you can automate this
> out := LinearAlgebra[SmithForm](M, output = ['U', 'S', 'V']); #get Smith form and save it in an expression sequence called "out"
> U := out[1];
> S := out[2];
> V := out[3];
> Iden := LinearAlgebra[IdentityMatrix](ArrayTools[Size](S)[1], ArrayTools[Size](S)[2]); #create an identity matrix of the same size as S
> result := LinearAlgebra[MatrixInverse](U).Iden.LinearAlgebra[MatrixInverse](V); #do U^-1 * Iden * V^-1
> result := ArrayTools[FlipDimension](LinearAlgebra[HermiteForm](ArrayTools[FlipDimension](result, 2)), 2); #put in column-reversed hermite form

[-21 6 5 0 0 1]
[ ]
[-12 1 3 0 1 0]
result := [ ]
[-20 5 4 1 0 0]
[ ]
[-25 7 6 0 0 0]

There it is.

-Mike

🔗Mike Battaglia <battaglia01@gmail.com>

Gene wrote this on XA:
>
> The step creating the identity matrix didn't work, and anyway you don't want
> to create an identity matrix.

If the mapping is of size nxm, then I want to take the first n rows of
the mxm identity matrix.

So this line didn't work then?

> Iden := LinearAlgebra[IdentityMatrix](ArrayTools[Size](S)[1], ArrayTools[Size](S)[2]);

That works fine for me and gives [[1 0 0 0 0 0] [0 1 0 0 0 0] [0 0 1 0
0 0] [0 0 0 1 0 0]]. Maybe we're using different versions of Maple or
something.

Gene wrote on XA:
> If I understand right, the next thing should have
> been I * V^(-1) = [[-1 1 0 0 0 6] [-6 -2 1 1 1 -6] [1 6 0 -1 -2 8] [1 -3 0 0 1 -3]].
> If that's right we can go on from there.

I don't get how this is different from what I wrote above, especially
if the thing you're calling "I" is the truncated identity matrix you
just said I don't want. But yes, that's right. If the above matrix is
called "M", then putting that in column-reversed Hermite form yields

> ArrayTools[FlipDimension](LinearAlgebra[HermiteForm](ArrayTools[FlipDimension](M, 2)), 2);
[-21 6 5 0 0 1]
[-12 1 3 0 1 0]
[-20 5 4 1 0 0]
[-25 7 6 0 0 0]

Which is the right answer.

-Mike

🔗genewardsmith <genewardsmith@sbcglobal.net>

--- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...> wrote:

> [-21 6 5 0 0 1]
> [-12 1 3 0 1 0]
> [-20 5 4 1 0 0]
> [-25 7 6 0 0 0]

For some reason before when I did the reverse HNF I got something different, but now I check with you! So I guess it was just a mistake on my part.

The convoluted procedure I have coded for doing this stuff gives me 15/14. If I take the monzo for that and tack 1 on the end and add the monzos for what the procedure I use for commas gives, which is [441/440, 539/540, 1375/1372], I can do the reverse HNF thing and come to the same result, everything checks. Equivalently, multiply (15/14)*13, tack on the commas and find the normal interval list. So the real question for me is still what's a good way to take your result, and find the least complex possibility?

🔗Mike Battaglia <battaglia01@gmail.com>

On Wed, May 30, 2012 at 2:54 PM, genewardsmith <genewardsmith@sbcglobal.net>
wrote:
>
> --- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...>
> wrote:
>
> > [-21 6 5 0 0 1]
> > [-12 1 3 0 1 0]
> > [-20 5 4 1 0 0]
> > [-25 7 6 0 0 0]
>
> For some reason before when I did the reverse HNF I got something
> different, but now I check with you! So I guess it was just a mistake on my
> part.

Success then!

> The convoluted procedure I have coded for doing this stuff gives me 15/14.
> If I take the monzo for that and tack 1 on the end and add the monzos for
> what the procedure I use for commas gives, which is [441/440, 539/540,
> 1375/1372], I can do the reverse HNF thing and come to the same result,
> everything checks.

There it is.

> Equivalently, multiply (15/14)*13, tack on the commas and
> find the normal interval list.

Normal interval list = reverse HNF?

> So the real question for me is still what's a
> good way to take your result, and find the least complex possibility?

Well, I was most interested in just finding the right representation
for the affine space in general. It's become painfully clear to me at
this point that all of these normal forms I've put out there are
pretty inadequate one way or another.

As for finding the simplest representation - seems like you guys have
a whole host of ways to do that for the vector part of the matrix;
just TM-reduce it or whatever (PS - I wish TM reduction were on the
Wiki!).

But to get the simplest representation of the note, seems like we just
need to find the point in the affine span which has the closest
weighted Lp distance to the origin, right? I don't have an exact
method and I'll give it some thought, but it seems like you could do
it by using the pseudoinverse to get a rough starting point and then
poking around a bit from there.

How are you finding the generator now and getting 15/14?

-Mike