Permanental bounds for nonnegative matrices via decomposition (Q1765888)

The author continues his significant and successful quest for useful upper bounds for the permanents of non-negative matrices. Let \(\gamma(0)=0\) and \(\gamma(k)=(k!)^{1/k}\) for \(k\geq 1\). For any non-negative matrix \(A\) let \(A^*=[a_{ij}^*]\) be the matrix obtained from \(A\) by sorting the entries in each row into non-increasing order. The main result of this paper is that \[ \text{ per}(A)\leq\prod_i\sum_k a_{ik}^*(\gamma(k)-\gamma(k-1)). \] This result, which agrees with the Minc-Brègman bound when applied to binary matrices, can be further improved by the technique of sharpening developed in the author's earlier papers [Linear Multilinear Algebra 47, 77--91 (2000; Zbl 0977.15009), ibid. 51, No. 4, 319--337 (2003; Zbl 1045.15005)]. Those papers contain several other upper bounds which the author claims are inferior to the new bound above. The performance of all bounds is compared on two test cases. The method of proof for the new bound is interesting in its own right. It is a departure from earlier papers, although it grew from an idea of Brouwer. The basic idea is to write each row of \(A\) as a non-negative linear combination of binary vectors (this is the decomposition alluded to in the title). The multilinearity of the permanent is then applied to express \(\text{ per}(A)\) as a non-negative linear combination of permanents of binary matrices. Finally, a known bound on the permanent of binary matrices is used to bound the answer. If the Minc-Brègman bound is used in this last step, the result is the bound quoted above, but other bounds are also discussed.