Birkhoff's theorem about doubly stochastic matrices - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T04:01:19Z http://mathoverflow.net/feeds/question/43569 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/43569/birkhoffs-theorem-about-doubly-stochastic-matrices Birkhoff's theorem about doubly stochastic matrices suVRit 2010-10-25T20:14:19Z 2010-10-25T22:43:06Z <p>Birkhoff's theorem states:</p> <p><em>The set of $n \times n$ doubly stochastic matrices is a convex set whose extreme points are the permutation matrices</em></p> <p>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?$\}$.</p> <p><strong>Question</strong>: Does anybody know whom Kuhn might have meant, and to whom this theorem should really be attributed? </p> <p>I would be very happy to learn the connection (also, yes, am embarrassed that despite listening carefully during the talk, I have still forgotten!)</p> http://mathoverflow.net/questions/43569/birkhoffs-theorem-about-doubly-stochastic-matrices/43572#43572 Answer by Greg Kuperberg for Birkhoff's theorem about doubly stochastic matrices Greg Kuperberg 2010-10-25T20:20:48Z 2010-10-25T22:43:06Z <p>See the <a href="http://en.wikipedia.org/wiki/Birkhoff_polytope" rel="nofollow">Wikipedia page</a> for the Birkhoff polytope. It says that equivalent results were obtained by Steinitz in 1894 and by Kőnig in 1916.</p> http://mathoverflow.net/questions/43569/birkhoffs-theorem-about-doubly-stochastic-matrices/43574#43574 Answer by Gjergji Zaimi for Birkhoff's theorem about doubly stochastic matrices Gjergji Zaimi 2010-10-25T20:26:29Z 2010-10-25T20:26:29Z <p>From Schneider's "The Birkhoff-Egervary-Konig theorem for matrices over lattice ordered abelian groups" after the following theorem is presented</p> <blockquote> <p>Let $G$ be a lattice ordered abelian group. Every generalized doubly stochastic matrix with elements from $G$ is the sum of generalized permutation matrices.</p> </blockquote> <p>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.</p>