Search

An $$m\times n\,\{0,1\}$$ -matrix $$A$$ is said to be totally convertible if there exists a matrix $$B$$ obtained from $$A$$ by changing some 1's in $$A$$ to $$-1$$ 's such that for any submatrix $$A^{\prime }$$ of $$A$$ of order $$m$$ , the corresponding submatrix $$B^{\prime }$$ of $$B$$ satisfies $$\mathrm{per}(xI-A^{\prime })=\det (xI-B^{\prime })$$ . In this paper, motivated by the well-known Pólya's problem, our object is to characterize those totally convertible matrices. Associate a matrix $$A$$ with a bipartite graph $$G^{*}_A$$ . We first prove that a square matrix $$A$$ is totally convertible if and only if $$G^{*}_A$$ is Pfaffian, and then we generalize this result to an $$m\times n$$ $$\{0,1\}$$ -matrix. Moreover, the characterization of a totally convertible matrix provides an equivalent condition to compute the permanental polynomial of a bipartite graph by the characteristic polynomial of the skew adjacency matrix of its orientation graph. As applications, we give some explicit expressions of the permanental polynomials of two totally convertible matrices by the technique of Pfaffian orientation. [ABSTRACT FROM AUTHOR]