Defactoring: Difference between revisions

'''[[Normal_lists|Integer Reduced Row Echelon Form]]''', or '''IRREF''' is the next form to discuss. Based on the name, one might expect this form to be a combination of the constraints for RREF and IREF, and therefore if represented in an [https://en.wikipedia.org/wiki/Euler_diagram Euler diagram] (generalization of Venn diagram) would only exist within their intersection. However this is not the case. That's because the IRREF does not include the key constraint of RREF which is that all of the pivots must be 1. IRREF is produced by simply taking the unique RREF and multiplying each row by whatever minimum value is necessary to make all of the entries integers<ref>Alternatively, IRREF can be computed by finding the null-space of a mapping, or in other words, the corresponding comma-basis for the temperament represented by the mapping, and then in turn taking the null-space of the comma-basis to get back to an equivalent mapping. The relationship between the process for finding the IRREF from the RREF and this process is not proven, but thousands of automated tests run as an experiment strongly suggest that these two techniques are equivalent.<br>

'''[https://en.wikipedia.org/wiki/Hermite_normal_form Hermite Normal Form]''', or '''HNF''', is the last form to discuss. This one's constraints begin with echelon form and integer, therefore every HNF is also IREF. But HNF is not exactly reduced; instead, it is ''normalized'', which — similarly to reduced — is a two-part constraint. Where reduced requires that all pivots be exactly equal to 1, normalized requires only that all pivots be positive (positive integers, of course, due to the other integer constraint). And where reduced requires that all entries in pivot columns besides the pivots are exactly equal to 0, normalized requires only that all entries in pivot columns below the pivots are exactly equal to 0, while entries in pivot columns above the pivots only have to be strictly less than the pivot in the respective column (while still being non-negative).<ref>The exact criteria for HNF are not always consistently agreed upon, however.</ref><ref>There is also a rarely mentioned Hermite Canonical Form, or HCF, described here: http://home.iitk.ac.in/~rksr/html/03CANONICALFACTORIZATIONS.htm, which sort of combines the HNF's normalization constraint and the RREF's reduced constraint (all pivots equal 1, all other entries in pivot columns are 0, both above and below the pivot), but we didn't find it useful because due to its constraint that all pivots be 1, it does not preserve periods that are genuinely unit fractions of an octave. It also doesn't qualify as an echelon form, which becomes apparent only when you use it on rank-deficient matrices, because it doesn't require the rows of all zeros to be at the bottom; instead it (bizarrely, though maybe it's related to how the SNF requires all pivots exactly along the main diagonal) requires the rows to be sorted so that all the pivots fall on the main diagonal.</ref><ref>We are using "row-style" Hermite Normal Form here, not "column-style"; the latter would involve simply flipping everything 90 degrees so that the echelon requirement was that pivots be strictly ''below'' the pivots in the previous ''column'', and that pivot ''rows'' are considered for the normalization constraint rather than pivot ''columns''.</ref> The normalization HNF uses is cool because this constraint, while strictly less strict than the reduced constraint used by RREF, is still strict enough to ensure uniqueness, but loose enough to ensure the integer constraint can be simultaneously satisfied, where RREF cannot ensure that.