Something I didn’t know

I didn’t know this, though probably I should have. Maybe you didn’t know it either.

We work in a semigroup, a system with an operation (called multiplication) satisfying the associative law. A generalised inverse of an element A is an element B satisfying ABA = A. The name comes from the fact that, if there is an identity element I, then an inverse of A (an element B satisfying AB = I) is a generalised inverse.

If a generalised inverse B of A exists, then we may assume that A is also a generalised inverse of B, that is, BAB = B. To see this, put C = BAB. Then

  • ACA = ABABA = ABA = A,
  • CAC = BABABAB = BABAB = BAB = C.

So C is also a generalised inverse of A and has the required property.

Now we come to the bit that I didn’t know. Let us consider matrices, over an arbitrary field. The following two theorems hold:

Theorem 1 Every matrix has a generalised inverse.

For let A be a matrix. Choose vectors v1,…,vr spanning the image of A, and let w1,…,wr be preimages of v1,…,vr. Choose B mapping vi to wi for i = 1,…,r. Then ABA = A.

Theorem 2 For a matrix A, the following are equivalent:

  1. A has a generalised inverse which commutes with A;
  2. A has a generalised inverse which is a polynomial in A;
  3. 0 is not a repeated root of the minimal polynomial of A.

Here is the proof.

2 implies 1: Clear.

3 implies 2: Suppose that 0 is not a repeated root of the minimal polynomial of A. Then there is a polynomial f with zero constant term and non-zero coefficient of x which is satisfied by A. (If 0 is a root of the minimal polynomial, use this; otherwise use the minimal polynomial multiplied by x.) After multiplying by a non-zero scalar we can write f(x) = xx2h(x). Then h(A) is a generalised inverse of A.

1 implies 3: Suppose that ABA = A and AB = BA. Then BA2 = A. But, if 0 is a repeated root of the minimal polynomial of A, then there is a vector v which is mapped to 0 by A2 but not by A, and applying the above equation to v gives a contradiction.

Corollary If a matrix A is diagonalisable, then it has a generalised inverse which is a polynomial in A. In particular, this holds for real symmetric matrices.

Posted in exposition | Tagged , , , , | 4 Comments

The Wall conjecture extended

Tim Wall boldly conjectured in 1961 that the number of maximal subgroups of a finite group G is at most |G|−1. (This would be best possible, since the the elementary abelian 2-group attains this bound.) He proved that the conjecture holds if G is soluble. The conjecture itself was disproved by participants in an AIM workshop in 2012, but in the meantime, Martin Liebeck, Laci Pyber and Aner Shalev had proved that the number of maximal subgroups is at most c|G|3/2. (The report of the workshop notes that the counterexamples have order smaller than |G|1+a, where a < 1/1000 (and possibly much smaller).)

The partition into right cosets of a subgroup of a group G is a system of imprimitivity for G in its regular action on itself by right multiplication, and in particular, maximal subgroups correspond to systems of maximal blocks. So, in our work on the Road Closure conjecture (described here), João Araújo and I speculated that the results on Wall’s conjecture might extend to the number of systems of maximal blocks of imprimitivity for all finite transitive permutation groups.

This did indeed turn out to be the case. Mariapia Moscatiello from Padova, who is visiting our department this month, gave a seminar talk on Wednesday, in which she showed that exactly the same bounds (cn3/2 for arbitrary transitive groups of degree n, and n−1 for finite soluble groups) hold for the more general problem. This lovely result is joint work with Andrea Lucchini and Pablo Spiga. Their paper is on the arXiv: 1907.08477.

So one (rather important) question remains. Is there an efficient algorithm to find all the maximal blocks through a point in a transitive permutation group? In particular, can this be done in polynomial time? An efficient algorithm would almost certainly allow us to push further with our computational test of the Road Closure conjecture. In the computation as we have done it so far, we use the fact that all the minimal blocks through a point can be found efficiently, and then climb up to the top of chains of blocks; this is very inefficient since we pass all possible blocks on the way and there may be very many of these!

Posted in exposition | Tagged , , | Leave a comment

A challenge

Let a(n) be defined in the following manner. Write n as an ordered sum of positive integers in all possible ways. (The number of such expressions is 2n−1; showing this is a pleasant exercise, but it is not relevant for what follows.) For each expression, multiply the summands together; then add the resulting products. So, for example,

3 = 2+1 = 1+2 = 1+1+1,

so

a(3) = 3+2.1+1.2+1.1.1 = 8.

Now the values a(1) = 1, a(2) = 3, a(3) = 8, … are alternate Fibonacci numbers.

This is an exercise, not a research problem. Try it for yourself before reading on. [According to Donald Knuth, Richard Bellman included a section called “Exercises and Research Problems” at the end of some chapters of his book Dynamic Programming. When asked how you tell the difference, he replied, “If you can solve it, it is an exercise; otherwise it’s a research problem.”]

I give a proof below, using formal power series. The challenge is to find a more direct proof. This would preferably consist of matching up the values with some known description of Fibonacci numbers (such as the number of binary sequences of length n without consecutive ones, or of expressions for n as a sum of ones and twos). Failing that, proving directly that the numbers a(n) satisfy the same recurrence relation as the alternate Fibonacci numbers (see below).

Here is the proof. It uses an auxiliary power series

F(x) = x+2x2+3x3+…

(the general term is nxn). Using the Binomial Theorem, or by any of various direct arguments, show that F(x) = x/(1−x)2.

The coefficient of xn in F(x) is n, which corresponds to our prescription for a(n) but with just one term in the sum.

Now the coefficient of xn in F(x)2 is the sum of all products kl, where k and l are positive integers summing to n; in other words, our prescription for a(n) but with just two terms in the sum. Similarly the coefficient of xn in F(x)3 corresponds to taking three terms in the sum, and so on.

So, if A(x) is the generating function for the sequence (a(n)), then we have

A(x) = F(x)+F(x)2+F(x)3+… = F(x)/(1−F(x)).

Substituting in our formula for F(x), we find that

A(x) = x/(1−3x+x2).

This shows that the sequence (a(n)) satisfies the recurrence

a(n) = 3a(n−1)-a(n−2),

which is the same as the recurrence for alternate Fibonacci numbers. Using the initial values, it is now immediate to get the result.

This post is the result of my having set this problem to my students, and then realising that I had forgotten how to do it myself.

Posted in exposition | Tagged , | 10 Comments

Very good news!

Cheryl Praeger has been awarded the Australian Prime Minister’s Prize for Science. Here is an announcement on the ABC website.

Congratulations Cheryl!

And my thanks to Liz for sending me the news.

Posted in Uncategorized | Tagged , | 1 Comment

Ginger Baker

At my age, it very often happens that someone who was part of the background of my younger self dies. Yesterday it was Ginger Baker.

The obituary said more about his extraordinary life and his short temper than his drumming, and quoted him as saying that a drummer was no more than a timekeeper. Yet he was one who could really make music with a drumkit.

There was another side of him which they didn’t touch on at all. You will see this if you listen to his song “East Timor”. A passionate denunciation of the hypocrisy of governments who will sell out a small community for money, it is a song with huge contemporary relevance. And after the vocal section and a very mathematical bridge, his colleagues Charlie Haden and Bill Frisell do a very convincing take-off of Jack Bruce and Eric Clapton. Close your eyes and you could be listening to Cream in their heyday.

Posted in Uncategorized | Tagged , , , | Leave a comment

A puzzle

Loch Leven and West Lomond

Last weekend we walked from Kinross to Falkland.

Kinross is on the shore of Loch Leven (not the sea-loch of the same name on the west coast), which is drained by the River Leven (which flows into the Firth of Forth) and is overlooked by the Lomond Hills.

Just north of Glasgow, the rather more famous Loch Lomond is drained by the River Leven (which flows into the Firth of Clyde) and is overlooked by Ben Lomond.

Now to complicate matters further, my Scottish place-name book suggests that Loch Lomond may have once been Loch Leven (it is documented as Loch Levin in 1535), and that there is some unknown connection between the names Lomond and Leven. It suggests that, most likely, the names were simply confused; Lomond may derive from the British word for “beacon hill”, or possibly from the Gaelic word leamhain for “elm”, which is also thought to be the origin of the river names.

Falkland lies on the slopes of the Lomond Hills in Fife, and is the site of Falkland Palace, a royal palace associated with the Stuarts, especially Mary Queen of Scots, who liked to hunt there. I visited the palace for the first time earlier this month with my sister. There are many portraits of Stuarts there, including Charles I, who prorogued Parliament and lost his head for his pains. His son James VII (or James II, if you are from south of the border) also prorogued Parliament, and was merely exiled, and the throne given to his daughter Mary and her husband. So clearly our treatment of such people is becoming milder: we don’t even lock them up now. When I remarked about Charles to my sister, she suggested enthusiastically that we should get out the block in Whitehall and sharpen the axe. I am not sure I would go quite so far …

Posted in geography, history | Tagged , | 1 Comment

G2D2, 5: The logo revisited

There has been further discussion of the G2 logo; here is a brief summary.

Elena Konstantinova tells me that it was designed by Vava Stefoglo; her portfolio is here. She is not a mathematician but received a good education in mathematics. She designed the logo to look like a faceted diamond.

Misha Klin told us about a survey paper he wrote with Christoph and Gerta Rücker and Gottfried Tinhofer on algebraic combinatorics in mathematical chemistry, published in Match (the journal of mathematical chemistry), volume 40 (1999), 7–138; you can find it here. The particular graph used in the logo (a circulant of order 8) is discussed, along with other circulants of order 8), in Example 8.16 on pages 99–100, but you might have to read quite a bit of the preceding material to see what is going on.

As I noted, it is an example of a Deza graph. It was discussed at previous G2 conferences, by Sergey Goryainov, Stefan Gyurki, Anton Betten and Yinfeng Zhu at G2R2, and by Sergei Lando at G2C2.

Posted in events | Tagged , | Leave a comment