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 read off in any consistent order, such as 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 240 edges of three different distinct types: type 4U (72 edges of length 2), type 6 (96 edges of length ), and type 8 (72 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 576 scalene triangles, 288 isosceles triangles, 96 equilateral triangles, and 18 squares, each of 1 type.

External links[edit | edit source]