## Birkhoff’s theorem about doubly stochastic matrices

Birkhoff's theorem states:

The set of $n \times n$ doubly stochastic matrices is a convex set whose extreme points are the permutation matrices

This theorem seems to be commonly attributed to Birkhoff (perhaps also von Neumann). But I recall listening to a talk by Harold Kuhn, where he said that this theorem should actually be attributed to some $P$ where $P \in \{$Jacobi, Dénes Kőnig, Jenő Egerváry, Somebody else?$\}$.

Question: Does anybody know whom Kuhn might have meant, and to whom this theorem should really be attributed?

I would be very happy to learn the connection (also, yes, am embarrassed that despite listening carefully during the talk, I have still forgotten!)

-
 It's strange that Hall is not on the list. – darij grinberg Oct 25 2010 at 23:56

## 2 Answers

See the Wikipedia page for the Birkhoff polytope. It says that equivalent results were obtained by Steinitz in 1894 and by Kőnig in 1916.

-
wow, rapid answer! thanks. Steinitz was the name that I was trying to recall. On the wikipedia page I also noticed a nice result about the volume of the Birkhoff polytope. – S. Sra Oct 25 2010 at 20:26
You meant 1894 for Steinitz. – Thierry Zell Oct 25 2010 at 20:34
But, of course, Steinitz mentioned neither "convex" nor "extreme point" ... since these are later notions. – Gerald Edgar Oct 25 2010 at 20:49
@Thierry Yes, thanks I fixed it. – Greg Kuperberg Oct 25 2010 at 22:43

From Schneider's "The Birkhoff-Egervary-Konig theorem for matrices over lattice ordered abelian groups" after the following theorem is presented

Let $G$ be a lattice ordered abelian group. Every generalized doubly stochastic matrix with elements from $G$ is the sum of generalized permutation matrices.

it is remarked that the theorem for $G=\mathbb{Z}$ was obtained by Konig in 1916 and for $G=\mathbb{R}$ by Birkhoff in 1946 however in 1931 "Egervary proved a result for integral matrices which is more general than Konig's theorem. He observed that by continuity considerations his theorem may be shown to hold for real matrices. Thus in this way one obtains a result which contains Birkhoff's theorem." There are many references in the paper.

-
 thanks Gjergji for the excellent reference. – S. Sra Oct 25 2010 at 20:28 A reference for Konig is Uber Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Math Annalen 77 (1915-16) 453-465. – Gerry Myerson Oct 25 2010 at 22:59