Xenharmonic Wiki

Defactoring: Difference between revisions

← Older editNewer edit →
VisualWikitext
Cmloegcmluin (talk | contribs)
autopatrolled, emailconfirmed
5,160 edits
section reorganization
Cmloegcmluin (talk | contribs)
autopatrolled, emailconfirmed
5,160 edits
Line 155: Line 155:
== relationship between various matrix echelon forms ==
== relationship between various matrix echelon forms ==


There are several well-known echelon matrix forms. The most general form, with the fewest constraints, is simply called Row Echelon Form, or REF. It's only constraints are:
There are several well-known echelon forms for matrices that predate DC form. Let's review them and their properties.
### the rows are shaped like echelon
and therefore it does not produce a unique representation.


An Integer Row Echelon Form, or IREF, is, unsurprisingly, any REF whose terms are all integers. Again, this is still not necessarily unique.
=== list of forms ===


The Reduced Row Echelon Form, or RREF, takes REF in a different direction. It stipulates that the pivots are all 1's. This may require dividing rows by a number such that resulting elements are no longer integers. Because of this constraint, however, the RREF form of a matrix is unique.  
The most general form, with the fewest constraints, is simply called '''[https://en.wikipedia.org/wiki/Row_echelon_form Row Echelon Form]''', or '''REF'''. Its only constraint is ''echelon<ref>The name "echelon" is a French word for a military troop formation with a similar triangular shape.</ref> form'': each row's pivot, or first nonzero entry, is strictly to the right of the preceding row's pivot. This single constraint is fairly weak, and therefore REF does not produce a unique representation. This constraint is shared by every matrix form discussed here.


So IREF and RREF make a Venn Diagram inside the category of REF: some IREF are RREF, but there are some RREF that are not IREF and some IREF that are not RREF. When we scope the situation to a specific matrix, however, because RREF is a unique form, this means that one or the other sector of the Venn diagram for RREF will be empty; either the unique RREF form will also be IREF (and therefore the RREF-but-not-IREF sector will be empty), or it will not be IREF (and vice versa).
'''Integer Row Echelon Form''', or '''IREF''', is, unsurprisingly, any REF which meets an additional ''integer'' constraint, or in other words, that all of its entries are integers. This is still not a sufficiently strict set of constraints to ensure a unique representation.


The next form to discuss is the Integer Reduced Row Echelon Form, or IRREF. 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 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 form and multiplying each row by whatever minimum value is necessary to make all of the elements integers. Of course, this sometimes results in the pivots no longer being 1, so sometimes it is no longer RREF. It is always still REF, though, and because it is also always integer, that makes it always IREF; therefore, IRREF is strictly a subcategory of IREF. And because the RREF form is unique, and the conversion process does not alter that, the IRREF form is also unique.
'''Reduced Row Echelon Form''', or '''RREF''', takes REF in a different direction than IREF. Instead of stipulating anything about integers, it requires that the matrix is ''reduced'', i.e. that the pivots are exactly equal to 1. This may require dividing rows by a number such that some resulting entries are no longer integers. Actually, there's a second part to the "reduced" constraint: each pivot column (a column which contains any row's pivot) has zeros for all other entries besides the pivot it contains. Due to these strict constraints, the RREF of a matrix is the first one we've looked at so far here which does ensure uniqueness.


It is not possible for an RREF form to be IREF without also being IRREF.  
So IREF and RREF make a [https://en.wikipedia.org/wiki/Venn_diagram Venn diagram] inside the category of REF: some IREF are RREF, but there are some RREF that are not IREF and some IREF that are not RREF. When we scope the situation to a specific matrix, however, because RREF is a unique form, this means that one or the other sector of the Venn diagram for RREF will be empty; either the unique RREF will also be IREF (and therefore the RREF-but-not-IREF sector will be empty), or it will not be IREF (and vice versa).


The last form to discuss is the HNF. This one's constraints
'''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. Of course, this sometimes results in the pivots no longer being 1, so sometimes it is no longer RREF. It is always still REF, though<ref>Also, it will always still satisfy the second aspect of reduced, i.e. that all other entries in pivot columns besides the pivots are zeroes.</ref>, and because it is also always integer, that makes it always IREF; therefore, IRREF is strictly a subcategory of IREF. And because the RREF is unique, and the conversion process does not alter that, the IRREF is also unique.
###
and so it is always integer, and always REF, and therefore always IREF, but it is not necessarily identical to the IRREF which is the IREF you find by converting the RREF.  


And so, four different states are possible: ### give the specifics for each example
It is not possible for an RREF to be IREF without also being IRREF.
# The RREF, IRREF, and HNF are all different. Example: porcupine.  
 
# The RREF, IRREF, and HNF are all the same. Example: meantone.
'''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). 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.
# The RREF and IRREF are the same, but the HNF is different. Example: [⟨2 3 5] ⟨7 6 13]⟩ (I haven't found a realistic one yet)
 
# The IRREF and HNF are the same, but the RREF is different. Example: hanson.
So HNF has a lot in common with IRREF, which is the IREF you find by converting the RREF, but it is not always the same as IRREF.
 
=== temperament states ===
 
All considered, three different states are possible for a given temperament:
# The RREF, IRREF, and HNF are all the same. Example: [[Meantone_family#Meantone_.2812.2619.2C_2.3.5.29|meantone]] with all three equal to {{vector|{{map|1 0 -4}} {{map|0 1 4}}}}.
# The RREF, IRREF, and HNF are all different. Example: [[Porcupine_family#Porcupine|porcupine]] with {{vector|{{map|1 0 <span><math>-\frac13</math></span>}} {{map|0 1 <span><math>\frac53</math></span>}}}}, {{vector|{{map|3 0 -1}} {{map|0 3 5}}}}, and {{vector|{{map|1 2 3}} {{map|0 3 5}}}}, respectively.  
# The IRREF and HNF are the same, but the RREF is different. Example: [[Kleismic_family#Hanson|hanson]] with IRREF and HNF of {{vector|{{map|1 0 1}} {{map|0 6 5}}}} but RREF of {{vector|{{map|1 0 1}} {{map|0 1 <span><math>\frac56</math></span>}}}}.
 
A fourth state is possible but only for enfactored mappings, i.e. for temperoids. This is where the RREF and IRREF are the same, but the HNF is different. This is only possible for enfactored mappings because:
* Whenever the RREF and IRREF match, the IRREF has all 1's for pivots.
* But in that case, the IRREF would also be the HNF, because there's only one possible nonnegative integer value less than 1, which is zero, and so this form would also satisfy the normal constraint.
* The only way to avoid this would be to ensure that at least one pivot of the HNF was not 1, so that it could have some positive value somewhere in the entries above that pivot in its pivot column, to distinguish it from IRREF. For example, we could use {{vector|{{map|1 1 0}} {{map|0 2 1}}}}.
* But now if we look at the RREF of this mapping with this HNF, we have to divide rows until all pivots are 1. So that second row would be changed to {{map|0 1 <span><math>\frac12</math></span>}}. So now RREF won't match IRREF, because it contains a noninteger. The only way to prevent this would be if a pivot of the HNF was not 1, but still every entry in that row was evenly divisible by that value, such as {{vector|{{map|1 1 0}} {{map|0 2 4}}}}. But now that row is enfactored by its pivot's value.


== generator manipulation ==
== generator manipulation ==
Retrieved from "https://en.xen.wiki/w/Defactoring"