Doubly Stochastic Matrix — Definition, Formula & Examples

A doubly stochastic matrix is a square matrix whose entries are all nonnegative and whose rows and columns each sum to 1. It combines the properties of a row-stochastic matrix and a column-stochastic matrix.

A square matrix $A = [a_{ij}]$ of order $n$ is doubly stochastic if $a_{ij} \geq 0$ for all $i, j$ , and $\sum_{j=1}^{n} a_{ij} = 1$ for every row $i$ and $\sum_{i=1}^{n} a_{ij} = 1$ for every column $j$ .

How It Works

To verify that a matrix is doubly stochastic, check three conditions: every entry is nonnegative, each row sums to exactly 1, and each column sums to exactly 1. The simplest example is the

n \times n

identity matrix. Another classic example is the matrix where every entry equals

\frac{1}{n}

. The Birkhoff–von Neumann theorem states that every doubly stochastic matrix is a convex combination of permutation matrices, meaning it can be written as a weighted average of matrices that have exactly one 1 in each row and column.

Worked Example

Problem: Determine whether the following matrix is doubly stochastic:

A = \begin{bmatrix} 0.5 & 0.25 & 0.25 \\ 0.25 & 0.5 & 0.25 \\ 0.25 & 0.25 & 0.5 \end{bmatrix}

Check nonnegativity: Every entry is 0.25 or 0.5, both nonnegative.

a_{ij} \geq 0 \text{ for all } i,j \quad \checkmark

Check row sums: Each row sums to

0.5 + 0.25 + 0.25 = 1

\sum_{j=1}^{3} a_{ij} = 1 \text{ for } i = 1, 2, 3 \quad \checkmark

Check column sums: Each column sums to

0.5 + 0.25 + 0.25 = 1

\sum_{i=1}^{3} a_{ij} = 1 \text{ for } j = 1, 2, 3 \quad \checkmark

Answer: All three conditions are satisfied, so

A

is doubly stochastic.

Why It Matters

Doubly stochastic matrices appear in optimization, combinatorics, and Markov chain theory. The Birkhoff polytope — the set of all

n \times n

doubly stochastic matrices — is a fundamental object in linear programming and the assignment problem. They also arise in quantum information and economics when modeling fair allocation or mixing processes.

Common Mistakes

Mistake: Assuming any stochastic matrix is doubly stochastic.

Correction: A row-stochastic matrix only requires row sums equal to 1. For a matrix to be doubly stochastic, both row sums and column sums must equal 1. Always verify both conditions.