The Birkhoff polytope has n! vertices, one for each permutation on n items [REF].
The Birkhoff polytope lies within an dimensional affine subspace of the n2-dimensional space of all matrices: this subspace is determined by the linear equality constraints that the sum of each row and of each column be one.