Partial Permutations

A permutation is generally defined as a bijection on a non-empty set.

Given a permutation on a set W, a partial permutation is a bijection from one subset W_X of W to another subset W_Y of W.  W_X and W_Y are the domain and range, respectively, of the partial permutation.  Because a partial permutation is a bijection, W_X and W_Y must contain the same number of elements (or must be of the same cardinality, if they are infinite).  Note that a partial permutation is defined only in the context of a specific and previously defined permutation.  Generally speaking, a partial permutation is not a permutation, and indeed a partial permutation is a permutation only if its domain and range are the same set.

I haven't seen the following definition given in a book, but it will prove useful to speak of a partial permutation whose domain and range consist of a single element each (not necessarily the same element, of course).  We will call such a partial permutation a unitary partial permutation.  A permutation clearly consists of the union of all its unitary partial permutations.

Both permutations and partial permutations are just special kinds of functions.  Some authors allow the domain and range of a function to be empty, and many do not.  It will prove useful for our purposes here to allow a partial permutation to be null.  That is, we will allow the both the domain W_X of a partial permutation and the range W_Y of a partial permutation to be null.

Most group theory books define two notations for finite permutations.  The most commonly used notation for a permutation is the cycle notation.  For example, x=(1,5,4) means x: 1->5, 5->4, 4->1.  This notation typically results in multiple names for the same permutation.  For example, (1,5,4), (5,4,1), and (4,1,5) are three different names for the same permutation.  It seems to me that the cycle notation is very vague about the numbers that aren't listed.  That is, does the permutation (1,5,4) fix 2 and 3, or are 2 and 3 missing from the permutation?  For that matter, what about 6, 7, 8, etc.?  However, the trouble with complaining about the vagueness is that the vagueness is very useful.

The second notation that is typically used is more or less a two row "matrix", enclosed in large parentheses.  Some authors seem to separate the columns of the "matrix" with commas, and other authors seem to separate the columns of the "matrix" with blanks.  We will use blanks, and we will simulate the large parentheses of proper mathematical typography with two smaller parentheses.  For example, we could write the cycle (1,5,4) as

(1 2 3 4 5)
(5 2 3 1 4)

The first row is the domain of the permutation, the second row is the range of the permutation, and each element of the first row is mapped to the element immediately below it in the second row.  I have chosen to treat the permutation as fixing elements 2 and 3, and to treat the permutation as not acting on elements greater than 5.  Thus, there is no vagueness.  However, the cycle structure of the permutation is not as apparent as it is in cycle notation.

It will prove useful to define a one row version of the latter notation.  If we assume that the first row always consist of natural numbers increasing one at a time, no generality is lost by writing only the second row thusly:

(5 2 3 1 4)

Some variation on the one row notation is how permutations are usually stored in a computer program.

It has been suggested to me that I might be better served by writing the one row notation with square brackets and commas thusly:

[5,2,3,1,4]

However, I am going to use the one row notation for partial permutations thusly:

(* * * 1 4)

This partial permutation means 4->1 and 5->4, nothing more nothing less.  The values to which 1, 2, and 3 are mapped are undefined rather than being unspecified.  That is, the values to which 1, 2, and 3 are mapped in this example are completely undefined.  With square brackets and commas, the same partial permutation would be written as

[,,,1,4]

I have rather strong dislike for counting commas, so I prefer the notation with the asterisks.  I suppose that one could argue that counting asterisks is just as bad as counting commas.  But I would rather deal with (* * * * * * * 3) than to deal with [,,,,,,,3].

Given the above conventions, the null partial permutation on five elements would be written thusly:

(* * * * *)

I will be presenting some applications of partial permutations to Rubik's cube in some follow up messages, but I wanted first to define some terms and to introduce some notational conventions.