The Setting
The permanent of an matrix is compared with determinants of matrices whose entries are affine linear forms in the permanent’s variables.
For a finite index set , let denote the polynomial ring with one variable for each .✦ For , put and let be its permutation group, with . The permanent is (1)✦ The matrix variable indices for size are the ordered pairs , where is the row index and is the column index.✦
An affine matrix pencil of size in the variables indexed by is a matrix whose constant and linear coefficient matrices and are arbitrary elements of . Writing for the family of linear coefficient matrices, its determinant is the polynomial (2)✦
An exact determinantal representation of size of a polynomial is a family of matrices in , with , satisfying (3); its existence is denoted by .✦ (3)
For a multi-index , write for the coefficient of in . A border determinantal representation of size of a polynomial is a sequence of families of matrices in , with , satisfying (4) for every multi-index , where ; its existence is denoted by .✦ (4)
The Claim
Theorem 1. Let with . If holds, then (5)✦ If holds, then (6)✦
In the paper, the result reads: there exist absolute constants and such that for every integer , where denotes border determinantal complexity, and one may take and .
What Is Checked
The bounds (5) and (6) are stated over the complex permanent (1), with positive determinant size, exact equality (3) or sequential convergence of every coefficient (4), and unrestricted affine matrix entries.