Doubly stochastic matrix
In mathematics, especially in probability and combinatorics, a doubly stochastic matrix (also called bistochastic), is a square matrix of nonnegative real numbers, each of whose rows and columns sum to 1, i.e.,
Such a transition matrix is necessarily a square matrix: if every row sums to one then the sum of all entries in the matrix must be equal to the number of rows, and since the same holds for columns, the number of rows and columns must be equal.
Birkhoff polytope and Birkhoff–von Neumann theorem
The class of doubly stochastic matrices is a convex polytope known as the Birkhoff polytope . Using the matrix entries as Cartesian coordinates, it lies in an -dimensional affine subspace of -dimensional Euclidean space. defined by independent linear constraints specifying that the row and column sums all equal one. (There are constraints rather than because one of these constraints is dependent, as the sum of the row sums must equal the sum of the column sums.) Moreover, the entries are all constrained to be non-negative and less than or equal to one.
Van der Waerden conjectured that the minimum permanent among all n × n doubly stochastic matrices is , achieved by the matrix for which all entries are equal to . Proofs of this conjecture were published in 1980 by B. Gyires and in 1981 by G. P. Egorychev and D. I. Falikman; for this work, Egorychev and Falikman won the Fulkerson Prize in 1982.
- Marshal, Olkin (1979). Inequalities: Theory of Majorization and Its Applications. p. 8. ISBN 0-12-473750-1.
- van der Waerden, B. L. (1926), "Aufgabe 45", Jber. Deutsch. Math.-Verein. 35: 117.
- Gyires, B. (1980), "The common source of several inequalities concerning doubly stochastic matrices", Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis 27 (3-4): 291–304, MR 604006.
- Egoryčev, G. P. (1980), Reshenie problemy van-der-Vardena dlya permanentov (in Russian), Krasnoyarsk: Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz., p. 12, MR 602332. Egorychev, G. P. (1981), "Proof of the van der Waerden conjecture for permanents", Akademiya Nauk SSSR (in Russian) 22 (6): 65–71, 225, MR 638007. Egorychev, G. P. (1981), "The solution of van der Waerden's problem for permanents", Advances in Mathematics 42 (3): 299–305, doi:10.1016/0001-8708(81)90044-X, MR 642395.
- Falikman, D. I. (1981), "Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix", Akademiya Nauk Soyuza SSR (in Russian) 29 (6): 931–938, 957, MR 625097.
- Fulkerson Prize, Mathematical Optimization Society, retrieved 2012-08-19.
- Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications 108. Cambridge: Cambridge University Press. ISBN 0-521-86565-4. Zbl 1106.05001.