Doubly stochastic matrix

In mathematics, especially in probability and combinatorics, a doubly stochastic matrix (also called bistochastic matrix), is a square matrix ${\displaystyle A=(a_{ij})}$ of nonnegative real numbers, each of whose rows and columns sums to 1,[1] i.e.,

${\displaystyle \sum _{i}a_{ij}=\sum _{j}a_{ij}=1}$,

Thus, a doubly stochastic matrix is both left stochastic and right stochastic.[1][2]

Indeed, any matrix that is both left and right stochastic must be square: 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.[1]

Birkhoff polytope

Main article: Birkhoff polytope

The class of ${\displaystyle n\times n}$ doubly stochastic matrices is a convex polytope known as the Birkhoff polytope ${\displaystyle B_{n}}$. Using the matrix entries as Cartesian coordinates, it lies in an ${\displaystyle (n-1)^{2}}$-dimensional affine subspace of ${\displaystyle n^{2}}$-dimensional Euclidean space defined by ${\displaystyle 2n-1}$ independent linear constraints specifying that the row and column sums all equal one. (There are ${\displaystyle 2n-1}$ constraints rather than ${\displaystyle 2n}$ 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.

Birkhoff–von Neumann theorem

The Birkhoff–von Neumann theorem states that the polytope ${\displaystyle B_{n}}$ is the convex hull of the set of ${\displaystyle n\times n}$ permutation matrices, and furthermore that the vertices of ${\displaystyle B_{n}}$ are precisely the permutation matrices. In other words, if ${\displaystyle A}$ is doubly stochastic matrix, then there exist ${\displaystyle \theta _{1},\ldots ,\theta _{k}\geq 0,\sum _{i=1}^{k}\theta _{i}=1}$ and permutation matrices ${\displaystyle P_{1},\ldots ,P_{k}}$ such that

${\displaystyle A=\theta _{1}P_{1}+\cdots +\theta _{k}P_{k}.}$

This representation is known as the Birkhoff–von Neumann decomposition, and it may not be unique in general. By Carathéodory's theorem, however, there exists a decomposition with no more than ${\displaystyle (n-1)^{2}+1=n^{2}-2n+2}$ terms, i.e. with[3]

${\displaystyle k\leq n^{2}-2n+2.}$

In other words, while there exists a decomposition with ${\displaystyle n!}$ permutation matrices, there is at least one constructible decomposition with no more than ${\displaystyle (n-1)^{2}+1}$ matrices. Such a decomposition can be found in polynomial time using the Birkhoff algorithm.

Other properties

• The product of two doubly stochastic matrices is doubly stochastic. However, the inverse of a nonsingular doubly stochastic matrix need not be doubly stochastic (indeed, the inverse is doubly stochastic iff it has nonnegative entries).
• The stationary distribution of an irreducible aperiodic finite Markov chain is uniform if and only if its transition matrix is doubly stochastic.
• Sinkhorn's theorem states that any matrix with strictly positive entries can be made doubly stochastic by pre- and post-multiplication by diagonal matrices.
• For ${\displaystyle n=2}$, all bistochastic matrices are unistochastic and orthostochastic, but for larger ${\displaystyle n}$ this is not the case.
• Van der Waerden conjectured that the minimum permanent among all n × n doubly stochastic matrices is ${\displaystyle n!/n^{n}}$, achieved by the matrix for which all entries are equal to ${\displaystyle 1/n}$.[4] Proofs of this conjecture were published in 1980 by B. Gyires[5] and in 1981 by G. P. Egorychev[6] and D. I. Falikman;[7] for this work, Egorychev and Falikman won the Fulkerson Prize in 1982.[8]

See also

• Stochastic matrix
• Unistochastic matrix

References

1. Gagniuc, Paul A. (2017). Markov Chains: From Theory to Implementation and Experimentation. USA, NJ: John Wiley & Sons. pp. 9–11. ISBN 978-1-119-38755-8.
2. Marshal, Olkin (1979). Inequalities: Theory of Majorization and Its Applications. pp. 8. ISBN 978-0-12-473750-1.
3. Marcus, M.; Ree, R. (1959). "Diagonals of doubly stochastic matrices". The Quarterly Journal of Mathematics. 10 (1): 296–302. doi:10.1093/qmath/10.1.296.
4. van der Waerden, B. L. (1926), "Aufgabe 45", Jber. Deutsch. Math.-Verein., 35: 117.
5. 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 0604006.
6. 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 0602332. Egorychev, G. P. (1981), "Proof of the van der Waerden conjecture for permanents", Akademiya Nauk SSSR (in Russian), 22 (6): 65–71, 225, MR 0638007. 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 0642395.
7. 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 0625097.
8. 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 978-0-521-86565-4. Zbl 1106.05001.

External links

• PlanetMath page on Birkhoff–von Neumann theorem
• PlanetMath page on proof of Birkhoff–von Neumann theorem