Defactoring algorithms: Difference between revisions

(12 intermediate revisions by 6 users not shown)

Line 1:

{{Todo|inline=1| rework |text=Try explaining without wedgies outside historical notes.}}

This article discusses how to identify [[enfactoring]] in [[regular temperament]] [[mapping]]s and then [[defactoring|defactor]] it.

Line 289:

Line 291:

After we know how to do these two things individually, we will learn how to tweak them and assemble them together in order to perform a complete column Hermite defactoring.

Fortunately, both of these two processes can be done using a technique you may already be familiar with if you have learned how to calculate the nullspace of a mapping by hand (as demonstrated [[Dave Keenan ~~%26~~ Douglas Blumeyer~~%27s~~ guide to RTT/Exploring temperaments #Nullspace|here]]):

Fortunately, both of these two processes can be done using a technique you may already be familiar with if you have learned how to calculate the nullspace of a mapping by hand (as demonstrated [[Dave Keenan & Douglas Blumeyer's guide to RTT/Exploring temperaments#Nullspace|here]]):

# Augmenting your matrix with an identity matrix

Line 339:

Line 341:

<math>

\left[ \begin{array} {ccc|cc}

0 & -11 & 4 & 13 & -6

0 & -11 & 4 & 13 & -6 \\

2 & 5 & 4 & -2 & 1 \\

\end{array} \right]

Line 353:

Line 355:

</math>

We're actually quite close to done! All we need to do is flip the signs on the 2nd row. But wait, you protest! Isn't that multiplying a row by -1, which we specifically forbade? Well, sure, but that just shows we need to clarity what we're concerned about, which is essentially enfactoring. Multiplying by -1 does not change the GCD of the row, where multiplying by -2 or 2 would. Note that because the process for taking the HNF forbids multiplying ''or dividing'', it will never introduce enfactoring where was there was none previously, but it also does not remove enfactoring that is there.

We're actually quite close to done! All we need to do is flip the signs on the 2nd row. But wait, you protest! Isn't that multiplying a row by −1, which we specifically forbade? Well, sure, but that just shows we need to clarity what we're concerned about, which is essentially enfactoring. Multiplying by −1 does not change the GCD of the row, where multiplying by −2 or 2 would. Note that because the process for taking the HNF forbids multiplying ''or dividing'', it will never introduce enfactoring where was there was none previously, but it also does not remove enfactoring that is there.

Perhaps another helpful way of thinking about this is that multiplying the row by -1 does not alter the potential effects this row could have being added or subtracted from other rows. It merely swaps addition and subtraction. Whereas multiplying the row by any integer with absolute value greater than 1 ''would'' affect the potential effects this row could have being added or subtracted from other rows: it would limit them.

Perhaps another helpful way of thinking about this is that multiplying the row by −1 does not alter the potential effects this row could have being added or subtracted from other rows. It merely swaps addition and subtraction. Whereas multiplying the row by any integer with absolute value greater than 1 ''would'' affect the potential effects this row could have being added or subtracted from other rows: it would limit them.

So, let's do that sign flip:

Line 368:

Line 370:

And we're done! Let's confirm though.

# '''All pivots > 0?''' Check. The 1st row's pivot is 2 and the 2nd row's pivot is 11.

# '''All entries in pivot columns below the pivots {{=}} 0'''? Check. This only applies to one entry—the bottom right one, below the 1st row's pivot—but it is indeed 0.

# '''All entries in pivot columns above the pivots ≥ 0 and strictly less than the pivot'''? Check. Again, this only applies to one entry—the center top one, above the 2nd row's pivot of 11—but it is 5, and 5 is indeed non-negative and < 11.

And so, we have performed the Hermite decomposition. The matrix to the left of the augmentation line—the one in place of our original matrix—is that original matrix in HNF:

Line 449:

Line 451:

</math>

Okay, let's next target the bottom-center entry. How can we make that -2 into a 0? Let's add the 2nd row to the 3rd row 2 times:

Okay, let's next target the bottom-center entry. How can we make that −2 into a 0? Let's add the 2nd row to the 3rd row 2 times:

<math>

Line 469:

Line 471:

</math>

Finally, we just need to divide the 3rd row by -2. Yes, unlike with the Hermite decomposition, all elementary row operations are permitted, including multiplying or dividing rows. And in this case there's no restrictions against non-integers (which we didn't even explicitly mention when doing the HNF, but yes, HNF requires integers). So here's where we end up:

Finally, we just need to divide the 3rd row by −2. Yes, unlike with the Hermite decomposition, all elementary row operations are permitted, including multiplying or dividing rows. And in this case there's no restrictions against non-integers (which we didn't even explicitly mention when doing the HNF, but yes, HNF requires integers). So here's where we end up:

<math>

Line 782:

Line 784:

\end{matrix} \right]</math>

The pivots are 1 and 11, so that 11 tells us that we had a common factor of 11<ref group="note">In the doubly-enfactored case of {{rket|{{map|17 16 -4}} {{map|4 -4 1}}}}, i.e. with a common factor of 33 = 3 × 11, the two pivots of the HNF are 3 and 11, putting each of them on display separately.</ref><ref group="note">It's interesting to observe that while the 11-enfactoring can be observed in the original matrix as a linear combination of 2 of the 1st row with -3 of the 2nd row, i.e. 2{{map|6 5 -4}} + -3{{map|4 -4 1}} = {{map|0 22 -11}}, the linear combination of ''columns'', i.e. slicing the original {{rket|{{map|6 5 -4}} {{map|4 -4 1}}}} mapping the other direction like {{rbra|{{vector|6 4}} {{vector|5 -4}} {{vector|-4 1}}}}, that leads to the revelation of this 11 is completely different: -1{{vector|6 4}} + 2{{vector|5 -4}} + 1{{vector|-4 1}} = {{vector|0 11}}.</ref>. You could say that the HNF is useful for identifying common factors, but not for removing them. But if you leave them behind in the column-style HNF, the information that is retained in the unimodular matrix which is the other product of the Hermite decomposition, is enough to preserve everything important about the temperament, to get you back to where you started via an inverse and a trimming of extraneous rows.

The pivots are 1 and 11, so that 11 tells us that we had a common factor of 11<ref group="note">In the doubly-enfactored case of {{rket|{{map|17 16 -4}} {{map|4 -4 1}}}}, i.e. with a common factor of {{nowrap|33 {{=}} 3 × 11}}, the two pivots of the HNF are 3 and 11, putting each of them on display separately.</ref><ref group="note">It's interesting to observe that while the 11-enfactoring can be observed in the original matrix as a linear combination of 2 of the 1st row with −3 of the 2nd row, i.e. 2{{map|6 5 -4}} + (−3){{map|4 -4 1}} {{=}} {{map|0 22 -11}}, the linear combination of ''columns'', i.e. slicing the original {{rket|{{map|6 5 -4}} {{map|4 -4 1}}}} mapping the other direction like {{rbra|{{vector|6 4}} {{vector|5 -4}} {{vector|-4 1}}}}, that leads to the revelation of this 11 is completely different: (−1){{vector|6 4}} + 2{{vector|5 -4}} + 1{{vector|-4 1}} {{=}} {{vector|0 11}}.</ref>. You could say that the HNF is useful for identifying common factors, but not for removing them. But if you leave them behind in the column-style HNF, the information that is retained in the unimodular matrix which is the other product of the Hermite decomposition, is enough to preserve everything important about the temperament, to get you back to where you started via an inverse and a trimming of extraneous rows.

}}

Line 792:

Line 794:

<blockquote>''Since this is an invariant of the temperament, it would be a good thing to use to refer to it, but for the fact that it is opaque and does not immediately tell us how to define the temperament.''<ref group="note">[https://yahootuninggroupsultimatebackup.github.io/tuning-math/topicId_1545.html#1545 Yahoo! Tuning Group | ''Standardizing our wedge product'']</ref></blockquote>

Regarding any other advantages EA brought to the RTT table for beginners: they did not find any. The only minor advantage identified was how the largest-minors of the mapping which wedgies are a list of could also be read as a list of denominators of unit fractions of the tempered lattice which are capable of being generated by the associated combination of primes whose columns in the mapping were used in the calculation of the corresponding largest-minor (this idea is discussed in more detail [[~~Dave_Keenan_%26_Douglas_Blumeyer%27s_guide_to_EA_for_RTT~~#~~Multicomma_entries~~:~~_tempered_lattice_fractions_generated_by_prime_combinations~~|here]]). Furthermore, several disadvantages of EA were identified, the main one being that it is more challenging to learn and use, involving higher level mathematical concepts than LA.

Regarding any other advantages EA brought to the RTT table for beginners: they did not find any. The only minor advantage identified was how the largest-minors of the mapping which wedgies are a list of could also be read as a list of denominators of unit fractions of the tempered lattice which are capable of being generated by the associated combination of primes whose columns in the mapping were used in the calculation of the corresponding largest-minor (this idea is discussed in more detail [[Dave Keenan & Douglas Blumeyer's guide to EA for RTT#Multicomma entries: tempered lattice fractions generated by prime combinations|here]]). Furthermore, several disadvantages of EA were identified, the main one being that it is more challenging to learn and use, involving higher level mathematical concepts than LA.

Regarding the development of a canonical form for temperaments using only linear algebra, Dave and Douglas did manage to develop such a form, which is documented here: [[defactored Hermite form]]. It was Gene himself who first described this form (as the result of his "saturation" algorithm), so he either did not realize the full implications of his discovery, or it was simply not popularized and plugged in with the rest of the hive knowledge.

Line 812:

Line 814:

===== How it works =====

Originally Dave was inspired by what [[Paul Erlich]] wrote on [http://tonalsoft.com/enc/t/torsion.aspx the article for torsion on the Tonalsoft site]. The algorithm simply checks every possible combination of sums and differences of rows. You have to check all <~~span~~><~~math~~>~~\frac{3^r -~~ 1}{2}~~</math>~~ sums and differences where ~~<math>~~r~~</math>~~ is the rank of the mapping. For example, for a rank-3 mapping with rows {{vector|A B C}}, you would need to check

Originally Dave was inspired by what [[Paul Erlich]] wrote on [http://tonalsoft.com/enc/t/torsion.aspx the article for torsion on the Tonalsoft site]. The algorithm simply checks every possible combination of sums and differences of rows. You have to check all {{sfrac|3''r'' − 1|2}} sums and differences where ''r'' is the rank of the mapping. For example, for a rank-3 mapping with rows {{vector|A B C}}, you would need to check

* A

Line 853:

Line 855:

This is the furthest progress that was made on SAD defactor before efforts were shifted to column Hermite defactor. This implementation still exhibits problems 2 and 3; only problems 1 and 4 were solved here. Problem 3 started to be solved, but was not quite quashed.

{{Databox|~~Code~~|

{{Databox|Wolfram Language code for SAD defactoring|

<pre>

confirmEnfactoredRowReplaced[m_] := Module[{i, enfactoredRowReplaced},

Line 905:

Line 907:

[[Category:Math]]

[[Category:Pages with proofs]]

[[Category:Algorithms]]

@@ Line 1: / Line 1: @@
+{{Todo|inline=1| rework |text=Try explaining without wedgies outside historical notes.}}
 This article discusses how to identify [[enfactoring]] in [[regular temperament]] [[mapping]]s and then [[defactoring|defactor]] it.
@@ Line 289: / Line 291: @@
 After we know how to do these two things individually, we will learn how to tweak them and assemble them together in order to perform a complete column Hermite defactoring.
-Fortunately, both of these two processes can be done using a technique you may already be familiar with if you have learned how to calculate the nullspace of a mapping by hand (as demonstrated [[Dave Keenan %26 Douglas Blumeyer%27s guide to RTT/Exploring temperaments #Nullspace|here]]):
+Fortunately, both of these two processes can be done using a technique you may already be familiar with if you have learned how to calculate the nullspace of a mapping by hand (as demonstrated [[Dave Keenan & Douglas Blumeyer's guide to RTT/Exploring temperaments#Nullspace|here]]):
 # Augmenting your matrix with an identity matrix
@@ Line 339: / Line 341: @@
 <math>
 \left[ \begin{array} {ccc|cc}
-& -11 & 4  &  13 & -6
+& -11 & 4  &  13 & -6 \\
 & 5 & 4  &  -2 & 1 \\
 \end{array} \right]
@@ Line 353: / Line 355: @@
 </math>
-We're actually quite close to done! All we need to do is flip the signs on the 2nd row. But wait, you protest! Isn't that multiplying a row by -1, which we specifically forbade? Well, sure, but that just shows we need to clarity what we're concerned about, which is essentially enfactoring. Multiplying by -1 does not change the GCD of the row, where multiplying by -2 or 2 would. Note that because the process for taking the HNF forbids multiplying ''or dividing'', it will never introduce enfactoring where was there was none previously, but it also does not remove enfactoring that is there.
+We're actually quite close to done! All we need to do is flip the signs on the 2nd row. But wait, you protest! Isn't that multiplying a row by &minus;1, which we specifically forbade? Well, sure, but that just shows we need to clarity what we're concerned about, which is essentially enfactoring. Multiplying by &minus;1 does not change the GCD of the row, where multiplying by &minus;2 or 2 would. Note that because the process for taking the HNF forbids multiplying ''or dividing'', it will never introduce enfactoring where was there was none previously, but it also does not remove enfactoring that is there.
-Perhaps another helpful way of thinking about this is that multiplying the row by -1 does not alter the potential effects this row could have being added or subtracted from other rows. It merely swaps addition and subtraction. Whereas multiplying the row by any integer with absolute value greater than 1 ''would'' affect the potential effects this row could have being added or subtracted from other rows: it would limit them.
+Perhaps another helpful way of thinking about this is that multiplying the row by &minus;1 does not alter the potential effects this row could have being added or subtracted from other rows. It merely swaps addition and subtraction. Whereas multiplying the row by any integer with absolute value greater than 1 ''would'' affect the potential effects this row could have being added or subtracted from other rows: it would limit them.
 So, let's do that sign flip:
@@ Line 368: / Line 370: @@
 And we're done! Let's confirm though.
-# '''All pivots > 0?''' Check. The 1st row's pivot is 2 and the 2nd row's pivot is 11.
+# '''All pivots &gt; 0?''' Check. The 1st row's pivot is 2 and the 2nd row's pivot is 11.
 # '''All entries in pivot columns below the pivots {{=}} 0'''? Check. This only applies to one entry&mdash;the bottom right one, below the 1st row's pivot&mdash;but it is indeed 0.
-# '''All entries in pivot columns above the pivots &ge; 0 and strictly less than the pivot'''? Check. Again, this only applies to one entry&mdash;the center top one, above the 2nd row's pivot of 11&mdash;but it is 5, and 5 is indeed non-negative and < 11.
+# '''All entries in pivot columns above the pivots &ge; 0 and strictly less than the pivot'''? Check. Again, this only applies to one entry&mdash;the center top one, above the 2nd row's pivot of 11&mdash;but it is 5, and 5 is indeed non-negative and &lt; 11.
 And so, we have performed the Hermite decomposition. The matrix to the left of the augmentation line&mdash;the one in place of our original matrix&mdash;is that original matrix in HNF:
@@ Line 449: / Line 451: @@
 </math>
-Okay, let's next target the bottom-center entry. How can we make that -2 into a 0? Let's add the 2nd row to the 3rd row 2 times:
+Okay, let's next target the bottom-center entry. How can we make that &minus;2 into a 0? Let's add the 2nd row to the 3rd row 2 times:
 <math>
@@ Line 469: / Line 471: @@
 </math>
-Finally, we just need to divide the 3rd row by -2. Yes, unlike with the Hermite decomposition, all elementary row operations are permitted, including multiplying or dividing rows. And in this case there's no restrictions against non-integers (which we didn't even explicitly mention when doing the HNF, but yes, HNF requires integers). So here's where we end up:
+Finally, we just need to divide the 3rd row by &minus;2. Yes, unlike with the Hermite decomposition, all elementary row operations are permitted, including multiplying or dividing rows. And in this case there's no restrictions against non-integers (which we didn't even explicitly mention when doing the HNF, but yes, HNF requires integers). So here's where we end up:
 <math>
@@ Line 782: / Line 784: @@
 \end{matrix} \right]</math>
-The pivots are 1 and 11, so that 11 tells us that we had a common factor of 11<ref group="note">In the doubly-enfactored case of {{rket|{{map|17 16 -4}} {{map|4 -4 1}}}}, i.e. with a common factor of 33 = 3 × 11, the two pivots of the HNF are 3 and 11, putting each of them on display separately.</ref><ref group="note">It's interesting to observe that while the 11-enfactoring can be observed in the original matrix as a linear combination of 2 of the 1st row with -3 of the 2nd row, i.e. 2{{map|6 5 -4}} + -3{{map|4 -4 1}} = {{map|0 22 -11}}, the linear combination of ''columns'', i.e. slicing the original {{rket|{{map|6 5 -4}} {{map|4 -4 1}}}} mapping the other direction like {{rbra|{{vector|6 4}} {{vector|5 -4}} {{vector|-4 1}}}}, that leads to the revelation of this 11 is completely different: -1{{vector|6 4}} + 2{{vector|5 -4}} + 1{{vector|-4 1}} = {{vector|0 11}}.</ref>. You could say that the HNF is useful for identifying common factors, but not for removing them. But if you leave them behind in the column-style HNF, the information that is retained in the unimodular matrix which is the other product of the Hermite decomposition, is enough to preserve everything important about the temperament, to get you back to where you started via an inverse and a trimming of extraneous rows.
+The pivots are 1 and 11, so that 11 tells us that we had a common factor of 11<ref group="note">In the doubly-enfactored case of {{rket|{{map|17 16 -4}} {{map|4 -4 1}}}}, i.e. with a common factor of {{nowrap|33 {{=}} 3 &#215; 11}}, the two pivots of the HNF are 3 and 11, putting each of them on display separately.</ref><ref group="note">It's interesting to observe that while the 11-enfactoring can be observed in the original matrix as a linear combination of 2 of the 1st row with &minus;3 of the 2nd row, i.e. 2{{map|6 5 -4}} + (&minus;3){{map|4 -4 1}} {{=}} {{map|0 22 -11}}, the linear combination of ''columns'', i.e. slicing the original {{rket|{{map|6 5 -4}} {{map|4 -4 1}}}} mapping the other direction like {{rbra|{{vector|6 4}} {{vector|5 -4}} {{vector|-4 1}}}}, that leads to the revelation of this 11 is completely different: (&minus;1){{vector|6 4}} + 2{{vector|5 -4}} + 1{{vector|-4 1}} {{=}} {{vector|0 11}}.</ref>. You could say that the HNF is useful for identifying common factors, but not for removing them. But if you leave them behind in the column-style HNF, the information that is retained in the unimodular matrix which is the other product of the Hermite decomposition, is enough to preserve everything important about the temperament, to get you back to where you started via an inverse and a trimming of extraneous rows.
 }}
@@ Line 792: / Line 794: @@
 <blockquote>''Since this is an invariant of the temperament, it would be a good thing to use to refer to it, but for the fact that it is opaque and does not immediately tell us how to define the temperament.''<ref group="note">[https://yahootuninggroupsultimatebackup.github.io/tuning-math/topicId_1545.html#1545 Yahoo! Tuning Group | ''Standardizing our wedge product'']</ref></blockquote>
-Regarding any other advantages EA brought to the RTT table for beginners: they did not find any. The only minor advantage identified was how the largest-minors of the mapping which wedgies are a list of could also be read as a list of denominators of unit fractions of the tempered lattice which are capable of being generated by the associated combination of primes whose columns in the mapping were used in the calculation of the corresponding largest-minor (this idea is discussed in more detail [[Dave_Keenan_%26_Douglas_Blumeyer%27s_guide_to_EA_for_RTT#Multicomma_entries:_tempered_lattice_fractions_generated_by_prime_combinations|here]]). Furthermore, several disadvantages of EA were identified, the main one being that it is more challenging to learn and use, involving higher level mathematical concepts than LA.
+Regarding any other advantages EA brought to the RTT table for beginners: they did not find any. The only minor advantage identified was how the largest-minors of the mapping which wedgies are a list of could also be read as a list of denominators of unit fractions of the tempered lattice which are capable of being generated by the associated combination of primes whose columns in the mapping were used in the calculation of the corresponding largest-minor (this idea is discussed in more detail [[Dave Keenan & Douglas Blumeyer's guide to EA for RTT#Multicomma entries: tempered lattice fractions generated by prime combinations|here]]). Furthermore, several disadvantages of EA were identified, the main one being that it is more challenging to learn and use, involving higher level mathematical concepts than LA.
 Regarding the development of a canonical form for temperaments using only linear algebra, Dave and Douglas did manage to develop such a form, which is documented here: [[defactored Hermite form]]. It was Gene himself who first described this form (as the result of his "saturation" algorithm), so he either did not realize the full implications of his discovery, or it was simply not popularized and plugged in with the rest of the hive knowledge.
@@ Line 812: / Line 814: @@
 ===== How it works =====
-Originally Dave was inspired by what [[Paul Erlich]] wrote on [http://tonalsoft.com/enc/t/torsion.aspx the article for torsion on the Tonalsoft site]. The algorithm simply checks every possible combination of sums and differences of rows. You have to check all <span><math>\frac{3^r - 1}{2}</math></span> sums and differences where <span><math>r</math></span> is the rank of the mapping. For example, for a rank-3 mapping with rows {{vector|A B C}}, you would need to check
+Originally Dave was inspired by what [[Paul Erlich]] wrote on [http://tonalsoft.com/enc/t/torsion.aspx the article for torsion on the Tonalsoft site]. The algorithm simply checks every possible combination of sums and differences of rows. You have to check all {{sfrac|3<sup>''r''</sup> &minus; 1|2}} sums and differences where ''r'' is the rank of the mapping. For example, for a rank-3 mapping with rows {{vector|A B C}}, you would need to check
 * A
@@ Line 853: / Line 855: @@
 This is the furthest progress that was made on SAD defactor before efforts were shifted to column Hermite defactor. This implementation still exhibits problems 2 and 3; only problems 1 and 4 were solved here. Problem 3 started to be solved, but was not quite quashed.
-{{Databox|Code|
+{{Databox|Wolfram Language code for SAD defactoring|
 <pre>
 confirmEnfactoredRowReplaced[m_] := Module[{i, enfactoredRowReplaced},
@@ Line 905: / Line 907: @@
 [[Category:Math]]
 [[Category:Pages with proofs]]
+[[Category:Algorithms]]