Yahoo Tuning Groups Ultimate Backup tuning-math Reduced echelon form

As the next step on my search for an invariant quantity for temperaments, I'm looking at row echelon form. This is best described in the Oxford Dictionary of Mathematics, which is unfortunately in a dead tree format so I can't send a link. It's also the result of Gauss-Jordan elimination.

The idea is to get the left hand side to look as much like the identity matrix as possible. Because temperament mappings can only contain integers, I implicitly multiply each row through by its lowest common denominator.

Because of the way the calculation's done I have to find the greatest common divisor (gcd) of each row. As a result, all information about contorsion gets lost.

The result looks pretty much like the wedgie-like invariant I came up with yesterday. The difference is that each row has a gcd of 1 and a first non-zero entry that's always postive. Also, contorted temperaments give the same result as their uncontorted relatives.

The result can still have contorsion, which is a pain. So this is no use as a way of removing torsion from a set of unison vectors. I still haven't worked out Hermite normal form, which Gene suggested for that. They seem to be related, anyway.

The advantage of reduced echelon form over the wedgie-like thing is that, like full wedgies, it's easily generalized to higher ranks. I've verified that the wedgies are recoverable for ranks 2 and 3.

The code's fiddly and likely to be inefficient because of the gcd calculations (which don't even tell us anything about contorsion). I haven't tested yet but it may be faster than my wedge product code because that's extremely inefficient for ranks greater than 2. There may be a better way of doing either.

Here's that code, with a bit of word wrapping:

from __future__ import division
import regular_wedgie
from regular_wedgie import hcf
from math import sqrt

def ref(ets):
"""Reduced echelon form"""
return [normalize_row(row) for row in raw_ref(ets)]

def raw_ref(ets):
"""Reduced echelon form without removing common factors
or adjusting signs.
"""
rows = [list(et) for et in ets]
n_rows = len(rows)
n_columns = len(rows[0])
for row in rows:
assert len(row)==n_columns
row = column = 0
while row < n_rows:
try:
row, column = reduction_point(rows, row, column)
except ReductionException:
raise LowerRankException, "Lower rank temperament"
n = rows[row][column]
for i in range(n_rows):
if i==row:
continue
m = rows[i][column]
for j in range(n_columns):
rows[i][j] = n*rows[i][j] - m*rows[row][j]
row += 1
column += 1
return rows

def check_ref(ets):
try:
reduced = ref(ets)
except LowerRankException:
for element in wedgie(ets):
assert element==0
return ###
torsion = False
for et in ets:
try:
multiples = un_ref(et, reduced)
for j in range(len(et)):
total = 0
for m, v in zip(multiples, reduced):
total += m*v[j]
assert total == et[j], "Failed for %s"%et
except ContorsionException:
torsion = True
except AssertionError:
print ets
raise
wedgie1 = wedgie(ets)
wedgie2 = wedgie(reduced)
contorsion1 = hcf(wedgie1)
contorsion2 = hcf(wedgie2)
if contorsion2==1:
assert not torsion
for m, n in zip(wedgie1, wedgie2):
assert m*contorsion2 == n*contorsion1, "wedgies don't match for %s"%str(
ets)

def un_ref(et, reduced):
"""Return the multiples of reduced that give et.
Assumes reduced is the result of ref.
"""
result = []
j=0
for i in range(len(reduced)):
while reduced[i][j]==0:
j += 1
y, check = divmod(et[j], reduced[i][j])
if check:
raise ContorsionException, "%s %s contorted" % (et, reduced)
result.append(y)
return tuple(result)

def wedgie(ets):
return tuple(normalize_sign(regular_wedgie.wedgie(ets)))

def normalize_row(mapping):
torsion = hcf(mapping)
return normalize_sign([m//torsion for m in mapping])

def normalize_sign(mapping):
nonzeros = [m for m in mapping if m]
if nonzeros==[] or nonzeros[0]>0:
return mapping
return [-m for m in mapping]

def reduction_point(rows, row, column):
if column >= len(rows[row]):
raise ReductionException, "Everything zero!"
try:
actual_row = first_non_zero(rows, row, column)
if row != actual_row:
rows[row], rows[actual_row] = rows[actual_row], rows[row]
return row, column
except ReductionException:
# this column all zer
# so try the next one
return reduction_point(rows, row, column+1)

def first_non_zero(rows, first_row, column):
for row in range(first_row, len(rows)):
if rows[row][column]:
return row
raise ReductionException, "Zero in all rows"

Gene Ward Smith wrote:
> --- In tuning-math@yahoogroups.com, Graham Breed <gbreed@...> wrote:
> > I still haven't worked out Hermite normal > >>form, which Gene suggested for that. They seem to be >>related, anyway.
> > > Closely, but I think it would be to your advantage to write up Hermite > form reduction.

The fact is I don't know how to do that! I looked at reduced echelon form because one reference said it was the same as Hermite normal form. But other references plainly contradict that. Everything I can find is either for non-singular matrices (which is obviously meaningless here), describes the result but not how to get there, or I plain couldn't understand.

In the end I found it easier to write a function that does what I want and not worry about what to call it. I do have one now that preserves contorsion, and is unique as far as I can test. The problem is I don't have any other way to be sure that two contorted temperament-like-things are distinct.

Some 5-limit examples:

5&7, 7&12, 12&19, 19&31, etc (meantone)

[[1, 0, -4],
[0, 1, 4]]

7&24, 7&31, 24&31 (Vicentino-like neutral thirds meantone)

[[1, 1, 0],
[0, 2, 8]]

5&24, 5&19, 19&24 (identical wedgie to the previous)

[[1, 0, -4],
[0, 2, 8]]

Some of the off-diagonals that are defined as zero in reduced echelon form are the smallest non-negative values here that don't increase torsion.

Graham

Reduced echelon form

🔗Graham Breed <gbreed@gmail.com>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Graham Breed <gbreed@gmail.com>

🔗Gene Ward Smith <genewardsmith@sbcglobal.net>

🔗Graham Breed <gbreed@gmail.com>