An entropy proof of Bregman's theorem

Radhakrishnan, Jaikumar (1997) An entropy proof of Bregman's theorem Journal of Combinatorial Theory, Series A, 77 (1). pp. 161-164. ISSN 0097-3165

Full text not available from this repository.

Official URL:

Related URL:


LetA=(ai, j) be ann×n0-1 matrix. LetSbe the set of permutationsσof [n] such that ai, σ(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.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
ID Code:57644
Deposited On:29 Aug 2011 08:35
Last Modified:29 Aug 2011 08:35

Repository Staff Only: item control page