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).
Birkhoff, G. "Three Observations on Linear Algebra." Univ. Nac. Tucumán. Rev. Ser. A5, 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. III49,
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. Monthly67, 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.
such that 
and
and 
. In other words, both the matrix itself and its transpose
are stochastic.
for small 
.
matrices over 
matrices over 
, 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.
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).
