22-02-18 15:32 To Robbert Fokkink Beste Robbert, Lang geleden, aan het begin van de eeuw, hadden we regelmatig contact. Je was toen redacteur van de Problemen Rubriek van het NAW. Problem 26 hield mij toen van de straat. Uiteindelijk vond ik 8 verschillende bewijzen. Toen werd ik door jou uitgedaagd om Problem 29 aan te pakken. Januari 2003 vond ik een oplossing in termen van de permanent van een (0,1)matrix. In die zelfde tijd vond ik een alternatief voor het bekende Ryser-algoritme. We hebben daarover nog gecorrespondeerd. Ik was zeer onzeker en kon eigenlijk niet geloven dat ik als non-professional zoiets had uitgedacht. Je bevestigde toen dat mijn stelling ok was. Ik heb in die periode ook anderen geraadpleegd. Bruno Codinotti: > Hi: > > I do not know well the literature on general permanents. I have always worked on some special permanents. Your algorithm however seems simple and correct. > > Maybe you could write to Professor Brualdi in Wisconsin asking if there could be > some interest in an alternative to Ryser's algorithm and you could also send > your algorithm to him for a better opinion. > > Bruno Codenotti en Professor Brualdi 13-05-03: > Your formula is interesting and I cannot recall seeing it before, > but maybe it appears buried in some paper or other. ... > Thanks for showing it to me. > > Best wishes > > Richard Brualdi en op 13-05-03 later: > I don't think it would be accepted for publication in a research > journal. I can think of two possibilities: > > 1. submit as a short note to the Amer. Math. Monthly > > 2. submit as a problem with solution to the Monthly. > > for references you can find a chapter on permanents in my book > > Combinatorial Matrix Theory (with H.J. Ryser), Cambridge > > and a whole book on permanents > > Permanents by H. Minc, Cambridge. > > Best wishes > > Richard Beide genoemde boeken had ik al in mijn bezit. Vooral CMT heeft mijn leven verregaand beïnvloed! Mijn algoritme is niet gepubliceerd in de AMM, maar wel in het NAW: http://www.nieuwarchief.nl/serie5/pdf/naw5-2006-07-4-283.pdf in een sidebox weliswaar, maar toch. En op mijn website: http://www.jaapspies.nl staat en stond een implementatie in de programmeertaal C, gebruikt voor verschillende bijdragen aan de OEIS. Waar moet dat heen? Hoor ik je vragen. Ik ben bezig met een boekje, een persoonlijk project over mijn ervaringen met het probleemoplossen in het bijzonder met betrekking tot het NAW. Ik stuur je een tussenresultaat en te zijner tijd een gedrukt exemplaar. Het gaat om hoofdstuk 33. Ben ik best nog wel een beetje trots op. Als je zo'n boekje aan het samenstellen bent, kom je weer allerlei dingen tegen, bijvoorbeeld maandag j.l.: https://nl.wikipedia.org/wiki/Permanent_%28wiskunde%29 Even naar beneden scrollen naar de formule van Glynn, gepubliceerd in 2010 in het EJC (zie andere bijlage). Een beetje handiger opgeschreven, want een professionele wiskundige, maar het is in essentie "mijn algoritme"! Ik was geschokt en https://en.wikipedia.org/wiki/Computing_the_permanent maakte het niet beter. Kan gebeuren dat iets min of meer gelijktijdig wordt ontdekt en gepubliceerd, maar een verschil van 4-7 jaar is wel groot. Grappig dat jij nu weer met Jan van Neerven een redactie voert. Dit keer de hoofdredactie van het NAW. Mag ik jullie dit verhaal voorleggen. Wat te doen? Met vriendelijke groet, Jaap Spies 23-02-18 09:07 From Robbert Fokkink Beste Jaap, Leuk om weer van je te horen na al die tijd en leuk om te zien dat je nog steeds bezig bent met permanenten. Dat zit ook wel opgesloten in de naam. Dank voor de eerste versie van het boek, dat ziet er goed uit. Als het klaar is kan het worden opgenomen in de NAW boekbesprekingen. Dat lijkt me de goede plaats. Ik denk dat de oplossing van de wiskundige uit Adelaide onafhankelijk is bedacht. Verschillende mensen komen wel meer op dezelfde ideeen. Heb je contact opgenomen met David Glynn? Ik denk dat hij het leuk vindt om te horen dat iemand anders ook op het idee is gekomen. Wel jammer dat Brualdi de publicatie ontmoedigde. Hij had best wat aanmoedigender mogen zijn. Hartelijke groeten, Robbert 08-03-18 14:06 From Robbert Fokkink Beste Jaap, Aan naamgenoten heb je ook niets. De twee Japen hebben zitten slapen. Lex Schrijver heb ik verschillende malen iets horen zeggen over permanenten. Bijvoorbeeld dat het zo goed is dat er zuivere wiskundigen zijn, zoals Marc Voorhoeve, die opeens met een geniale methode aankomen om permanenten te berekenen. Misschien moet je contact opnemen met Lex Schrijver. Hartelijke groeten, Robbert 08-03-18 14:42 To Robber Fokkink Beste Robbert, Marc Voorhoeve? Straks even opzoeken. Je hebt Lex Schrijvers al eens eerder genoemd bij het oplossen van probleem 26, lang geleden. Ga ik doen. Intussen de wikipedia pagina bescheiden aangepast. https://nl.wikipedia.org/wiki/Permanent_(wiskunde) Met hartelijke groet, Jaap 08-03-18 21:53 To David Glynn Dear professor David Glynn, May I introduce myself. Born in 1944, educated as a mathematician (I have a degree in pure mathematics and the foundation of mathematics) but never practised as a professional mathematician. I was teacher and a college lecturer. At the end of my career I became interested in problem solving. More about me you can find on my website: http://www.jaapspies.nl I'm writing a book about my activities around Problem Solving especially concerning Problems from the Nieuw Archief voor Wiskunde (NAW) a journal of the Dutch Mathematical Society (KNWG). For a history see: http://www.jaapspies.nl/mathfiles/problems.html Problem 26 grabbed me and I found several solutions. Challenged by the editor of the Problem Section Robbert Fokkink (now editor in chief of the NAW) I started to look at Problem 29. http://www.nieuwarchief.nl/serie5/pdf/naw5-2002-03-4-375.pdf In January 2003 I found a solution in terms of the permanent of a (0,1)-matrix. See attachment. I needed an algorithm to calculate the permanent of square matrices. So I programmed one and an other one. I was lucky to have a copy of Brualdi & Ryser: Combinatorial Matrix Theory and eventually I implemented Ryser's Algorithm for an mxn-matrix in the programming language C/C++ and in Python. But thinking, playing and counting I found an other algorithm, see attachment. I implemented it in http://www.jaapspies.nl/mathfiles/problem29.c In the beginning I was unsure, so I asked experts for advise: Bruno Codinotti: > Hi: > > I do not know well the literature on general permanents. I have always worked on some special permanents. Your algorithm however seems simple and correct. > > Maybe you could write to Professor Brualdi in Wisconsin asking if there could be > some interest in an alternative to Ryser's algorithm and you could also send > your algorithm to him for a better opinion. > > Bruno Codenotti and than the famous Professor Brualdi 13-05-03: > Your formula is interesting and I cannot recall seeing it before, > but maybe it appears buried in some paper or other. ... > Thanks for showing it to me. > > Best wishes > > Richard Brualdi and on 13-05-03 later that day: > I don't think it would be accepted for publication in a research > journal. I can think of two possibilities: > > 1. submit as a short note to the Amer. Math. Monthly > > 2. submit as a problem with solution to the Monthly. > > for references you can find a chapter on permanents in my book > > Combinatorial Matrix Theory (with H.J. Ryser), Cambridge > > and a whole book on permanents > > Permanents by H. Minc, Cambridge. > > Best wishes > > Richard I didn't try the AMM, but some time later my solution of Problem 29 and the algorithm got published in the NAW: http://www.nieuwarchief.nl/serie5/pdf/naw5-2006-07-4-283.pdf In 2006 I started to do some work for SAGE, now called SageMath, see: http://www.sagemath.org I contributed permanent related stuff and more. At Sage Days 6, November 10-14, 2007 in Bristol I worked on an idea to compute the permanent in a boolean setting. I opened a ticket https://trac.sagemath.org/ticket/933 At that time I returned to my implementation of my algorithm and noticed that I should use symmetry! It could be done almost twice as fast and timing confirmed that. In my program I fixed x[n] = 1. > int per(int n, int *M) > { > int i, j, sum; > int *x; > > > // this algorthm generates all n-tuples with entries 0 and 1 > // it is based on the algorithm M from Knuth's taocp part 4: 7.2.1.1 > // to be publiced (See his homepage). > // However we need entries -1 and 1. we do the processing in Q(M, n, x) > // See my note for the definition of Q. Modified: we take advantage of > // the symmetry by putting x[n] = 1. Division is by 2**(n-1) > > // M1. Initialize > x = (int *) calloc((n+1),sizeof(int)); > sum = 0; > j = n; > // We always let x[n] = 1, symmetry! > // Start the count down at j = n-1 > // So we do half of the calculations. > x[n] = 1; > while(j > 0) > { > // M2. Visit > sum += Q(M, n, x); > // M3. Prepare to add 1 > j = n-1; > // M4. Carry if necessary > while( *(x+j) == 1) > { > *(x+j) = 0; > j--; > } > // M5. Increase, unless done > *(x+j) += 1; > } > // final division by 2^(n-1) see modified theorem 1 > return (sum >> (n-1)); > } > Ten years later doing some research for my book I stumbled on the 'formula of Glynn' and your article in the EJC! https://en.wikipedia.org/wiki/Computing_the_permanent Much to my surprise I saw the similarity. Your presentation is much more clever, but essentially the results are the same. Your 2013 article looks very interesting https://link.springer.com/article/10.1007%2Fs10623-012-9618-1 but paying 42.29 Euro just for reading it, is too much for me. Best regards, Jaap Spies 10-03-18 From David Glynn Hi Jaap! 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. Thanks for your message. Regards, David Glynn Mobile: +61 (0)451836213 Flinders Phone: +61 (0)8 82017582 Flinders University of SA, PO Box 2100, Adelaide, SA 5001, Australia 11-03-18 12:07 To Robbert Fokkink Hi Robbert, Die K. Balasubramanian heeft vele naamgenoten (en daar moet je het niet van hebben -)). Maar die chemicus is het vast niet. https://www.genealogy.math.ndsu.nodak.edu/id.php?id=143990 Ik zou die thesis wel eens willen zien, maar kan er niets concreets over vinden. Brualdi kende dit resultaat kennelijk niet. Als David Glynn iemand inzet om die Wikipediapagina aan te passen zou dat heel mooi zijn. Mijn wijzigingen in de Nederlandse wikipedia lijken geaccepteerd te zijn. 'Wikiwerner' heeft de referentie naar de NAW geplaatst en nog wat andere bewerkingen: https://nl.wikipedia.org/wiki/Permanent_(wiskunde) 'Vergelijk met de formule van Glynn' is een uitnodiging voor verdere bewerking. Daar is iemand met gezag voor nodig. Vandaar mijn vraag waar je geen antwoord op gaf. > Ik had je willen vragen of ik onze e-mail wisseling mag gebruiken als > introductie bij Lex Schrijver. Hartelijke groet, Jaap 11-03-18 12:25 Hi David, Thanks for your kind message. I've been searching for the Balasubramanian thesis for a long time. To no prevail. Did you see it? I've got your 2013 paper from Robbert Fokkink. Couldn't say I understand it completely! Looks like a great idea you find someone to edit the wikipedia page! I'm looking forward to see it. Best regards, Jaap 01-05-18 From the AMM Dear Mr. Spies, The PDF for your submission, "Note on the Permanent of a Matrix of order n An elementary approach" is ready for viewing. This is an automatic email sent when your PDF is built. You may have already viewed and approved your PDF while on-line, in which case you do not need to return to view and approve the submission Please go to https://monthly.editorialmanager.com/ to approve your submission. Username: jaapspies@home.nl If you do not already know your password, you can go to www.editorialmanager.com/monthly and click on "send username/ password" to receive a temporary password. You will be prompted to change your password when you first login. Your submission must be approved in order to complete the submission process and send the manuscript to the The American Mathematical Monthly editorial office. Please view the submission before approving it to be certain that your submission remains free of any errors. Thank you for your time and patience. Editorial Office Staff The American Mathematical Monthly https://monthly.editorialmanager.com/ 15-05-18 14:07 From American Mathematical Monthly Ref.: Ms. No. MONTHLY-D-18-00277 Note on the Permanent of a Matrix of order n An elementary approach The American Mathematical Monthly Dear Mr. Spies, I am writing about your paper, "Note on the Permanent of a Matrix of order n An elementary approach," which you submitted to The American Mathematical Monthly. I have reviewed your paper and discussed it with members of the Editorial Board. After careful consideration of your paper and the mix of topics we hope to bring to the Monthly's readers, the Board has decided to reject your manuscript. Here is a summary of the remarks I received on your paper from the Board. “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.” The decision to reject a manuscript is always difficult. The Monthly receives a large number of submissions each year, and we are able to publish only a small fraction of them. We regret that page limitations force us to turn away many fine papers. Thank you for submitting your paper to the Monthly. We wish you luck in finding an appropriate journal for the publication of your work. Yours sincerely, Susan Jane Colley, Ph.D. Editor The American Mathematical Monthly 25-08-18 13:39 To David Glynn Hi David, Maybe you know my manuscript for the AMM is rejected with the following arguments: > “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.” So you win 4-1! And your proof was more 'insightful'. But imagine you have a class first year students, teaching some graph theory and you come to the permanent. Which method would you prefer giving some insight in the calculation of a permanent? You didn't give any reactions on my last messages. I'm very sorry because your first reaction was nice and so promising: > Hi Jaap! > > 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. > > Thanks for your message. > > > Regards, > > > David Glynn Regards, Jaap Spies