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 $$

  • $\begingroup$ Are the equations inequalities? $\endgroup$
    – A.Schulz
    Feb 5 '13 at 17:27
  • $\begingroup$ The second equation is redundant. $\endgroup$
    – copper.hat
    Feb 5 '13 at 17:46

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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.