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: http://www.sciencedirect.com/science/article/pii/S...

Related URL: http://dx.doi.org/10.1006/jcta.1996.2727

## 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.

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