Birkhoff–von Neumann theorem

E637943

mathematical theorem theorem in matrix theory

The Birkhoff–von Neumann theorem is a fundamental result in matrix theory and combinatorics stating that every doubly stochastic matrix can be expressed as a convex combination of permutation matrices.

Try in SPARQL Jump to: Statements Referenced by

Statements (47)

Predicate	Object
instanceOf	mathematical theorem ⓘ theorem in matrix theory ⓘ
alsoKnownAs	Birkhoff theorem on doubly stochastic matrices NERFINISHED ⓘ
appliesTo	finite square matrices ⓘ
assumes	column sums of the matrix equal 1 ⓘ matrix entries are nonnegative real numbers ⓘ row sums of the matrix equal 1 ⓘ
author	Garrett Birkhoff NERFINISHED ⓘ John von Neumann NERFINISHED ⓘ
characterizes	Birkhoff polytope as convex hull of permutation matrices ⓘ
concerns	n×n doubly stochastic matrices ⓘ n×n permutation matrices ⓘ
conclusion	matrix is a convex combination of permutation matrices ⓘ
describes	structure of doubly stochastic matrices ⓘ
equivalentTo	statement that extreme points of the Birkhoff polytope are permutation matrices ⓘ
field	combinatorics ⓘ linear algebra ⓘ matrix theory ⓘ polyhedral combinatorics ⓘ
hasConsequence	doubly stochastic matrices form a polytope ⓘ every doubly stochastic matrix is a finite convex combination of permutation matrices ⓘ vertices of the Birkhoff polytope are permutation matrices ⓘ
implies	The set of doubly stochastic matrices is the convex hull of permutation matrices. ⓘ
involves	convex hull ⓘ extreme points of a polytope ⓘ
namedAfter	Garrett Birkhoff NERFINISHED ⓘ John von Neumann NERFINISHED ⓘ
relatedTo	Carathéodory's theorem NERFINISHED ⓘ Hall's marriage theorem NERFINISHED ⓘ polytope theory ⓘ
relatesConcept	Birkhoff polytope NERFINISHED ⓘ assignment problem ⓘ bipartite graph perfect matchings ⓘ convex combination ⓘ doubly stochastic matrix ⓘ permutation matrix ⓘ transportation problem ⓘ
statement	Every doubly stochastic matrix can be expressed as a convex combination of permutation matrices. ⓘ
typeOfResult	extreme point characterization ⓘ representation theorem ⓘ
usedIn	combinatorial optimization ⓘ design of randomized algorithms ⓘ matrix scaling and decomposition ⓘ network flow theory ⓘ quantum information theory ⓘ statistics ⓘ
yearProved	1946 ⓘ

Referenced by (1)

Full triples — surface form annotated when it differs from this entity's canonical label.

Garrett Birkhoff → notableConcept → Birkhoff–von Neumann theorem ⓘ