Pólya convertibility problem for symmetric matrices (Q1946423): Difference between revisions

Let \(A\) be an \(n\times n\) matrix. Its determinant and permanent are defined by the formulas \[ \det A=\sum_{\sigma\in S_n}(-1)^{\sigma} a_{1,\sigma(1)}\cdots a_{n,\sigma(n)},\,\,\,\text{per}A=\sum_{\sigma\in S_n} a_{1,\sigma(1)}\cdots a_{n,\sigma(n)}. \] Starting from Pólya the following question is investigated: Is it possible to convert the permanent to the determinant? For \(n=2\), such a transformation was found by Pólya. But further the nonexistence of such a transformation for all matrices was proved for several classes of transformations. In the paper under review, matrices with entries \(0\) or \(1\) are considered. Let \(M_n\) be the set of such matrices and let \(S_n\) be the set of symmetric matrices of such type. For a matrix \(A \in M_n\) denote \(v(A)\) the number of nonzero entries. A matrix \(A\) is called (symmetrically) convertible if there exists a (symmetric) \(n\times n\) matrix \(X\) with entries \(\pm 1\) such that \[ \text{per}A=\det XA. \] A matrix \(A\) is symmetrically weakly convertible if \[ \text{per}A=\pm \det XA. \] \textit{P. M. Gibson} [Proc. Am. Math. Soc. 27, 471--476 (1971; Zbl 0194.06002)] has found an upper bound \(v(A)\leq \Omega_n:=(n^2+3n-2)/2\) for the number of nonzero entries of a convertible matrix \(A\). The subject of the paper under review is an analogue of this result in the case of symmetric matrices. Since a permanent of a \((0,1)\)-matrix is nonnegative, it is natural to consider its symmetric weak-convertability. \textit{C. H. C. Little} [J. Comb. Theory, Ser. B 18, 187--208 (1975; Zbl 0281.05013)] posed the following three problems: \textbf{1.} Determine the minimal integer \(\Omega_n\) such that for any \(A\in S_n\) with \(v(A)>\Omega_n\), \(A\) is not symmetrically weakly convertible. \textbf{2.} Determine the maximal integer \(\omega_n\) such that for any \(A\in S_n\) with \(v(A)<\omega_n\), \(A\) is symmetrically weakly-convertible \textbf{3.} If \(\omega_n\leq v(A)\leq \Omega_n\) what can we say about the symmetric weak-convertibility of \(A\)? The main result of the paper under review is the solution of these problems.