Theorems · Theorem · linear algebra

doublyStochastic_eq_convexHull_permMatrix

• 1000+ list: Birkhoff–Von Neumann theorem

∀ {R : Type u_1} {n : Type u_2} [inst : Fintype n] [inst_1 : DecidableEq n] [inst_2 : Field R] [inst_3 : LinearOrder R]
  [inst_4 : IsStrictOrderedRing R], ↑(doublyStochastic R n) = (convexHull R) {x | ∃ σ, Equiv.Perm.permMatrix R σ = x}

Birkhoff's theorem The set of doubly stochastic matrices is the convex hull of the permutation matrices. Note exists_eq_sum_perm_of_mem_doublyStochastic gives a convex weighting of each permutation matrix directly. To show doublyStochastic n is convex, use convex_doublyStochastic.

Defined in

Mathlib.Analysis.Convex.Birkhoff

Cited by

2 results in Mathlib

Foundations

Depth 91 from the axioms · uses propext, Classical.choice, Quot.sound

Assumes

FintypeDecidableEqFieldLinearOrderIsStrictOrderedRing