# Birkhoff polytope

The **Birkhoff polytope** B_{n} is a convex polytope whose points are the doubly stochastic n × n matrices. A matrix is called doubly stochastic if its rows and columns each sum to 1. To convert matrices to points in n^{2}-dimensional Euclidean space, the entries are unraveled in reading order. B_{n} is (n - 1)^{2}-dimensional, as it lies within an affine subspace of that dimension.

*Birkhoff's theorem* states that the vertices of B_{n} are the n × n permutation matrices (defined as matrices where each row and column contains exactly one 1 and all other entries are 0), of which there are n!. B_{2} is a line segment, while for n > 2, B_{n} has n^{2} facets. B_{n} is centered on the point corresponding to the n × n matrix all of whose entries are 1/n.

Birkhoff polytopes are isogonal and isotopic, and are therefore noble polytopes. All faces of Birkhoff polytopes are either triangles or rectangles.

The four-dimensional B_{3} is a triangular duotegum with edge lengths 2 and . All faces are triangular.

The nine-dimensional B_{4} has 24 vertices and 276 edges of four different distinct types: type 4U (72 edges of length 2), type 6 (96 edges of length ), type 8 (72 edges of length ), and type 8U (36 edges of length ). The "U" indicates that the points along the edges of those types are *unistochastic* matrices; a matrix B is unistochastic if it can be expressed as the element-wise (Hadamard) product of a unitary matrix and its complex conjugate. The faces of B_{4} are squares and triangles.

## External links[edit | edit source]

- Wikipedia Contributors. "Birkhoff polytope".
- Bengtsson et al. "Birkhoff’s Polytope and Unistochastic Matrices, N = 3 and N = 4."