Matrix echelon forms: Difference between revisions

(One intermediate revision by one other user not shown)

Line 112:

== HNF ==

'''~~[https://en.wikipedia.org/wiki/Hermite_normal_form~~ Hermite ~~Normal Form]~~''', or '''HNF''': this one's constraints begin with echelon form and integer, therefore every HNF is also IREF. But HNF is not exactly reduced (as discussed above; [[canonical_form#RREF|link here]]); 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 group="note">The exact criteria for HNF are not always consistently agreed upon, however.</ref><ref group="note">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> In other words, elements above the pivot have to be reduced modulo the pivot. 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 '''Hermite normal form''', or '''HNF''': this one's constraints begin with echelon form and integer, therefore every HNF is also IREF. But HNF is not exactly reduced (as discussed above; [[canonical_form#RREF|link here]]); 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 group="note">The exact criteria for HNF are not always consistently agreed upon, however.</ref><ref group="note">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> In other words, elements above the pivot have to be reduced modulo the pivot. 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.

Line 174:

Line 176:

[[File:Cases for temperament mapping forms3.png|300px|thumb|right]]

Considering only full-rank, integer mappings, we find three cases for a given temperament which is not enfactored. In all three cases, HNF is the same as canonical form (here abbreviated as DCF, for defactored canonical form<ref group="note">This was before the community decided on "defactored Hermite form", and I was too lazy to go back and update all these diagrams.</ref>):

# The RREF, IRREF, and HNF are all ''different''. Example: [[Porcupine_family#Porcupine|porcupine]] with RREF of {{rket|{{map|1 0 {{~~sfrac~~|1|3}} {{map|0 1 {{~~sfrac~~|5|3}}}}}}, IRREF of {{rket|{{map|3 0 -1}} {{map|0 3 5}}}}, and HNF of {{rket|{{map|1 2 3}} {{map|0 3 5}}}}.

# The RREF, IRREF, and HNF are all ''different''. Example: [[Porcupine_family#Porcupine|porcupine]] with RREF of {{rket|{{map|1 0 {{frac|1|3}} {{map|0 1 {{frac|5|3}}}}}}}}, IRREF of {{rket|{{map|3 0 -1}} {{map|0 3 5}}}}, and HNF of {{rket|{{map|1 2 3}} {{map|0 3 5}}}}.

# The RREF, IRREF, HNF are all ''the same''. Example: [[Meantone_family#Meantone_.2812.2619.2C_2.3.5.29|meantone]] with all equal to {{rket|{{map|1 0 -4}} {{map|0 1 4}}}}. This case is quite rare.

# The IRREF and HNF are the same, but the ''RREF is different''. Example: [[Kleismic_family#Hanson|hanson]] with IRREF and HNF of {{rket|{{map|1 0 1}} {{map|0 6 5}}}} but RREF of {{rket|{{map|1 0 1}} {{map|0 1 {{~~sfrac~~|5|6}}}}}}.

# The IRREF and HNF are the same, but the ''RREF is different''. Example: [[Kleismic_family#Hanson|hanson]] with IRREF and HNF of {{rket|{{map|1 0 1}} {{map|0 6 5}}}} but RREF of {{rket|{{map|1 0 1}} {{map|0 1 {{frac|5|6}}}}}}.

And there are three corresponding cases when a temperament is enfactored. In all three cases, the key difference is that HNF is no longer the same as DCF, with the only difference being that the common factor is not removed. In all cases below, the examples are shown with a common factor of 2 introduced in their second row, which stays behind in the second row of the HNF:

Line 183:

Line 185:

# The ''only match'' now is between IRREF and DCF. In other words, the HNF and DCF diverged, and it was the DCF which remained the same as IRREF. Example: enfactored hanson, e.g. {{rket|{{map|15 24 35}} {{map|38 60 88}}}} causes the HNF to be {{rket|{{map|1 0 1}} {{map|0 12 10}}}}.

There is also a final case which is incredibly rare. It can be compared to the #3 cases above, the ones using hanson as their example. The idea here is that when the HNF and DCF diverge, instead of DCF remaining the same as IRREF, it's the HNF that remains the same as IRREF. There may be no practical temperoids with this case, but {{rket|{{map|165 264 393}} {{map|231 363 524}}}} will do it,<ref group="note">AKA 165b4c19&231b6c24, which makes the 7.753¢ comma {{vector|-131 131 -33}} [[vanish]]!</ref> with IRREF and HNF of {{rket|{{map|33 0 -131}} {{map|0 33 131}}}}, DCF of {{rket|{{map|1 1 0}} {{map|0 33 131}}}}, and RREF of {{rket|{{map|1 0 ~~<math>\frac~~{~~-131}~~{33}~~</math>~~}} {{map|0 1 ~~<math>\~~frac{131}~~{33~~}~~</math>~~}}}}.

There is also a final case which is incredibly rare. It can be compared to the #3 cases above, the ones using hanson as their example. The idea here is that when the HNF and DCF diverge, instead of DCF remaining the same as IRREF, it's the HNF that remains the same as IRREF. There may be no practical temperoids with this case, but {{rket|{{map|165 264 393}} {{map|231 363 524}}}} will do it,<ref group="note">AKA 165b4c19&231b6c24, which makes the 7.753¢ comma {{vector|-131 131 -33}} [[vanish]]!</ref> with IRREF and HNF of {{rket|{{map|33 0 -131}} {{map|0 33 131}}}}, DCF of {{rket|{{map|1 1 0}} {{map|0 33 131}}}}, and RREF of {{rket|{{map|1 0 {{frac|−131|33}}}}}} {{map|0 1 {{frac|131|33}}}}}}.

That accounts for 7 of the 15 total possible cases for a system of equalities between 4 entities. The remaining 9 cases are impossible due to properties of the domain:

@@ Line 112: / Line 112: @@
 == HNF ==
-'''[https://en.wikipedia.org/wiki/Hermite_normal_form Hermite Normal Form]''', or '''HNF''': this one's constraints begin with echelon form and integer, therefore every HNF is also IREF. But HNF is not exactly reduced (as discussed above; [[canonical_form#RREF|link here]]); 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 group="note">The exact criteria for HNF are not always consistently agreed upon, however.</ref><ref group="note">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> In other words, elements above the pivot have to be reduced modulo the pivot. 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.
+{{main|Normal forms#Hermite normal form}}
+{{wikipedia|Hermite normal form}}
+The '''Hermite normal form''', or '''HNF''': this one's constraints begin with echelon form and integer, therefore every HNF is also IREF. But HNF is not exactly reduced (as discussed above; [[canonical_form#RREF|link here]]); 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 group="note">The exact criteria for HNF are not always consistently agreed upon, however.</ref><ref group="note">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> In other words, elements above the pivot have to be reduced modulo the pivot. 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.
@@ Line 174: / Line 176: @@
 [[File:Cases for temperament mapping forms3.png|300px|thumb|right]]
 Considering only full-rank, integer mappings, we find three cases for a given temperament which is not enfactored. In all three cases, HNF is the same as canonical form (here abbreviated as DCF, for defactored canonical form<ref group="note">This was before the community decided on "defactored Hermite form", and I was too lazy to go back and update all these diagrams.</ref>):
-# The RREF, IRREF, and HNF are all ''different''. Example: [[Porcupine_family#Porcupine|porcupine]] with RREF of {{rket|{{map|1 0 {{sfrac|1|3}} {{map|0 1 {{sfrac|5|3}}}}}}, IRREF of {{rket|{{map|3 0 -1}} {{map|0 3 5}}}}, and HNF of {{rket|{{map|1 2 3}} {{map|0 3 5}}}}.
+# The RREF, IRREF, and HNF are all ''different''. Example: [[Porcupine_family#Porcupine|porcupine]] with RREF of {{rket|{{map|1 0 {{frac|1|3}} {{map|0 1 {{frac|5|3}}}}}}}}, IRREF of {{rket|{{map|3 0 -1}} {{map|0 3 5}}}}, and HNF of {{rket|{{map|1 2 3}} {{map|0 3 5}}}}.
 # The RREF, IRREF, HNF are all ''the same''. Example: [[Meantone_family#Meantone_.2812.2619.2C_2.3.5.29|meantone]] with all equal to {{rket|{{map|1 0 -4}} {{map|0 1 4}}}}. This case is quite rare.
-# The IRREF and HNF are the same, but the ''RREF is different''. Example: [[Kleismic_family#Hanson|hanson]] with IRREF and HNF of {{rket|{{map|1 0 1}} {{map|0 6 5}}}} but RREF of {{rket|{{map|1 0 1}} {{map|0 1 {{sfrac|5|6}}}}}}.
+# The IRREF and HNF are the same, but the ''RREF is different''. Example: [[Kleismic_family#Hanson|hanson]] with IRREF and HNF of {{rket|{{map|1 0 1}} {{map|0 6 5}}}} but RREF of {{rket|{{map|1 0 1}} {{map|0 1 {{frac|5|6}}}}}}.
 And there are three corresponding cases when a temperament is enfactored. In all three cases, the key difference is that HNF is no longer the same as DCF, with the only difference being that the common factor is not removed. In all cases below, the examples are shown with a common factor of 2 introduced in their second row, which stays behind in the second row of the HNF:
@@ Line 183: / Line 185: @@
 # The ''only match'' now is between IRREF and DCF. In other words, the HNF and DCF diverged, and it was the DCF which remained the same as IRREF. Example: enfactored hanson, e.g. {{rket|{{map|15 24 35}} {{map|38 60 88}}}} causes the HNF to be {{rket|{{map|1 0 1}} {{map|0 12 10}}}}.
-There is also a final case which is incredibly rare. It can be compared to the #3 cases above, the ones using hanson as their example. The idea here is that when the HNF and DCF diverge, instead of DCF remaining the same as IRREF, it's the HNF that remains the same as IRREF. There may be no practical temperoids with this case, but {{rket|{{map|165 264 393}} {{map|231 363 524}}}} will do it,<ref group="note">AKA 165b<sup>4</sup>c<sup>19</sup>&231b<sup>6</sup>c<sup>24</sup>, which makes the 7.753¢ comma {{vector|-131 131 -33}} [[vanish]]!</ref> with IRREF and HNF of {{rket|{{map|33 0 -131}} {{map|0 33 131}}}}, DCF of {{rket|{{map|1 1 0}} {{map|0 33 131}}}}, and RREF of {{rket|{{map|1 0 <math>\frac{-131}{33}</math>}} {{map|0 1 <math>\frac{131}{33}</math>}}}}.
+There is also a final case which is incredibly rare. It can be compared to the #3 cases above, the ones using hanson as their example. The idea here is that when the HNF and DCF diverge, instead of DCF remaining the same as IRREF, it's the HNF that remains the same as IRREF. There may be no practical temperoids with this case, but {{rket|{{map|165 264 393}} {{map|231 363 524}}}} will do it,<ref group="note">AKA 165b<sup>4</sup>c<sup>19</sup>&231b<sup>6</sup>c<sup>24</sup>, which makes the 7.753¢ comma {{vector|-131 131 -33}} [[vanish]]!</ref> with IRREF and HNF of {{rket|{{map|33 0 -131}} {{map|0 33 131}}}}, DCF of {{rket|{{map|1 1 0}} {{map|0 33 131}}}}, and RREF of {{rket|{{map|1 0 {{frac|−131|33}}}}}} {{map|0 1 {{frac|131|33}}}}}}.
 That accounts for 7 of the 15 total possible cases for a system of equalities between 4 entities. The remaining 9 cases are impossible due to properties of the domain: