[GAP Forum] Pfaffian?

[Mathieu Dutour]

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