Implementation And Application Of An Algorithm For Pólya’s Permanent Problem

Permanent is an invariant of matrices defined similar to determinant. It has wide ap-plications in combinatorics, statistical physics, molecular chemistry, communication etc.The calculation of permanent is much harder than determinant. In fact it’s#P complete incounting problems, much like NP complete in decision problems.Similarities between permanent and determinant play an important role in researchof permanent. Three approaches have been used so far: Laplace expansion; reduction todeterminant of random matrices; reduction to determinant by changing signs of entries.First two approaches are taken quite often. The third approach is introduced by Pólya inearlylastcenturybyaskingtheproblemofwhetherwecanchangesignsofsomeentriesina matrix such that the determinant of new matrix gives the permanent of original matrix,namely Pólya’s permanent problem. Nearly a century later a breakthrough is made aboutthis problem. In1999a polynomial algorithm for this problem is published in Annals ofMathematics[1–3].In this article we give a systematic description of this algorithm. An matlab programisalsoimplemented. Basedonlargeamountofnumericalexperiments,weresearchsparsematrix’s Pólya convertibility.First we review some properties of permanent especially in relation to structures ingraph theory such as cycle covering, perfect matching and complete Sachs graph. Weintroduce Pfaffian orientation of graph and show the equivalence between Pfaffian orien-tation of bipartite graph and Pólya’s permanent problem. Using results in [1–3], we givea detailed and complete description of the algorithm for Pólya’s permanent problem andfix some minor errors in original paper. Finally we give an implementation in matlab.For3-regularmatrixcorrespondingtofullereneinchemistry, weexaminethechangeof ratio of Pólya convertible matrices when transforming from2-regular to3-regular. Form n2grid glued by two planar m n grids, we examine the relationship betweenPólya’s convertibility and the number of crossing edges. By these experiments, we getsome empirical results between Pólya’s convertibility and sparsity of matrices.At last, we give an upper bound for permanent of nonnegative matrix which is an improvement of one result in Minc’s Permanent.