Pólya convertibility problem for symmetric matrices
type: Item
instance of: scholarly article
title: Pólya convertibility problem for symmetric matrices
zbMATH Open document ID: 1268.15004
DOI: 10.1134/S0001434612110053
published in: Mathematical Notes
publication date: 2013-04-15T00:00:00Z
review text: 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 t…
Mathematics Subject Classification ID: 15A15
Mathematics Subject Classification ID: 15B57
zbMATH DE Number: 6153794
zbMATH Keywords: determinant
zbMATH Keywords: permanent
zbMATH Keywords: symmetric matrices
author: Alexander Guterman
author: Gregor Dolinar
author: Bojan Kuzma
reviewed by: Dmitry Artamonov
MaRDI profile type: Publication
cites work: On the Conversion of the Determinant into the Permanent
cites work: Immanant preserving and immanant converting maps
cites work: On the relation between the determinant and the permanent
cites work: Q3974962
cites work: On the Pólya permanent problem over finite fields
cites work: Pólya's permanent problem
cites work: An exploration of the permanent-determinant method
cites work: The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
cites work: Dimer problem in statistical mechanics-an exact result
cites work: On the Relation Between the Determinant and the Permanent on Symmetric Matrices
cites work: On the Conversion of an Immanant into Another on Symmetric Matrices
cites work: Subspaces where an immanant is convertible into its conjugate∗
cites work: Conversion of the Permanent into the Determinant
cites work: A characterization of convertible (0,1)-matrices
cites work: An Identity Between Permanents and Determinants
full work available at URL: s0001434612110053
OpenAlex ID: W2069821933
description: scientific article; zbMATH DE number 6153794