Permanents, Pfaffian orientations, and even directed circuits (Q1971908): Difference between revisions

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.