Smith normal form

I've talked quite a bit about the utility of Hermite normal form,
which is a reduction of an integral matrix which uses elementary row
operations (or the column form, elementary column operations.) Another
normal form, useful for getting at more abstract, group theoretic
properties, is Smith normal form. This allows reduction by elementary
row *and* column operations.

If M is a square integral matrix, then the Smith normal form is a
diagonal matrix S, such that

S = UMV

Here the diagonal elements are nonnegative integers, where aii might
be zero from some point on, but before that aii divides ajj when i<j.
If M is nonsingular, then S has only positive integers along the
diagonal. U and V are unimodular matricies, so the absolute value of
the determinants of S and M are the same. The numbers along the
diagonal are the invariants, also called invariant factors or
elementary divisors.

Here are some examples of the use of Smith normal form. Suppose we
take the matrix of monzos corresponding to [2, 81/80, 128/125]; the
Smith normal form has invariants 1,1,12, which tells us that the image
of the group obtained from this as a kernel is C12, the cyclic group
of order 12. If we take the monzo matrix and multiply it on the left
by the "U" in the reduction to Smith normal form, we get a monzo
matrix [|1 0 1>, |0 -4 1>, |0 12 0>]. The element which is a power of
12 is |0 12 0>, or 3^12. This tells us that the generator for this
mapping can be taken as 3.

Suppose instead we start with [2, 648/625, 2048/2025]; now the Smith
normal form has 1,2,12 along the diagonal. This tells us that the
image group is C2 x C12; and we have torsion. The C2 part is our
extraneous torsional part. The Smith normal form here clearly
distinguishes C2 x C12 from C24; these are not the same abelian
groups. If we take UM, where M is the monzo matrix, the partial
reduction to Smith normal form is [|1 0 0>, |0 4 2>, |0 -36 -12>].
We can take |0 2 1>, or 45, and |0 -3 -1>, or 1/135, as generators for
the C2 and C12 parts; if we want we can work mod octaves, taking
45/32 and 135/128 as our generators. The 5-limit is generated by 2,
45/32, and 135/128, and modulo 2, 648/625 and 2048/2025 we find that
45/32 is of order 2 and 135/128 is of order 12, but modulo these
(45/32)/(135/128)^6 reduces to 81/80, not 1. Hence the group we get is
*not* a cyclic group, but C2 x C12.

We can also work with vals; for instance the standard 5-limit vals for
17, 21 and 27 have invarints 2 and 4. We can now multiply the matrix
obtained from the column vectors of these by "V" on the right, and
find it is equivalent to [<17 27 39|, <10 16 28|, <0 0 4|], where we
see the second val is divisible by 2 and the third by 4.

>I've talked quite a bit about the utility of Hermite normal form,
>which is a reduction of an integral matrix which uses elementary row
>operations (or the column form, elementary column operations.) Another
>normal form, useful for getting at more abstract, group theoretic
>properties, is Smith normal form. This allows reduction by elementary
>row *and* column operations.

Named after you?

-Carl

--- In tuning-math@yahoogroups.com, Carl Lumma <ekin@l...> wrote:

> Named after you?

Strangely enough, no 19th century mathematics is named after me.

--- In tuning-math@yahoogroups.com, "Gene Ward Smith" <gwsmith@s...>
wrote:
> --- In tuning-math@yahoogroups.com, Carl Lumma <ekin@l...> wrote:
>
> > Named after you?
>
> Strangely enough, no 19th century mathematics is named after me.

Here's the correct Smith:

http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Smith.html