Defactoring algorithms: Difference between revisions
ArrowHead294 (talk | contribs) |
ArrowHead294 (talk | contribs) m →By hand |
||
| Line 289: | Line 289: | ||
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. | 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 | 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 | # Augmenting your matrix with an identity matrix | ||
| Line 353: | Line 353: | ||
</math> | </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 | 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. | ||
| Line 368: | Line 368: | ||
And we're done! Let's confirm though. | And we're done! Let's confirm though. | ||
# '''All pivots | # '''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 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 | # '''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: | 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 449: | ||
</math> | </math> | ||
Okay, let's next target the bottom-center entry. How can we make that | 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> | <math> | ||
| Line 469: | Line 469: | ||
</math> | </math> | ||
Finally, we just need to divide the 3rd row by | 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> | <math> | ||
| Line 782: | Line 782: | ||
\end{matrix} \right]</math> | \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 | 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 &inus;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. | ||
}} | }} | ||