Generalizations of the Birkhoff-von Neumann Theorem

Question

The famous Birkhoff-von Neumann theorem asserts that every doubly stochastic matrix can be written as a convex combination of permutation matrices.

The question is to point out different generalizations of this theorem, different "non-generalizations" namely cases where an expected generalization is false, and to briefly describe the context of these generalizations.

A related MO question: Sampling from the Birkhoff polytope

Answer 1

I am cheating a little to give this answer, because I am fairly sure that it is part of Gil's motivation in asking the question. The most natural generalization of the Birkhoff hypothesis to quantum probability is only true for qubits. (It might also be true for a qubit tensor a classical system; I did not check that case.)

A quantum measurable space is a von Neumann algebra. We are most interested in the finite-dimensional case, where classically "measurable space" is just a fancy name for the random variables on a finite set. A finite-dimensional von Neumann algebra is a direct sum of matrix algebras. In particular, $M_2$ is called a qubit and $M_d$ is called a qudit.

To make a long story short, the Birkhoff hypothesis can be stated for a direct sum of $a$ copies of $M_b$, or $aM_b$. In this setting, a doubly stochastic map $E$ is a linear map from $aM_b$ to itself that preserves trace, that preserves the identity element, and that is completely positive. In this setting, $E$ is completely positive if it takes positive semidefinite elements of $aM_b$ to positive semidefinite elements, and if $E \otimes I$ also has that property on the algebra $aM_b \otimes N$ for another von Neumann or $C^*$-algebra $N$. The natural analogue of permutation matrices are the *-algebra automorphisms of $aM_b$. These are permutations of the matrix blocks, composed with maps of the form $E(x) = uxu^*$, where $u$ is a unitary element of $aM_b$. The question as before is whether the doubly stochastic maps are the convex hull of the automorphisms.

This Birkhoff hypothesis is true for $M_2$, false for $M_d$ for $d \ge 3$, and I should check it for $nM_2$. It is true for $aM_1 = a\mathbb{C}$, because then it is the usual Birkhoff-von Neumann theorem.

I am left wondering about two infinite classical versions of Birkhoff's theorem, for the algebras $\ell^\infty(\mathbb{N})$ and $L^\infty([0,1])$. In the former case, one would ask whether any stochastic map that preserves counting measure (even though counting measure is not normalized) is an infinite convex sum of permutations of $\mathbb{N}$. In the latter case, whether any stochastic map that preserve Lebesgue measure is a convex integral of measure-preserving permutations of $[0,1]$. Addendum: At least the discrete infinite case is addressed, with generally positive results, in this review and in this older review. The older paper also raises the continuous question but with no results. However, with some more Googling I found this counterexample paper.

---

Since Gil asks for a reference, a recent one is Unital Quantum Channels - Convex Structure and Revivals of Birkhoff's Theorem, by Mendl and Wolf.

---

Here also is a more orthodox combinatorial generalization of the Birkhoff theorem, and also another case that I once encountered that is between a generalization and a non-generalization. Since Gil now offers a bounty, maybe it's better to merge this answer with the other one.

A doubly stochastic matrix can be interpreted as a flow through a directed graph, with unit capacities. (See Unimodular matrix in Wikipedia; I learned about this long ago from Jesus de Loera.) Any such graph has a polytope of flows, called a network flow polytope. Any network flow polytope has integer vertices, because it is a totally unimodular polytope.

A totally unimodular polytope is a polytope whose facets have integer equations, and with the property that any maximal, linearly independent collection of facets intersects in an integer point because their matrix has determinant $\pm 1$. In particular the vertices are such intersections, so the vertices are all integral. This is a vast generalization of Birkhoff's theorem that comes from generalizing one of the proofs of Birkhoff's theorem.

Example: An alternating-sign matrix is equivalent to a square ice orientation of a square grid. The square ice orientations can be defined by a network flow, so you obtain an alternating-sign-matrix polytope. The generalized Birkhoff theorem in this case says that every vertex of the polytope is an alternating-sign matrix, in fact that every integer point of the $n$-dilated polytope is a sum of $n$ alternating-sign matrices.

---

The other case that I encountered was the polytope of fractional perfect matchings of a non-bipartite set with $2n$ elements. By contrast, the Birkhoff polytope is the case of a bipartite set with $n$ elements of each type. By definition, it is the polytope of non-negative weights assigned to the edges of the complete graph on $2n$ vertices, such that the total weight at each vertex is 1. Strictly speaking, the Birkhoff theorem is false; not every vertex is a perfect matching. Instead, all of the vertices are combinations of matched pairs, and odd cycles with weight $\frac12$.

At first glance this looks like bad news for the application of computing a perfect matching or the optimum perfect matching of a graph. Indeed, if instead you take the convex hull of the perfect matchings, the result is a polytope with exponentially many facets. However, a good algorithm exists anyway; there is a version of the simplex algorithm that only ever uses polynomially many of the facets.

Answer 2

There is a relevant paper by Gromova regarding high dimensional matrices:

Gromova, M. B., The Birkhoff-von Neumann theorem for polystochastic matrices. (Russian) Operations research and statistical simulation, No. 2 (Russian), pp. 3–15, 149. Izdat. Leningrad. Univ., Leningrad, 1974. It was translated to English in the early 90s.

The MR review by by George P. Barker reads: In Section 1 the author gives the basic definitions and introduces a notion of the spectrum of a multidimensional matrix as a vector. The basic theorem which gives necessary and sufficient conditions for a vector to be the spectrum of an extremal matrix is then formulated. The necessary condition of the basic theorem consists of a direct generalization of the Birkhoff-von Neumann theorem.

A related paper is: Brualdi, R. A.; Csima, J. Extremal plane stochastic matrices of dimension three. Linear Algebra and Appl. 11 (1975), no. 2, 105–133.

and an older paper with some relevance is: Jurkat, W. B.; Ryser, H. J. Extremal configurations and decomposition theorems. I. J. Algebra 8 1968 194–222.

Answer 3

A non-combinatorial non-generalization occurs in the Monge-Kantorovich optimal transport problem. In the finite, combinatorial, version, there are $N$ sources and $N$ destinations. One wants to transport one object from each source to a different destination. Different source-destination combinations have different costs, represented by an $N\times N$-matrix $C$. The problem is now to find the cheapest (in sum) way to get the objects from the sources to the destinations. Formally, one wants to find a cost-minimizing permutation matrix. One can solve the problem as a linear programming problem over the set of doubly stochastic matrices. A linear programming problem has a solution at extreme points, so the Birkhoff-von Neumann theorem guarantees that this approach works.

In the measure theoretic optimal transport problem (I'm not using the most general formulation), one is given two nonempty compact metric spaces $S\times T$, a continuous function $c:S\times T\to\mathbb{R}$ and two Borel probability measures $\mu_S$ and $\mu_T$ on $S$ and $T$ respectively. Let $P$ be the set of all Borel probability measures on $S\times T$ with $S$-marginal $\mu_S$ and $T$-marginal $\mu_T$. The set $P$ generalizes the doubly stochastic matrices and is a convex and weak*-compact set. The optimal transport problem is now solving the linear programming problem $$\min_{\mu\in P}\int c~d\mu.$$ The problem has a solution and there is a solution concentrated at an extreme point of $P$. But the extreme points of $P$ are in general not measures concentrated on the graph of a measure-preserving function, and so there is a natural generalization of the Birkhoff-von Neumann theorem that fails

Answer 4

I have found a paper on a generalization of the Birkhoff-von Neumann theorem here:

http://cowles.econ.yale.edu/conferences/2009/sum-09/theory/che.pdf (Wayback Machine)

The authors are Eric Budish, Yeon-Koo Che, Fuhito Kojima, and Paul Milgram.

Here is the Abstract:

The Birkhoff-von Neumann Theorem shows that any bistochastic matrix can be written as a convex combination of permutation matrices. In particular, in a setting where n objects must be assigned to n agents, one object per agent, any random assignment matrix can be resolved into a deterministic assignment in accordance with the specified probability matrix. We generalize the theorem to accommodate a complex set of constraints encountered in many real-life market design problems. Specifically, the theorem can be extended to any environment in which the set of constraints can be partitioned into two hierarchies. Further, we show that this bihierarchy structure constitutes a maximal domain for the theorem, and we provide a constructive algorithm for implementing a random assignment under bihierarchical constraints. We provide several applications, including (i) single-unit random assignment, such as school choice; (ii) multi-unit random assignment, such as course allocation and fair division; and (iii) two- sided matching problems, such as the scheduling of inter-league sports matchups. The same method also finds applications beyond economics, generalizing previous results on the minimize makespan problem in the computer science literature

I have also found a master's thesis that involved generalization from a matrix to a hyper matrix, a matrix in higher dimensions. So one example would be a cubic array of numbers instead of a square. He proves a generalization to the three dimensional matrices which are called blocks. There are some open questions there as well. I found it interesting as I have wondered about extending the two dimensions of matrices to three coordinates and seeing what happened. It is available here:

https://ritdml.rit.edu/dspace/bitstream/1850/5967/1/NReffThesis05-18-2007.pdf

Answer 5

The remaining case is actually H4. For this case the conjecture is false, since I found 1063 orbits of facets. In the same paper, it is claimed that for F4 the convex hull is given by the Birkhoff tensors. But this is false since I found another orbit defined by a matrix of rank 3. See details there (Wayback Machine)

Answer 6

Dave Perkinson and coauthors have studied sub-polytopes of the Birkhoff-von Neumann polytope, in the sense that they consider convex hulls of the permutation matrices corresponding to certain subgroups of $S_n$. See, e.g., his paper with Jeff Hood (Wayback Machine) for the case $A_n$.

Answer 7

There exists a "true" generalization within quantum theory given by John Watrous in arXiv 0807.2668v1, where it is shown that a mixture of a double stochastic channel with a completely depolarizing channel satisfies the "quantum version" of the Birkhoff's theorem (convex combination of unitary channels).

Answer 8

On recent extension of Birkhoff's theorem is by Ellis, Friedgut and Pilpel. The context is Erdos-Ko-Rado theorems for permutations. See Section 5 and especially Definition 17 and Theorem 29 of this paper.

Let me also mention the paper The alternating sign matrix polytope, by Jessica Striker, regarding the alternating-sign-matrix polytope.

A conjecture extending Birkoff von Neumann theorem to finite Coxeter groups (The A_n family gives the original case) which is proved in all cases but one can be found in this paper by N. McCarthy, D. Ogilvie, I. Spitkovsky, and N. Zobin.

Answer 9

Not sure if this is what you're looking for, but the statement for symmetric doubly stochastic matrices is that every such one can be written as a convex combination of $(\sigma + \sigma^t)/2$ where $\sigma$ is a permutation matrix. Not all of these are necessarily vertices, but it definitely is not an integral polytope, so maybe this would be a "non-generalization."

Answer 10

The book Combinatorial Matrix Classes by Richard Brualdi has a number of generalizations of a combinatorial nature, around Chapter 8. Also, the least common denominator of the vertices of a rational polytope is related to the period of the Ehrhart quasipolynomial, see for example Exercise 3.25 in the book of Beck and Robins, http://math.sfsu.edu/beck/papers/noprint.pdf .

Answer 11

The asymptotic quantum Birkhoff conjecture by Smolin, Verstraete, and Winter was disproved by Haagerup and Musat. The following paper http://www.iro.umontreal.ca/~qip2012/SUBMISSIONS/short/qip2012_submission_105.pdf presents the state of the art and gives some references.

Answer 12

The paper DESIGNING RANDOM ALLOCATION MECHANISMS: THEORY AND APPLICATIONS by ERIC BUDISH, YEON-KOO CHE, FUHITO KOJIMA, AND PAUL MILGROM Also describes an extension of the Birkhoff-von Neumann theorem.

This is related to the following: There is some relation between the Birkhoff-von Neumann theorem and Scarf's theorem that asserts that balanced games have non empty core. The fact that that the houses allocation game is balanced follows directly from B-vN theorem. The fact that the game describing the stable-marriage problem requires a certain generalization.

Answer 13

The theorem still holds if we ask each row and column to sum to some integer $m$; permutation matrices are replaced with zero-one matrices having the same constraints. See Watkins and Merris, Convex Sets of Doubly Stochastic Matrices and Lewandowski, Liu and Liu, An Algorithmic Proof of a Generalization of the Birkhoff - Von Neumann Theorem.

Answer 14

There is also a characterization here for non-square doubly stochastic matrices: https://www.jstor.org/stable/4355884 by R. M. Caron, Xin Li, P. Mikusiński, H. Sherwood and M. D. Taylor from University of California.

"An $n \times m$ non-negative matrix with uniform row sum $m$ and column sum $n$ is called a "doubly stochastic" matrix. When $n = m$, such a matrix is a scale multiple of a doubly stochastic matrix in its classical sense. Garrett Birkhoff proved a theorem characterizing all classical extremal doubly stochastic matrices as permutation matrices. We will discuss the characterization of the extremal matrices for nonsquare "doubly stochastic" matrices in the spirit of Birkhoff's theorem."

Answer 15

From Roger A. Horn "Topics in Matrix Analysis", section 3.2 page 164-165.

A matrix $Q$ is said to be doubly substochastic if its entries are nonnegative and all its row and column sums are at most one.

The doubly stochastic matrix $\begin{bmatrix} Q & I-D_r\\I-D_c & Q^T\end{bmatrix}$ is a dilation of $Q$, where $D_r$ and $D_c$ are diagonal matrices with the row and column sums of $Q$ respectively.

A matrix $P$ is said to be a partial permutation matrix if it has at most one nonzero entry in each row and column, and these nonzero entries (if any) are all $1$.

The generalization of the Birkhoff-von Neumann theorem for substochastic matrices is

Every doubly substochastic matrix is a finite convex combination of partial permutation matrices. Conversely, a finite convex combination of partial permutation matrices is evidently double substochastic.

This generalization reduces to the original theorem, because we can construct a doubly stochastic dilation of the doubly substochastic matrix $Q$ as shown above. The original theorem also follows from the generalization, because a convex combination of doubly substochatic matrices is doubly stochastic exactly if all contribution matrices are doubly stochastic themselves, and the only doubly stochastic partial permutation matrices are the permutation matrices.

Answer 16

A coupling between two probability spaces $(X, \mu)$ and $(Y, \nu)$ is a probability measure on $X \times Y$ with marginals $\mu$ and $\nu$. The space of couplings between two given measures is naturally a compact convex space, so it is natural to ask what its extreme points are. Birkhoff's theorem is the answer to this question in the case of uniform measures on $n$-element sets: the extreme couplings are supported on graphs of bijections. The fully general case appears to be quite complicated, but there is a somewhat explicit description of extreme couplings between probability measures on finite sets. The result is as follows:

Call a subset $S \subset X \times Y$ acyclic if it doesn't contain a subset of the form $\{(x_1, y_1), (x_1, y_2), (x_2, y_2), \dots, (x_i, y_i), (x_i, y_{i+1}), \dots, (x_{n}, y_1)\}$ for any $n \ge 2$, $x_1,\dots,x_n \in X, y_1,\dots,y_n \in Y$, and all pairs $(x_i, y_i), (x_i, y_{i+1})$ are distinct.

For a coupling $\kappa$ between two finite probability spaces the following are equivalent:

1. $\kappa$ is extreme
2. $\kappa$ is the unique coupling between $\mu$ and $\nu$ with support contained in $S := \operatorname{supp} \kappa$
3. $S$ is acyclic

Acyclic sets can be described in terms of the following construction. For any set $X^\prime$, any map $f : X^\prime \to Y$, and any acyclic set $S \subset X \times Y$, the set $S \sqcup \Gamma_f \subset (X \sqcup X^\prime) \times Y$ is acyclic, where $\Gamma_f$ is the graph of $f$. This follows from the fact that any cycle only involves columns and rows with at least two elements. Similarly, for any $g : Y^\prime \to X$, $S \sqcup \Gamma_g \subset X \times (Y \sqcup Y^\prime)$ is acyclic. In terms of this construction we can add another condition equivalent to 1-3 above:

4. $S$ can be constructed starting from $\varnothing \subset \varnothing \times \varnothing$ by adjoing graphs of maps, as described above, or empty columns or rows.