The symmetric group, 13

In my post on the Novi Sad Algebraic Conference, I described how the symmetric group on a set X is “contained” in the full transformation semigroup on X, which is itself contained in the clone of functions on X. In this post, I want to describe a different “enlargement” of the symmetric group. I will concentrate on the finite case, but much of this (though not the representation theory) works for infinite symmetric groups too.

I learned about partition monoids from a talk by James East at the NSAC; he also mentioned Brauer monoids. The following week I heard a very nice talk by Anton Cox in the London Algebra Colloquium about Brauer algebras and their representation theory. This synchronicity convinced me that I wanted to understand this better; and how better to understand than to write about it? Because this is all rather new to me, it may be even more unreliable than usual!

The symmetric group via diagrams

We take the set X to be {1,2,…,n}, and the objects we consider are diagrams drawn in a 2×n rectangle, whose rows are labelled “top” and “bottom” and whose columns are numbered by the elements of X.

A permutation can be represented as a diagram which has n “edges”, each edge joining a point in column i in the top row with the point in the image column in the bottom row.

Permutations are composed by writing the diagram of the second underneath the diagram for the first, identifying the points in the top row of the second with the corresponding points in the bottom row of the first, and then suppressing these points.

The figure below shows two permutations in the symmetric group of degree 6 (in cycle form, (1)(2,4,5,3)(6) and (1,2)(3,4)(5,6)) and their composition (1,2,3)(4,6,5).

Composition in the symmetric group
Composition in the symmetric group

We are going to interpret such a diagram, not as a graph, but as a partition of the set of 2n vertices into n parts of size 2, with the restriction that each part contains one vertex from the top row and one vertex from the bottom row.

The Brauer monoid

The Brauer algebra was first defined by Richard Brauer. The background was the work of Schur and Weyl, who established a duality between representations of symmetric groups and general linear groups, which enabled information about the representations of the latter to be deduced from information about the former. (Acting on a tensor power of the natural module for the general linear groups, the two groups are each other’s centralisers.) Brauer wished to construct something to take the place of the symmetric group in order to investigate similarly the representations of other classical groups.

I will begin with the Brauer monoid. The elements of this are diagrams, rather like those for permutations. Again, a diagram is a set of 2n points arranged in a 2×n rectangle, and partitioned into n sets of size 2, but this time without the restriction that each part has one point in each row; all possible partitions are allowed. The number of such partitions is the number usually written (2n−1)!!, the product of the odd numbers from 1 to 2n−1.

Composition is done in the same way as before. To compose two diagrams, place the second under the first, identify the top row of the second with the bottom row of the first, and then suppress the vertices in the second row. Now, however, there can be loops involving only vertices in the suppressed row; we delete these loops. Another such diagram is obtained, as the picture shows.

Composition in the Brauer monoid
Composition in the Brauer monoid

It is readily checked that we do indeed obtain a monoid (an associative structure with the identity permutation as its identity element) containing the symmetric group.

The Brauer algebra

The Brauer algebra over a field K has as basis the diagrams just described. It also depends on a parameter δ, which can be any element of the field. Composition is as above but with a twist. In the last stage of the composition, we delete loops using the suppressed vertices. For each such loop, we multiply the resulting diagram by a factor δ.

The group algebra of the symmetric group over K is a subalgebra. It is also a quotient algebra, by the ideal given by the diagram shown below.

Generator of an ideal
Generator of an ideal

In his talk, Anton showed how the representations of the Brauer algebra can be built up from those of the symmetric groups of degrees n, n−2, n−4, …

The symmetric inverse semigroup

As a warm-up to the partition monoid, I will describe the symmetric inverse semigroup, and how to enlarge the Brauer monoid to embed it.

The elements of the symmetric inverse semigroup on a set X are the partial bijections on X, that is, bijections f:YZ, where Y and Z are subsets of X. Such maps are composed in the natural way. If f:YZ and g:UV, then the composition fg is defined on the points of Y whose image under f happens to lie in U, so that g can be applied to it.

Such an element can be represented by a diagram corresponding to a partition with parts of sizes 1 and 2, such that any part of size 2 contains one point from the top row and one point from the bottom row, as shown.

Composition in the symmetric inverse semigroup
Composition in the symmetric inverse semigroup

Note that a twig which does not reach from top to bottom loses its “growing tip” when the points in the middle row are suppressed, and withers away to a point.

To produce a common enlargement of the Brauer monoid and the symmetric inverse semigroup, it is now clear what we have to do: we take all partitions of the set of 2n points into subsets of size 1 and 2. Then composition works as usual, and the resulting monoid contains both the Brauer monoid (consisting of diagrams with no parts of size 1) and the symmetric inverse semigroup (consisting of diagrams in which all parts of length 2 contain a point from the top and one from the bottom).

The partition monoid

Now, if I have understood things correctly, the definition of the partition monoid is clear. Its elements are diagrams representing arbitrary partitions of the set of 2n points. Composition is done in the usual way.

There is one complication. Each diagram can be regarded as a graph, which is a
disjoint union of complete graphs. When we put two diagrams together to compose them, we can add edges from top to bottom if there is a middle vertex joined to both. Then suppressing the vertices gives us a graph which is no longer necessarily a disjoint union of complete graphs; we have to take its connected components as giving the composite partition. Here is an example.

Composition in the partition monoid
Composition in the partition monoid

The full transformation semigroup

The partition monoid, as described above, also embeds the full transformation semigroup on the set X. This is the semigroup whose elements are all maps from X to itself, with the operation of composition.

To define the embedding, we identify the function f with the partition each of whose parts consists of a point of X in the bottom row and all of its preimages in the top row. It is easy to check that our definition of composition of diagrams agrees with composition of maps.

The diagram in the last section actually shows composition in the transformation semigroup.

I don’t know anything about partition monoids, so this seems like a good place to stop.



About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , , , , . Bookmark the permalink.

2 Responses to The symmetric group, 13

  1. We obtain presentations for the Brauer monoid, the partial analogue of the Brauer monoid, and for the greatest factorizable inverse submonoid of the dual symmetric inverse monoid. In all three cases we apply the same approach, based on the realization of all these monoids as Brauer-type monoids.

  2. Des FitzGerald says:

    Hi Peter and readers,
    Just one of the really interesting things about the partition monoid is that it is dual to the monoid of binary relations, in the following sense. A binary relation on the set X is a subset of the product X \times X; a partition is a quotient set of the coproduct (disjoint union) X \plus X . Moreover, if you draw category-type diagrams you can see that there is a diagrammatic way of constructing the composite of two binary relations within the category of sets and mappings. If you then do the corresponding process in the category dual to the category of sets, i.e., reversing arrows, and turning monos into epis, then you get exactly the product of partitions.

    Incidentally, James Mitchell’s forthcoming implementation of this monoid in the Semigroups package in the GAP software chooses to refer to these partitions of a 2n-set as _bipartitions_, and this is actually a better term: it echoes the binary relation name, and distinguishes them from partitions of the underlying n-set, which also figure in the whole story.

    Both of the monoids named above have a lot of extra structure. For example, both have an inclusion order compatible with the multiplication; essentially because of the categorical duality, there is also a Galois connection between the posets. As a semigroup, each also has a “natural” partial order derived from the multiplication, and these natural p.o.s are “about as independent of the inclusion orders as they can be”.

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 )

Google+ photo

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

Connecting to %s