Birkhoff polytope
The Birkhoff polytope Bn, also called the assignment polytope, the polytope of doubly stochastic matrices, or the perfect matching polytope of the complete bipartite graph , is the convex polytope in RN (where N = n²) whose points are the , i.e., the n × n matrices whose entries are non-negative real numbers and whose rows and columns each add up to 1.
The Birkhoff polytope has n! vertices, one for each permutation on n items. This follows from the Birkhoff–von Neumann theorem, which states that the extreme points of the Birkhoff polytope are the permutation matrices, and therefore that any doubly stochastic matrix may be represented as a convex combination of permutation matrices; this was stated in a 1946 paper by Garrett Birkhoff, but equivalent results in the languages of projective configurations and of regular bipartite graph matchings, respectively, were shown much earlier in 1894 in Ernst Steinitz's thesis and in 1916 by Dénes Kőnig.
The edges of the Birkhoff polytope correspond to pairs of permutations differing by a cycle:
...
Wikipedia