Normal forms

IMPORTED REVISION FROM WIKISPACES

This is an imported revision from Wikispaces. The revision metadata is included below for reference:

This revision was by author mbattaglia1 and made on 2012-07-31 03:19:59 UTC.

The original revision id was 355646652.

The revision comment was:

The revision contents are below, presented both in the original Wikispaces Wikitext format, and in HTML exactly as Wikispaces rendered it.

Original Wikitext content:

[[toc]]
An integral matrix is a matrix whose entries are all integers. An important normalized form for integral matrices is [[http://en.wikipedia.org/wiki/Hermite_normal_form|Hermite normal form]], and by using Hermite normal form we may define normalized forms of lists of [[Harmonic Limit|p-limit]] musical intervals (or [[Monzos and Interval Space|monzos]]) or lists of [[Vals and Tuning Space|vals]], the normal interval (or monzo) list and the normal val list.

There are slightly different definitions of Hermite normal form 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 by m integral matrix H is in Hermite normal form if when we define a function F such that F(i) = 0 if all of the entries in the ith column of H are 0, and otherwise F(i) is equal to the row number of the first nonzero entry in the ith column, checking up from the bottom, ie from the nth row, we have

(1) If i > j, H[i, j] = 0 (H is upper triangular.)

(2) F(i) is a function of the column number i.

(3) F(i) = 0 if and only if all of the entries in the ith column are 0.

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

(5) If k > F(i) > 0 then H[k, i] = 0; that is, F(i) is the row of the first nonzero entry in the ith column, counting up from the bottom.

(6) If F(i) > 0 then H[F(i), i] > 0; that is, the first nonzero entry in the ith column, counting up from the bottom, is positive.

(7) If F(i) > 0 and i < j then H[F(i), i] > H[F(i), j] >= 0; that is, the first nonzero entry in the ith 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.

==Normal interval lists== 
Given a list of p-limit intervals, we can convert it to a normal list by the following procedure:

(1) Convert the list to a list of monzos

(2) Reverse the order of the elements of the monzos

(3) Form a matrix whose rows are these reversed monzos

(4) Hermite reduce this matrix to Hermite normal form

(5) Reverse (once again) the entries in each row of the Hermite normal form matrix, and use these re-reversed rows to form a new list of monzos

(6) Discard all of the all-zero monzos, corresponding to the unison 1/1

(7) Reverse the whole list (not the entries) of the remaining monzos

(8) Convert this list back to a list of p-limit rational numbers

(9) For any number q < 1 on this list, replace q with 1/q

The result is a normal interval list. The set of elements of the original list generates a finitely generated free abelian subgroup of the positive rationals under multiplication, and therefore of any p-limit group it lives inside. The normalized list contains a minimal set of generators, each greater than zero, in an ordering of nondecreasing prime limit which is parsimonious in its use of higher limits. For example, if we normalize [81/80, 126/125] we obtain [81/80, 59049/57344]. The first interval is 5-limit, which is as small as possible. The second is 7-limit, which must be the case because the group these two generate is 7-limit. However, it uses only 2, 3 and 7 in its prime factorization, parsimoniously rejecting 5 as the next highest prime limit. Because [[Abstract regular temperament|abstract regular temperaments]], where the prime mappings are known but not the specific tuning of the generators, are fully characterized by their kernel, the group of intervals they map to the unison, they can be also be characterized by the regular interval list of a set of generators (called commas or unison vectors) for the kernel. The above normal interval list, for example, characterizes septimal meantone, defining the normal [[Comma sequences|comma sequence]] of septimal meantone.

Normal interval lists can also be used to characterize the [[just intonation subgroups]] on which subgroup temperaments are defined and using which subgroup scales may be constructed. On the pages [[Chromatic pairs]], [[Subgroup temperaments]] and [[Just intonation subgroups]] can be found many examples; the subgroup lists are given in a form where generators of the subgroup are separated by periods so as to flag the fact that the list defines a subgroup. An example would be the Barbados subgroup, 2.3.13/5.

==Normal val lists== 
If L is a list of n vals, we may write it as an nxm matrix, where the rows of the matrix are the vals, and m = pi(p), where p is the prime limit. To get the normal val list, we do the following:

(1) Hermite reduce the matrix for L

(2) Throw away all rows which consist of nothing but zeros, resulting in a kxm matrix

(3) Find the [[http://en.wikipedia.org/wiki/Moore%E2%80%93Penrose_pseudoinverse|Moore-Penrose pseudoinverse]] of the kxm matrix, and multiply this from the left by the row vector [1 log2(3) log2(5) ... log2(p)]. If the ith entry in the result is negative, multiply the corresponding val by -1. Return the result as the normalized val list.

The point of steps two and three is that now the vals on the list correspond to a list of generators which are all positive (written additively) or equivalently greater than 1 (written multiplicatively.) Just as a normal comma list can be used to classify an [[abstract regular temperament]], so can a normal val list. The val list is what on [[Graham Breed]]'s [[http://x31eq.com/temper/|web site]] is called a "mapping", put into a canonical form. The "Maps" (though not the "Map to lattice") listed on temperament pages of this wiki are all normal val lists; an example would be [<1 0 -4 -13|, <0 1 4 10|], the normal val list for septimal meantone.

==Maple code== 
Below is Maple code for finding the normal interval and val list, given an interval list or a val list.

log2 := proc(x) evalf(ln(x)/ln(2)) end:

transpos := proc(w)
# transpose of listlist w
local u;
u := Matrix(w);
u := LinearAlgebra[Transpose](u);
convert(u, listlist) end:

pseudo := proc(w)
# pseudoinverse of listlist w
local u;
u := Matrix(w);
u := LinearAlgebra[MatrixInverse](u, method='pseudo');
convert(u, listlist) end:

psu := proc(w) transpos(pseudo(w)) end:

pril := proc(n)
# log2 of first n primes
local i, u;
u := NULL;
for i from 1 to n do
u := u,log2(ithprime(i)) od;
[u] end:

revlist := proc(l)
# reverse of list
local i, v, e;
e := nops(l);
for i from 1 to e do
v[i] := l[e-i+1] od;
convert(convert(v,array),list) end:

orp := proc(w, p) padic[ordp](w, p) end:

pim := proc(q)
# rank of p-limit of q
local r, i, p;
r := 1;
i := 0;
while not (r=q) do
i := i+1;
p := ithprime(i);
r := r*p^orp(q, p) od;
if i=0 then RETURN(0) fi;
i end:

plim := proc(q)
# prime limit of rational number q
ithprime(pim(q)) end:

rat2monz := proc(q, n)
# converts rational number q to monzo of length n
local v, i;
for i from 1 to n do
v[i] := ordp(q, ithprime(i)) od;
convert(convert(v, array), list) end:

monz2rat := proc(m)
# converts monzo to rational number
local i, t;
t := 1;
for i from 1 to nops(m) do
t := t * ithprime(i)^m[i] od;
t end:

herm := proc(l)
# hermite normal form of listlist l
local M;
M := Matrix(l);
convert(convert(HermiteForm[Z](M), array), listlist) end:

nori := proc(l)
# normal interval list from list of intervals l
local i, p, u, v, w;
p := 1;
for i from 1 to nops(l) do
p := max(p, plim(l[i])) od;
u := [];
for i from 1 to nops(l) do
u := [op(u), revlist(rat2monz(l[i], p))] od;
v := herm(u);
for i from 1 to nops(l) do
u := revlist(v[i]);
u := monz2rat(u);
w[i] := u od;
u := [];
for i from 1 to nops(l) do
v := w[i];
if v<1 then v:=1/v fi;
if not v=1 then u := [op(u), v] fi od;
revlist(u) end:

norv := proc(l)
# normal val list from list of vals l
local u, v, w, i, n, a;
u := herm(l);
n := rnk(u);
v := NULL:
for i from 1 to n do
v := v,u[i] od;
v := [v];
u := pseudo(v);
w := pril(nops(l[1]));
a := op(matmul(w, u));
u := NULL;
for i from 1 to n do
if a[i] < 0 then u := u,-v[i] fi;
if a[i] >= 0 then u := u,v[i] fi od;
[u] end:

Original HTML content:

<html><head><title>Normal lists</title></head><body><!-- ws:start:WikiTextTocRule:6:&lt;img id=&quot;wikitext@@toc@@normal&quot; class=&quot;WikiMedia WikiMediaToc&quot; title=&quot;Table of Contents&quot; src=&quot;/site/embedthumbnail/toc/normal?w=225&amp;h=100&quot;/&gt; --><div id="toc"><h1 class="nopad">Table of Contents</h1><!-- ws:end:WikiTextTocRule:6 --><!-- ws:start:WikiTextTocRule:7: --><div style="margin-left: 2em;"><a href="#x-Normal interval lists">Normal interval lists</a></div>
<!-- ws:end:WikiTextTocRule:7 --><!-- ws:start:WikiTextTocRule:8: --><div style="margin-left: 2em;"><a href="#x-Normal val lists">Normal val lists</a></div>
<!-- ws:end:WikiTextTocRule:8 --><!-- ws:start:WikiTextTocRule:9: --><div style="margin-left: 2em;"><a href="#x-Maple code">Maple code</a></div>
<!-- ws:end:WikiTextTocRule:9 --><!-- ws:start:WikiTextTocRule:10: --></div>
<!-- ws:end:WikiTextTocRule:10 -->An integral matrix is a matrix whose entries are all integers. An important normalized form for integral matrices is <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Hermite_normal_form" rel="nofollow">Hermite normal form</a>, and by using Hermite normal form we may define normalized forms of lists of <a class="wiki_link" href="/Harmonic%20Limit">p-limit</a> musical intervals (or <a class="wiki_link" href="/Monzos%20and%20Interval%20Space">monzos</a>) or lists of <a class="wiki_link" href="/Vals%20and%20Tuning%20Space">vals</a>, the normal interval (or monzo) list and the normal val list.<br />
<br />
There are slightly different definitions of Hermite normal form 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.<br />
<br />
An n by m integral matrix H is in Hermite normal form if when we define a function F such that F(i) = 0 if all of the entries in the ith column of H are 0, and otherwise F(i) is equal to the row number of the first nonzero entry in the ith column, checking up from the bottom, ie from the nth row, we have<br />
<br />
(1) If i &gt; j, H[i, j] = 0 (H is upper triangular.)<br />
<br />
(2) F(i) is a function of the column number i.<br />
<br />
(3) F(i) = 0 if and only if all of the entries in the ith column are 0.<br />
<br />
(4) F is an increasing function of the column number i, and becomes strictly increasing after F(i) becomes positive.<br />
<br />
(5) If k &gt; F(i) &gt; 0 then H[k, i] = 0; that is, F(i) is the row of the first nonzero entry in the ith column, counting up from the bottom.<br />
<br />
(6) If F(i) &gt; 0 then H[F(i), i] &gt; 0; that is, the first nonzero entry in the ith column, counting up from the bottom, is positive.<br />
<br />
(7) If F(i) &gt; 0 and i &lt; j then H[F(i), i] &gt; H[F(i), j] &gt;= 0; that is, the first nonzero entry in the ith column, counting up from the bottom, is greater than any of the rest along that row, which however are all non-negative.<br />
<br />
There is some redundancy in the statement of these conditions, but that does no harm.<br />
<br />
<!-- ws:start:WikiTextHeadingRule:0:&lt;h2&gt; --><h2 id="toc0"><a name="x-Normal interval lists"></a><!-- ws:end:WikiTextHeadingRule:0 -->Normal interval lists</h2>
 Given a list of p-limit intervals, we can convert it to a normal list by the following procedure:<br />
<br />
(1) Convert the list to a list of monzos<br />
<br />
(2) Reverse the order of the elements of the monzos<br />
<br />
(3) Form a matrix whose rows are these reversed monzos<br />
<br />
(4) Hermite reduce this matrix to Hermite normal form<br />
<br />
(5) Reverse (once again) the entries in each row of the Hermite normal form matrix, and use these re-reversed rows to form a new list of monzos<br />
<br />
(6) Discard all of the all-zero monzos, corresponding to the unison 1/1<br />
<br />
(7) Reverse the whole list (not the entries) of the remaining monzos<br />
<br />
(8) Convert this list back to a list of p-limit rational numbers<br />
<br />
(9) For any number q &lt; 1 on this list, replace q with 1/q<br />
<br />
The result is a normal interval list. The set of elements of the original list generates a finitely generated free abelian subgroup of the positive rationals under multiplication, and therefore of any p-limit group it lives inside. The normalized list contains a minimal set of generators, each greater than zero, in an ordering of nondecreasing prime limit which is parsimonious in its use of higher limits. For example, if we normalize [81/80, 126/125] we obtain [81/80, 59049/57344]. The first interval is 5-limit, which is as small as possible. The second is 7-limit, which must be the case because the group these two generate is 7-limit. However, it uses only 2, 3 and 7 in its prime factorization, parsimoniously rejecting 5 as the next highest prime limit. Because <a class="wiki_link" href="/Abstract%20regular%20temperament">abstract regular temperaments</a>, where the prime mappings are known but not the specific tuning of the generators, are fully characterized by their kernel, the group of intervals they map to the unison, they can be also be characterized by the regular interval list of a set of generators (called commas or unison vectors) for the kernel. The above normal interval list, for example, characterizes septimal meantone, defining the normal <a class="wiki_link" href="/Comma%20sequences">comma sequence</a> of septimal meantone.<br />
<br />
Normal interval lists can also be used to characterize the <a class="wiki_link" href="/just%20intonation%20subgroups">just intonation subgroups</a> on which subgroup temperaments are defined and using which subgroup scales may be constructed. On the pages <a class="wiki_link" href="/Chromatic%20pairs">Chromatic pairs</a>, <a class="wiki_link" href="/Subgroup%20temperaments">Subgroup temperaments</a> and <a class="wiki_link" href="/Just%20intonation%20subgroups">Just intonation subgroups</a> can be found many examples; the subgroup lists are given in a form where generators of the subgroup are separated by periods so as to flag the fact that the list defines a subgroup. An example would be the Barbados subgroup, 2.3.13/5.<br />
<br />
<!-- ws:start:WikiTextHeadingRule:2:&lt;h2&gt; --><h2 id="toc1"><a name="x-Normal val lists"></a><!-- ws:end:WikiTextHeadingRule:2 -->Normal val lists</h2>
 If L is a list of n vals, we may write it as an nxm matrix, where the rows of the matrix are the vals, and m = pi(p), where p is the prime limit. To get the normal val list, we do the following:<br />
<br />
(1) Hermite reduce the matrix for L<br />
<br />
(2) Throw away all rows which consist of nothing but zeros, resulting in a kxm matrix<br />
<br />
(3) Find the <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Moore%E2%80%93Penrose_pseudoinverse" rel="nofollow">Moore-Penrose pseudoinverse</a> of the kxm matrix, and multiply this from the left by the row vector [1 log2(3) log2(5) ... log2(p)]. If the ith entry in the result is negative, multiply the corresponding val by -1. Return the result as the normalized val list.<br />
<br />
The point of steps two and three is that now the vals on the list correspond to a list of generators which are all positive (written additively) or equivalently greater than 1 (written multiplicatively.) Just as a normal comma list can be used to classify an <a class="wiki_link" href="/abstract%20regular%20temperament">abstract regular temperament</a>, so can a normal val list. The val list is what on <a class="wiki_link" href="/Graham%20Breed">Graham Breed</a>'s <a class="wiki_link_ext" href="http://x31eq.com/temper/" rel="nofollow">web site</a> is called a &quot;mapping&quot;, put into a canonical form. The &quot;Maps&quot; (though not the &quot;Map to lattice&quot;) listed on temperament pages of this wiki are all normal val lists; an example would be [&lt;1 0 -4 -13|, &lt;0 1 4 10|], the normal val list for septimal meantone.<br />
<br />
<!-- ws:start:WikiTextHeadingRule:4:&lt;h2&gt; --><h2 id="toc2"><a name="x-Maple code"></a><!-- ws:end:WikiTextHeadingRule:4 -->Maple code</h2>
 Below is Maple code for finding the normal interval and val list, given an interval list or a val list.<br />
<br />
log2 := proc(x) evalf(ln(x)/ln(2)) end:<br />
<br />
transpos := proc(w)<br />
<ol><li>transpose of listlist w</li></ol>local u;<br />
u := Matrix(w);<br />
u := LinearAlgebra[Transpose](u);<br />
convert(u, listlist) end:<br />
<br />
pseudo := proc(w)<br />
<ol><li>pseudoinverse of listlist w</li></ol>local u;<br />
u := Matrix(w);<br />
u := LinearAlgebra[MatrixInverse](u, method='pseudo');<br />
convert(u, listlist) end:<br />
<br />
psu := proc(w) transpos(pseudo(w)) end:<br />
<br />
pril := proc(n)<br />
<ol><li>log2 of first n primes</li></ol>local i, u;<br />
u := NULL;<br />
for i from 1 to n do<br />
u := u,log2(ithprime(i)) od;<br />
[u] end:<br />
<br />
revlist := proc(l)<br />
<ol><li>reverse of list</li></ol>local i, v, e;<br />
e := nops(l);<br />
for i from 1 to e do<br />
v[i] := l[e-i+1] od;<br />
convert(convert(v,array),list) end:<br />
<br />
orp := proc(w, p) padic[ordp](w, p) end:<br />
<br />
pim := proc(q)<br />
<ol><li>rank of p-limit of q</li></ol>local r, i, p;<br />
r := 1;<br />
i := 0;<br />
while not (r=q) do<br />
i := i+1;<br />
p := ithprime(i);<br />
r := r*p^orp(q, p) od;<br />
if i=0 then RETURN(0) fi;<br />
i end:<br />
<br />
plim := proc(q)<br />
<ol><li>prime limit of rational number q</li></ol>ithprime(pim(q)) end:<br />
<br />
rat2monz := proc(q, n)<br />
<ol><li>converts rational number q to monzo of length n</li></ol>local v, i;<br />
for i from 1 to n do<br />
v[i] := ordp(q, ithprime(i)) od;<br />
convert(convert(v, array), list) end:<br />
<br />
monz2rat := proc(m)<br />
<ol><li>converts monzo to rational number</li></ol>local i, t;<br />
t := 1;<br />
for i from 1 to nops(m) do<br />
t := t * ithprime(i)^m[i] od;<br />
t end:<br />
<br />
herm := proc(l)<br />
<ol><li>hermite normal form of listlist l</li></ol>local M;<br />
M := Matrix(l);<br />
convert(convert(HermiteForm[Z](M), array), listlist) end:<br />
<br />
nori := proc(l)<br />
<ol><li>normal interval list from list of intervals l</li></ol>local i, p, u, v, w;<br />
p := 1;<br />
for i from 1 to nops(l) do<br />
p := max(p, plim(l[i])) od;<br />
u := [];<br />
for i from 1 to nops(l) do<br />
u := [op(u), revlist(rat2monz(l[i], p))] od;<br />
v := herm(u);<br />
for i from 1 to nops(l) do<br />
u := revlist(v[i]);<br />
u := monz2rat(u);<br />
w[i] := u od;<br />
u := [];<br />
for i from 1 to nops(l) do<br />
v := w[i];<br />
if v&lt;1 then v:=1/v fi;<br />
if not v=1 then u := [op(u), v] fi od;<br />
revlist(u) end:<br />
<br />
norv := proc(l)<br />
<ol><li>normal val list from list of vals l</li></ol>local u, v, w, i, n, a;<br />
u := herm(l);<br />
n := rnk(u);<br />
v := NULL:<br />
for i from 1 to n do<br />
v := v,u[i] od;<br />
v := [v];<br />
u := pseudo(v);<br />
w := pril(nops(l[1]));<br />
a := op(matmul(w, u));<br />
u := NULL;<br />
for i from 1 to n do<br />
if a[i] &lt; 0 then u := u,-v[i] fi;<br />
if a[i] &gt;= 0 then u := u,v[i] fi od;<br />
[u] end:</body></html>