Doubly Stochastic Matrix

A doubly stochastic matrix is a matrix A=(a_(ij)) such that a_(ij)>=0 and


is some field for all i and j. In other words, both the matrix itself and its transpose are stochastic.

The following tables give the number of distinct doubly stochastic matrices (and distinct nonsingular doubly stochastic matrices) over Z_m for small m.

mdoubly stochastic n×n matrices over Z_m
21, 2, 16, 512, ...
31, 3, 81, ...
41, 4, 256, ...
mdoubly stochastic nonsingular n×n matrices over Z_m
21, 2, 6, 192, ...
31, 2, 54, ...
41, 4, 192, ...

Horn (1954) proved that if y=Ax, where x and y are complex n-vectors, A is doubly stochastic, and c_1, c_2, ..., c_n are any complex numbers, then sum_(i=1)^(n)c_iy_i lies in the convex hull of all the points sum_(i=1)^(n)c_ix_(alphai), alpha in R^n, where R^n is the set of all permutations of {1,...,n}. Sherman (1955) also proved the converse.

Birkhoff (1946) proved that any doubly stochastic n×n matrix is in the convex hull of m permutation matrices for m<=(n-1)^2+1. There are several proofs and extensions of this result (Dulmage and Halperin 1955, Mendelsohn and Dulmage 1958, Mirsky 1958, Marcus 1960).

See also

Majorization, Stochastic Matrix

Explore with Wolfram|Alpha


Birkhoff, G. "Three Observations on Linear Algebra." Univ. Nac. Tucumán. Rev. Ser. A 5, 147-151, 1946.Dulmage, L. and Halperin, I. "On a Theorem of Frobenius-König and J. von Neumann's Game of Hide and Seek." Trans. Roy. Soc. Canada Sect. III 49, 23-29, 1955.Horn, A. "Doubly Stochastic Matrices and the Diagonal of a Rotation Matrix." Amer. J. Math. 76, 620-630, 1954.Marcus, M. "Some Properties and Applications of Doubly Stochastic Matrices." Amer. Math. Monthly 67, 215-221, 1960.Mendelsohn, N. S. and Dulmage, A. L. "The Convex Hull of Subpermutation Matrices." Proc. Amer. Math. Soc. 9, 253-254, 1958.Mirsky, L. "Proofs of Two Theorems on Doubly Stochastic Matrices." Proc. Amer. Math. Soc. 9, 371-374, 1958.Schreiber, S. "On a Result of S. Sherman Concerning Doubly Stochastic Matrices." Proc. Amer. Math. Soc. 9, 350-353, 1958.Sherman, S. "A Correction to 'On a Conjecture Concerning Doubly Stochastic Matrices.' " Proc. Amer. Math. Soc. 5, 998-999, 1954.Sherman, S. "Doubly Stochastic Matrices and Complex Vector Spaces." Amer. J. Math. 77, 245-246, 1955.

Referenced on Wolfram|Alpha

Doubly Stochastic Matrix

Cite this as:

Weisstein, Eric W. "Doubly Stochastic Matrix." From MathWorld--A Wolfram Web Resource.

Subject classifications