Seen this before?

Last week, Abdullahi Umar, a Nigerian mathematician working in Oman, visited me in London on his way home from a visit to St Andrews. He works in semigroup theory and has obtained some beautiful results on counting the orders, and numbers of nilpotent elements, in some inverse semigroups of partial bijections on a finite set. Among these are the factorials, binomial coefficients, Stirling, Bell, Catalan, Schröder and Lah numbers.

As it happens, I am in the final stages of writing a book which will be a gentle introduction to enumerative combinatorics; many of these sequences of numbers will occur in the book. So, with his permission, I am going to include some of these results in the book.

However, the basic numbers in this game, the total numbers of partial bijections on an n-element set, are somewhat mysterious; there is no known closed formula for these numbers, and they do not agree with any familiar series from any other part of combinatorics.

Here are the details. To count bijections between k-sets, we first choose two k-sets (there are nCk choices for each, so the square of this number of pairs of such sets – I use this notation because I don’t know a simple way to produce the standard notation for binomial coefficients in HTML), and then choose a bijection between them (there are k! bijections); multiply, and then sum over k. The first few numbers in this sequence are 1, 2, 7, 34, 209, 1546, 13327, . . . This is sequence number A002720 in the On-Line Encyclopedia of Integer Sequences, an indispensible resource for this kind of work, maintained by Neil Sloane.

I began to wonder about the existence of a linear analogue of the formula. This would count the number of partial bijections between subspaces of a finite vector space. I soon found a remarkable fact:

The number of linear bijections between subspaces of a finite vector space is equal to the number of linear maps on the space.

If the space is n-dimensional over a field of order q, the number is qn2.

This result certainly does not hold for the case of sets. The numbers of mappings from a set of size n to itself is simply nn; the sequence begins 1, 1, 4, 27, 256, 3125, 46656, . . .

The proof is remarkably simple. We show that the numbers of transformations of each kind of given rank k are equal. We use the preliminary lemma that the number of complements to a k-dimensional subspace of the n-dimensional vector space V is qk(n-k). The crucial fact is that this formula is unchanged when k is replaced by n-k.

Count pairs consisting of a linear bijection T between k-dimensional subspaces, and a linear map S on V extending T. For each T, to extend it we must choose a complement for the domain of T and map it to zero. For each S, we must choose a complement to the (n-k)-dimensional null space of S and restrict S to this subspace. By our above remark, the number of pairs with a given T is equal to the number of pairs with a given S; so the numbers of Ts and Ss are equal.

Now the point of this post is:

Have you seen this result before?

I would be very interested to hear about it if you have!

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in open problems. Bookmark the permalink.

6 Responses to Seen this before?

  1. ahwingsecretagent says:

    That’s quite a nice result! I am afraid I’ve never seen it before though.

  2. Peter Cameron says:

    It just got even better! Yesterday, Nik Ruskuc and I discovered that the same result (that is, the number of endomorphisms equals the number of isomorphisms between substructures) holds in all finite abelian groups. The proof becomes even nicer (as often in mathematics, stripping away inessential details shows more clearly what is really going on).
    Of course, this naturally led us to wonder what other kinds of algebraic structures have this property. We couldn’t find any non-abelian groups that do. Obviously non-abelian simple groups do not!

  3. Nick Krempel says:

    For this theorem to hold in some arbitrary algebraic structure, it seems the basic ingredients are the first isomorphism theorem and the following property:

    * The number of substructures with a given isomorphism type is equal to the number of quotients with that isomorphism type.

    From this, it is straightforward to deduce. I don’t know if this viewpoint is new to you, but it seemed worth mentioning.

  4. Nick Krempel says:

    I should have added:
    The property (*) above holds in f.d. vector spaces due to the duality Hom(_, k) and holds in finite abelian groups due to the duality Hom(_, Q/Z).

  5. Certainly this kind of duality is a sufficient condition. But the real problem is, could the numbers accidentally be equal for some particular structure without any kind of nice duality? Your condition (*) actually only has to happen for structures which are actually embeddable in the given structure. It is not hard to show that a group with this property has to be abelian. But this doesn’t show that we can’t have equally many endomorphisms and partial isomorphisms in some strange non-abelian group, as far as I can see.

  6. Nick Krempel says:

    Indeed. Would such examples have more significance than just a coincidence of numerology? I guess the only way to really know would to be find them or prove they don’t exist…

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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