Transversal generators
Also known as a generator preimage transversal or a generator detempering. Every generator of a regular temperament has a preimage, which is an infinite set of JI intervals that map to it. A transversal means a selection of one representative element from each of a list of sets. So if for each generator in our temperament's list of generators we choose one JI interval that maps to it, then we have a generator preimage transversal for that temperament.
Technical Definition
Given a reduced list of p-limit vals V, we may define a set of transversal generators for V as a set of p-limit intervals q such that one of the vals of V maps q to 1 and the rest map it to 0. By reduced is meant that the GCD of the elements of each of the vals is 1--or in other words, none of the vals are contorted--and that they are linearly independent, so that if there are r vals, the rank of V as a matrix is r.
If v1, v2, ... vr are the vals of V and t1, t2, ... tr are the corresponding transversal generators, then for any p-limit q we have, modulo the regular temperament defined by V
q ≅ t1^v1(q) * t2^v2(q) * ... * tr^vr(q)
In this way the transversal generators provide a transversal of the p-limit, and hence the name.
Examples
Suppose V consists of the 7-limit patent vals for 12 and 19; that is, V = [<12 19 28 34|, <19 30 44 53|]. Then a corresponding list of transversal generators is [49/48, 36/35]. 49/48 corresponds to one step of 12et, and zero steps of 19et, whereas 36/35 is zero steps of 12et, and one step of 19et. This gives us a septimal meantone transversal of the 7-limit where 3/2 is represented by (49/48)^7 * (36/35)^11, and 2 is represented by (49/48)^12 * (36/35)^19. A more familiar septimal meantone transversal starts from the normal val list, [<1 0 -4 -13|, <0 1 4 10|], which corresponds to the transversal generators [2, 3].
Given a list of transversal generators, we may append a comma basis for V and obtain a basis for the entire p-limit. For instance, we may extend [49/48, 36/35] to [49/48, 36/35, 81/80, 126/125]. Taking the corresponding matrix of monzos, whose rows are monzos for this list, inverting it and then transposing, we obtain
[<12 19 28 34|, <19 30 44 53|, <-4 -6 -9 -11|, <-5 -8 -12 -14|]
This is a unimodular matrix defining a change of basis for the p-limit.
For another example, consider [<1 1 1 2|, <0 2 1 1|, <0 0 2 1|] which is the normal val list for breed temperament, the temperament tempering out 2401/2400. A corresponding list of transversal generators is [2, 49/40, 10/7].
Finding the generator preimage transversal
Two methods for finding the generator preimage transversal have been developed. The first was developed by Gene Ward Smith sometime in or before June 2011, which uses the Hermite normal form. The second was developed by Sintel in December 2021, which uses the Smith normal form.
Method using the Smith Normal Form
So we want to find a generator preimage transversal [math]T[/math] for a mapping [math]M[/math] where:
[math]MT = I,[/math]
and where [math]I[/math] is the identity matrix. When this is the case, then for each generator of the temperament represented by [math]M[/math], a different column of [math]T[/math] as a prime-count vector represents an interval that [math]M[/math] maps to that generator. And when this [math]T[/math] has all integer entries, then these generators are all JI.
Essentially we need a way to do:
[math]
M^{-1}MT = M^{-1}I \\
\cancel{M^{-1}M}T = M^{-1}I \\
T = M^{-1}
[/math]
But there's two major problems with this simplistic approach:
- [math]M[/math] is rectangular and therefore cannot be inverted (it has no inverse).
- The pseudoinverse we use in lieu of a true inverse in situations like this doesn't generally give integer results, and so it won't give us the JI generators we seek.
So the pseudoinverse won't solve this problem for us, but the Smith decomposition can help! For a given [math]M[/math], it finds invertible matrices [math]L[/math] and [math]R[/math] for which
[math]
LMR = D,
[/math]
where [math]D[/math] is the Smith Normal Form of [math]M[/math], which is a rectangular diagonal matrix (the name 'D' is for "diagonal"). Furthermore, if [math]M[/math] was defactored, then not only is [math]D[/math] diagonal (only has nonzero values along its main diagonal) but the numbers along its main diagonal are all equal to 1. This type of matrix is called an orthonormal matrix, and has the property that [math]D^{T}D = I[/math], which we're going to take advantage of.
So first let's solve the decomposition equation for [math]M[/math]. First, left-multiply by [math]L^{-1}[/math]:
[math]
L^{-1}LMR = L^{-1}D \\
\cancel{L^{-1}L}MR = L^{-1}D \\
MR = L^{-1}D
[/math]
And then right-multiply by [math]R^{-1}[/math]:
[math]
MRR^{-1} = L^{-1}DR^{-1} \\
M\cancel{RR^{-1}} = L^{-1}DR^{-1} \\
M = L^{-1}DR^{-1}
[/math]
Now we can substitute this result in for [math]M[/math] in our original equation:
[math]
(L^{-1}DR^{-1})T = I
[/math]
And we can proceed to solve this for our target [math]T[/math]. The rest is busywork. First, left-multiply by [math]L[/math]:
[math]
LL^{-1}DR^{-1}T = LI \\
\cancel{LL^{-1}}DR^{-1}T = LI \\
DR^{-1}T = L
[/math]
Then left-multiply by [math]D^{T}[/math]:
[math]
D^{T}DR^{-1}T = D^{T}L \\
\cancel{D^{T}D}R^{-1}T = D^{T}L \\
R^{-1}T = D^{T}L
[/math]
And finally, left-multiply by [math]R[/math]:
[math]
RR^{-1}T = RD^{T}L \\
\cancel{RR^{-1}}T = RD^{T}L \\
T = RD^{T}L
[/math]
And there's our answer! It's still not necessarily giving the simplest or best JI generators, but arriving at those is an independent problem (perhaps by choosing a complexity metric and minimizing it though linear combinations with the commas and the other generators, or perhaps using LLL).
Example
Our mapping is 5-limit meantone, in equave-reduced generator form:
[math]
\left[ \begin{array} {rrr}
1 & 1 & 0 \\
0 & 1 & 4 \\
\end{array} \right]
[/math]
Its Smith Decomposition [math]L, D, R[/math] is:
[math]
\begin{array} {lll}
\left[ \begin{array} {rrr}
1 & -1 \\
0 & 1 \\
\end{array} \right]
, &
\left[ \begin{array} {rrr}
1 & 0 & 0 \\
0 & 1 & 0 \\
\end{array} \right]
, &
\left[ \begin{array} {rrr}
1 & 0 & 4 \\
0 & 1 & -4 \\
0 & 0 & 1 \\
\end{array} \right]
\end{array}
[/math]
And so a transversal of the preimages of its generators are [math]RD^{T}L[/math]:
[math]
\left[ \begin{matrix}
1 & 0 & 4 \\
0 & 1 & -4 \\
0 & 0 & 1 \\
\end{matrix} \right]
\left[ \begin{matrix}
1 & 0 \\
0 & 1 \\
0 & 0 \\
\end{matrix} \right]
\left[ \begin{matrix}
1 & -1 \\
0 & 1 \\
\end{matrix} \right]
=
\left[ \begin{matrix}
1 & -1 \\
0 & 1 \\
0 & 0 \\
\end{matrix} \right]
[/math]
That is, 2/1 and 3/2.
Wolfram Language implementation
getGpt[m_] := Module[{decomp, left, snf, right},
decomp = SmithDecomposition[m];
left = Part[decomp, 1];
snf = Part[decomp, 2];
right = Part[decomp, 3];
right.Transpose[snf].left
];
Method using the Hermite Normal Form
We can find a generator preimage transversal for V by the following procedure:
- Take the transpose of the pseudoinverse of V, call that U
- Find a basis for the commas of V
- For each row U[i] of U, clear denominators and append the monzos of the comma basis for V
- Saturate the result to a list of monzos, call that S
- Apply the ith val V[i] (dot product) to each element of S
- Insert V[i].S[j] in front of the elements of S[j] as the first element, obtaining the jth element T[j] of a modified list T
- Hermite reduce the modified list T, take the first row, and remove the first element (which should be a 1.)
- Consider the rest to be a monzo and convert it to a rational number
- This is a corresponding transveral generator to the ith val V[i] of V; it may be reduced to an equivalent generator of minimal Tenney height by multiplying by the commas of V
Example
Note: I've followed the algorithm as described above. But clearly I am transposing things here way more often than is necessary than if the algorithm was superficially revised.
For 5-limit meantone, [math]V[/math] is
[math] \begin{bmatrix} 1 & 2 & 4 \\ 0 & -1 & -4 \\ \end{bmatrix} [/math]
The pseudoinverse [math]V⁺[/math] is
[math] \frac{1}{33} \begin{bmatrix} 17 & 18 \\ 16 & 15 \\ -4 & -12 \\ \end{bmatrix} [/math]
And that transposed is [math](V⁺)ᵀ[/math], which we'll call [math]U[/math]:
[math] \frac{1}{33} \begin{bmatrix} 17 & 16 & -4 \\ 18 & 15 & -12 \\ \end{bmatrix} [/math]
And here's the comma basis for [math]V[/math]:
[math] \begin{bmatrix} -4 \\ 4 \\ -1 \\ \end{bmatrix} [/math]
Beginning with [math]i = 1[/math], we'll create a matrix out of [math]U[i][/math] with denominators cleared and the comma basis appended (transposed so each comma is a row):
[math] \begin{bmatrix} 17 & 16 & -4 \\ -4 & 4 & -1 \\ \end{bmatrix} [/math]
Defactor and call this [math]S[/math]:
[math] \begin{bmatrix} 1 & 32 & -8 \\ 0 & 4 & -1 \\ \end{bmatrix} [/math]
Now take the dot product of [math]V[1][/math] to each element of [math]S[/math], or in other words, left multiply [math]Sᵀ[/math] by [math]V[1][/math]:
[math] \begin{bmatrix} 1 & 2 & 4 \\ \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 32 & 4 \\ -8 & -1 \\ \end{bmatrix} = \begin{bmatrix} 33 & 4 \\ \end{bmatrix} [/math]
Now prepend that result, transposed, to [math]S[/math]:
[math] \begin{bmatrix} 33 & 1 & 32 & -8 \\ 4 & 0 & 4 & -1 \\ \end{bmatrix} [/math]
Take the Hermite Normal Form:
[math] \begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 4 & -4 & 1 \\ \end{bmatrix} [/math]
Take the first row:
[math] \begin{bmatrix} 1 & 1 & 0 & 0 \\ \end{bmatrix} [/math]
Remove the first element (which should and indeed is a 1):
[math] \begin{bmatrix} 1 & 0 & 0 \\ \end{bmatrix} [/math]
So indeed that gives the period for meantone, 2/1.
Let's repeat the latter steps but now with [math]i = 2[/math]. Here's [math]U[2][/math] with denominators cleared and the comma basis appended:
[math] \begin{bmatrix} 18 & 15 & -12 \\ -4 & 4 & -1 \\ \end{bmatrix} [/math]
Defactor to get our new [math]S[/math]:
[math] \begin{bmatrix} 2 & 31 & -16 \\ 0 & 2 & -1 \\ \end{bmatrix} [/math]
Now take the dot product of [math]V[2][/math] to each element of [math]S[/math], or in other words, left multiply [math]Sᵀ[/math] by [math]V[2][/math]:
[math] \begin{bmatrix} 0 & -1 & -4 \\ \end{bmatrix} \begin{bmatrix} 2 & 0 \\ 31 & 2 \\ -16 & -1 \\ \end{bmatrix} = \begin{bmatrix} 33 & 2 \\ \end{bmatrix} [/math]
Now prepend that result, transposed, to [math]S[/math]:
[math] \begin{bmatrix} 33 & 2 & 31 & -16 \\ 2 & 0 & 2 & -1 \\ \end{bmatrix} [/math]
Take the Hermite Normal Form:
[math] \begin{bmatrix} 1 & 2 & -1 & 0 \\ 0 & 4 & -4 & 1 \\ \end{bmatrix} [/math]
Take the first row:
[math] \begin{bmatrix} 1 & 2 & -1 & 0 \\ \end{bmatrix} [/math]
Remove the first element (which should and indeed is a 1):
[math] \begin{bmatrix} 2 & -1 & 0 \\ \end{bmatrix} [/math]
So indeed that gives the generator for meantone, 4/3. We're done!
Wolfram Language implementation
getGptEntry[u_, v_, c_] := Module[{base},
base = Transpose[columnHermiteDefactor[Join[{u}, Transpose[c]]]];
Drop[First[Take[hnf[Transpose[Join[{v}.base,base]]],1]],1]
];
getGptSmithMethod[m_] := Module[{c},
c = nullSpaceBasis[m];
Transpose[MapThread[getGptEntry[#1, #1, c]&, {Map[multByLcd,Transpose[PseudoInverse[m]]],m}]]
];
getGptSmithMethod[{{1,2,4},{0,-1,-4}}] (* {{1,2},{0,-1},{0,0}} = 2/1 and 4/3 as expected *)