TOPICS

# Doubly Stochastic Matrix

A doubly stochastic matrix is a matrix such that and

is some field for all and . 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 for small .

 doubly stochastic matrices over 2 1, 2, 16, 512, ... 3 1, 3, 81, ... 4 1, 4, 256, ...
 doubly stochastic nonsingular matrices over 2 1, 2, 6, 192, ... 3 1, 2, 54, ... 4 1, 4, 192, ...

Horn (1954) proved that if , where and are complex -vectors, is doubly stochastic, and , , ..., are any complex numbers, then lies in the convex hull of all the points , , where is the set of all permutations of . Sherman (1955) also proved the converse.

Birkhoff (1946) proved that any doubly stochastic matrix is in the convex hull of permutation matrices for . There are several proofs and extensions of this result (Dulmage and Halperin 1955, Mendelsohn and Dulmage 1958, Mirsky 1958, Marcus 1960).

Majorization, Stochastic Matrix

## Explore with Wolfram|Alpha

More things to try:

## References

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. https://mathworld.wolfram.com/DoublyStochasticMatrix.html