Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Are the equations inequalities? –  A.Schulz Feb 5 '13 at 17:27
    
The second equation is redundant. –  copper.hat Feb 5 '13 at 17:46

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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