Birkhoff polytope

Wireframe of the four-dimensional B₃.

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²-dimensional Euclidean space, the entries are unraveled in reading order. B_n is (n - 1)²-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₂ is a line segment, while for n > 2, B_n has n² 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₃ is a triangular duotegum with edge lengths 2 and $\sqrt{6}$. All faces are triangular.

The nine-dimensional B₄ has 24 vertices and 276 edges of four different distinct types: type 4U (72 edges of length 2), type 6 (96 edges of length $\sqrt{6}$), type 8 (72 edges of length $2\sqrt{2}$), and type 8U (36 edges of length $2\sqrt{2}$). 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₄ are squares and triangles.

External links

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