New permanental bounds for Ferrers matrices (Q636241): Difference between revisions

Let \(r_1,\dots,r_n\) be the row sums of a \((0,1)\)-matrix \(A=[a_{ij}]\) of order \(n\). If \(r_1\leq r_2\leq \cdots \leq r_n\) and \(a_{ij}=1\) for all \(1\leq j\leq r_i\) then \(A\) is a Ferrers matrix. The permanent of a Ferrers matrix is \(\prod_i(r_i-i+1)\). This paper gives a variety of upper and lower bounds for this quantity, expressed in terms of \(n\) and quantities such as \(\alpha=\sum_i r_i\), \(\beta=\sum_i r_i^2\), \(\gamma=\sum_i (i-1)r_i\) and \(\delta=\sum_i r_i^{1/2}\). For example, it is shown that per\(\,A\geq n^{(\alpha-{n+1\choose2})/(n-1)}\). Many of the bounds are proved using various estimates of the ratio or difference between the arithmetic and geometric means. These strengthenings of the arithmetic-geometric mean inequality are not original, but are collected here from various sources and could be independently useful. Likewise, the authors survey the known bounds on permanents of non-negative matrices, and this provides a useful general reference. It should be noted that there is a typo in Theorem 8.1. Rather than ``non-singular'' the condition should be that the permanent is non-zero.