Math 2.0

Convex and discrete geometry Polytopes and polyhedra Example

Birkhoff polytope

Builds on Doubly stochastic matrixPermutation matrixBirkhoff–von Neumann theoremVertex of a polytopeFacet

Example

Let n≥1n \ge 1. The Birkhoff polytope BnB_n is the set of n×nn \times n doubly stochastic matrices, seen as points of ℝn×n\R^{n \times n}: Bn={X∈ℝn×n:xij≥0, ∑jxij=1 for all i, ∑ixij=1 for all j}.B_n = \set{X \in \R^{n \times n} : x_{ij} \ge 0, \ \textstyle\sum_{j} x_{ij} = 1 \text{ for all } i, \ \sum_{i} x_{ij} = 1 \text{ for all } j}. It is bounded, since 0≤xij≤10 \le x_{ij} \le 1, and is cut out by finitely many linear inequalities and equations, so it is a convex polytope. By the Birkhoff–von Neumann theorem, BnB_n is the convex hull of the n!n! permutation matrices, and these are its vertices. The 2n2n equations have rank 2n−12n - 1, so dim⁡Bn=n2−(2n−1)=(n−1)2\dim B_n = n^2 - (2n - 1) = (n-1)^2. For n≥3n \ge 3 the facets are the n2n^2 sets {X∈Bn:xij=0}\set{X \in B_n : x_{ij} = 0}.

Remarks

For n=2n = 2, B2B_2 is the segment of matrices (t1−t1−tt)\begin{pmatrix} t & 1-t \\ 1-t & t \end{pmatrix}, 0≤t≤10 \le t \le 1, with the two permutation matrices as endpoints. For n=3n = 3, B3B_3 is a 44-dimensional polytope with 66 vertices and 99 facets. Its role in optimisation is that a linear function on BnB_n attains its maximum at a permutation matrix, which solves the assignment problem by linear programming.

Reading path

To understand this page from the ground up, read these 12 pages in order. The foundations come first.

Show the path as a graph
Affine combination, concept, no evidence levelAffine combinationconceptConvex set, concept, no evidence levelConvex setconceptDoubly stochastic matrix, concept, no evidence levelDoubly stochastic mat…conceptFacet, concept, no evidence levelFacetconceptMatrix, definition, no evidence levelMatrixdefinitionPermutation matrix, concept, no evidence levelPermutation matrixconceptVertex of a polytope, concept, no evidence levelVertex of a polytopeconceptConvex hull, definition, no evidence levelConvex hulldefinitionSquare matrix, definition, no evidence levelSquare matrixdefinitionPermutation matrix, definition, no evidence levelPermutation matrixdefinitionBirkhoff–von Neumann theorem, statement, no evidence levelBirkhoff–von Neumann …statementBirkhoff polytope, example, no evidence levelBirkhoff polytopeexample
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Affine combination concept
  2. Convex set concept
  3. Doubly stochastic matrix concept
  4. Facet concept
  5. Matrix definition
  6. Permutation matrix concept
  7. Vertex of a polytope concept
  8. Convex hull definition
  9. Square matrix definition
  10. Permutation matrix definition
  11. Birkhoff–von Neumann theorem statement
  12. Birkhoff polytope example

Further reading

  1. Web https://en.wikipedia.org/wiki/Birkhoff_polytope
About this page
TagADEXY830S8
URIm2://ADEXY830S8
Kindexample
WritingW0 stub
MSC52B12, 15B51, 52B05
Instance ofConvex polytope
UsesDoubly stochastic matrix, Permutation matrix, Birkhoff–von Neumann theorem, Vertex of a polytope, Facet
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.