The Birkhoff–von Neumann theorem
ProvedFamousTheorems.birkhoff_von_neumannThe Birkhoff–von Neumann theorem. Over an ordered field, the set of doubly stochastic matrices (nonnegative entries, all row and column sums ) is the convex hull of the permutation matrices.
Equivalently, the permutation matrices are the extreme points of the Birkhoff polytope. The theorem is the basis of the assignment problem in linear programming and of majorisation theory, and it is equivalent to Hall's and König's theorems on bipartite matchings.
Formalization note. Mathlib's doublyStochastic_eq_convexHull_permMatrix; doublyStochastic R n is a submonoid of matrices and Equiv.Perm.permMatrix R σ is the permutation matrix of σ.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem birkhoff_von_neumann {R n : Type*} [Fintype n] [DecidableEq n] [Field R] [LinearOrder R] [IsStrictOrderedRing R] :
(doublyStochastic R n : Set (Matrix n n R)) =
convexHull R {x : Matrix n n R | ∃ σ : Equiv.Perm n, Equiv.Perm.permMatrix R σ = x} := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `doublyStochastic_eq_convexHull_permMatrix`. Proof here reduces to that Mathlib result.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.