An overview in e-mail. The history of an idea.
Early in 2003 I found an algorithm for the calculation of the permanent of a square matrix.
It's derivation was elementary. So simple, I could not imagine to be the first to find it!
in Dutch:
11-02-03 22:08 To Robbert Fokkink
Beste Robbert,
[snipped]
Al weken ben ik op zoek naar een implementatie van een efficient algorithme om de permanent van een matrix te berekenen. Dat valt niet mee. Duizenden pagina's internet, maar geen praktische realisaties. Ik kon bij Elsevier voor fl. 175 een Fortran routine kopen! Mooi niet. Er wordt wel veel gerefereerd aan Ryser's algorithme, maar geen programma's.
Spelend met Maple, een (0,1)-matrix B van orde n, vectorvermenigvuldiging, vermenigvuldigingen van de resultaten, kreeg ik een onverwacht resultaat in de expansie van een veelterm (zie conjecture.tex).
Met wat plussen en minnen (ook letterlijk) met kleine waarden van n kwam ik op formule (3).
Een vermoeden dat tot nu toe steeds wordt bevestigd (zie per.c), maar helaas geen spoor van bewijs!
Helaas heb ik geen toegang tot de wereldliteratuur. Mijn vraag aan jou is: is dit resultaat bekend? Zou er iets te vinden zijn in Knuth's taocp?
Gewoon doen, dacht ik. Het C-programma problem29.c geeft voor
waarden van n en h alle mogelijke verzamelingen A met bijbehorende per(B).
Een ander gevolg is te vinden op:
http://www.research.att.com/~njas/sequences/
Als je zoekt op het 'word' Spies krijg je een verwijzing naar 21 nieuwe rijtjes getallen, afgeleid van het Dancing School Problem. Zoeken naar A079908 t/m A079928 kan ook.
Met vriendelijke groet,
Jaap
25-03-03 15:41 From Robbert Fokkink
Beste Jaap
Veel dank voor de oplossing van probleem A.
Je vermoeden over permanenten klopt. Hier is een schets van een bewijs. Het polynoom Q(x) dat jij opschrijft is homogeen van graad n. Dan vermenigvuldig je met X1X2...Xn en maakt het polynoom homogeen van graad 2n. Door de sommatie vallen alle bijdragen weg van de termen met een oneven macht voor een van de Xi. Dus in het oorspronkelijke polynoom Q(x) hebben de wegvallende termen ergens een even macht. Nu is Q(x) homogeen van graad n en als de graad van elke Xi oneven is, dan moet die 1 zijn (anders telt de graad van de term op tot meer dan n).
[snipped]
veel groeten uit het zwarte gat,
Robbert
26-03-03 08:55 From Robbert Fokkink
Ik weet niet of de algoritme met permanenten al bekend is. Bij permanent dacht ik tot voor kort aan kapsels. Jan Aarts vertelde me dat er zoiets bestaat als de permanenten stelling van Van der Waerden. Je zult het aan een grafentheoreticus moeten vragen. Wat vaak werkt is gewoon een email sturen aan een autoriteit.
Robbert
I followed his advice: send an email to an authority.
08-05-03 18:38 From codenotti@imc.pi.cnr.it
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
08-05-03 22:02 codenotti@imc.pi.cnr.it
Interesting problem!
May I suggest that you contact my coauthor Giovanni Resta on my behalf for this
stuff? I am now on sabbatical at Chicago and am working on different things at
present. But he has a lot of interest for permanents arising from sequences. His
email is resta@imc.pi.cnr.it.
Cheers,
Bruno
> My interest for calculating a permanent comes from a special case:
> A (0,1)-matrix A=(a_ij) of size n x (n+h). a_ij = 1 iff i <= j <= i+h, n
>> 0, h>=0.
>
> See Sloane's Encyclopedia of Integer Sequences for my Dancing School
> Problem.
>
> %A A079908 Jaap Spies (j.spies(AT)hccnet.nl), Jan 28 2003
>
>
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A079908
>
> I hoped to find an efficient algorithm to calculate per(A) for this
> special cases.
>
> Jaap Spies
>
13-05-03 17:13 From Richard Brualdi
Sorry for the late reply.
Your formula is interesting and I cannot recall seeing it before,
but maybe it appears buried in some paper or other.
As you say it is `similar' to Ryser's formula and can also be obtained via
the inclusion-exclusion principle. It would be interesting if you could
derive some new determinant identities using it.
Thanks for showing it to me.
Best wishes
Richard Brualdi
13-05-03 23:49 Richard Brualdi
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
14-05-03 23:24 to Richard Brualdi
Richard Brualdi wrote:
> I don't think it would be accepted for publication in a research
> journal.
You are absolutely right. It is too light weighted.
But for me as an amateur it is new and I would like to share my
discovery with the world. I thank you for your advice.
> 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.
>
I do not know the AMM. For me the AMM seems to be a rather closed environment.
I prefer more open publication systems (internet journals, etc.), but maybe I give it a try.
> for references you can find a chapter on permanents in my book
>
> Combinatorial Matrix Theory (with H.J. Ryser), Cambridge
>
As you may have noticed. I own a copy of your book, so I know chapter 7.
Six years ago I came across it. I bought it with the idea
this is nice stuff to study when I am retired.
With some years to go: it is now nice to read and study!
For your information I attach a text to show you where my interest
for permanents came from.
Once again, thank you for your advice. Regards,
Jaap
07-10-03 21:06 to monthly@math.utexas.edu
Dear Sir,
Earlier this year (februari 2003) I needed an algorithm for the calculation
of the permanent of a (square) matrix. Playing around with 'Maple', doing
some plus and minus, I stumbled on an algorithm new to me.
Intensive search in literature and on the internet gave no clues what so ever.
So I asked Mr. Brualdi as a well known expert in this field. He wrote:
> 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.
> Richard Brualdi
A few days later he wrote:
> 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
>
>
> The AMM is probably one of the most widely circulated math journals.
> Thanks for your text.
>
> Best wishes
>
> Richard
So with this recommandation I send it to you.
Sincerely,
Jaap Spies
jaapspies@home.nl
Landschaplaan 88
7824 BM Emmen
The Netherlands
07-10-03 23:12 from "Margaret A. Combs"
Dear Mr. Spies:
REF: MS #03-656
Your paper "Note on the Permanent of a Matrix of order n"
is being forwarded to Professor William Adkins for
consideration in the Notes section of the Monthly.
The refereeing process can take several months and you will hear from
Dr. Adkins (or our office) when a decision is made on your paper.
The Notes editor address is: Professor William Adkins, Dept of Mathematics,
Louisiana State University, Baton Rouge LA 70803-4918.
Thanks for thinking of the Monthly.
Sincerely,
Margaret A. Combs
Editorial Assistant
American Mathematical Monthly
monthly@math.utexas.edu
15-10-04 20:53 to "Margaret A. Combs", adkins@math.lsu.edu
On 10/07/2003 Margaret A. Combs wrote:
> Dear Mr. Spies:
> *REF: MS #03-656*
>
> Your paper "Note on the Permanent of a Matrix of order n"
> is being forwarded to Professor William Adkins for
> consideration in the Notes section of the Monthly.
> The refereeing process can take several months and you will hear from
> Dr. Adkins (or our office) when a decision is made on your paper. The Notes editor address is: Professor William Adkins, Dept of Mathematics,
> Louisiana State University, Baton Rouge LA 70803-4918.
>
> Thanks for thinking of the Monthly.
>
> Sincerely,
> Margaret A. Combs
> Editorial Assistant
> American Mathematical Monthly
> monthly@math.utexas.edu
After more than a year of silence I have a question. What happened to my note?
Was it to lightweighted and is it blown with the wind or what? I do have a version
in a more substantial classic definition/theorem style.
Additionally I mention the implementation of my algorithm in C++, faster than an optimized
Ryser's code. I used this software in some contributions to
Neil Sloane's On-Line Encyclopedia of Integer Sequences.
Sincerely,
Jaap Spies
28-10-03 17:00 from Neil Sloane
very impressive! I will extend that sequence
So here is a (hard) question: can you solve the 5x5 case?
Is 24 the max permanent of an invertible 5x5 +-1 matrix?
(I don't know if this is already proved by some other
method than exhaustive search)
Neil J. A. Sloane
AT&T Shannon Labs, Room C233,
180 Park Avenue, Florham Park, NJ 07932-0971
29-10-03 11:55 To Edwin Clark
Edwin Clark wrote:
> Hi,
>
> I just wonder if you have done exhaustive search for any values of n greater than 5 for this problem?
> (or perhaps something less than exhaustive--using, for
> example, the fact that the absolute value of the permanent
> is unchanged by assuming the last row and last column
> are all 1's.)
>
> Edwin
>
At the moment I'm running a n=6 search at 90% CPU and 240 MB mem.
It is running for hours. I did not any tuning of the program, so maybe
I have to stop it and think. Those (-1,1) square matrices are a kind of special.
There is something to gain. I will give it a try, but for now back to work.
Jaap
29-10-03 21:27 To Neil Sloane:
N. J. A. Sloane wrote:
> very impressive! I will extend that sequence
>
> So here is a (hard) question: can you solve the 5x5 case?
> Is 24 the max permanent of an invertible 5x5 +-1 matrix?
>
I can do now an exhaustive search in the 5x5 case:
33554432 matrices in 3m13.240s user time on my laptop.
The 6x6 case may need a couple of days? Maybe I follow the suggestion of Edwin Clark:
> I just wonder if you have done exhaustive search
> for any values of n greater than 5 for this problem?
> (or perhaps something less than exhaustive--using, for
> example, the fact that the absolute value of the permanent
> is unchanged by assuming the last row and last column
> are all 1's.)
Maybe I can speed things up a little bit. Confirming a(6)=128 seems feasible.
Jaap
30-10-03 09:11 To Neil Sloane, Edwin Clarke
After almost 3 hours and processing 1073741824 (-1,1)-matrices of order 6 with 1s on
the first row, my program returned:
there are no such matrices with abs(permanent) > 128
Jaap Spies
15-11-03 00:15 to Edwin Clarke
Edwin Clark wrote:
> I pasted your data into a file, read it into Maple and used Maple to
> add up the frequencies. I hope you have a good rest and can figure out the
> discrepancy when you are refreshed. Cheers, Edwin
>
>
I figured out what went wrong. It was the determinant code. I did some extensive
testing. For n=6 my program produces now the correct values for the determinant.
I'm happy it is not the permanent code because that is based on my 'new'
algorithm. I had three altenatives for the case:
a naive implementation of Ryser's alg, a more sophisticated one suggested in
the thesis of Giovanni Resta and my own algorithm. My alg won the speed contest.
In march I showed it to Richard Brualdi, he wrote:
> Your formula is interesting and I cannot recall seeing it before,
> but maybe it appears buried in some paper or other.
> As you say it is `similar' to Ryser's formula and can also be obtained via
> the inclusion-exclusion principle. It would be interesting if you could
> derive some new determinant identities using it.
>
> Thanks for showing it to me.
>
> Best wishes
>
> Richard Brualdi
>
and later he suggested:
> 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 so I did send it as a note to the AMM. If you are interrested
I could send you a copy.
Jaap
17-11-03 16:32 To Edwin Clarke
Jaap,
Thanks for the copy of you note on permanents. It is an
interesting approach. It might be a good idea to write
it up as a new algorithm and compare it to known algorithms.
It looks like the time is about 2^n which is certainly better
than brute force n!.
Edwin
17-11-03 20:31 To Edwin Clarke
Edwin,
Thank you for your reaction.
I think the complexity is comparable to that of Ryser's: O(n^2 2^n).
What I did was implementing three algorithms in C and running various
profile tests.
1. an implementation of Brualdi & Ryser Cor. 7.1.2..
2. a more smart approach using binary representation of 2^n and bit-operations
3 an implementation of what I call my algorithm.
Not suprisingly 1. lost. Much to my surprise 3 was the fastest in a range of problems.
I'm an amateur in this field (and many more), so probably it can be done better.
In the problem at hand: frequencies of permanents of non-singular (0,1)-matrices,
it took my program 1m09s user time to do the case n=5. For n=6 it will take 4 to 5 days.
I'm waiting.
Let me try to write down the algorithm in an understandable way.
Jaap