Formula of Spies vs Formula of Glynn

Introduction

While doing research for my book A Bit of Math, The Art of Problem Solving, I stumbled upon a Wikipedia article: Computing the permanent.

I came across the Balasubramanian–Bax–Franklin–Glynn formula. But wait a minute — isn't this my very own formula from 2003? It looks almost the same! It’s essentially the same!

At the end of 2002, early 2003 I solved Problem 29 of the NAW (see my Math Page). The solution involved the permanent of a square (0,1)-matrix. For practical calculations, I needed a fast algorithm. Ryser’s algorithm was one possibility, but I found a formula that was at least as fast. The derivation was simple, almost elementary.

I implemented my alternative in a C/C++ program, which was used to contribute to Neil Sloane's On-line Encyclopedia of Integer Sequences (OEIS). See for instance A087982, A088672 and A089476. Some of the records still stand! Maybe I should give it another try with today’s knowledge and computing power.

A short history from e-mails

Emails exchanged with Robbert Fokkink, Bruno Codenotti, Richard Brualdi, The American Mathematical Monthly, Neil Sloane and Edwin Clarke.

A compilation of the messages in text format: here.

In an email dated February 11th, 2003, I showed my results to Robbert Fokkink, who was then the editor of the Problem Section of the NAW — as a conjecture. Robbert confirmed the correctness with a sketch of a proof. Meanwhile, I had written a short note with a complete proof. How 'new' was the formula? Robbert suggested contacting an expert.

My message to Bruno Codenotti was met with the suggestion to go straight to the master of permanents: Richard Brualdi. I owned a copy of his book Brualdi, Ryser: Combinatorial Matrix Theory. It contains a chapter on permanents and had been the source of my solution to Problem 29. Brualdi and Ryser changed my life.

Richard Brualdi wrote: 'Your formula is interesting, and I cannot recall seeing it before, but maybe it appears buried in some paper or other.' In a follow-up message, he suggested sending the result as a note to the American Mathematical Monthly.

With this recommendation, I submitted my note to the AMM on October 7th, 2003. I received an email notifying me that it had been forwarded to Professor William Adkins for refereeing. The review process could take several months, and I would hear from Dr. Adkins at Louisiana State University. But nothing came of it! After more than a year, I asked: "What happened to my note? Was it too lightweight? Did it blow away with the wind or what? I do have a version in a more substantial, classic definition/theorem style." I also mentioned my C++ implementation, which was faster than an optimized Ryser’s code.

From October 2003 onward, I put my program to work calculating sequences related to permanents. See my discussions with Neil Sloane and Edwin Clarke on the topic. From Edwin Clarke: "Thanks for the copy of your note on permanents. It's an interesting approach. It might be a good idea to write it up as a new algorithm and compare it to known ones. It looks like the time is about 2ⁿ, which is certainly better than brute-force n!."

In the years that followed, I wrote a few things up in an article for the Nieuw Archief voor Wiskunde 5/7 nr. 4 December, 2006: Dancing School problems, Permanent solutions of Problem 29. A preprint can be found here. The article in print here. In a sidenote there is my formula for the permanent of a square matrix. See also the sidenote on The Van der Waerden Conjecture!

More recent developments

As I mentioned in the Introduction, I found Glynn’s formula. I was flabbergasted (I like that word!). I wrote an email to my lifeline in mathematics, Robbert Fokkink. Robbert suggested contacting David Glynn in Adelaide. And yes, David replied after reading my long message.

A compilation of the messages in text format: here.

I quote: "It looks like you could be added to an increasing list of people that have rediscovered this formula for the permanent. (But the first I think was Balasubramanian in his PhD thesis in India.) My 2013 paper indeed shows that there are very many different formulae that are related via an algebraic structure called the Veronesean. Maybe I can get someone to put a reference to your articles around 2003-2006 or others on the wikipedia website so that it can be noted there. If you have trouble obtaining my reprints you could look at the researchgate site below where many of my papers can be downloaded."

Once again, someone suggested I write a short note for The American Mathematical Monthly. And once again, I did. If I may say so, it was a very readable manuscript — with an emphasis on the elementary approach, some history of the permanent, and an educational tone. This time, the rejection came almost immediately.

The motivation: “In 2010, Glynn published ‘The permanent of a square matrix,’ a five-page note in The European Journal of Combinatorics that offered four different formulas for the matrix permanent. Now comes this manuscript, which offers an elementary proof of the first of these. The Monthly does publish new, elementary, proofs of old results, but only if the old results are famous, and/or the new proofs are beautiful and insightful. Unfortunately, neither of these applies here; on the contrary, Glynn’s proof was more insightful. Consequently, we must decline your submission for publication.”

I wrote to David Glynn: "So you win 4–1! And your proof was more 'insightful'. But imagine you’re teaching a first-year graph theory class, and you come to the permanent. Which method would you choose to give insight into its calculation? Do you prefer the 'insightful' one — connected with invariant theory via the polarization identity for a symmetric tensor?"

David Glynn’s first email was also his last. All my follow-up messages disappeared into a black hole.

What next?

My programming skills are a little rusty, but I managed to implement both Glynn’s formula and my own in Sage. SAGE — now SageMath — was started in 2005 by William Stein. I discovered it at the end of 2005 and became an early adopter. In 2006 and beyond, I contributed quite a bit of code and more. Sage is like Python+, easy to learn and use. SageMath aims to be an open-source alternative to the big M’s: Magma, Mathematica, Maple, and Matlab. It integrates a wide range of other mathematical software. SageMath is a free, open-source mathematics system. SageMath is a free open-source mathematics software system.

SageMath offers various options for calculating the permanent of matrices over a field. Guess who implemented Ryser's algorithm? In the demo worksheet we calculate the permanent of the example in Glynn's 2010 article. Note the differences: in Glynn's formula you see row sums in the iterations; in mine, column sums. This difference stems from the use of right or left multiplication in matrix theory. The result, of course, is the same: the sum of all diagonal products!

I did some timings too - see here. The default implementation wins of course, because it is written in Cython. Cython is an optimising compiler for Python code.

Important note: The permanent fuction in SageMath accepts rectangular matrices! The formula of Spies (and that of Glynn) works only for square matrices.

And now?

In the NAW 5/21 nr. 1 March 2020 there is an article "A formula for the permanent".

On the Dutch Wikipedia page on Permanents we now see the formula of Spies.

I still hope there will be an addition to the English version of the Wikipedia page! Volonteers?