[Axiom-developer] 20070929.01.tpd.patch

[daly]

This change removes pfaffian.input.pamphlet.

=======================================================================
diff --git a/changelog b/changelog
index c254ce6..6c10a71 100644
--- a/changelog
+++ b/changelog
@@ -1,3 +1,5 @@
+20070929 tpd src/input/Makefile pfaffian regression test removed
+20070929 tpd src/input/pfaffian.input regression test removed
 20070927 tpd src/input/Makefile pfaffian regression test added 
 20070927 mxr src/input/pfaffian.input regression test added 
 20070920 tpd src/input/Makefile add bug101.input regression test
diff --git a/src/input/Makefile.pamphlet b/src/input/Makefile.pamphlet
index b9e5374..f62095a 100644
--- a/src/input/Makefile.pamphlet
+++ b/src/input/Makefile.pamphlet
@@ -340,7 +340,7 @@ REGRES= algaggr.regress algbrbf.regress  algfacob.regress 
alist.regress  \
     padic.regress     parabola.regress pascal1.regress  pascal.regress \
     patch51.regress   page.regress \
     patmatch.regress  pat.regress      perman.regress   perm.regress \
-    pfaffian.regress  pfr1.regress     pfr.regress      pmint.regress \
+    pfr1.regress      pfr.regress      pmint.regress \
     poly1.regress     polycoer.regress poly.regress     psgenfcn.regress \
     quat1.regress     quat.regress     r20abugs.regress r20bugs.regress \
     r21bugsbig.regress r21bugs.regress radff.regress    radix.regress \
@@ -593,7 +593,7 @@ FILES= ${OUT}/algaggr.input  ${OUT}/algbrbf.input    
${OUT}/algfacob.input \
        ${OUT}/pascal.input   \
        ${OUT}/patch51.input \
        ${OUT}/patmatch.input ${OUT}/perman.input \
-       ${OUT}/perm.input     ${OUT}/pfaffian.input \
+       ${OUT}/perm.input     \
        ${OUT}/pfr.input      ${OUT}/pfr1.input \
        ${OUT}/pinch.input    ${OUT}/plotfile.input   ${OUT}/pollevel.input \
        ${OUT}/pmint.input    ${OUT}/polycoer.input \
@@ -870,7 +870,7 @@ DOCFILES= \
   ${DOC}/pat.input.dvi         ${DOC}/patch51.input.dvi   \
   ${DOC}/patmatch.input.dvi   \
   ${DOC}/pdecomp0.as.dvi       ${DOC}/perman.input.dvi     \
-  ${DOC}/perm.input.dvi        ${DOC}/pfaffian.input.dvi   \
+  ${DOC}/perm.input.dvi        \
   ${DOC}/pfr1.input.dvi       \
   ${DOC}/pfr.input.dvi         ${DOC}/pinch.input.dvi      \
   ${DOC}/plotfile.input.dvi    ${DOC}/plotlist.input.dvi   \
diff --git a/src/input/pfaffian.input.pamphlet 
b/src/input/pfaffian.input.pamphlet
deleted file mode 100755
index ad4d7f0..0000000
--- a/src/input/pfaffian.input.pamphlet
+++ /dev/null
@@ -1,483 +0,0 @@
-\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<j} a_{ij}~e^i\wedge e^j$$
-
-where $\{e^1, e^2, \ldots,  e^{2n}\}$ is the standard basis of 
-$\mathbb{R}^{2n}$. The Pfaffian is then defined by the equation
-
-$$\frac{1}{n!}\omega^n = \mbox{Pf}(A)~e^1\wedge e^2\wedge\cdots\wedge e^{2n}$$
-
-here $\omega^n$ denotes the wedge product of $n$ copies of 
-$\omega^n$ with itself.
-
-\subsection{Derivation from Determinant}
-
-The Pfaffian can be derived from the determinant for a skew-symmetric
-matrix $A$ as follows. Using Laplace's formula we can write the
-determinant as
-
-$$\det(A)=(-1)^{p+1}a_{p1}A_{p1} + 
-(-1)^{p+2}a_{p2}A_{p2}+\cdots+(-1)^{n+p}a_{pn}A_{pn}$$
-
-where $A_{pi}$ is the $p,i$ minor matrix of the matrix $A$. We further
-use Laplace's formula to note that
-
-$$\det(A[A_{ij}]) = \vert A \vert^n$$
-
-since this determinant is that of an $n \times n$ matrix whose only
-non-zero elements are the diagonals (each with value det(A)) and
-$[A_{ij}]$ is a matrix whose $i,j$th component is the corresponding $i,j$
-minor matrix. In this way, following a proof by Parameswaran, we can
-write the determinant as,
-
-$$\det(A)\equiv\Delta_n=
-\left| 
-\begin{array}{cccc} 
-a_{11}&a_{12}&\cdots&a_{1n}\\
-a_{21}&a_{22}&\cdots&a_{2n}\\
-\vdots&&&\vdots\\
-a_{n1}&a_{n2}&\cdots&a_{nn}
-\end{array}
-\right|
-$$
-
-The minor of 
-$$
-\left| 
-\begin{array}{cc} 
-a_{11}&a_{12}\\
-a_{21}&a_{22}
-\end{array}
-\right|
-$$
-would be $\Delta_{n - 2}$. With this notation
-
-$$\left| 
-\begin{array}{cccc}
-1&0&\cdots&0\\
-0&1&\cdots&0\\
-a_{31}&a_{32}&\cdots&a_{3n}\\
-\cdots&\cdots&\cdots&\cdots\\
-a_{n1}&a_{n2}&\cdots&a_{nn}
-\end{array}
-\right|
-\times 
-\left| 
-\begin{array}{cccc}
-A_{11}&A_{21}&\cdots&A_{n1}\\
-A_{12}&A_{22}&\cdots&A_{n2}\\
-A_{13}&A_{23}&\cdots&A_{n3}\\
-\cdots&\cdots&\cdots&\cdots\\
-A_{1n}&A_{2n}&\cdots&A_{nn}
-\end{array}
-\right| =
-\left| 
-\begin{array}{cc} 
-A_{11}&A_{21}\\
-A_{12}&a_{22}
-\end{array}
-\right|
-\Delta_n^{n-2}
-$$
-
-Thus
-
-$$\Delta_{n-2}\Delta_n^{n-1}=
-\left| 
-\begin{array}{cc} 
-A_{11}&A_{21}\\
-A_{12}&a_{22}
-\end{array}
-\right|
-\Delta_n^{n-2}
-$$
-
-Of course, it was only arbitrarily that we chose to remove the first
-two rows, and more generically we can write
-
-$$A_{rr}A_{ss} - A_{rs}A_{sr} = \Delta_{rs,rs}\Delta_n$$
-
-where $\Delta_{rs,rs}$ is the determinant of the original matrix with
-the rows $r$ and $s$, as well as the columns $r$ and $s$ removed. The
-equation above simplifies in the skew-symmetric case to
-
-$$A_{rs} = \sqrt{\Delta_{rs,rs}\Delta_n}$$
-
-We now plug this back into the original formula for the determinant,
-
-$$\Delta_n=
-(-1)^{p+1}a_{p1}\sqrt{\Delta_{p1,p1}\Delta_n} + 
-(-1)^{p+2}a_{p2}\sqrt{\Delta_{p2,p2}\Delta_n} +
-\cdots +
-(-1)^{n+p}a_{pn}\sqrt{\Delta_{pn,pn}\Delta_n}
-$$
-
-or with slight manipulation,
-
-$$\sqrt{\Delta_n}=(-1)^{p+1}
-\left( \ a_{p1}\sqrt{\Delta_{p1,p1}} - 
-a_{p2}\sqrt{\Delta_{p2,p2}} +
-\cdots +
-(-1)^{n-1}a_{pn}\sqrt{\Delta_{pn,pn}} \ 
-\right)
-$$
-
-The determinant is thus the square of the right hand side, and so we
-identify the right hand side as the Pfaffian.
-
-\section{Identities}
-
-For a $2n \times 2n$ skew-symmetric matrix $A$ and an arbitrary 
-$2n \times 2n$ matrix B,
-\begin{itemize}
-\item $Pf(A)^2 = \det(A)$
-\item $Pf(BAB^T) = \det(B)Pf(A)$
-\item $Pf(\lambda{}A) = \lambda^nPf(A)$
-\item $Pf(A^T) = ( - 1)^nPf(A)$
-\item For a block-diagonal matrix
-$$A_1\oplus A_2=
-\left[
-\begin{array}{cc}
-A_1 & 0 \\
-0 & A_2 
-\end{array}
-\right]
-$$
-$$Pf(A1\oplus A2) = Pf(A_11)Pf(A_2)$$
-\item For an arbitrary $n \times n$ matrix $M$:
-$$\mbox{Pf}
-\left[
-\begin{array}{cc}
-0 & M \\
--M^T & 0 
-\end{array}
-\right] = 
-(-1)^{n(n-1)/2}\det M
-$$
-\end{itemize}
-\section{Applications}
-
-The Pfaffian is an invariant polynomial of a skew-symmetric matrix
-(note that it is not invariant under a general change of basis but
-rather under a proper orthogonal transformation). As such, it is
-important in the theory of characteristic classes. In particular, it
-can be used to define the Euler class of a Riemannian manifold which
-is used in the generalized Gauss-Bonnet theorem.
-
-The number of perfect matchings in a planar graph turns out to be the
-absolute value of a Pfaffian, hence is polynomial time
-computable. This is surprising given that for a general graph, the
-problem is very difficult (so called \#P-complete). This result is used
-to calculate the partition function of Ising models of spin glasses in
-physics, respectively of Markov random fields in machine learning
-(Globerson and Jaakkola, 2007), where the underlying graph is
-planar. Recently it is also used to derive efficient algorithms for
-some otherwise seemingly intractable problems, including the efficient
-simulation of certain types of restricted quantum computation.
-
-The calculation of the number of possible ways to tile a standard
-chessboard or 8-by-8 checkerboard with 32 dominoes is a simple example
-of a problem which may be solved through the use of the Pfaffian
-technique. There are 12,988,816 possible ways to tile a chessboard in
-this manner. Specifically, 12988816 is the number of possible ways to
-cover an 8-by-8 square with 32 1-by-2 rectangles. 12988816 is a square
-number: $12988816 = 3604^2$). Note that 12988816 can be written in the
-form: $2\times 1802^2 + 2\times 1802^2$, 
-where all the numbers have a digital root of 2.
-
-More generally, the number of ways to cover a $2n \times 2n$ square with 
-$2n^2$ dominoes (as calculated independently by Temperley and M.E. Fisher and
-Kasteleyn in 1961) is given by
-
-$$
-\prod_{j=1}^N 
-\prod_{k=1}^N 
-\left ( 4\cos^2 \frac{\pi j}{2n + 1} + 
-4\cos^2 \frac{\pi k}{2n + 1} \right ) 
-$$
-
-This technique can be applied in many mathematics-related subjects,
-for example, in the classical, 2-dimensional computation of the
-dimer-dimer correlator function in quantum mechanics.
-
-\section{History}
-
-The term Pfaffian was introduced by Arthur Cayley, who used the term
-in 1852: ``The permutants of this class (from their connection with the
-researches of Pfaff on differential equations) I shall term
-Pfaffians.'' The term honors German mathematician Johann Friedrich
-Pfaff.
-
-\section{Axiom code}
-I have hacked together an algorithm to compute a Pfaffian, using an algorithm
-of Gunter Rote.  Currently it's only an .input script, but if it's useful for
-somebody else than myself, we could make it a little more professional.
-
-Martin
-
-<<*>>=
-)spool pfaffian.output
-)set message test on
-)set message auto off
-)clear all
- 
---S 1 of 12
-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 12
-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 12
-pfaffian A == eval(PfChar(l, A), l=0)
---R 
---R                                                                   Type: 
Void
---E 3
-
---S 4 of 12
-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 12
-pfaffian m
---R
---R   (5)  15
---R                                                     Type: Polynomial 
Integer
---E 5
-
---S 6 of 12
-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   (6)  |                |
---R        |- b  - d   0   f|
---R        |                |
---R        +- c  - e  - f  0+
---R                                              Type: Matrix Polynomial 
Integer
---E 6
-
---S 7 of 12
-pfaffian m1
---R 
---R   Compiling function B0 with type PositiveInteger -> Matrix Integer 
---R
---R   (7)  a f - b e + c d
---R                                                     Type: Polynomial 
Integer
---E 7
-
---S 8 of 12
-(a,b,c,d,e,f):=(3,5,7,11,13,17)
---R
---R   (8)  17
---R                                                        Type: 
PositiveInteger
---E 8
-
---S 9 of 12
-m1
---R 
---R
---R        + 0    a    b   c+
---R        |                |
---R        |- a   0    d   e|
---R   (9)  |                |
---R        |- b  - d   0   f|
---R        |                |
---R        +- c  - e  - f  0+
---R                                              Type: Matrix Polynomial 
Integer
---E 9
-
---S 10 of 12
-a*f-b*e+d*c
---R 
---R
---R   (10)  63
---R                                                        Type: 
PositiveInteger
---E 10
-
---S 11 of 12
-n:=pfaffian m1
---R
---R   (11)  a f - b e + c d
---R                                                     Type: Polynomial 
Integer
---E 9
-
---S 12 of 12
-eval(n,['a,'b,'c,'d,'e,'f]::List(Symbol),[a,b,c,d,e,f])
---R
---R   (12)  63
---R                                                     Type: Polynomial 
Integer
---E 12
-)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}