# zbMATH — the first resource for mathematics

Permanents, Pfaffian orientations, and even directed circuits. (English) Zbl 0947.05066
The paper deals with the following problem asked by Pólya in 1913: Given a 0-1 matrix $$A$$, is there a matrix $$B$$ obtained from $$A$$ by changing signs of some $$1$$’s to $$-1$$’s so that the permanent of $$A$$ equals the determinant of $$B$$? Such $$B$$ is called a Pólya matrix for $$A$$. The paper provides a structural characterization of matrices for which Pólya’s matrices exist. This characterization is used to construct a polynomial-time algorithm to decide whether a matrix has its Pólya matrix.

##### MSC:
 05C75 Structural characterization of families of graphs 15A15 Determinants, permanents, traces, other special matrix functions 05C85 Graph algorithms (graph-theoretic aspects) 68Q25 Analysis of algorithms and problem complexity 68R10 Graph theory (including graph drawing) in computer science 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C38 Paths and cycles 05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.) 05C20 Directed graphs (digraphs), tournaments
Full Text: