The previous talk in the series is here. The next talk in the series is here.
The permanent of a square matrix is like the determinant except that you don’t multiply by the signs of the permutations. Since the determinant arises very naturally, the ‘simpler’ definition of the permanent actually leads to a quantity that is less natural and very hard to calculate. However, it still has its uses: for example, the permanent of a 01-matrix A is the number of perfect matchings in the bipartite graph of which A is the bipartite adjacency matrix. Brégman’s theorem is an upper bound for the permanent of a 01-matrix. It says that if the ith row contains ri 1s, then the permanent is at most the product over all i of (ri!)1/ri. In this video I present a short and very clever proof of the theorem due to Jaikumar Radhakrishnan that uses entropy. We first give an introduction and brief discussion of permanents, before moving on to the statement and proof of Brégman’s theorem.
This video was produced by Tim Gowers as part of his Part III course at the University of Cambridge. Printed notes for this course are available here.