Linear and multilinear algebra; matrix theory Nonnegative and stochastic matrices Theorem

Birkhoff–von Neumann theorem

Builds on Doubly stochastic matrix Permutation matrix Convex hull

Statement

Let $n \ge 1$ and let $A$ be an $n \times n$ doubly stochastic matrix. So $A$ has real nonnegative entries, and its rows and columns each sum to $1$ . Then $A$ is a convex combination of $n \times n$ permutation matrices. That is, there are permutation matrices $P_1, \dots, P_k$ and real numbers $\theta_1, \dots, \theta_k \ge 0$ with $\theta_1 + \cdots + \theta_k = 1$ such that $A = \theta_1 P_1 + \cdots + \theta_k P_k.$

Remarks

The proof is by induction on the number of nonzero entries of $A$ . Form the bipartite graph whose two sides are the rows and the columns, with an edge for each nonzero entry. Any $r$ rows carry total mass $r$ , and this mass lies in the columns joined to them, which carry at most $1$ each. So Hall's marriage theorem gives a perfect matching. It is a permutation matrix $P$ supported on nonzero entries of $A$ . If $\theta$ is the least entry of $A$ on this support and $A \ne P$ , then $(A - \theta P)/(1 - \theta)$ is doubly stochastic with fewer nonzero entries. For example, $\begin{pmatrix} 1/2 & 1/2 \\ 1/2 & 1/2 \end{pmatrix} = \frac12 \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} + \frac12 \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}.$ Equivalently, the set of doubly stochastic matrices, the Birkhoff polytope, is the convex hull of the $n!$ permutation matrices, and these are its vertices.

Going deeper

For a student

The theorem is the matrix form of Hall's and Kőnig's theorems on bipartite matchings. It shows that the linear program for the assignment problem has a permutation matrix among its optimal solutions. It is also used in the theory of majorization and in proofs of inequalities for permanents and eigenvalues.

Reading path

To understand this page from the ground up, read these 8 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Affine combination concept
Convex set concept
Doubly stochastic matrix concept
Matrix definition
Convex hull definition
Square matrix definition
Permutation matrix definition
Birkhoff–von Neumann theorem statement

Tag	`3KY1RMEDMJ`
URI	`m2://3KY1RMEDMJ`
Kind	statement, theorem
Writing	W0 stub
MSC	15B51, 05C70, 52B12
Status	This copy of the site has no build data. Run `m2 status 3KY1RMEDMJ`.
About	Doubly stochastic matrix
Uses	Doubly stochastic matrix, Permutation matrix, Convex hull
Changed	2 November 2026