$SPAD/src/input pfaffian

Timothy Daly, Gunter Rote, Martin Rubey

December 3, 2016

Abstract

The Pfaffian is a function defined on skew-symmetric 2n × 2n matrices. It is the square root of the determinant.[?]

Contents

1 Examples

Pfaffian [ \begin{matrix}0 & a \\ −a & 0 \end{matrix} ] = a

Pfaffian [ \begin{matrix}0 & a & b & c \\ −a & 0 & d & e \\ −b & −d & 0 & f \\ −c & −e & −f & 0 \end{matrix} ] = af − be + dc

Pfaffian [ \begin{matrix}\begin{matrix}0 & λ_{1} \\ −λ_{1} & 0 \end{matrix} & 0 & ⋯ & 0 \\ 0 & \begin{matrix}0 & λ_{2} \\ −λ_{2} & 0 \end{matrix} & & 0 \\ ⋮ & & ... & ⋮ \\ 0 & 0 & ⋯ & \begin{matrix}0 & λ_{n} \\ −λ_{n} & 0 \end{matrix} \end{matrix} ] = λ_{1}λ_{2} ⋯ λ_{n}

2 Formal definition

A matrix is skew-symmetric if A^{T} = −A

Let A = {a_{i,j}} be a 2n × 2n skew-symmetric matrix. The Pfaffian of A is defined by the equation

P f(A) = \frac{1}{s^{n}n!} ∑_{σ∈S_{2n}} sgn(σ) ∏_{i=1}^{n} a_{σ(2i−1),σ(2i)}

where S_{2n} is the symmetric group and sgn(σ) is the signature of σ. The Pfaffian of a n × n skew-symmetric matrix for n odd is defined to be zero.

3 Axiom code

— * —

)set break resume
)spool pfaffian.output
)set message test on
)set message auto off
)clear all

———-

The function B0 has an input range of PositiveInteger. It computes a square matrix. — * —

--S 1 of 26
B0 n == matrix [[(if i=j+1 and odd? j then -1 else _
                   if i=j-1 and odd? i then 1 else 0) _
                     for j in 1..n] for i in 1..n]
--R
--R                                                                   Type: Void
--E 1

———-

The first 8 values computed are: — * —

--S 2 of 26
B0 1
--R
--R   Compiling function B0 with type PositiveInteger -> Matrix(Integer)
--R
--R   (2)  [0]
--R                                                        Type: Matrix(Integer)
--E 2
--S 3 of 26
B0 2
--R
--R
--R        + 0   1+
--R   (3)  |      |
--R        +- 1  0+
--R                                                        Type: Matrix(Integer)
--E 3
--S 4 of 26
B0 3
--R
--R
--R        + 0   1  0+
--R        |         |
--R   (4)  |- 1  0  0|
--R        |         |
--R        + 0   0  0+
--R                                                        Type: Matrix(Integer)
--E 4
--S 5 of 26
B0 4
--R

--R
--R        + 0   1   0   0+
--R        |              |
--R        |- 1  0   0   0|
--R   (5)  |              |
--R        | 0   0   0   1|
--R        |              |
--R        + 0   0  - 1  0+
--R                                                        Type: Matrix(Integer)
--E 5
--S 6 of 26
B0 5
--R
--R
--R        + 0   1   0   0  0+
--R        |                 |
--R        |- 1  0   0   0  0|
--R        |                 |
--R   (6)  | 0   0   0   1  0|
--R        |                 |
--R        | 0   0  - 1  0  0|
--R        |                 |
--R        + 0   0   0   0  0+
--R                                                        Type: Matrix(Integer)
--E 6
--S 7 of 26
B0 6
--R
--R
--R        + 0   1   0   0   0   0+
--R        |                      |
--R        |- 1  0   0   0   0   0|
--R        |                      |
--R        | 0   0   0   1   0   0|
--R   (7)  |                      |
--R        | 0   0  - 1  0   0   0|
--R        |                      |
--R        | 0   0   0   0   0   1|
--R        |                      |
--R        + 0   0   0   0  - 1  0+
--R                                                        Type: Matrix(Integer)
--E 7
--S 8 of 26
B0 7
--R
--R
--R        + 0   1   0   0   0   0  0+

--R        |                         |
--R        |- 1  0   0   0   0   0  0|
--R        |                         |
--R        | 0   0   0   1   0   0  0|
--R        |                         |
--R   (8)  | 0   0  - 1  0   0   0  0|
--R        |                         |
--R        | 0   0   0   0   0   1  0|
--R        |                         |
--R        | 0   0   0   0  - 1  0  0|
--R        |                         |
--R        + 0   0   0   0   0   0  0+
--R                                                        Type: Matrix(Integer)
--E 8
--S 9 of 26
B0 8
--R
--R
--R        + 0   1   0   0   0   0   0   0+
--R        |                              |
--R        |- 1  0   0   0   0   0   0   0|
--R        |                              |
--R        | 0   0   0   1   0   0   0   0|
--R        |                              |
--R        | 0   0  - 1  0   0   0   0   0|
--R   (9)  |                              |
--R        | 0   0   0   0   0   1   0   0|
--R        |                              |
--R        | 0   0   0   0  - 1  0   0   0|
--R        |                              |
--R        | 0   0   0   0   0   0   0   1|
--R        |                              |
--R        + 0   0   0   0   0   0  - 1  0+
--R                                                        Type: Matrix(Integer)
--E 9
--S 10 of 26
PfChar(lambda, A) ==
    n := nrows A
    odd? n => 0
    (n = 2) => lambda^2 + A.(1,2)
    M := subMatrix(A, 3, n, 3, n)
    r := subMatrix(A, 1, 1, 3, n)
    s := subMatrix(A, 3, n, 2, 2)
    p := PfChar(lambda, M)
    d := degree(p, lambda)
    B := B0(n-2)

    C := r*B
    g := [(C*s).(1,1), A.(1,2), 1]
    if d >= 4 then
        B := M*B
        for i in 4..d by 2 repeat
            C := C*B
            g := cons((C*s).(1,1), g)
    g := reverse! g
    res := 0
    for i in 0..d by 2 for j in 2..d+2 repeat
        c := coefficient(p, lambda, i)
        for e in first(g, j) for k in 2..-d by -2 repeat
            res := res +  c * e * lambda^(k+i)
    res
--R
--R                                                                   Type: Void
--E 10
--S 11 of 26
pfaffian A == eval(PfChar(l, A), l=0)
--R
--R                                                                   Type: Void
--E 11
--S 12 of 26
m:Matrix(Integer):=[[0,15],[-15,0]]
--R
--R
--R         + 0    15+
--R   (12)  |        |
--R         +- 15  0 +
--R                                                        Type: Matrix(Integer)
--E 12
--S 13 of 26
pfaffian m
--R
--R   Compiling function B0 with type Integer -> Matrix(Integer)
--R   The type of the local variable res has changed in the computation.
--R   We will attempt to interpret the code.
--R   Cannot compile map: PfChar
--R   We will attempt to interpret the code.
--R
--R   (13)  15
--R                                                    Type: Polynomial(Integer)
--E 13
--S 14 of 26

m1:Matrix(Polynomial(Integer)):=[[0,a,b,c],[-a,0,d,e],[-b,-d,0,f],[-c,-e,-f,0]]
--R
--R
--R         + 0    a    b   c+
--R         |                |
--R         |- a   0    d   e|
--R   (14)  |                |
--R         |- b  - d   0   f|
--R         |                |
--R         +- c  - e  - f  0+
--R                                            Type: Matrix(Polynomial(Integer))
--E 14
--S 15 of 26
pfaffian m1
--R
--R
--R   (15)  a f - b e + c d
--R                                                    Type: Polynomial(Integer)
--E 15
--S 16 of 26
(a,b,c,d,e,f):=(3,5,7,11,13,17)
--R
--R
--R   (16)  17
--R                                                        Type: PositiveInteger
--E 16
--S 17 of 26
m1
--R
--R
--R         + 0    a    b   c+
--R         |                |
--R         |- a   0    d   e|
--R   (17)  |                |
--R         |- b  - d   0   f|
--R         |                |
--R         +- c  - e  - f  0+
--R                                            Type: Matrix(Polynomial(Integer))
--E 17
--S 18 of 26
a*f-b*e+d*c
--R
--R
--R   (18)  63
--R                                                        Type: PositiveInteger
--E 18

--S 19 of 26
n:=pfaffian m1
--R
--R
--R   (19)  a f - b e + c d
--R                                                    Type: Polynomial(Integer)
--E 19
--S 20 of 26
eval(n,['a,'b,'c,'d,'e,'f]::List(Symbol),[a,b,c,d,e,f])
--R
--R
--R   (20)  63
--R                                                    Type: Polynomial(Integer)
--E 20

———-

Here we demonstrate the pfaffian of a block matrix which is anti-symmetric at each level. The proper result is to return a single matrix in the ground field. Maybe. It’s not clear.

— * —

)clear properties z
)clear properties d
)clear properties v
--S 21 of 26
z:SQMATRIX(2,INT):=[[0,0],[0,0]]
--R
--R
--R         +0  0+
--R   (21)  |    |
--R         +0  0+
--R                                                Type: SquareMatrix(2,Integer)
--E 21
--S 22 of 26
d:SQMATRIX(2,INT):=[[0,1],[-1,0]]
--R
--R
--R         + 0   1+
--R   (22)  |      |
--R         +- 1  0+
--R                                                Type: SquareMatrix(2,Integer)
--E 22
--S 23 of 26
v:SQMATRIX(4,SQMATRIX(2,INT)):=[[z,d,d,d],[-d,z,d,d],[-d,-d,z,d],[-d,-d,-d,z]]

--R
--R
--R         + +0  0+   + 0   1+  + 0   1+  + 0   1++
--R         | |    |   |      |  |      |  |      ||
--R         | +0  0+   +- 1  0+  +- 1  0+  +- 1  0+|
--R         |                                      |
--R         |+0  - 1+   +0  0+   + 0   1+  + 0   1+|
--R         ||      |   |    |   |      |  |      ||
--R         |+1   0 +   +0  0+   +- 1  0+  +- 1  0+|
--R   (23)  |                                      |
--R         |+0  - 1+  +0  - 1+   +0  0+   + 0   1+|
--R         ||      |  |      |   |    |   |      ||
--R         |+1   0 +  +1   0 +   +0  0+   +- 1  0+|
--R         |                                      |
--R         |+0  - 1+  +0  - 1+  +0  - 1+   +0  0+ |
--R         ||      |  |      |  |      |   |    | |
--R         ++1   0 +  +1   0 +  +1   0 +   +0  0+ +
--R                                Type: SquareMatrix(4,SquareMatrix(2,Integer))
--E 23
--S 24 of 26
pfaffian v
--R
--R   There are 1 exposed and 0 unexposed library operations named
--R      subMatrix having 5 argument(s) but none was determined to be
--R      applicable. Use HyperDoc Browse, or issue
--R                            )display op subMatrix
--R      to learn more about the available operations. Perhaps
--R      package-calling the operation or using coercions on the arguments
--R      will allow you to apply the operation.
--R
--RDaly Bug
--R   Cannot find a definition or applicable library operation named
--R      subMatrix with argument type(s)
--R                   SquareMatrix(4,SquareMatrix(2,Integer))
--R                               PositiveInteger
--R                               PositiveInteger
--R                               PositiveInteger
--R                               PositiveInteger
--R
--R      Perhaps you should use "@" to indicate the required return type,
--R      or "$" to specify which version of the function you need.
--E 24
--S 25 of 26
mypf(m) ==
 nr:= nrows m
 odd? nr => 0
-- not zero? (nr mod 2)
 not square? m => 0

 not antisymmetric? m => 0
 nr = 2 => m.(1,2)
 nr = 4 => m.(1,2)*m.(3,4)-m.(1,3)*m.(2,4)+m.(2,3)*m.(1,4)
 0
--R
--R                                                                   Type: Void
--E 25

———-

We can construct an anti-symmetric matrix from a sequence by taking the first n elements of the sequence:

— * —

--S 26 of 26
antisymmetric(seq,n) ==
  m:= matrix [[(if i<j then (seq.(j-i)) _
                 else if i>j then -(seq.(i-j))
                  else 0) for j in 1..n] for i in 1..n]
--R
--R                                                                   Type: Void
--E 26

———-

According to Austin[?] we can construct a map, called the “Pfaffian transformation” of a sequence which maps the sequence (a_{0}, a_{1}, a_{2}, …) to (P f(A_{0}), P f(A_{1}), P f(A_{2}), …). Here we construct and test the examples given in the paper:

--
seq:=[i for i in 1..]
--R
--R
--R   (26)  [1,2,3,4,5,6,7,8,9,10,...]
--R                                                 Type: Stream PositiveInteger
--
--
[pfaffian makepfaff(seq,m) for m in 2..10 by 2]
--
--
seq:=[2 for i in 1..]
--R
--R
--R   (27)  [2,2,2,2,2,2,2,2,2,2,...]
--R                                                 Type: Stream PositiveInteger
--
--

[pfaffian makepfaff(seq,m) for m in 2..10 by 2]
--
--
seq:=[2^i for i in 0..]
--R
--R
--R   (28)  [1,2,4,8,16,32,64,128,256,512,...]
--R                                                 Type: Stream PositiveInteger
--
--
[pfaffian makepfaff(seq,m) for m in 2..10 by 2]
--
--
seq:=[1,1,2,3,5,8,13,21,34]
--R
--R
--R   (29)  [1,1,2,3,5,8,13,21,34]
--R                                                   Type: List PositiveInteger
--
--
[pfaffian makepfaff(seq,m) for m in 2..10 by 2]
--

— * —

)spool
)lisp (bye)

———-

The Pfaffian is the square root of the determinant. The determinant can be calculated by

|a b c|
|d e f| = a|e f| - b|d f| + c|d e|
|g h i|    |h i|    |g i|    |g h|

References

[1] Austin, T., Bantilan, H., Jonas, I., Kory, P., “The Pfaffian Transformation”, March 9, 2007 “apps.carleton.edu/curricular/math/assets/pfaffian comps 06 07.pdf”

[2] “http://en.wikipedia.org/wiki/Pfaffian”