# Assignment polytope

$LaTeX: \textstyle \left\{ x \in \mathbb{R}^{n^2} : x \ge 0, \; \sum_i x_{i,j} = 1 \mbox{ for } j = 1, 2, \ldots, n, \; \sum_j x_{i,j} = 1 \mbox{ for } i = 1, 2, \ldots, n \right\}.$
The name originates from an interpretation of its extreme points in the assignment problem. If $LaTeX: x_{i,j} = 1$, assign person $LaTeX: i$ to task $LaTeX: j$. Each extreme point has the property that each element of $LaTeX: x$ is 0 or 1. The sums describing the polytope require that each row ($LaTeX: i$) and each column ($LaTeX: j$) has exactly one 1 in it. This means every person is assigned to some task, and every task is assigned to be done by one person. The polytope is also the set of doubly stochastic matrices, whose extreme points are the permutation matrices.