Normal forms: Difference between revisions

Line 4:

== Hermite normal form ==

~~[[Wikipedia:~~ Hermite normal form|Hermite normal form]], or HNF for short, is an important normal form that is defined for integer matrices in the mathematical field of linear algebra. An integer matrix is simply a 2D array of integers, and so we can easily think of lists of vals or commas as integer matrices and therefore leverage HNF in regular temperament theory.

The '''Hermite normal form''', or HNF for short, is an important normal form that is defined for integer matrices in the mathematical field of linear algebra.

An integer matrix is simply a 2D array of integers, and so we can easily think of lists of vals or commas as integer matrices and therefore leverage HNF in regular temperament theory.

~~HNF by itself is not used as a~~ normal form ~~for regular temperament theory~~. ~~However~~, it is ~~part~~ of the ~~definition of most normal forms here~~, so it ~~is important~~ to ~~have a basic understanding~~ of it.

The Hermite normal form is unique. Besides that, it is also the integer analogue of the reduced echelong form, so it can be used to solve systems of equations in the integers by Gaussian elimination.

There are slightly different definitions of HNF in use, and if you are using a computer program to compute it, you should take care that the same normal monzo or val list is finally achieved. The definition used by the Wikipedia article on Hermite form, probably the most standard, works as follows.

There are slightly different definitions of HNF in use, and if you are using a computer program to compute it, you should take care that the same normal monzo or val list is finally achieved.

The definition used by the Wikipedia article on Hermite form, probably the most standard, works as follows.

An ''n''×''m'' integer matrix H is in (row-wise) HNF if it satisfies the following conditions:

~~An ''n''×''m'' integral matrix~~ H is ~~in HNF if when we define a function ''F'' such that {{nowrap|''F''(''i'') {{=}} 0}} if all of~~ the entries ~~in the~~ ''i''~~-th column of H are~~ 0~~, and otherwise ''F''(~~''i''~~) is equal to the row number of the first nonzero entry in the ''i''-th column, checking up from the bottom, i.e. from the ''n''-th row, we have~~

# H is upper triangular: the entries ''h<sub>ij</sub>'' = 0 for ''i'' > ''j'', and any rows of zeros are located below the other rows.

# The first non-zero entry from the left (called the ''leading coefficient'') of any non-zero row is always stricly to the right of the leading coefficient of the row above it.

~~# If {{nowrap|''i'' >~~ ''j''}}, ~~{{nowrap|H[''i'', ''j''] {{=}} 0}} (H is upper triangular.)~~

# The leading coefficients are positive.

~~# ''F''(''i'') is a function~~ of the ~~column number ''i''~~.

# The elements below every leading coefficient are zero, and the entries above are strictly smaller than the leading coefficient.

# ~~{{nowrap|''F''~~(''i'') ~~{{=}} 0}} if and only if all~~ of ~~the entries in the ''i''~~-~~th column are 0.~~

~~# ''F''~~ is ~~an increasing function~~ of the ~~column number ''i'', and becomes strictly increasing after ''F''(''i'') becomes positive.~~

~~# If {{nowrap|''k'' > ''F''(''i'') > 0}} then {{nowrap|H[''k'', ''i''] {{=}} 0}}; that is, ''F''(''i'') is~~ the row ~~of the first nonzero entry in the ''i''-th column, counting up from the bottom~~.

# ~~If {{nowrap|''F''(''i'') > 0}} then {{nowrap|H[''F''(''i''), ''i''] > 0}}; that is, the first nonzero entry in the ''i''-th column, counting up from the bottom, is~~ positive.

# ~~If {{nowrap|''F''(''i'') > 0}}~~ and ~~{{nowrap|''i'' < ''j''}} then {{nowrap|H[''F''(''i''), ''i''] > H[''F''(''i''), ''j''] ≥ 0}}; that is,~~ the ~~first nonzero entry in the ''i''-th column, counting up from the bottom, is greater~~ than ~~any of the rest along that row, which however are all non-negative.~~

~~There is some redundancy in~~ the ~~statement of these conditions, but that does no harm~~.

For more information, diagrams, an alternative articulation of the same definition, and comparisons with related integer matrix forms, see: [[Matrix echelon forms #HNF]].

@@ Line 4: / Line 4: @@
 == Hermite normal form ==
-[[Wikipedia: Hermite normal form|Hermite normal form]], or HNF for short, is an important normal form that is defined for integer matrices in the mathematical field of linear algebra. An integer matrix is simply a 2D array of integers, and so we can easily think of lists of vals or commas as integer matrices and therefore leverage HNF in regular temperament theory.
+{{wikipedia|Hermite normal form}}
+The '''Hermite normal form''', or HNF for short, is an important normal form that is defined for integer matrices in the mathematical field of linear algebra.
+An integer matrix is simply a 2D array of integers, and so we can easily think of lists of vals or commas as integer matrices and therefore leverage HNF in regular temperament theory.
-HNF by itself is not used as a normal form for regular temperament theory. However, it is part of the definition of most normal forms here, so it is important to have a basic understanding of it.
+The Hermite normal form is unique. Besides that, it is also the integer analogue of the reduced echelong form, so it can be used to solve systems of equations in the integers by Gaussian elimination.
-There are slightly different definitions of HNF in use, and if you are using a computer program to compute it, you should take care that the same normal monzo or val list is finally achieved. The definition used by the Wikipedia article on Hermite form, probably the most standard, works as follows.
+There are slightly different definitions of HNF in use, and if you are using a computer program to compute it, you should take care that the same normal monzo or val list is finally achieved.
+The definition used by the Wikipedia article on Hermite form, probably the most standard, works as follows.
+An ''n''&times;''m'' integer matrix H is in (row-wise) HNF if it satisfies the following conditions:
-An ''n''&times;''m'' integral matrix H is in HNF if when we define a function ''F'' such that {{nowrap|''F''(''i'') {{=}} 0}} if all of the entries in the ''i''-th column of H are 0, and otherwise ''F''(''i'') is equal to the row number of the first nonzero entry in the ''i''-th column, checking up from the bottom, i.e. from the ''n''-th row, we have
+# H is upper triangular: the entries ''h<sub>ij</sub>'' = 0 for ''i'' > ''j'', and any rows of zeros are located below the other rows.
+# The first non-zero entry from the left (called the ''leading coefficient'') of any non-zero row is always stricly to the right of the leading coefficient of the row above it.
-# If {{nowrap|''i'' &gt; ''j''}}, {{nowrap|H[''i'', ''j''] {{=}} 0}} (H is upper triangular.)
+# The leading coefficients are positive.
-# ''F''(''i'') is a function of the column number ''i''.
+# The elements below every leading coefficient are zero, and the entries above are strictly smaller than the leading coefficient.
-# {{nowrap|''F''(''i'') {{=}} 0}} if and only if all of the entries in the ''i''-th column are 0.
-# ''F'' is an increasing function of the column number ''i'', and becomes strictly increasing after ''F''(''i'') becomes positive.
-# If {{nowrap|''k'' &gt; ''F''(''i'') &gt; 0}} then {{nowrap|H[''k'', ''i''] {{=}} 0}}; that is, ''F''(''i'') is the row of the first nonzero entry in the ''i''-th column, counting up from the bottom.
-# If {{nowrap|''F''(''i'') &gt; 0}} then {{nowrap|H[''F''(''i''), ''i''] &gt; 0}}; that is, the first nonzero entry in the ''i''-th column, counting up from the bottom, is positive.
-# If {{nowrap|''F''(''i'') &gt; 0}} and {{nowrap|''i'' &lt; ''j''}} then {{nowrap|H[''F''(''i''), ''i''] &gt; H[''F''(''i''), ''j''] &ge; 0}}; that is, the first nonzero entry in the ''i''-th column, counting up from the bottom, is greater than any of the rest along that row, which however are all non-negative.
-There is some redundancy in the statement of these conditions, but that does no harm.
 For more information, diagrams, an alternative articulation of the same definition, and comparisons with related integer matrix forms, see: [[Matrix echelon forms #HNF]].