Birkhoff polytope

From Polytope Wiki
Jump to navigation Jump to search
Wireframe of the four-dimensional B3.

The Birkhoff polytope Bn 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 n2-dimensional Euclidean space, the entries are unraveled in reading order. Bn is (n - 1)2-dimensional, as it lies within an affine subspace of that dimension.

Birkhoff's theorem states that the vertices of Bn 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!. B2 is a line segment, while for n > 2, Bn has n2 facets. Bn 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 B3 is a triangular duotegum with edge lengths 2 and . All faces are triangular.

The nine-dimensional B4 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 B4 are squares and triangles.

External links[edit | edit source]