Extracting from some set of target intervals those consistent with a subgroup

I'm trying to find an elegant way to find the intersection of some
subgroup with some set of target intervals in the parent group. For
example, let's say I want to find the intersection of the 15-odd-limit
tonality diamond with the 2.9.11/7.15 subgroup. What's the easiest way
to do so?

The above situation specifically is rather easy, but for an arbitrary
subgroup and an arbitrary set of target intervals it might not be. I'd
rather code something up that lets me find the intersection of an
arbitrary subgroup with an arbitrary set of target intervals.

I had a few ideas about how to do this:

1) Build a projection matrix that zeros out components that aren't in
my subgroup, multiply all my target monzos by that, and prune for
duplicates. But I'd also like to express the monzos in the new
subgroup basis, which is where I'm running into trouble.
2) Treat the shift to a new subgroup as the same thing as a change of
basis. Keenan suggested using Gram-Schmidt Orthogonalization as a way
to "complete" the subgroup basis within the original limit; I'll call
these "junk vectors." Then, if I get any junk vector components when I
shift the basis, I'll know the target interval isn't in the subgroup I
want. (Some finessing of this approach is required for subgroup bases
like 2.9.7.11, but it's trivial and not worth talking about.)

#1 makes me happy in some kind of OCD way, but #2 is probably simpler.
The problem is that MATLAB doesn't have Gram-Schmidt
Orthogonalization, and I don't have the time to implement a routine
for it now. What I really need is the simplest way to get a set of
junk vectors that are linearly independent from my subgroup basis
vectors, expressed in the original basis. I know how to implement this
in NP time (try combinations of primes and check to see if the
determinant of the matrix is nonzero), but this is pretty slow
especially given all the overhead MATLAB throws onto things.

Does anyone know a quick algorithm to get a complementary set of
vectors, which is linearly independent from a set of other vectors, in
a way that the union of the two sets spans the entire vector space?

I also remember Graham had some way to do this too, involving writing
a matrix that expresses the subgroup in the original basis, and going
from there.

-Mike

The term for what I'm looking for is apparently "complementary subspace."

Any subgroup has a corresponding "full-limit," defined as the group of
all primes up to the largest prime factor in the subspace. The
subgroup spans a subspace of this group.

What would be of great help to me is to find the quickest way to find
the complementary subspace of this space, and then get a set of basis
vectors for it. I feel like it's related to the null space of the
matrix which represents the new partial basis in terms of the old one,
but I'm not sure what the exact connection is.

I don't have Gram-Schmidt orthogonalization in MATLAB, but I have QR
decomposition; maybe that'll be of some help?

-Mike

On Mon, Jan 16, 2012 at 4:38 PM, Mike Battaglia <battaglia01@gmail.com> wrote:
> I'm trying to find an elegant way to find the intersection of some
> subgroup with some set of target intervals in the parent group. For
> example, let's say I want to find the intersection of the 15-odd-limit
> tonality diamond with the 2.9.11/7.15 subgroup. What's the easiest way
> to do so?
>
> The above situation specifically is rather easy, but for an arbitrary
> subgroup and an arbitrary set of target intervals it might not be. I'd
> rather code something up that lets me find the intersection of an
> arbitrary subgroup with an arbitrary set of target intervals.
>
> I had a few ideas about how to do this:
>
> 1) Build a projection matrix that zeros out components that aren't in
> my subgroup, multiply all my target monzos by that, and prune for
> duplicates. But I'd also like to express the monzos in the new
> subgroup basis, which is where I'm running into trouble.
> 2) Treat the shift to a new subgroup as the same thing as a change of
> basis. Keenan suggested using Gram-Schmidt Orthogonalization as a way
> to "complete" the subgroup basis within the original limit; I'll call
> these "junk vectors." Then, if I get any junk vector components when I
> shift the basis, I'll know the target interval isn't in the subgroup I
> want. (Some finessing of this approach is required for subgroup bases
> like 2.9.7.11, but it's trivial and not worth talking about.)
>
> #1 makes me happy in some kind of OCD way, but #2 is probably simpler.
> The problem is that MATLAB doesn't have Gram-Schmidt
> Orthogonalization, and I don't have the time to implement a routine
> for it now. What I really need is the simplest way to get a set of
> junk vectors that are linearly independent from my subgroup basis
> vectors, expressed in the original basis. I know how to implement this
> in NP time (try combinations of primes and check to see if the
> determinant of the matrix is nonzero), but this is pretty slow
> especially given all the overhead MATLAB throws onto things.
>
> Does anyone know a quick algorithm to get a complementary set of
> vectors, which is linearly independent from a set of other vectors, in
> a way that the union of the two sets spans the entire vector space?
>
> I also remember Graham had some way to do this too, involving writing
> a matrix that expresses the subgroup in the original basis, and going
> from there.
>
> -Mike

--- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...> wrote:
>
> The term for what I'm looking for is apparently "complementary subspace."
>
> Any subgroup has a corresponding "full-limit," defined as the group of
> all primes up to the largest prime factor in the subspace. The
> subgroup spans a subspace of this group.
>
> What would be of great help to me is to find the quickest way to find
> the complementary subspace of this space, and then get a set of basis
> vectors for it. I feel like it's related to the null space of the
> matrix which represents the new partial basis in terms of the old one,
> but I'm not sure what the exact connection is.
>
> I don't have Gram-Schmidt orthogonalization in MATLAB, but I have QR
> decomposition; maybe that'll be of some help?

QR actually generalizes Gram-Schmidt. Anything you can do with Gram-Schmidt you can do with QR just as well.

Let A be the non-square matrix whose columns are the monzos of the subgroup generators.

octave:1> A = [[1;0;0;0;0] [0;2;0;0;0] [0;0;0;-1;1] [0;1;1;0;0]]
A =

1 0 0 0
0 2 0 1
0 0 0 1
0 0 -1 0
0 0 1 0

Now we do QR decomposition of A.

octave:2> [Q,R,S] = qr(A);
octave:3> Q
Q =

0.00000 0.00000 0.00000 1.00000 0.00000
-1.00000 0.00000 0.00000 0.00000 0.00000
-0.00000 -0.00000 1.00000 0.00000 0.00000
-0.00000 0.70711 0.00000 -0.00000 0.70711
-0.00000 -0.70711 -0.00000 0.00000 0.70711

A has 4 columns, meaning the subgroup has dimension 4. Therefore, the first 4 columns of Q are a basis for the subgroup. (They're actually just the normalized columns of A, in a different permutation.) The rest of the columns of Q are the "junk monzos" that you want.

So, if you want a change-of-basis matrix, here's what you do:

octave:4> [A Q(:,5:5)]
ans =

1.00000 0.00000 0.00000 0.00000 0.00000
0.00000 2.00000 0.00000 1.00000 0.00000
0.00000 0.00000 0.00000 1.00000 0.00000
0.00000 0.00000 -1.00000 0.00000 0.70711
0.00000 0.00000 1.00000 0.00000 0.70711

This matrix is guaranteed to have full rank, with the first columns of it being A and the rest spanning a complementary subspace.

Let's do another example: 2.7/5.11/5

octave:1> A = [[1;0;0;0;0] [0;0;-1;1;0] [0;0;-1;0;1]];
octave:2> [Q,R,S] = qr(A);
octave:3> Q
Q =

0.00000 0.00000 -1.00000 0.00000 0.00000
-0.00000 0.00000 0.00000 0.57735 -0.81650
0.70711 0.40825 0.00000 0.47140 0.33333
-0.70711 0.40825 0.00000 0.47140 0.33333
-0.00000 -0.81650 -0.00000 0.47140 0.33333

octave:4> [A Q(:,4:5)]
ans =

1.00000 0.00000 0.00000 0.00000 0.00000
0.00000 0.00000 0.00000 0.57735 -0.81650
0.00000 -1.00000 -1.00000 0.47140 0.33333
0.00000 1.00000 0.00000 0.47140 0.33333
0.00000 0.00000 1.00000 0.47140 0.33333

In this case the last 2 columns of this matrix span the 2D complementary subspace. They are guaranteed to be orthogonal to all the columns of A and to each other, which avoids numerical instability.

The only serious drawback to this method is that all the math is floating point rather than integer, and you can't fix that with just QR. Maybe Gene has some analog to QR for integer matrices.

RREF is to Hermite normal form as QR decomposition is to ___?

Keenan

--- In tuning-math@yahoogroups.com, "Keenan Pepper" <keenanpepper@...> wrote:

> The only serious drawback to this method is that all the math is floating point rather than integer, and you can't fix that with just QR. Maybe Gene has some analog to QR for integer matrices.

You might try our old friend from the saturation problem, the right reducing matrix for Smith normal form.