Xenharmonic Wiki

Generator preimage: Difference between revisions

← Older editNewer edit →
VisualWikitext
Cmloegcmluin (talk | contribs)
autopatrolled, emailconfirmed
5,170 edits
GCF back to GCD, for better distention from "greatest factor", and it's more popular anyway
Cmloegcmluin (talk | contribs)
autopatrolled, emailconfirmed
5,170 edits
Line 22: Line 22:


=Finding the transversal generators=
=Finding the transversal generators=
Two methods for finding transversal generators have been developed. The first was developed by [[Gene Ward Smith]] sometime in or before June 2011. After Gene's passing, an effort was led to discover an explanation for why it works. This effort was unsuccessful in its original mission, however, did lead [[User:Sintel|Sintel]] to his development of a simpler method in December 2021.
== The Sintel method ==
So we want to find a generators matrix <math>G</math> for a mapping <math>M</math> where:
<math>MG = 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>G</math> as a prime-count vector represents an interval that <math>M</math> maps to that generator. And when this <math>G</math> has all integer entries, then these generators are all JI.
Essentially we need a way to do:
<math>
M^{-1}MG = M^{-1}I \\
\cancel{M^{-1}M}G = M^{-1}I \\
G = 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 diagonal matrix (hence the name "D"). 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})G = I
</math>
And we can proceed to solve this for our target <math>G</math>. The rest is busywork. First, left-multiply by <math>L</math>:
<math>
LL^{-1}DR^{-1}G = LI \\
\cancel{LL^{-1}}DR^{-1}G = LI \\
DR^{-1}G = L
</math>
Then left-multiply by <math>D^{T}</math>:
<math>
D^{T}DR^{-1}G = D^{T}L \\
\cancel{D^{T}D}R^{-1}G = D^{T}L \\
R^{-1}G = D^{T}L
</math>
And finally, left-multiply by <math>R</math>:
<math>
RR^{-1}G = RD^{T}L \\
\cancel{RR^{-1}}G = RD^{T}L \\
G = 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).
=== 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 some JI 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 ===
{{Databox|jiG[]|
<syntaxhighlight lang="mathematica">
jiG[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
];
</syntaxhighlight>}}
== The Smith method ==
We can find transversal generators for V by the following procedure:
We can find transversal generators for V by the following procedure:


<ul><li>Take the transpose of the [[Tenney-Euclidean_Tuning#The pseudoinverse|pseudoinverse]] of V, call that U</li><li>Find a basis for the commas of V</li><li>For each row U[i] of U, clear denominators and append the monzos of the comma basis for V</li><li>[[Saturation|Saturate]] the result to a list of monzos, call that S</li><li>Apply the ith val V[i] (dot product) to each element of S</li><li>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</li><li>Hermite reduce the modified list T, take the first row, and remove the first element (which should be a 1.)</li><li>Consider the rest to be a monzo and convert it to a rational number</li><li>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|Tenney height]] by multiplying by the commas of V</li></ul>       
<ul><li>Take the transpose of the [[Tenney-Euclidean_Tuning#The pseudoinverse|pseudoinverse]] of V, call that U</li><li>Find a basis for the commas of V</li><li>For each row U[i] of U, clear denominators and append the monzos of the comma basis for V</li><li>[[Saturation|Saturate]] the result to a list of monzos, call that S</li><li>Apply the ith val V[i] (dot product) to each element of S</li><li>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</li><li>Hermite reduce the modified list T, take the first row, and remove the first element (which should be a 1.)</li><li>Consider the rest to be a monzo and convert it to a rational number</li><li>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|Tenney height]] by multiplying by the commas of V</li></ul>       


== Example ==
=== 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.
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.
Line 210: Line 394:
So indeed that gives the generator for meantone, 4/3. We're done!
So indeed that gives the generator for meantone, 4/3. We're done!


== Wolfram Language implementation ==
=== Wolfram Language implementation ===


{{Databox|transversalGenerators[]|
{{Databox|transversalGenerators[]|
Line 230: Line 414:
[[Category:generator]]
[[Category:generator]]
[[Category:theory]]
[[Category:theory]]
[[Category:Regular temperament theory]]
[[Category:todo:reduce_mathslang]]
[[Category:todo:reduce_mathslang]]
Retrieved from "https://en.xen.wiki/w/Generator_preimage"