An entropy proof of Bregman's theorem

Abstract

LetA=(a_{i, j}) be ann^×n0-1 matrix. LetSbe the set of permutationsσof [n] such that a_{i, σ(i)}=1 for i=1, 2,..., n. Then, the permanent ofAis perm(A)=^def|S|. Theorem(Bregman,Soviet Math. Dokl.14(1973), 945-949). If the number of 1's in rowiofAisri, then[formula]A short proof of this theorem was given by Schrijver (J. Combin. Theory Ser. A25(1978), 80-83); Alon and Spencer ("The Probabilistic Method," Wiley/Interscience, New York, 1992), obtained a similar proof by analyzing a randomized procedure for estimating the permanent. In this note we present a proof based on entropy.