The Lumber Room

"Consign them to dust and damp by way of preserving them"

Visualizing product of permutations

with 4 comments

A simple pedagogical trick that may come in handy: represent a permutation \sigma using arrows (curved lines) from k to \sigma(k) for each k. Then, the product of two permutations can be represented by just putting the two corresponding figures (sets of arrows) one below the other, and following the arrows.

Representing permutations and products of permutations.

Representing permutations and products of permutations.

The figure is from an article called Symmetries by Alain Connes, found via the Wikipedia article on Morley’s trisector theorem (something entirely unrelated to permutations, but the article covers both of them and more).

I’m thinking how one might write a program to actually draw these: if we decide that the “height” of the figure is some h, then each arrow needs to go from some (k, 0) to (\sigma(k), h) (using here the usual screen convention of x coordinate increasing from left to right, and y coordinate increasing from top to bottom). Further, each curve needs to have vertical slope at its two endpoints, so that successive curves can line up smoothly. The constraint on starting point, ending point, and directions at the endpoints defines almost a quadratic Bezier curve, except that here the two directions are parallel. So it’s somewhere between a quadratic and the (usual) cubic Bezier curve, which is given by the start point, end point, and derivatives at the start and end point. (Here we only care about the direction of the derivative; we can pick some arbitrary magnitude to fix the curve: the larger we pick, the more smooth it will look at the ends, at the cost of smoothness in the interior.)

Even knowing the curve, how do we generate an image?


Written by S

Thu, 2014-03-06 at 23:15:44

4 Responses

Subscribe to comments with RSS.

  1. Are you looking for software / package to do this, or interested in how any such software will draw it internally*?

    For the former, I am sure something like GraphViz supports that. I have done such things in latex using the TikZ library. It allows something like: \draw[->] (a) to [out=270, in=90] (b); where out and in are directions at end points (a) and (b) respectively.

    For the latter, I don’t know :) But, TikZ has a very good documentation, and towards the end it has lot of technical details. There are very few basic constructs, on top of which most of TikZ constructs are defined (see PGF/TikZ).

    (*or neither at this point, since this post is several months old now :) )


    Sat, 2014-06-21 at 20:16:15

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: