6
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ It's strange that Hall is not on the list. $\endgroup$ Commented Oct 25, 2010 at 23:56

2 Answers 2

9
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Suvrit
    Commented Oct 25, 2010 at 20:26
  • $\begingroup$ But, of course, Steinitz mentioned neither "convex" nor "extreme point" ... since these are later notions. $\endgroup$ Commented Oct 25, 2010 at 20:49
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ A reference for Konig is Uber Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Math Annalen 77 (1915-16) 453-465. $\endgroup$ Commented Oct 25, 2010 at 22:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .