Math guys! What does "s = (0)(1,2,4,8,7,5)(3,6)(9)" mean?

General Questions
#1

I’m neither particularly excellent nor particularly poor in mathematics; however, I’m somewhat interested in practical applications of “pure” mathematics, and I’ve always had good math grades in (the German equivalent of) college, so I guess grasping this wouldn’t be totally beyond my scope.

On the net, I stumbled over this page, dealing with a check digit algorithm used in various numbering schemes. It mentions the “permutation” s = (0)(1,2,4,8,7,5)(3,6)(9) [s being the Greek letter sigma, don’t know how to code this] to be applied to the single digits of a number.

From other web sources, I’ve learned that this equals doubling the digits, and subtracting 9 if the result of the doubling is larger than 9. So could anybody please (try to) explain to me how s = (0)(1,2,4,8,7,5)(3,6)(9) is supposed to work, i.e. what the grouping of the digits in brackets means? From what I remember from statistics, permutations are the various possibilities of grouping a set of objects in different orders.

#2

A permutation is basically a rearrangement of some set of elements, which we can designate numerically for convenience. Usually one labels them starting with 1, but in your example, 0 is one of the elements, presumably because we are talking about rearranging the digits of a number.

It can be shown that any permutation can be represented as a set of disjoint cycles, and the customary way to represent them is the notation you quoted. It means 0 and 9 stay in place. 1 is mapped to 2, 2 to 4, 4 to 8, 7 to 5, and 5 back to 1. 3 is mapped to 6 and 6 back to 3. Sometimes the notation simply uses spaces rather than commas to separate the numbers.

For a number of reasons, this is a convenient way to study permutations, which are important in group theory, and one can easily learn to impose one permutation on another with a special form of “multiplication”:

(1 2 3)(1 3) = (1 2)
(1 2 3)(1 3) = (2 3)

The first answer is multiplying left to right, the second right to left. Both conventions are sometimes used.

#3

Oh, I should have said “4 to 8, 8 to 7, 7 to 5”.

#4

I think I got it (at least the mapping part; doesn’t seem obvious to me that you can represent any permutation as a set of cycles, but I surely do believe you that there’s been a proof for this). Thanks!

#5

Actually, it isn’t too difficult to see why that is. Imagine your permutation expressed as a 1-1 map of elements. Note that any particular element can only have one element mapped to it (perhaps itself). Start with an element a whose cycle membership you haven’t determined, and follow the chain formed by the mapping: a -> b -> c -> … At each point, the element can be mapped only to an element you haven’t mentioned yet, or element a that started the chain (b, c, etc are out because we already know something else maps to them). If it is a, we have completed a cycle. And since we assume there are a finite number of elements, you will eventually run out of other elements. Having determined this cycle, proceed to another element whose cycle membership is undetermined.

#6

Usually, permutations are applied on the left and therefore read right to left and the indicated one would map 5 to 7, 7 to 8 and so on. But this is purely a convention and some people apply on the right and therefore read this from the left.

#7

FYI:

σ is coded: by typing ‘& sigma ;’ without the spaces (and apostrophes) this works for any greek letter and to capitailize you simply start the greek letter with a capital: & Sigma ; = Σ

#8

MC, that works for most newer browsers, but not on older browsers. In turn, on older browsers, you can usually use the Symbol font to get the same effect, but that won’t work on many newer browsers. Unfortunately, there doesn’t seem to be any way to produce Greek letters on webpages that works for all (or even most) browsers.

#9

HAH! You must have one of those space-age browsers I’ve been hearing about, MCMC!

Also, yes, everybody’s right about the notation. I might add a point to the hard math geeks. An indecomposable permutation p on [n] (the set {1, 2, … ,n} is one such that there is no m < n such that the image of [m], p([m]), is [m] itself (i.e. the first m numbers come in the first m positions).

There is a transposition Gray code for indecomposable permutations, and they can be generated in this code in constant amortized time (as well as the order in which they would appear in the SJT (Steinhaus-Johnson-Trotter) algorithm for generating all permutations.

Now THAT’s geeky.

#10

Nothing to add to the math, but [symbol]s[/symbol] can be coded as [symbol]s[/symbol] on this board.

Permutations are treated in any introductory group theory book.

#11

Actually, the most common convention reads left-to-right within a cycle and right-to-left for products of cycles. (This is because permutations are thought of as functions, and function composition is conventionally written right-to-left so that (f º g)(x) = f(g(x)).) I’ve never seen a case where the cycle (1 2 3) meant “1 maps to 3, 3 to 2, and 2 to 1”; it’s always “1 to 2, 2 to 3, 3 to 1.”