Questions.
(numerical.generalPfaffian) Is it proved anywhere that in general it is not easier0 to calculate the determinant (over $\mathbb{Q}$) of the skew-symmetric signed adjacency matrix defined by any of the Pfaffian orientations of a given finite undirected simple Pfaffian graph on $n$ vertices than to compute the determinant (over $\mathbb{Q}$) of an arbitrary given skew-symmetric $(-1,0,1)$-matrix of size $n\times n$?
(algebraic.generalPfaffian) Same question as (0.numerical), except that 'over $\mathbb{Q}$' is to be replaced with 'over the polynomial ring $\mathbb{Q}[z_{ij}\colon (i,j)\in n\times n]$' and 'signed adjacency matrix' is to be replaced with '$n\times n$ matrix which has the entry $z_{ij}$ if $i$ is oriented towards $j$ in the Pfaffian orientation $o$, has entry $-z_{ij}$ if $j$ is oriented towards $i$ in $o$, and has entry $0$ otherwise.
(numerical.Planar) Same question as (0.numerical.generalPfaffian), except that 'Pfaffian graph' is to be replaced by 'planar graph'.
(algebraic.Planar) Same question as (0.algebraic.generalPfaffian), except that 'Pfaffian graph' is to be replaced by 'planar graph'.
(bibliographic.complexity) What are recommendable references on the complexity of computing the determinant of the skew adjacency matrix defined by a Pfaffian orientation of a graph? Has this rather obvious question of mine been discussed in the literature? (This question should have occurred to countless people who used the Permanent-Determinant method to compute the total number of, or even---using indeterminates---the total set of all, perfect matchings of a graph. And yet I do not find it addressed anywhere.)
(bibliographic.practical.numerical) what are recommendable references on methods to actually compute determinants of skew-symmetric $(-1,0,1)$-matrices (resp. skew-symmetric matrices containing independent indeterminates)? (I would appreciate both relevant references to practical methods, maybe even feasible for manual calculation in moderate dimensions, but also to references which address the obvious 'hierarchy' or 'separation of complexity classes' questions. I expect that the computer algebra literature, or even the 19th century British literature, contains relevant entries, yet I do not find one.)
(bibliographic.practical.algebraic) Same as (bibliographic.practical.numerical), yet with '$(-1,0,1)$-matrices' replaced with 'matrices over a polynomial ring $\mathbb{Z}[x_{ij}\colon (i,j)\in n\times n]$'. (There should be something in the literature on this. Many people have worked with Pfaffians.)
Commentary.
- To summarize the question in one sentence: a rough version of this question is
Does the conceptual simplification in the Permanent-Determinant-Method have to stop at the usual recommendation 'and now go and compute the determininant of the $(-1,0,1)$-matrix you obtained from a Pfaffian orientation of your graph'?
Shouldn't readers be given more specific prescriptions, rather than be left to their fate with general purpose determinant calculation algorithms. Was this aspect just neglected in the literature so far (and next-generation treatments should go further when giving the usual recipe) or is there a mathematical reason for why one cannot do much better than say 'go compute the determinant somehow'?
Can one make use of the fact that the relevant matrices are of a much more special type than even the already rather special 'skew-symmetric $(-1,0,1)$-matrix'? Are there usual linear-algebraic properties that set skew-symmetric signed adjacency matrices defined by a Pfaffian orientation of a Pfaffian graph apart from generic skew-symmetric $(-1,0,1)$-matrix?Has this been discussed in the literature already and where?
- Hoping for relevant answers by people having experience with the Permanent-Determinant-method and/or computer algebra and/or numerical linear algebra, I will not give much background for this question. Here is a micro-summary: there are good theoretical grounds to doubt the existence of a general algorithm which would efficiently compute the exact number of perfect matchings of any specified finite graph (this problem was proved to be #P complete), yet there is a class, which I won't define here, called $\mathsf{PfaffianGraphs}$, for which this problem happens to be efficiently solvable. While easily definable in (subsystems of) second-order arithmetic, the class $\mathsf{PfaffianGraphs}$ is not well-understood to this day, let alone known to be axiomatized by any reasonably 'low-order' kind of axiom system1. From celebrated work of Fisher, Kasteleyn, Temperley, Vazirani, Yannakakis and others it is known that
$\mathsf{PlanarGraphs}\subset\mathsf{K}^{3,3}\mathsf{minorfreeGraphs}\subset\mathsf{PfaffianGraphs}$
yet these are all proper inclusions. Not even the complexity of checking whether a proposed orientation of a given finite graph is Pfaffian is known. (There are merely known equivalent reformulations.)
The version (0.algebraic) is important because it is related to computing the set of all perfect matchings by one standard determinant calculation over a polynomial ring. For reasons I will not go into here, (0.algebraic) is what interests me most, and, of course, the 'independent indeterminates' version of Kasteleyn's method is sometimes only mentioned in passing in elementary treatments of the topic, already for the superficial reason that some people seem out of their depths when it comes to linear algebra over commutative rings.
Given that it is not even proved---the philosophically discouraging #P-completeness notwithstanding---whether one can compute permanents of specified matrices in polynomial time, I expect the complexity- and separation questions above to be unknown. Yet I do not expect there nothing to be known on practical aspects of doing the Permanent-Determinant Method more skillfully that using off-the-shelf determinant functionality of some software package. The latter seems just too undiscerning.
Part of my motivation for this question is theoretical interest in this topic, part is having to actually do (and present and certify) a very specific calculation of the determinant of a skew-symmetric matrix over $\mathbb{Z}[x_{ij}\colon (i,j)\in n\times n]$, a calculation which seems to be in the tantalizing borderland between the trivial-to-do-by-hand and the impossible-even-with-a-contemporary-desktop-computer.
Perhaps unsurprisingly, the mention of $\mathbb{Q}$ above does not mean that this is a condition sine qua non, and I expect that relevant references will vary in this respect, sometimes speaking of matrices over $\mathbb{Z}$, or over $\mathbb{Q}$, or even over an abstract field $K$ with perhaps some conditions imposed. The precise choice of field or ring is not essential to this question, was rather made for specificity of the questions proper.
It seems somewhat surprising to me that none of the several references known to me that treat Kasteleyn's celebrated method ever touches on the obvious facile question 'And how to calculate the determinant? Can I do better than use a generic off-the-shelf method for computing determiants and rather use a dedicated method?' To name but three (otherwise very nice) references, neither Kuperberg's An Exploration of the Permanent-Determinant Method, nor Lovász-Plummer's monograph, nor Thomas' 2006 ICM contribution even mention this obvious question. This is not to blame the authors, who have other things to do and discuss.
And yet, not addressing the problem of how to compute the determinant (as much as an improvement from the probably-exponential complexity of computing the permanent this is) to me seems similar to a treatise on bridge-construction first telling readers 'You do not have to build a test-bridge and see whether it collapses under its own weight before you build the bridge. You can do static analysis mathematically, thereby reduce the problem to a sparse linear system of equations, like so:[...]', then give the method, but then stop and leave readers to their own devices when it comes to solving the system of linear equations,. Instead, readers should at least be briefly told about methods for sparse linear systems, and the great savings one can get from this. It seems that if there is something significant to be said about how to exactly calculate determinants of skew-symmetric $(-1,0,1)$-matrices more quickly than by Gaussian elimination (or any other general purpose determinant algorithm), then a new generation of (editions of) texts on algebraic graph theory could save the word quite a bit of energy by not ending the treatment of the FKT algorithm when the reduction to determinants has been achieved, but rather go on making prescriptions. There are probably many students who just type the relevant matrix into whatever general purpose package for dense linear algebra they have available, and probably they could do better.
- To sum it up again, does one have to 'shut up and calculate' already when the 'determinant of this matrix' formulation is reached, or should one go on for a little longer with one's conceptural preparations before 'going mechanical'?
0 In any reasonable precise sense of 'not easier' appropriate to the discussion.
1 Digression: while it seems inconceivable that it is elementary, it even seems unknown whether $\mathsf{PfaffianGraphs}$ is an elementary class w.r.t. the traditional single-sorted singleton-signature first-order logic of graphs.
