[GAP Forum] Pfaffian?

[Igor Korepanov]

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