---
tag: 3X74C58NCH
kind: definition
name: Doubly stochastic matrix
msc: [15B51]
defines: JJA90EB2PS
uses: [0JXZKX526R, JPQCCFCY8X]
sources:
  - url: https://en.wikipedia.org/wiki/Doubly_stochastic_matrix
---

## Definition

Let $n \ge 1$ and let $A = (a_{ij})$ be a real $n \times n$ [[matrix|0JXZKX526R]].
The matrix $A$ is *doubly stochastic* if:

1. $a_{ij} \ge 0$ for all $i$ and $j$.
2. $\sum_{j=1}^{n} a_{ij} = 1$ for each row index $i$.
3. $\sum_{i=1}^{n} a_{ij} = 1$ for each column index $j$.

## Remarks

Clause 1 says that $A$ is a [[nonnegative matrix|JPQCCFCY8X]].
With $e = (1, \ldots, 1)^T$, clauses 2 and 3 say $Ae = e$ and $e^T A = e^T$.
Example: $A = \frac{1}{2}\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$; all entries are $\frac{1}{2} \ge 0$, and each row and each column sums to $1$.
Every [[permutation matrix|08SP3DF8NB]] is doubly stochastic.
Non-example: $\begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix}$ satisfies clauses 1 and 2, but its columns sum to $2$ and $0$, so clause 3 fails.
The set of doubly stochastic $n \times n$ matrices is the Birkhoff polytope.