Existing in Mathlib · Combinatorics and convexity

Birkhoff–von Neumann Theorem

A finite square matrix with nonnegative entries and every row and column summing to one can be expressed as a weighted average of permutation matrices, and every such weighted average is doubly stochastic.

doubly stochastic matrices
permutation matrices
convex hulls
Hall’s theorem
bipartite matchings

Exact theorem

Exact Mathlib statement

theorem doublyStochastic_eq_convexHull_permMatrix {R n : Type*} [Fintype n] [DecidableEq n] [Field R] [LinearOrder R] [IsStrictOrderedRing R] : doublyStochastic R n = convexHull R {σ.permMatrix R | σ : Equiv.Perm n}

The theorem at a glance

Birkhoff–von Neumann Theorem at a glance

A visual guide to the theorem's hypotheses, structure, and conclusion; the exact statement gives the formal detail.

An editorial theorem poster places a doubly stochastic matrix inside the convex hull of permutation-matrix vertices and traces the Hall-matching proof. — Every finite doubly stochastic matrix is a convex blend of permutation matrices.

Statement structure

Statement and scope

Read the exact Mathlib declaration

This map summarizes the statement's structure; the exact Mathlib declaration remains authoritative.

A doubly stochastic matrix becomes a bipartite support graph, a Hall matching, and then a convex combination of permutation matrices. — Hall matchings peel permutation matrices from a doubly stochastic matrix until only a convex combination remains.

Why it matters

A mathematical landmark

The Birkhoff–von Neumann theorem connects matrix theory, convex geometry, and matching theory. Mathlib’s proof visibly reuses Hall’s theorem, already indexed by ProofAtlas, to peel permutation matrices from the positive support.

ProofAtlas record

What has been checked

Upstream indexedPinned source bytes verified locally

Locally reproducedExact upstream declaration replayed

Reviewed pageCurrent public presentation reviewed

Accepted Atlas resultNot recorded for the preferred artifact

Mathlib is the source of the theorem; the local Lean replay and page review are separate.

Claim boundary

No new theorem is claimed

This page indexes Mathlib’s finite square-matrix convex-hull identity over a linearly ordered field. It proves existence of convex decompositions into permutation matrices, not uniqueness, a canonical or minimal decomposition, an algorithmic complexity bound, an assignment-optimization theorem, or the separate majorization characterization. The extreme-point identity is a companion declaration, not the selected endpoint.

ProofAtlas did not originate the Birkhoff–von Neumann theorem or Mathlib’s declaration.
The selected endpoint is finite and square; it is not an infinite or rectangular extension.
The theorem does not assert uniqueness or optimality of the convex decomposition.
The generated explanation and visuals are not proof evidence.

Source and local evidence

Where the theorem comes from

Existing declaration: doublyStochastic_eq_convexHull_permMatrix in mathlib
Relationship: The checked artifact is the upstream declaration itself
Local Lean evidence: artifact.library.mathlib.birkhoff-von-neumann-theorem.v001
Source: Open the pinned upstream reference