Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Let $x,n$ be 2 integers with $x<n$.
I need to find the vertices of the polytope $P$ of $2 \times n$ nonnegative matrices $A$ such that:
The first row in $A$ is summed to $x$. $$\sum_{j=1}^n a_{1,j} = x $$
The second row in $A$ is summed to $n-x$.
$$\sum_{j=1}^n a_{2,j} = n-x $$
Also, each column is summed to 1.
$$a_{j,1} + a_{j,2} = 1 $$
Write the first constraint as $\sum_j a_{1j} = m$, with $m < n$ ( I am just replacing the variable $x$ by $m$).
Since $a_{i1}+a_{i2} = 1$, and $a_{ij}\geq 0$, we see that this is equivalent to $a_{i2} = 1-a_{i1}$, with $a_{i1} \in [0,1]$.
Furthermore, if $\sum_j a_{1j} = m$ and $a_{i2} = 1-a_{i1}$ then $\sum_j a_{2j} = \sum_j (1-a_{1j}) = n-m$, so the second constraint is automatically satisfied. Hence the problem reduces to finding the vertices of the set $A=\{(a_{11},...,a_{1n})| \sum_j a_{1j} = m, a_{1j} \in [0,1] \}$.
$A$ is a compact convex set, and by Krein Millman can be written as the closed convex hull of $E$, the set of extreme points. We will show that $E$ is finite, hence it is sufficient to find $E$ to determine the vertex set.
I need the following lemma (a proof can be found here: Prove one set is a convex hull of another set):
Let $C = \{ x \in \mathbb{R}^n | \; g_i (x) \leq 0, \; \forall i \in I \}$, where each $g_i$ has the form $g_i(x) = \langle \gamma_i, x \rangle - \beta_i$. Define the 'active index set' $I_{x_0} = \{ i \in I | g_i(x_0) = 0 \}$.
Lemma: $x_0$ is an extreme point of $C$ iff $x_0 \in C$ and $\mathbb{sp} \{ \gamma_i \}_{i \in I_{x_0}} = \mathbb{R}^n$.
We can write $A=\{x \in \mathbb{R}^n | \langle e , x \rangle \leq m, \langle e , x \rangle \geq m, \langle e_k , x \rangle \geq 0, \langle e_k , x \rangle \leq 1, \}$, where $e=(1,...,1)^T$. It follows from the lemma (note that the constraints $\langle e , x \rangle \leq m, \langle e , x \rangle \geq m$ are always active), that if $x$ is an extreme point, then at least $n-1$ of the remaining constraints are active. Since at most one of the pairs of constraints $\langle e_k , x \rangle \geq 0, \langle e_k , x \rangle \leq 1$ can be active, this implies that $x$ must have $n-1$ components that are either $0$ or $1$, and suppose for simplicity that the $n-1$ components in question are $x_1,...,x_{n-1}$. Then we have $x_n = m-\sum_k x_k$. Suppose $p$ of the components $x_1,...,x_{n-1}$ are $1$. Then we have $x_n = m-p$, and since we require $x_n \in [0,1]$, this means that $p \in \{m-1,m\}$. If $p=m-1$, we see that $x_n = 1$, if $p=m$, we see that $x_n = 0$. It follows that $x$ has exactly $m$ ones and $n-m$ zeros.
Furthermore, if $x$ has exactly $m$ ones and $n-m$ zeros, then the lemma above shows that $x$ is extreme.
Consequently, the set $E$ of extreme points consists of the $\binom{n}{m}$ points that have exactly $m$ ones and $n-m$ zeros.
Hence if we let $i: \mathbb{R}^n \to \mathbb{R}^{2 \times n}$ be $i(x) = \begin{bmatrix} x_1 & \cdots x_n \\ 1-x_1 & \cdots 1-x_n \end{bmatrix}$, we can write $P = \text{co} \{ i(x) \}_{x \in E}$.
