Bregman–Minc inequality

In discrete mathematics, the Bregman–Minc inequality, or Bregman's theorem, allows one to estimate the permanent of a binary matrix via its row or column sums. The inequality was conjectured in 1963 by Henryk Minc and first proved in 1973 by Lev M. Bregman. Further entropy-based proofs have been given by Alexander Schrijver and Jaikumar Radhakrishnan. The Bregman–Minc inequality is used, for example, in graph theory to obtain upper bounds for the number of perfect matchings in a bipartite graph.

Statement

The permanent of a square binary matrix $A = (a_{ij})$ of size $n$ with row sums $r_i = a_{i1} + \cdots + a_{in}$ for $i=1, \ldots , n$ can be estimated by

$\operatorname{per}A \leq \prod_{i=1}^n (r_i!)^{1/r_i}.$

The permanent is therefore bounded by the product of the geometric means of the numbers from $1$ to $r_i$ for $i=1, \ldots , n$. Equality holds if the matrix is a block diagonal matrix consisting of matrices of ones or results from row and/or column permutations of such a block diagonal matrix. Since the permanent is invariant under transposition, the inequality also holds for the column sums of the matrix accordingly.

Application

File:Perfect matching qtl1.svg

A binary matrix and the corresponding bipartite graph with a possible perfect matching marked in red. According to the Bregman–Minc inequality, there are at most 18 perfect matchings in this graph.

There is a one-to-one correspondence between a square binary matrix $A$ of size $n$ and a simple bipartite graph $G = (V \, \dot\cup \, W, E)$ with equal-sized partitions $V = \{ v_1, \ldots , v_n \}$ and $W = \{ w_1, \ldots , w_n \}$ by taking

$a_{ij} = 1 \Leftrightarrow \{ v_i, w_j \} \in E.$

This way, each nonzero entry of the matrix $A$ defines an edge in the graph $G$ and vice versa. A perfect matching in $G$ is a selection of $n$ edges, such that each vertex of the graph is an endpoint of one of these edges. Each nonzero summand of the permanent of $A$ satisfying

$a_{1\sigma(1)} \cdots a_{n\sigma(n)} = 1$

corresponds to a perfect matching $\{ \{ v_1, w_{\sigma(1)} \}, \ldots , \{ v_n, w_{\sigma(n)} \} \}$ of $G$. Therefore, if $\mathcal{M}(G)$ denotes the set of perfect matchings of $G$,

$| \mathcal{M}(G) | = \operatorname{per}A$

holds. The Bregman–Minc inequality now yields the estimate

$| \mathcal{M}(G) | \leq \prod_{i=1}^n (d(v_i)!)^{1/d(v_i)},$

where $d(v_i)$ is the degree of the vertex $v_i$. Due to symmetry, the corresponding estimate also holds for $d(w_i)$ instead of $d(v_i)$. The number of possible perfect matchings in a bipartite graph with equal-sized partitions can therefore be estimated via the degrees of the vertices of any of the two partitions.

Related statements

Using the inequality of arithmetic and geometric means, the Bregman–Minc inequality directly implies the weaker estimate

$\operatorname{per}A \leq \prod_{i=1}^n \frac{r_i+1}{2},$

which was proven by Henryk Minc already in 1963. Another direct consequence of the Bregman–Minc inequality is a proof of the following conjecture of Herbert Ryser from 1960. Let $k$ by a divisor of $n$ and let $\Lambda_{kn}$ denote the set of square binary matrices of size $n$ with row and column sums equal to $k$, then

$\max_{A \in \Lambda_{kn}} \operatorname{per}A = (k!)^{n/k}.$

The maximum is thereby attained for a block diagonal matrix whose diagonal blocks are square matrices of ones of size $k$. A corresponding statement for the case that $k$ is not a divisor of $n$ is an open mathematical problem.

See also

• Computing the permanent