Defactoring: Difference between revisions

Line 157:

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.

'''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.

'''[https://people.sc.fsu.edu/~jburkardt/f_src/row_echelon_integer/row_echelon_integer.html 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.

'''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.

'''[https://en.wikipedia.org/wiki/Row_echelon_form#Reduced_row_echelon_form 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.

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).

'''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.

'''[[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. 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.

It is not possible for an RREF to be IREF without also being IRREF.

'''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.

'''[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). 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.

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.

'''Defactored Canonical Form''', or '''DCF''' is closely related to HNF, because the second step of finding the DCF is taking the HNF. So the DCF is always ''a'' HNF, and therefore it has all the same properties of being echelon, integer, and normalized, and in turn therefore it also provides a unique representation. However it is not necessary ''the'' same HNF of the original mapping, due to the first step being defactoring; it is the same as as HNF except when the original mapping is enfactored.

There is also the '''[https://en.wikipedia.org/wiki/Smith_normal_form Smith Normal Form]''', or '''SNF''', but we won't be discussing it in this context, because putting a mapping into SNF obliterates a lot of meaningful RTT information. SNF is also echelon, and integer, so like HNF it is also always IREF. But SNF requires that every single entry other than the pivots are zero, and that the pivots all fall exactly along the main diagonal of the matrix. The SNF essentially reduces a matrix down to the information of what its rank is and whether it is enfactored. For example, all 5-limit rank-2 temperaments such as meantone, porcupine, mavila, hanson, etc. have the same SNF: {{vector|{{map|1 0 0}} {{map|0 1 0}}}}. Or, if you 2-enfactor them, they will all have the SNF {{vector|{{map|1 0 0}} {{map|0 2 0}}}}. So while the SNF is closely related to defactoring, it is not itself a useful form to put mappings into.<ref>Here is a useful resource for computing the Smith Normal Form manually, if you are interested: https://math.stackexchange.com/questions/133076/computing-the-smith-normal-form</ref>

=== temperament states ===

@@ Line 157: / Line 157: @@
 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.
-'''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.
+'''[https://people.sc.fsu.edu/~jburkardt/f_src/row_echelon_integer/row_echelon_integer.html 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.
-'''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.
+'''[https://en.wikipedia.org/wiki/Row_echelon_form#Reduced_row_echelon_form 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.
 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).
-'''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.
+'''[[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. 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.
 It is not possible for an RREF to be IREF without also being IRREF.
-'''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.
+'''[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). 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.
 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.
+'''Defactored Canonical Form''', or '''DCF''' is closely related to HNF, because the second step of finding the DCF is taking the HNF. So the DCF is always ''a'' HNF, and therefore it has all the same properties of being echelon, integer, and normalized, and in turn therefore it also provides a unique representation. However it is not necessary ''the'' same HNF of the original mapping, due to the first step being defactoring; it is the same as as HNF except when the original mapping is enfactored.
+There is also the '''[https://en.wikipedia.org/wiki/Smith_normal_form Smith Normal Form]''', or '''SNF''', but we won't be discussing it in this context, because putting a mapping into SNF obliterates a lot of meaningful RTT information. SNF is also echelon, and integer, so like HNF it is also always IREF. But SNF requires that every single entry other than the pivots are zero, and that the pivots all fall exactly along the main diagonal of the matrix. The SNF essentially reduces a matrix down to the information of what its rank is and whether it is enfactored. For example, all 5-limit rank-2 temperaments such as meantone, porcupine, mavila, hanson, etc. have the same SNF: {{vector|{{map|1 0 0}} {{map|0 1 0}}}}. Or, if you 2-enfactor them, they will all have the SNF {{vector|{{map|1 0 0}} {{map|0 2 0}}}}. So while the SNF is closely related to defactoring, it is not itself a useful form to put mappings into.<ref>Here is a useful resource for computing the Smith Normal Form manually, if you are interested: https://math.stackexchange.com/questions/133076/computing-the-smith-normal-form</ref>
 === temperament states ===