Permanental bounds for nonnegative matrices via decomposition (Q1765888)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Permanental bounds for nonnegative matrices via decomposition
scientific article

    Statements

    Permanental bounds for nonnegative matrices via decomposition (English)
    0 references
    0 references
    23 February 2005
    0 references
    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.
    0 references
    permanent
    0 references
    nonnegative matrix
    0 references
    upper bound
    0 references
    decomposition
    0 references
    scale symmetries
    0 references
    Minc-Brègman bound
    0 references

    Identifiers