\documentclass{article} \usepackage{amsfonts} \usepackage{axiom} \begin{document} \title{\$SPAD/src/input pfaffian} \author{Timothy Daly, Gunter Rote, Martin Rubey} \maketitle \begin{abstract} In mathematics, the determinant of a skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries. This polynomial is called the Pfaffian of the matrix. The Pfaffian is nonvanishing only for$2n \times 2n$skew-symmetric matrices, in which case it is a polynomial of degree$n$. \end{abstract} \eject \tableofcontents \eject \section{Examples} $${\rm Pfaffian}\left[ \begin{array}{cc} 0 & a\\ -a & 0 \end{array} \right] = a$$ $${\rm Pfaffian}\left[ \begin{array}{cccc} 0 & a & b & c\\ -a & 0 & d & e\\ -b & -d & 0 & f\\ -c & -e & -f & 0 \end{array} \right] = af -be + dc$$ $${\rm Pfaffian}\left[ \begin{array}{cccc} \begin{array}{cc} 0 & \lambda_1\\ -\lambda_1 & 0 \end{array} & 0 & \cdots & 0\\ 0 & \begin{array}{cc} 0 & \lambda_2\\ -\lambda_2 & 0 \end{array} & & 0\\ \vdots & & \ddots & \vdots\\ 0 & 0 & \cdots & \begin{array}{cc} 0 & \lambda_n\\ -\lambda_n & 0 \end{array} \end{array} \right] = \lambda_1\lambda_2\cdots\lambda_n$$ \section{Formal definition} Let$A = \{a_{i,j}\}$be a$2n \times 2n$skew-symmetric matrix. The Pfaffian of A is defined by the equation $$Pf(A) = \frac{1}{s^n n!}\sum_{\sigma\in{}S_{2n}}sgn(\sigma) \prod_{i=1}^n{a_{\sigma(2i-1),\sigma(2i)}}$$ where$S_{2n}$is the symmetric group and$sgn(\sigma)$is the signature of$\sigma$. One can make use of the skew-symmetry of$A$to avoid summing over all possible permutations. Let$\Pi$be the set of all partitions of$\{1, 2, \ldots, 2n\}$into pairs without regard to order. There are$(2n - 1)!!$such partitions. An element$\alpha \in \Pi$, can be written as $$\alpha=\{(i_1,j_1),(i_2,j_2),\cdots,(i_n,j_n)\}$$ with$i_k < j_k$and$i_1 < i_2 < \cdots < i_n$. Let $$\pi= \left[ \begin{array}{cccccc} 1 & 2 & 3 & 4 & \cdots & 2n \\ i_1 & j_1 & i_2 & j_2 & \cdots & j_{n} \end{array} \right]$$ be a corresponding permutation. This depends only on the partition$\alpha$and not on the particular choice of$\Pi$. Given a partition$\alpha$as above define $$A_\alpha =sgn(\pi)a_{i_1,j_1}a_{i_2,j_2}\cdots a_{i_n,j_n}$$ The Pfaffian of$A$is then given by $$Pf(A)=\sum_{\alpha\in\Pi} A_\alpha$$ The Pfaffian of a$n\times n$skew-symmetric matrix for n odd is defined to be zero. \subsection{Alternative definition} One can associate to any skew-symmetric$2n \times 2n$matrix$A=\{a_{ij}\}$a bivector$\$\omega=\sum_{i>= )clear all --S 1 of 9 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 --S 2 of 9 PfChar(lambda, A) == n := nrows A (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 2 --S 3 of 9 pfaffian A == eval(PfChar(l, A), l=0) --R --R Type: Void --E 3 --S 4 of 9 m:Matrix(Integer):=[[0,15],[-15,0]] --R --R + 0 15+ --R (4) | | --R +- 15 0 + --R Type: Matrix Integer --E 4 --S 5 of 9 pfaffian m --R --R (5) 15 --R Type: Polynomial Integer --E 5 --S 6 of 9 (a,b,c,d,e,f):=(3,5,7,11,13,17) --R --R (6) 17 --R Type: PositiveInteger --E --S 7 of 9 m1:Matrix(Integer):=[[0,a,b,c],[-a,0,d,e],[-b,-d,0,f],[-c,-e,-f,0]] --R --R + 0 3 5 7 + --R | | --R |- 3 0 11 13| --R (7) | | --R |- 5 - 11 0 17| --R | | --R +- 7 - 13 - 17 0 + --R Type: Matrix Integer --E 7 --S 8 of 9 m1ans:=a*f-b*e+d*c --R --R --R (8) 63 --R Type: PositiveInteger --E 8 --S 9 of 9 pfaffian m1 --R --R Compiling function B0 with type PositiveInteger -> Matrix Integer --R --R (9) 63 --R Type: Polynomial Integer --E 9 )spool )lisp (bye) @ \eject \begin{thebibliography}{99} \bibitem{1} {\bf "http://en.wikipedia.org/wiki/Pfaffian"} \bibitem{2} The statistics of dimers on a lattice, Part I'', Physica, vol.27, 1961, pp.1209-25, P.W. Kasteleyn. \bibitem{3} Propp, James (2004), Lambda-determinants and domino-tilings'', arXiv:math.CO/0406301. \bibitem{4} Globerson, Amir and Tommi Jaakkola (2007), Approximate inference using planar graph decomposition'', Advances in Neural Information Processing Systems 19, MIT Press. \bibitem{5} The Games and Puzzles Journal'', No.14, 1996, pp.204-5, Robin J. Chapman, University of Exeter \bibitem{6} Domino Tilings and Products of Fibonacci and Pell numbers'', Journal of Integer Sequences, Vol.5, 2002, Article 02.1.2, James A. Sellers, The Pennsylvania State University \bibitem{7} The Penguin Dictionary of Curious and Interesting Numbers'', revised ed., 1997, ISBN 0-14-026149-4, David Wells, p.182. \bibitem{8} A Treatise on the Theory of Determinants'', 1882, Macmillan and Co., Thomas Muir, Online \bibitem{9} Skew-Symmetric Determinants'', The American Mathematical Monthly, vol. 61, no.2., 1954, p.116, S. Parameswaran Online-Subscription \end{thebibliography} \end{document}