On lower bounds for permanents of (0,1) matrices
Henryk Minc · Proceedings of the American Mathematical Society · 1969
HENRYK MINCwhere r,= 2*-i a«v» î = L • ■ • » n-Several upper bounds, significantly improving the upper bound in (1), have been obtained in the last few years.On the other hand, nontrivial lower bounds for permanents of (0, 1) matrices in terms of row sums, column sums, or some other simple functions of the matrix, are difficult to establish.Indeed the permanent of an «-square (0, 1) matrix may be zero although all its row sums are « -1.The first result improving the lower bound in (1) was obtained by P. Hall [3].In the context of «-square (0, 1) matrices, Hall's theorem states that per(^4)>0 if and only if every kXn submatrix of A, k=l, • • • , «, contains at least k nonzero columns.M. Hall [2] improved the above result and showed that if A is an «-square (0, 1) matrix with a positive permanent and if r.-^i, * = 1, • • • , «, for some positive integer t, then(2) per(^) ^ il.The inequality (2) does not provide a good lower bound if « is substantially greater than t.In fact, it is known [8] that if every row