Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!)

share|improve this question
    
It's strange that Hall is not on the list. –  darij grinberg Oct 25 '10 at 23:56
add comment

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
    
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. –  Suvrit Oct 25 '10 at 20:26
2  
You meant 1894 for Steinitz. –  Thierry Zell Oct 25 '10 at 20:34
    
But, of course, Steinitz mentioned neither "convex" nor "extreme point" ... since these are later notions. –  Gerald Edgar Oct 25 '10 at 20:49
    
@Thierry Yes, thanks I fixed it. –  Greg Kuperberg Oct 25 '10 at 22:43
add comment

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.

share|improve this answer
    
thanks Gjergji for the excellent reference. –  Suvrit Oct 25 '10 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 '10 at 22:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.