Tutorial: Working with Permutations - Maple Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Combinatorics : Permutations : Tutorial: Working with Permutations

Working with Permutations

 Permutation groups are the most common form of finite group encountered when working with groups on a computer.  The elements of a permutation group are permutations. By definition, a permutation of a set $X$ is a bijective (that is, one-to-one and onto) mapping from $X$ to itself.  In particular, a permutation is a function. The GroupTheory package allows you to compute with permutations on finite sets of the form $\left\{1,2,n,\left(\right)..\left(\right)\right\}$, for some positive integer $n$.

Creating a Permutation

To create a permutation in Maple, you must specify either an explicit list of the images of the integers in the range 1..n, or the disjoint cycle structure of the permutation. In the first case, you use a list L of the form [a__1, a__2, ..., a__n], where a__i is the image of i under the permutation.

 > p := Perm( [2, 3, 1] );
 ${p}{≔}\left({1}{,}{2}{,}{3}\right)$ (1)

To create a permutation by specifying its disjoint cycle structure, use nested lists in which each sublist represents the corresponding cycle.

 > p := Perm( [[1,3],[2,5,4]] );
 ${p}{≔}\left({1}{,}{3}\right)\left({2}{,}{5}{,}{4}\right)$ (2)

In this earlier example, the sublist [1,3] represents the cycle (transposition) that interchanges the points $1$ and $3$, and the sublist [2,5,4] represents the cycle that takes $2$ to $5$, $5$ to $4$ and $4$ to $2$.

Note that permutations are displayed in disjoint cycle notation. This notation is not available for inputting permutations, however, as it has a different, pre-existing meaning in Maple.

 > (1,2,3)(4,5,6,7)(11,12);
 ${1}{,}{2}{,}{3}$ (3)

The example above evaluates to the expression sequence $1,2,3$ because, in Maple, it represents the application of the sequence of constant operators $1$, $2$ and $3$ to some arguments.

Permutations have type Perm.

 > type( p, 'Perm' );
 ${\mathrm{true}}$ (4)

Many of the commands available for computing with permutations reside in the GroupTheory package, and the following command can be used to access them.

 > with( GroupTheory ):

The Action of a Permutation

To apply a permutation p to a point i, you use the "indexed" notation p[i].  For example,

 > p := Perm( [[1,2],[3,4,5]] );
 ${p}{≔}\left({1}{,}{2}\right)\left({3}{,}{4}{,}{5}\right)$ (5)
 > p[ 3 ];
 ${4}$ (6)

Note: Despite the notation, permutations act on the 'right'. This is important to understand when multiplying (or composing) permutations.

You can also use the PermApply command to compute the image of a point, or to map a permutation onto a set or list of points.

 > PermApply( p, 3 );
 ${4}$ (7)
 > map2( PermApply, p, [ 1, 3, 5 ] );
 $\left[{2}{,}{4}{,}{3}\right]$ (8)

The more common exponential notation ${\mathrm{\alpha }}^{p}$ for the image of $\mathrm{\alpha }$ under a permutation $p$ is also available, but must be used with care due to automatic simplification.

 > p := Perm([[1,4,7]]);
 ${p}{≔}\left({1}{,}{4}{,}{7}\right)$ (9)

These examples work as expected:

 > 5^p;
 ${5}$ (10)
 > 7^p;
 ${1}$ (11)

However, automatic simplification results in an incorrect result in this case.

 > 1^p;
 ${1}$ (12)

Note that this applies only for an explicit $1$ in the expression.

 > alpha := 1:
 > alpha^p;
 ${4}$ (13)

The set of points that are actually displaced by a permutation is called the "support" of the permutation. To compute the set of moved points, use the PermSupport command.

 > p := Perm( [[1, 3], [4,6,7]] );
 ${p}{≔}\left({1}{,}{3}\right)\left({4}{,}{6}{,}{7}\right)$ (14)
 > PermSupport( p );
 $\left\{{1}{,}{3}{,}{4}{,}{6}{,}{7}\right\}$ (15)

The largest point moved by a permutation is called the "degree" of the permutation, you can compute it by using the PermDegree command.

 > PermDegree( p );
 ${7}$ (16)

The smallest point displaced by a permutation p is returned by the PermMinSupport command.

 > PermMinSupport( p );
 ${1}$ (17)

The PermFixed command returns the set of those points less or equal to the degree of a permutation that are fixed by it.

 > PermFixed( p );
 $\left\{{2}{,}{5}\right\}$ (18)

Permutation Arithmetic

The noncommutative multiplication operator . is used to multiply (or compose) two permutations.

 > a := Perm( [[1,2]] ); b := Perm( [[2,3,4]] );
 ${a}{≔}\left({1}{,}{2}\right)$
 ${b}{≔}\left({2}{,}{3}{,}{4}\right)$ (19)
 > a . b;
 $\left({1}{,}{3}{,}{4}{,}{2}\right)$ (20)
 > b . a;
 $\left({1}{,}{2}{,}{3}{,}{4}\right)$ (21)

Observe that $a·b$ and $b·a$ are different permutations; that is, multiplication of permutation is, in general, 'not' commutative.

You can compute a power ${a}^{n}$, for an integer $n$, of a permutation $a$, by using the ^ operator.

 > a^37;
 $\left({1}{,}{2}\right)$ (22)
 > b^(-2);
 $\left({2}{,}{3}{,}{4}\right)$ (23)

In particular, you can compute the inverse of a permutation as a power with $-1$.

 > b^(-1);
 $\left({2}{,}{4}{,}{3}\right)$ (24)

You can also compute the inverse of a permutation by using the PermInverse command.

 > PermInverse( b );
 $\left({2}{,}{4}{,}{3}\right)$ (25)

Note that computing powers of a permutation is efficient for large powers.

 > b^(7^(7^7));
 $\left({2}{,}{3}{,}{4}\right)$ (26)

Alternatively, you can use the PermPower command.

 > PermPower( a, 5 );
 $\left({1}{,}{2}\right)$ (27)

The smallest positive integer $n$ for which ${a}^{n}$ is the identity permutation is called the "order" of the permutation $a$.  The PermOrder command computes the order of a permutation.

 > PermOrder( b );
 ${3}$ (28)
 > PermOrder( a );
 ${2}$ (29)

To compute the conjugate ${a}^{b}$ of a permutation $a$ by a permutation $b$, you can use either exponential notation, or the PermConjugate command.

 > a^b;
 $\left({1}{,}{3}\right)$ (30)
 > PermConjugate( a, b );
 $\left({1}{,}{3}\right)$ (31)

The commutator $\frac{1}{a}·\frac{1}{b}·a·b$ of two permutations $a$ and $b$ is computed by the PermCommutator command.

 > PermCommutator( a, b );
 $\left({1}{,}{2}{,}{3}\right)$ (32)

Other Operations on Permutations

Every permutation $p$ can be written as a product of transpositions. There are infinitely many such products for any given permutation, but the number of transpositions in such a product is either always even or always odd. The "parity" of $p$ is defined to be $1$ if $p$ can be written as a product of an even number of transpositions, and is defined to be $-1$ otherwise. This defines a homomorphism from the symmetric group ${S}_{n}$ to the multiplicative group $\left\{-1,1\right\}$. The PermParity command computes this homomorphism.

 > PermParity( a );
 ${-1}$ (33)
 > PermParity( b );
 ${1}$ (34)

Every permutation can be written, in an essentially unique way, as a product of disjoint cycles. The multi-set of lengths of these cycles is called the "cycle type" of the permutation, and the PermCycleType command computes the cycle type as a list of the form $\left[{c}_{1},{c}_{2},..,{c}_{k}\right]$, where the lengths of the cycles in a disjoint cycle decomposition of the permutation are listed in non-decreasing order. Thus, a cycle type of $\left[2,2,3,5,5\right]$ indicates a permutation that is a product of two transpositions, one $3$-cycle and two $5$-cycles.

 > b;
 $\left({2}{,}{3}{,}{4}\right)$ (35)
 > PermCycleType( b );
 $\left[{3}\right]$ (36)
 > PermCycleType( Perm([[1,2],[3,4,5],[6,7,8],[9,10],[11,12,13,14,15]] ) );
 $\left[{2}{,}{2}{,}{3}{,}{3}{,}{5}\right]$ (37)

Use the PermRandom command to generate a pseudo-random permutation of (at most) a given degree.

 > PermRandom( 10 );
 $\left({1}{,}{3}{,}{9}{,}{4}{,}{5}\right)\left({2}{,}{8}{,}{10}{,}{6}{,}{7}\right)$ (38)
 > PermRandom( 10 );
 $\left({1}{,}{6}\right)\left({2}{,}{7}{,}{5}{,}{10}{,}{8}{,}{9}{,}{3}\right)$ (39)
 Compatibility The Working with Permutations tutorial was introduced in Maple 2015. For more information on Maple 2015 changes, see Updates in Maple 2015.