Birkhoff–von Neumann theorem
E637943
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.
All labels observed (2)
| Label | Occurrences |
|---|---|
| Birkhoff theorem on doubly stochastic matrices | 1 |
| Birkhoff–von Neumann theorem canonical | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T7059218 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Birkhoff–von Neumann theorem Context triple: [Garrett Birkhoff, notableConcept, Birkhoff–von Neumann theorem]
-
A.
Szekeres–Lindström theorem
The Szekeres–Lindström theorem is a result in combinatorics that characterizes the maximum size of intersecting families of subsets, serving as a precursor to and special case of the Erdős–Ko–Rado theorem.
-
B.
Gleason’s theorem
Gleason’s theorem is a foundational result in the mathematical formulation of quantum mechanics that characterizes all probability measures on the lattice of projection operators in a Hilbert space, effectively justifying the Born rule.
-
C.
de Bruijn–van Aardenne–Ehrenfest theorem
The de Bruijn–van Aardenne–Ehrenfest theorem is a fundamental result in combinatorics that characterizes the number of Eulerian circuits in directed graphs, particularly de Bruijn graphs, and underpins constructions in coding theory and discrete mathematics.
-
D.
Gelfand–Naimark theorem
The Gelfand–Naimark theorem is a foundational result in functional analysis that characterizes C*-algebras as algebras of bounded operators on a Hilbert space (and, in the commutative case, as algebras of continuous functions on a locally compact Hausdorff space).
-
E.
Erdős–Ko–Rado theorem
The Erdős–Ko–Rado theorem is a fundamental result in extremal combinatorics that determines the maximum size of a family of subsets of a finite set in which every pair of subsets has a non-empty intersection.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Birkhoff–von Neumann theorem Target entity description: 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.
-
A.
Szekeres–Lindström theorem
The Szekeres–Lindström theorem is a result in combinatorics that characterizes the maximum size of intersecting families of subsets, serving as a precursor to and special case of the Erdős–Ko–Rado theorem.
-
B.
Gleason’s theorem
Gleason’s theorem is a foundational result in the mathematical formulation of quantum mechanics that characterizes all probability measures on the lattice of projection operators in a Hilbert space, effectively justifying the Born rule.
-
C.
de Bruijn–van Aardenne–Ehrenfest theorem
The de Bruijn–van Aardenne–Ehrenfest theorem is a fundamental result in combinatorics that characterizes the number of Eulerian circuits in directed graphs, particularly de Bruijn graphs, and underpins constructions in coding theory and discrete mathematics.
-
D.
Gelfand–Naimark theorem
The Gelfand–Naimark theorem is a foundational result in functional analysis that characterizes C*-algebras as algebras of bounded operators on a Hilbert space (and, in the commutative case, as algebras of continuous functions on a locally compact Hausdorff space).
-
E.
Erdős–Ko–Rado theorem
The Erdős–Ko–Rado theorem is a fundamental result in extremal combinatorics that determines the maximum size of a family of subsets of a finite set in which every pair of subsets has a non-empty intersection.
- F. None of above. chosen
Statements (47)
| Predicate | Object |
|---|---|
| instanceOf |
mathematical theorem
ⓘ
theorem in matrix theory ⓘ |
| alsoKnownAs |
Birkhoff theorem on doubly stochastic matrices
ⓘ
linked to:
Birkhoff–von Neumann theorem
|
| 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
ⓘ
John von Neumann ⓘ |
| 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
ⓘ
John von Neumann ⓘ |
| relatedTo |
Carathéodory's theorem
ⓘ
linked to:
Carathéodory’s theorem in convex geometry
Hall's marriage theorem ⓘ polytope theory ⓘ |
| relatesConcept |
Birkhoff polytope
ⓘ
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 ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Birkhoff–von Neumann theorem Description of subject: 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.
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.
linked to: Birkhoff–von Neumann theorem