[GAP Forum] Pfaffian?

[Mathieu Dutour]

Free to use of course, just keep me informed.

It is part of my package plangraph from
http://www.liga.ens.fr/~dutour/PlanGraph/index.html
It may be included in GAP in the future but that
is relatively unlikely since none of what it does
is groundbreaking, there is no manual and there are
some designs errors.

The idea was to enumerate perfect matching of some
surfaces. There is a theory giving formulas for
the number of perfect matching as a sum of 4^g
pfaffians. But since I never understood how it works
the project never took off the ground.

  Mathieu

>> Dear Forum, dear Mathieu,
>> 
>> Great! It seems to work excellent!
>> 
>> Mathieu: What are my right for using this? Is this code going
>> to be included in some GAP package? Can I include it (also) in
>> my package PL (which is still in its "pre-alpha" stage, but the
>> work will hopefully go faster soon when a graduate student of
>> mine grows a bit more mature :) ), with a proper indication
>> who its author is? 
>> 
>> Igor
>> 
>> 
>> 
>> 31.08.2011, 20:02, "Mathieu Dutour" <Mathieu.Dutour at ens.fr>:
>> > Right now, no as far as I know.
>> >
>> > But meanwhile, there is a way to compute polynomially by some
>> > analog of the row column operations for the determinant.
>> >
>> > See below some code:
>> > # operation Li <--> Lj and Ci <--> Cj if ThePerm=(i,j)
>> > PermutationRowColumn:=function(TheMat, ThePerm)
>> >   local NewMat, i;
>> >   NewMat:=[];
>> >   for i in [1..Length(TheMat)]
>> >   do
>> >     Add(NewMat, Permuted(TheMat[i], ThePerm));
>> >   od;
>> >   return Permuted(NewMat, ThePerm);
>> > end;
>> >
>> > # operations, Lj <- alpha*Lj and Cj<-alpha*Cj
>> > RowColumnMultiplication:=function(TheMat, j, alpha)
>> >   local NewMat, i;
>> >   NewMat:=[];
>> >   for i in [1..Length(TheMat)]
>> >   do
>> >     if i<>j then
>> >       Add(NewMat, TheMat[i]);
>> >     else
>> >       Add(NewMat, alpha*TheMat[i]);
>> >     fi;
>> >   od;
>> >   for i in [1..Length(TheMat)]
>> >   do
>> >     NewMat[i][j]:=alpha*NewMat[i][j];
>> >   od;
>> >   return NewMat;
>> > end;
>> >
>> > # operations, Li<- Li+alpha Lj
>> > # operations, Ci<- Ci+alpha Ci
>> > AdditionRowColumn:=function(TheMat, i, j, alpha)
>> >   local NewMat, k;
>> >   NewMat:=[];
>> >   for k in [1..Length(TheMat)]
>> >   do
>> >     if k=i then
>> >       Add(NewMat, TheMat[i]+alpha*TheMat[j]);
>> >     else
>> >       Add(NewMat, TheMat[k]);
>> >     fi;
>> >   od;
>> >   for k in [1..Length(NewMat)]
>> >   do
>> >     NewMat[k][i]:=NewMat[k][i]+alpha*NewMat[k][j];
>> >   od;
>> >   return NewMat;
>> > end;
>> >
>> > Pfaffian:=function(MatInput)
>> >   local i, m, p, piv, zero, pfaff, j, k, sgn, row, row2, mult, mult2, result, AntiSymMat;
>> >   AntiSymMat:=StructuralCopy(MatInput);
>> >   m:=Length(AntiSymMat);
>> >   if m mod 2=1 then
>> >     return 0;
>> >   fi;
>> >   p:=m/2;
>> >   zero:=Zero(AntiSymMat[1][1]);
>> >   pfaff:=1;
>> >   sgn:=1;
>> >   for k in [1..p]
>> >   do
>> >     j:=2*k;
>> >     while j<=m and AntiSymMat[2*k-1][j]=zero
>> >     do
>> >       j:=j+1;
>> >     od;
>> >     if j>m then
>> >       return zero;
>> >     fi;
>> >     if j<> 2*k then
>> >       AntiSymMat:=PermutationRowColumn(AntiSymMat, (j,2*k));
>> >       sgn:=-sgn;
>> >     fi;
>> >     row:=AntiSymMat[2*k];
>> >     piv:=row[2*k-1];
>> >     for j in [2*k+1..m]
>> >     do
>> >       row2:=AntiSymMat[j];
>> >       mult:=-row2[2*k-1];
>> >       #
>> >       AntiSymMat:=RowColumnMultiplication(AntiSymMat, j, piv);
>> >       #
>> >       AntiSymMat:=AdditionRowColumn(AntiSymMat, j, 2*k, mult);
>> >       #
>> >       row2:=AntiSymMat[j];
>> >       mult2:=row2[2*k]/piv;
>> >       AntiSymMat:=AdditionRowColumn(AntiSymMat, j, 2*k-1, mult2);
>> >       #
>> >       AntiSymMat:=RowColumnMultiplication(AntiSymMat, j, Inverse(pfaff));
>> >     od;
>> >     pfaff:=-piv;
>> >   od;
>> >   result:=pfaff;
>> >   for k in [1..p-1]
>> >   do
>> >     result:=result/AntiSymMat[2*k-1][2*k];
>> >   od;
>> >   return sgn*result;
>> > end;
>> >
>> > On Wed, Aug 31, 2011 at 06:24:12PM +0400, Igor Korepanov wrote:
>> >
>> >>>  Dear Forum,
>> >>>
>> >>>  does GAP calculate a Pfaffian? And with the right sign? And for a big antisymmetric matrix with indeterminates?
>> >>>
>> >>>  I will be grateful for any advice.
>> >>>
>> >>>  Currently, I found the letter
>> >>>  http://mail.gap-system.org/pipermail/forum/2006/001324.html
>> >>>  from Mathieu Dutour Sikiric whom I am sending a personal copy of this letter.
>> >>>
>> >>>  Igor