On the Pólya permanent problem over finite fields (Q607375): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Changed an Item
ReferenceBot (talk | contribs)
Changed an Item
(3 intermediate revisions by 3 users not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1976669345 / rank
 
Normal rank
Property / arXiv ID
 
Property / arXiv ID: 1003.1984 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4858541 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4862693 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Conversion of the Determinant into the Permanent / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3974962 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A note on the determinant and permanent problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Immanant preserving and immanant converting maps / rank
 
Normal rank
Property / cites work
 
Property / cites work: The complexity of theorem-proving procedures / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5343356 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5562013 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The asymptotic number of (0,1)-matrices with zero permanent / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4198056 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5748673 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4142699 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5532610 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5633357 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A note on immanant preservers / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the relation between the determinant and the permanent / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4184984 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Permanents, Pfaffian orientations, and even directed circuits / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3851094 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3665103 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4311535 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The complexity of computing the permanent / rank
 
Normal rank
Property / cites work
 
Property / cites work: Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Permanent and determinant / rank
 
Normal rank

Revision as of 11:41, 3 July 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
    0 references
    0 references
    0 references
    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

    Identifiers