Multidimensional permanents of polystochastic matrices

• Published in: Linear algebra and its applications 2020-02, Vol.586, p.89-102
• Main Authors: Child, Billy, Wanless, Ian M.
• Format: Article
• Language: English
• Subjects: Apexes; Birkhoff polytope; Hypercube; Hyperplanes; Linear algebra; Mathematical analysis; Matrix methods; Permanent; Permutations; Polystochastic; Transversal
• ISSN: 0024-3795; 1873-1856
• DOI: 10.1016/j.laa.2019.10.008

A d-dimensional matrix is called 1-polystochastic if it is non-negative and the sum over each line equals 1. Such a matrix that has a single 1 in each line and zeros elsewhere is called a 1-permutation matrix. A diagonal of a d-dimensional matrix of order n is a choice of n elements, no two in the same hyperplane. The permanent of a d-dimensional matrix is the sum over the diagonals of the product of the elements within the diagonal. For a given order n and dimension d, the set of 1-polystochastic matrices forms a convex polytope that includes the 1-permutation matrices within its set of vertices. For even n and odd d, we give a construction for a class of 1-permutation matrices with zero permanent. Consequently, we show that the set of 1-polystochastic matrices with zero permanent contains at least nn3/2(1/2−o(1)) 1-permutation matrices and contains a polytope of dimension at least cn3/2 for fixed c,d and even n→∞. We also provide counterexamples to a conjecture by Taranenko [11] about the location of local extrema of the permanent. For odd d, we give a construction of 1-permutation matrices that decompose into a convex linear sum of positive diagonals. These combine with a theorem of Taranenko [11] to provide counterexamples to a conjecture by Dow and Gibson [4] generalising van der Waerden's conjecture to higher dimensions.