Every doubly stochastic matrix is a convex combination of permutation matrices. The polytope of these matrices is where the assignment problem lives.
The doubly stochastic matrices — n×n with non-negative entries, all rows and columns summing to 1 — form a convex polytope in n²-dimensional matrix space. The Birkhoff polytope Bn is one of the most studied polytopes in combinatorial optimization.
It is the feasible region of the assignment problem (LP), the convex hull of n! permutation matrices (combinatorics), the space of couplings between uniform distributions (measure theory), the smoothing operator in majorization theory, and the entropy-regularized relaxation in optimal transport.
The Birkhoff–von Neumann theorem: Bn's extreme points are exactly the permutation matrices, so every doubly stochastic matrix is a weighted average of permutations.
The Pi are permutation matrices; weights θi ≥ 0 sum to 1. This decomposition makes the assignment LP integer-optimal and the Hungarian algorithm correct.
Although Bn lives in an ambient space of dimension n2, the sum-to-one constraints force it onto a lower-dimensional slice. The row sums give n equations; the column sums give another n; but one of these is redundant (they both imply the total equals n). That leaves 2n−1 independent constraints and so
B3 has dimension 4 and 6 vertices (3! permutations), combinatorially a cyclic polytope. B4: dim 9, 24 vertices. B5: dim 16, 120 vertices. Facets come from non-negativity xij ≥ 0, giving n² for n ≥ 3. Vertex count explodes factorially; facet count only quadratically.
Exact volumes are known only for n ≤ 10; by n = 9 the Ehrhart polynomial has degree 64. The volume problem is a famous open problem in polyhedral combinatorics.
Dimension snapshot.
B2: dimension 1, 2 vertices (just a line segment between I and the swap).
B3: dimension 4, 6 vertices, 9 facets, combinatorially a cyclic polytope.
B4: dimension 9, 24 vertices, 16 facets.
B5: dimension 16, 120 vertices, 25 facets.
Each jump from n to n+1 multiplies the vertex count by n+1 and adds 2n+1 dimensions.
Sixteen entries of a 4×4 matrix give 16 axes. A doubly stochastic matrix becomes a polyline visiting entries in reading order. Sum constraints are structural: within each block of four adjacent axes, the row sums to 1; every four axes apart, the column sums to 1.
Figure 1. 4×4 doubly stochastic matrices generated by Sinkhorn-normalizing random positive matrices. Each polyline visits the 16 entries in reading order. Each row of four axes must sum to 1; each column of four axes separated by four positions must also sum to 1. The toggle shades those groupings.
Every polyline passes through the same 9D slice of the 16-cube. Pick three row entries; the fourth is forced. Same for columns. Six constraints, two redundant: 16 − 7 = 9.
The 24 size-4 permutation matrices are the 24 placements of four non-attacking rooks on a 4×4 board. Each polyline consists entirely of 0s and 1s; the 1-pattern is a permutation.
Figure 2. All 24 permutation matrices of size 4 as polylines over the 16 matrix entries. Even permutations (blue) and odd permutations (red) split the vertex set into the alternating group A4 and its coset. Every polyline has exactly four 1-valued axes and twelve 0-valued axes.
Every doubly stochastic matrix is a convex combination of these 24 polylines. Mixing all 24 vertices with equal weight gives the uniform doubly stochastic matrix: every entry 1/4, every axis at height 1/4.
Pick two, three, or four permutation matrices, assign weights that sum to 1, and the result is a doubly stochastic matrix lying on the convex hull of those vertices. If you pick just two vertices you get a point on an edge. Three give a point on a face. Four give a point in a tetrahedral face (or the interior, if the four vertices are in general position).
Figure 3. Pick up to four permutation matrices (top controls) and assign weights with the sliders. The selected vertices appear as faded polylines; the convex combination appears in solid color and as a heatmap. Every doubly stochastic matrix in B4 can be written this way, often with at most (n−1)2+1 = 10 vertices.
Carathéodory's theorem says any point in a d-dimensional polytope can be written as a combination of at most d+1 vertices. For B4, that is ten permutation matrices, so although a doubly stochastic 4×4 matrix might be a mixture of many permutations, it always has a decomposition using at most ten. The decomposition is rarely unique. This is the content of Birkhoff's algorithm: repeatedly pull out the permutation matrix that supports the largest weight until nothing remains.
Given a cost matrix C, we want the permutation σ that minimizes Σi C[i, σ(i)]. Four workers, four jobs, and a 4×4 table of costs: which worker gets which job?
The LP feasible region is the Birkhoff polytope. We minimize C·X over X ∈ B4. A linear function over a polytope attains its minimum at a vertex; by Birkhoff–von Neumann, the vertices are permutation matrices, so the LP optimum is automatically a permutation. This is the geometric content of the Hungarian algorithm.
Click any matrix cell to edit its cost. The ranking of all 24 permutations updates live.
Figure 4. Left: an editable 4×4 cost matrix (click entries to cycle through costs). Right: all 24 permutations plotted by total cost. The optimum is highlighted in blue; it is always a vertex of B4. Toggle the checkbox to overlay 4,000 random doubly stochastic matrices. Their costs fall between the best and worst vertex costs, with the minimum still attained at the leftmost vertex.
Dragging the costs reorders permutations without changing the feasible set. Only the objective rotates. As it sweeps past an edge, the optimal vertex jumps — exactly what the simplex method traces along the edges of B4.
Sinkhorn's theorem (1964) maps a positive matrix to Bn by alternating row and column normalization. The process converges to a doubly stochastic matrix of the form D1AD2 for positive diagonal D1, D2.
Figure 5. Sinkhorn iteration on a random 4×4 positive matrix. Each “step” normalizes rows (odd) or columns (even). The row-sum and column-sum deviations shrink exponentially. After a handful of iterations the matrix is indistinguishable from doubly stochastic. The limiting matrix is the Sinkhorn projection, a specific point inside B4.
Sinkhorn projection is central to modern optimal transport. With entropy regularization, the optimum is the Sinkhorn projection of exp(−C/ε), computed by the same alternating normalization.
Sinkhorn converges because row and column normalization contract the Hilbert (projective) metric on positive matrices. The fixed point is unique up to scale; convergence rate is governed by the spectral gap of a doubly stochastic operator.
A vector y majorizes x (written x ≺ y) if they have the same total and, in sorted order, partial sums of y dominate those of x. Hardy–Littlewood–Pólya: this is equivalent to x = Dy for some doubly stochastic D.
Smoothing is averaging over permuted copies. The set of vectors majorized by y is the permutohedron of y — the convex hull of all n! permutations of y's entries — equal to the image of Bn under D ↦ Dy.
Figure 6. For a 3-dimensional starting vector y, the six permuted copies (red dots) are vertices of a hexagonal permutohedron. 400 doubly stochastic averages Dy (blue dots) fill its interior. Everything inside is majorized by y. As you drag the sliders, watch the hexagon shrink when y's entries become more equal: a flatter y majorizes fewer things.
For equal y, all permutations collapse and the permutohedron degenerates. For maximally unequal y, the hexagon is largest. Inequality and majorization depth go together.
The Birkhoff polytope is the assignment polytope of LP. Its vertex graph is a Cayley graph on Sn. Its projection under D ↦ Dy gives the permutohedron. Its integer points are magic squares. Its rational points are probability distributions over permutations.
Sn has two very different geometric lives: in Bn, a permutation σ is a 0/1 n×n matrix in n² dimensions with polytope dimension (n−1)². In the permutohedron, σ is the vector (σ(1), …, σ(n)) in n dimensions with polytope dimension n−1.
The Hungarian algorithm walks edges of Bn: each pivot composes with a transposition. Correctness comes from LP-vertex optimality; efficiency from O(n³) shortest paths between vertices.
Five fields, one polytope: Birkhoff–von Neumann (every doubly stochastic = convex combination of permutations), Hardy–Littlewood–Pólya (doubly stochastic = majorization smoothing), Sinkhorn (alternating normalization projects positive matrices to Bn), Hungarian algorithm (LP over Bn), and entropy-regularized optimal transport.