On the Pólya permanent problem over finite fields (Q607375): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q308665 |
Changed an Item |
||
Property / author | |||
Property / author: Alexander E. Guterman / rank | |||
Normal rank |
Revision as of 14:36, 12 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the Pólya permanent problem over finite fields |
scientific article |
Statements
On the Pólya permanent problem over finite fields (English)
0 references
22 November 2010
0 references
This paper is motivated by a classical problem of Pólya, which asks for what matrices there exists a transformation that enables the permanent to be calculated as a determinant. A comprehensive reference on the subject, overlooked by the present authors, is \textit{W. McCuaig}'s ``Pólya's permanent problem'' [Electron. J. Comb. 11, No.~1, R79 (2004; Zbl 1062.05066)]. Let \(\mathbb{F}\) be a field of characteristic other than \(2\) and let \(M_n(\mathbb{F})\) denote the \(n\times n\) matrices over \(\mathbb{F}\). The authors' main result is that if \(\mathbb{F}\) is finite and sufficiently large (relative to \(n\)) then there is no bijection \(\Phi:M_n(\mathbb{F})\rightarrow M_n(\mathbb{F})\) satisfying \(\mathrm{per}\,A=\det\Phi(A)\). They prove this by showing that there are more matrices with zero determinant (a class it is easy to count exactly) than there are matrices with zero permanent (a class for which they find upper and lower bounds on the size). When \(\mathbb{F}\) is infinite they show that such a bijection \(\Phi\) does exist. They also show that for any field \(\mathbb{F}\) of finite order \(q\) (of characteristic other than \(2\)) and for any \(\alpha\in\mathbb{F}\), the probability that \(\det A=\alpha\) is \(1/q+O(1/q^2)\), when \(A\) is chosen uniformly at random from \(M_n(\mathbb{F})\). The probability that \(\mathrm{per}\,A=\alpha\) is also \(1/q+O(1/q^2)\).
0 references
permanent
0 references
determinant
0 references
Polya's problem
0 references
finite field
0 references