Matrix echelon forms - Revision history

Fredg999: Use new redirect

2026-07-28T18:18:06Z

Use new redirect

← Older revision		Revision as of 18:18, 28 July 2026
Line 1:		Line 1:
	The mathematical field of [[~~linear algebra formalism\|~~linear algebra]] has defined a number of echelon forms for matrices, many of them have been used in [[regular temperament theory]]. This article is intended as a reference and gathering place for relevant information about these matrix forms.		The mathematical field of [[linear algebra]] has defined a number of echelon forms for matrices, many of them have been used in [[regular temperament theory]]. This article is intended as a reference and gathering place for relevant information about these matrix forms.

	== Row echelon form ==		== Row echelon form ==

ArrowHead294 at 12:55, 28 July 2026

2026-07-28T12:55:31Z

← Older revision		Revision as of 12:55, 28 July 2026
Line 192:		Line 192:
	# 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}}}}.		# 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 {{frac\|−131\|33}}}}}} {{map\|0 1 {{frac\|131\|33}}}}}}.		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{{cent}} 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:		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 204:		Line 204:

	== References ==		== References ==
	<references/>		<references />

	[[Category:Regular temperament theory]]		[[Category:Regular temperament theory]]
	[[Category:Terms]]		[[Category:Terms]]
	[[Category:Math]]		[[Category:Math]]

FloraC: Finish

2026-07-28T05:46:07Z

Finish

← Older revision		Revision as of 05:46, 28 July 2026
Line 57:		Line 57:
	\|}		\|}

	== ~~RREF~~ ==		== Reduced row echelon form ==
	{{Wikipedia\|Row echelon form #Reduced row echelon form}}		{{Wikipedia\|Row echelon form #Reduced row echelon form}}

Line 86:		Line 86:
	So IREF and RREF make a {{w\|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).		So IREF and RREF make a {{w\|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).

	== ~~IRREF~~ ==		== Integer reduced row echelon form ==
	'''Integer reduced row echelon form''' ('''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 {{w\|Euler diagram}} (generalization of Venn diagram) would only exist within their intersection. However this is not the case. That is 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 group="note">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.		'''Integer reduced row echelon form''' ('''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 {{w\|Euler diagram}} (generalization of Venn diagram) would only exist within their intersection. However this is not the case. That is 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 group="note">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.

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

	== ~~HNF~~ ==		== Hermite normal form ==
	{{Wikipedia\|Hermite normal form}}		{{Wikipedia\|Hermite normal form}}
	{{Main\|Normal forms #Hermite normal form}}		{{Main\|Normal forms #Hermite normal form}}

FloraC: Internalize Wikipedia links; various linking and style improvements

2026-07-28T05:45:02Z

Internalize Wikipedia links; various linking and style improvements

Show changes

Sintel: /* HNF */ Link main

2025-06-15T17:05:16Z

HNF: Link main

← Older revision		Revision as of 17:05, 15 June 2025
Line 112:		Line 112:

	== HNF ==		== 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.		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.

ArrowHead294: /* Mapping form equivalence possibilities */

2025-02-05T18:22:21Z

Mapping form equivalence possibilities

← Older revision		Revision as of 18:22, 5 February 2025
Line 174:		Line 174:
	[[File:Cases for temperament mapping forms3.png\|300px\|thumb\|right]]		[[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>):		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 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:		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 183:
	# 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}}}}.		# 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:		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:

ArrowHead294: Formatting tweaks

2025-02-05T18:20:11Z

Formatting tweaks

Show changes

Dummy index: /* HNF */ fix link

2025-02-05T13:39:54Z

HNF: fix link

← Older revision		Revision as of 13:39, 5 February 2025
Line 142:		Line 142:
	\|}		\|}

	For an example of working out a HNF by hand, see: [[~~defactoring~~#Hermite decomposition by hand]].		For an example of working out a HNF by hand, see: [[Defactoring algorithms #Hermite decomposition by hand]].

	==SNF==		==SNF==

Dave Keenan: /* SNF */ Replaced "generator preimage transversals" with "generator detemperings".

2023-02-15T00:19:42Z

SNF: Replaced "generator preimage transversals" with "generator detemperings".

← Older revision		Revision as of 00:19, 15 February 2023
Line 148:		Line 148:
	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: {{rket\|{{map\|1 0 0}} {{map\|0 1 0}}}}. Or, if you 2-enfactor them, they will all have the SNF {{rket\|{{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 The fact that it involves calculating so many GCDs is unsurprising given its ability to defactor matrices.</ref>		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: {{rket\|{{map\|1 0 0}} {{map\|0 1 0}}}}. Or, if you 2-enfactor them, they will all have the SNF {{rket\|{{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 The fact that it involves calculating so many GCDs is unsurprising given its ability to defactor matrices.</ref>

	The SNF is used for finding [[generator ~~preimage transversal~~]]s.		The SNF is used for finding [[generator detempering]]s.

	{\| class="wikitable" style="text-align: center;"		{\| class="wikitable" style="text-align: center;"

Cmloegcmluin: fix link and remove misleading footnote

2023-01-08T23:53:51Z

fix link and remove misleading footnote

@@ Line 84: / Line 84: @@
 ==IRREF==
-'''[[Normal_lists|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 [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 nullspace of a mapping, or in other words, the corresponding [[comma basis]] for the temperament represented by the mapping, and then in turn taking the nullspace 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>
+'''[[Normal_lists|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 [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.
 {| class="wikitable" style="text-align: center;"
@@ Line 173: / Line 148: @@
 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: {{rket|{{map|1 0 0}} {{map|0 1 0}}}}. Or, if you 2-enfactor them, they will all have the SNF {{rket|{{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 The fact that it involves calculating so many GCDs is unsurprising given its ability to defactor matrices.</ref>
-The SNF is used for finding [[generators preimage transversal]]s.
+The SNF is used for finding [[generator preimage transversal]]s.
 {| class="wikitable" style="text-align: center;"